The Problem of Simplifying Truth Functions

Author(s): W. V. Quine
Reviewed work(s):
Source: The American Mathematical Monthly, Vol. 59, No. 8 (Oct., 1952), pp. 521-531
Published by: Mathematical Association of America
Stable URL: http://www.jstor.org/stable/2308219 .
Accessed: 18/07/2012 11:46

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .
http://www.jstor.org/page/info/about/policies/terms.jsp

.
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of
content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms
of scholarship. For more information about JSTOR, please contact [email protected].

Mathematical Association of America is collaborating with JSTOR to digitize, preserve and extend access to
The American Mathematical Monthly.

http://www.jstor.org
 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS
W. V. QUINE, HarvardUniversity
The formulasof the propositional calculus,or the logicof truthfunctions,
are hereto be understood as builtup ofthestatement letters'p', 'q', 'r', * - * by
just the notationsof negation,conjunction,and alternation(or disjunction),
viz.'P3','pq', and 'p v q', to anydegreeofiteration. A formulais validifit comes
out trueunderall assignments of truthvalues to the letters,and consistent if
it comesout trueundersome.One formulaimpliesanotherifthereis no assign-
mentof truthvalues whichmakesthe firstformulatrueand the secondfalse.
Two formulas are equivalent iftheyimplyeach other.Implicationand equiva-
lence,so defined, are relationsofformulas; theyare notto be confusedwiththe
conditionaland biconditional,commonlyexpressedby 'D' and '=_'. These
latternotationswillbe omitted,beingtranslatableintotermsofnegation,con-
junction,and alternation in familiarfashion.
It will be convenientto use the words'conjunction'and 'alternation'in
slightly extendedsenses.Ordinarily one speaksofa conjunction oftwoor more
formulas; but I shallspeakalso ofa conjunction ofoneformula, meaningthereby
simplytheformulaitself.Thus everyformulais a conjunction at leastofitself.
Correspondingly foralternation.
Lettersand negationsof letterswillbe spokenof collectively as literals.A
conjunction ofliteralswillbe called a fundamental formulaifno letterappears
in it twice.Literalsthemselves countas fundamental formulas, in view of my
broad use of the word 'conjunction'.Finallyany alternationof fundamental
formulas willbe calleda normalformula, and thefundamental formulas ofwhich
it is an alternation willbe called its clauses.Fundamentalformulasthemselves
countas normal,in view of mybroad use of the word'alternation';a funda-
mentalformulais a one-clausenormalformula.In general,thus,normalfor-
mulasare simplywhathave beenknownin the literature as disjunctive normal
forms,or alternational normalforms,exceptthat normalformulasare subject
to one additionalrequirement: no lettercan occurin a clause twice.A normal
formulacannotcontain'pqp' nor'iqf3'nor'pqf3'.Mechanicalroutinesare well
knownfortransforming any consistentformulainto an equivalentwhichis
normal.*
But thereremainsa problemwhich,despitethe trivialcharacterof truth-
functionlogic,has provedcuriouslystubborn;viz.,the problemof devisinga
generalmechanicalprocedureforreducingany formulato its simplestequiva-
lent.Since Shannon'scorrelation of the formulasof truth-function logicwith
electriccircuits, t this problemof simplification has takenon significance for
engineering; for,a techniqueforsimplifying truth-functionalformulas wouldbe
* See, e.g.,?10 ofmyMethods ofLogic,HenryHolt & Co., 1950.
t C. E. Shannon,A symbolicanalysisof relayand switching circuits,Trans. Amer.Inst. of
ElectricalEngineers, vol. 57, 1938,pp. 713-723.
521
522 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS [October

a techniqueforsimplifying circuits.It is noteworthy thatthestaffofthe Com-

putationLaboratoryof HarvardUniversity have foundit worthwhileto set
forthelaborateprocedures forsimplifying truthfunctions, and evento tabulate
all the simplestequivalentsof formulasinvolvingfouror fewerletters.$
In a certaintheoreticalsense,indeed,thereis no problem.Givenany for-
mula,we can, in principle,survey-thetotalityofsimplerformulas involvingno
additionalletters;forthistotalityis finite.By truthtablesor otherwise, we can
testeach of thesesimplerformulasforequivalenceto the givenformula,and
thus pick out the simplestequivalent.This procedureis mechanical;what is
wanted,however,is a mechanicalprocedurewhichis shortenoughto be prac-
tical.
Because of the perspicuityand generalconvenience of normalformulas, an
interesting ofthesimplification
specialization problemis theproblemoffinding
a simplestnormalequivalent.In factwe maylimitour problemto normalfor-
mulasfromstartto finish, sincethepreliminary stepofconverting a givenfor-
mula into some normalequivalent,not necessarilya simplest,presentsno
problem.By limitingourconsideration thusto normalformulaswe are indeed
disregarding formulas,
inconsistent butthisis no reallimitation, sincea shortest
equivalentofanyinconsistent formulacan be suppliedout ofhand: 'pf'. So the
problemwhichI shallexamineis thatofconverting any normalformulaintoa
simplestnormalequivalent.This is notthe mostgeneralformofthesimplifica-
tionproblemfromthepointofviewofengineering, sinceitcan happenthatsome
shortnon-normal formula represents a still cheaper electriccircuitthan any
normalequivalent.But it willbe morethanenoughto occupyus on thepresent
occasion.
Limitingourselvesto normalformulas, we stillhave somechoiceas to our
of
measure simplicity. We might simplycount all occurrences of literalsand
alternation a
signs,orwe mightput premium on fewness of clauses and so resort
to a countof occurrences of literalsonlywhen comparing formulas whichare
alikein numberofclauses.WhatI shallhaveto say in thispaperwillnotrequire
any decision,however,betweentheseor otherreasonablestandardsofsimplic-
ity.
Let us use theGreekletter'T to referto any literal,and '?', '#/','X' to refer
to any fundamental formulas,and '"V and '"' moregenerallyto referto any
normalformulas. In orderto referto compoundsofformulas whichare severally
referred to thusby Greekletters,let us use corresponding compoundsof the
Greek lettersthemselves;thus wherer is taken as 'P' and 4 as vpq', v4 is to be
understoodas 'j v pq'.
Now it can happenthatsome clause 4'is superfluous in a normalformula
4 v; i.e.,that4 vI is equivalentto I alone.It can also happenthatan occur-
in a normalformula4' v'; i.e., that4'?v* is
renceofa literalt is superfluous
equivalentto 4 vi alone. Weedingout suchsuperfluous clausesand literalsis
ofElectronic
t Synthesis and Control
Computing by theaforementioned
Circuits, headed
staff,
Press,1951.
by HowardH. Aiken.HarvardUniversit5r
1952] THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS 523

theobviouswayofreducingnormalformulas to simplernormalequivalents.To
implement thissortofreduction,all we needare convenienttechniquesforspot-
tingsuperfluous clausesand literals.Now suchtechniquesare readilydevised,
as follows.
To say thatO vT is equivalentto 'I is the same as sayingthatgbimplies'I.
Also,as is slightly to say thatOrv'I is equiv-
lessevidentbut readilyverifiable,
alent to v'T is the same as saying that 4 implies r vT. To test a clause O for
superfluousness in a normalformula,therefore, we have onlyto see whether4
impliesthe restof the normalformula;and to testan occurrence of a literalr
in a clauseOD of a normalformulaforsuperfluousness, we have again onlyto
see whether 4 impliestherestofthenormalformula.Now the4 in eitherprob-
lemis a fundamental formula;and any questionofimplication on thepartofa
fundamental formula 4 is alwaysquicklysettled.To findwhether 4 impliesany
givenformulawe have merelyto markas true,throughout thegivenformula,
all the letterswhichoccuraffirmatively in 4, and as falseall the letterswhich
occurnegatedin 4, and thensee whetherthe givenformulathereuponcomes
out true(forall valuesofanyremaining letters).
Example1: We findtheclause'pr' of'pq v prv q?' superfluous by testingto
see ifit impliestherest,'pq v q?'. The testofimplication consistsin putting'T'
for'p' and 'F' for'r' (conformably with'pi') in 'pq v q*'; theresultis 'Tq v q7',
whichreducesto 'q v q'.
Example2: We findthefirstoccurrence of 'q' in 'pq v pqrv Mi?i'superfluous
bytestingto seeif'pr' impliestherest,'pq v q v Mie'.The testofimplication con-
sistsin putting'T' for'p' and 'r' in 'pq v q v fig'; the result'Tq v q v FqF' re-
ducesto 'q v q'.
Let us call a normalformulairredundant ifit has no superfluous clausesand
noneof its clauseshas superfluous literals.We nowhave a mechanicalroutine
forreducingany normalformulato an irredundant equivalent.Summedup, it
runsas follows.Firsttryeach clause in turnto see whetherit impliesthe rest
of the formula;wheneverany clause is foundwhichdoes implythe restofthe
formula, deleteit onceand forall beforecontinuing thesurvey.Afterall reduc-
tionsofthistypeare at an end,thentryeach "immediatesubclause"(a clause
minusone ofits literals)to see whetherit impliestherestoftheformula;ifit
does,deletethesuperfluous occurrenceoftheliteral.Whenthisprocesscan be
carriedno farther, we havean irredundant formula.
It seemsreasonableto hopethatthisprocedureofsimplification, issuingas
it does in a normalequivalentwhichis irredundant, may solve our original
problem;namely,the problemof reducingany normalformulato a simplest
normalequivalent.The procedure leads to a normalformulain whichno clause
is superfluous and no occurrences ofliteralswithinclausesare superfluous; and
it seemsreasonableto supposethat such a normalformulais as simpleas any
equivalentnormalformulacan be.
But this is not so. Consider the normal formula'pq v fiqv qi v qr'. This is ir-
redundant;no clause can be dropped,nor can any occurrences of literalsbe
524 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS [October

dropped,withoutbreachof equivalence.Yet thisformulahas simplernormal

equivalents,indeedtwo:both'pq V Pr v qf' and 'Sq v prv qr',as can be checked
by truthtables.Thesearesimplerthantheoriginalbyanyconceivablestandard
ofsimplicity, but theycannotbe got fromthe originalby any processofdrop-
pingor curtailing clauses.
The routineof eliminating redundancies by droppingor curtailingclauses
remainsuseful,forit is quickand easyand it bringsgainsin simplicity wherever
it can be used.But it doesnotassureus alwaysofa simplestresult.The remain-
der of thispaperwillbe devotedto presenting a generalprocedureforfinding
a reallysimplestnormalequivalent.The procedure willbe laborious,but notto
the pointofunmanageability.
A normalformulais calleddeveloped ifall ofits lettersappearin each ofits
clauses; e.g., 'pq?v p7r'. Any normalformulacan be turnedintoa developed
equivalentby an obviousprocedure:any clause4 whichlacksa letterr can be
supplantedby its equivalentOrv OT, and the processcan be continueduntil
each clausecontainseach letter,duplicateclausesbeingdroppedas theyarise.
Example:the normalformula'pqrv rs' becomes'pqrsv pqrsv pr vfir', which
in turnbecomes'pqrsVpqrsVpqrsv jqrs Vfiqrg',a developednormalformula.
The procedureforfinding simplestnormalequivalentswilltakedevelopednor-
mal formulas as its pointofdeparture.Meanwhilea coupleofauxiliarynotions
mustbe defined, and theirpropertiesestablished.
DEFINITIONS:4 will be said to subsume 4/' ifand only ifall the literalswhereof

VIis a are
conjunction among the whereof
literals 4 is a conjunction. 4 willbe
calleda primeimplicant of I ifand onlyif4 impliesI and subsumesno shorter
formulawhichimpliesI. 4 willbe calleda completion ofX withrespectto 'I if
and onlyif4 subsumesXand containsall lettersofI and no others.
THEOREM 1. Any simplest normalequivalent of 1?is an alternation
ofprime
implicants of(D.
Proof.EveryclauseVIofa normalequivalentI of ( implies'I and therefore
(D.So, if t,'is nota primeimplicantof(, then &subsumesa shorterformulaV,&'
whichimplies(Dand therefore 'I. But thenI has one or moreredundantoccur-
rences literals,inVI,whichcouldbe deleted(as notedin earlierpages); so ' is
of
not a simplestnormalequivalent.
The above theorembringsout the relevance,to our simplification project,
oflistingtheprimeimplicants ofa formula'1. The wayto obtainsucha listwill
becomeevident,in thecase ofdeveloped(D,afterthenextthreetheorems.
THEOREM2. No primeimplicant
of(Dcontainsletters to 1.
foreign
Proof.If +? implies(Dand theletterin t is foreign
to 4I,thenanyassignment
oftruthvalueswhichmakes^L'truewillmakeTXtrue,regardless oft; i.e.,i/ will
will not be a primeimplicantof b.
imply 4', and hence Or'?
1952] THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS 525

THEOREM 3. If 4) is a developednormalformulaand containsall letters of ',

ofi1 withrespectto 4) are clauses
theni1implies1iif and onlyif all completions
of4.
Proof.If y6has a completion 4"'whichis nota clauseof 4I,theneach clause
of '1 containsa letteraffirmatively whichis negatedin i1' or vice versa.Then
theassignment of truthvaluesto letterswhichmakesy6'truemakesall clauses
of 4 false,thoughmakingy1true;so y6does not imply(D.Conversely, each as-
signmentof truthvalues to the lettersof 4 whichmakesy1truemakessome
completion of^t-true;so, ifall thecompletions ofa1are clausesof 4), theneach
assignment whichmakes,6truemakes4) true,and hence,6implies4).
FromTheorems2 and 3 and thedefinition ofprimeimplicant, therefollows
thiscorollary:
THEOREM 4. i1is a primeimplicant normalformula
ofa developed b ifand only
ifall letters of41withrespect
of41areamongthoseofb and all completions to( are
(
clausesof and thereis no shorterformula41',subsumed byi1,suchthatall com-
pletionsofi1' withrespectto (Dare clauses of b.
Theorem4 enablesus, givena developednormalformula 1 v *v V , to
arriveat its primeimplicants mechanicalroutine.We makea
by the following
growinglist whichdoes not begin as a list of primeimplicants, but begins
ratherwith4i, , 4n and is extendedaccordingto the following principle:
whenevertwo entriescan be foundin the list whichare relatedas xr and XI
(thusidenticalexceptfora negationsign),add theircommonpartX as a new
entryin thelist.Checkmarksare to be appliedto any entriesxt and XIwhich
thusgeneratenewentries, btita checkmarkis notto be treatedas disqualifying
an entryfromreuse;thus'pqrs'can be used once with'pqrs'to generate'pqr'
and oncewith'pqrs'to generate'prs'.Whenthelisthas beenextendedas faras
possibleby theabove process,we can readofftheprimeimplicants of4l v ...
vO. fromit thus: they are the entrieswhich bear no check marks.
Example: Suppose 41, * * , 4 are 'pqrs', Pqrs', 'pq?s', 'pqfs9,'pqfr', and
'pqfr'.The firstand thirdof thesesix yield'pqs' as a seventhentryin ourlist;
thethirdand fourthyield'prs' as an eighth;thethirdand fifth yield'pqF'as a
ninth;the fourthand sixthyield'pqr' as a tenth;and the fifth and sixthyield
'prs' as an eleventh.Of theoriginalsix entries,all but thesecondreceivecheck
marksin the process.Proceedingnowto generatestillfurther entriesfromthe
fiveadded ones,we get 'pr' twiceand nothingmore;and accordingly we apply
checkmarksto 'prs' and 'pfr',and also to 'pqr' and 'pqf. (Note the necessity
ofapplyingcheckmarksto all four,despitetheduplicatenatureoftheiryield.)
Surveyingthe finishedlist,we findjust theseentrieswithoutchecks:'f3qrs',
'pqs', 'pf'. These are the primeimplicantsof 'pqrsv iqrsv pq?sv pqFsv pqf
v pqF3'.
in orderto obtaina simplestnormal
How to use thelistofprimeimplicants,
526 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS (October

equivalentofa developednormalformula,
is suggestedby thenexttheoremto-
getherwithTheorem1.
THEOREM 5. If 'I is a simplest
normalequivalent
ofa developed
normal
formula
tI, theneachclauseofTXsubsumes
a clauseof*I.
Proof..Considerany clause'kof L'.By Theorems1 and 2,' containsno let-
tersforeign to 4b,nor,therefore,to '. Hence any clause of' which4 does not
subsumemustcontaina letteraffirmatively whichis negatedin 4 or viceversa.
Hence theassignment of truthvalues to letterswhichmakes4 truewillmake
all clauses of ' falseexceptthosewhich4 subsumes.Hence 4 mustsubsume
a clauseof I if4 is to imply'. But4 doesimply*I,since4 is equivalentto I.
In viewofTheorems1 and 5, we can obtaina panoramaofall simplestnor-
mal equivalentsof a developednormalformula41v * - - vti as follows.First
we list the primeimplicants, as seen earlier.Then we surveythe varioussub-
setsofthe list,such that4$ foreach i subsumesa memberofthesubset.Each
simplestsuchsubset,writtenas an alternation, is a simplestnormalequivalent
of01 v ... *On.
V
The surveyis facilitatedby constructing whatI shallcall thetableofprime
implicants of41v ... * v .,.The abscissasofthetable,inscribedacrossthetop,
are4, , 4$,.The ordinatesofthetable,inscribed downtheleftside,are the
primeimplicants of4, v ... v 4$n.In theinterior ofthetablewe entercrosses
in thosepositionswhoseabscissassubsumetheirordinates.
For the example'pqrsvfqrs v pq?sv pqrsv pqg v pqr?, whoseprimeimpli-
cantswerederivedearlier,the table is this:
pqrs Mqrs pqFs pqrs pqfr pqrS
Miqrs X
pqs X X
pr X X X X
Once we have the table of primeimplicants, we canvassall ways of so se-
lectingordinatesas to representall abscissas; i.e., to show crossesunderall
abscissas.We settleupon a selectionsuch that the alternationof the selected
ordinateswillbe as simpleas possible.In theabove examplethereis no choice;
no selectionofrows,shortofall three,exhibitscrossesin all columns.So in this
examplethe simplestnormalequivalentis 'pqrsv pqsv pr', whichuses all the
primeimplicants.
For anotherexamplelet us returnto 'p7 v pq v qrqr', v whichwas cited
earlierto showthatirredundant formulascould have simplerequivalents.To
findthesimplestnormalequivalentsofthisexamplebyournewgeneralmethod,
we mustfirstexpandtheformulaintoa developednormalformula, thenderive
the list of primeimplicants,and finallyformthe table. The table turnsout
thus:
1952] THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS 527

pqr pqr Pqr S3q? pqf Pqr

pq x x
qr X X
pr x x
3q X X
Sir X X
qr X X
Survey of the table shows two ways of so pickingthreerows as to representall
columns, so we come out with two simplest normal equivalents, 'fiq v qr v pf'
and 'pqv Pr vqf'.
Incidentally the list of prime implicantsof a formula b has other uses be-
sides its use in obtaining the simplest normal equivalents of 1?.It provides a
panorama of all the fundamentalformulaswhichimply D; for,the fundamental
formulaswhich imply 1?are simply the prime implicantsand all other funda-
mental formulaswhich subsume any of them.
So far as concerns the topic of the present paper, however, the use of the
table is in findingshortestnormal equivalents. As described thus far, the use
of the table forthis purpose proceedsby exhaustion: tryingall the combinations
of ordinateswhich representall abscissas, and comparingall the resultingalter-
nations forsimplicity.Now this process of canvassing the table can be speeded
up in many examples (though not in the above two) by the followingroutineof
preparatoryreduction.*
(i) If any columns of the table of a formula4 contain only one cross apiece,
then recordforfuturereference, the alternationof the ordinatesof those crosses.
Let us call this alternationthe coreof 4. (The clauses of the core are bound, by
Theorem 5, to be clauses of any simplestnormal equivalent of 4a.)
(ii) Reduce the table by deletingthe ordinatesconcernedin (i), and deleting
also all abscissas representedby those ordinates. (These abscissas need no fur.
therconsiderationbecause they will be representedby clauses of our finalsim-
plificationof 1?anyway as long as we take care to include the core as part of that
finalsimplification.)
(iii) Whereverin the survivingtable thereare abscissas 4i and 4i such that
4i has crosses only in rows in which4j has crosses,delete 4,. (For, our finalfor-
mula is bound to representfj anyway, throughrepresenting4i.)
* Note the resemblance of the ensuingoperationsto the operationson 'minimizing charts"
whichare set forthin pp. 56 ff.of Synthesis(see precedingfootnote).The clausesofwhat I call
thecore(below)correspond to whatare called "essentialcombinations" in Synthesis.
Moreaccu-
rately,theclausesofthecoreare thedualsoftheessentialcombinations.; fortheminimizingcharts
produceconjunctional normalforms, ratherthanalternation
in effect, ones.Betweentheminimiz-
ing chartsand the tablesof the presentpaper thereare profound however,beyond
differences,
thatofduality.A minimizing chartbeginsas a fixedformwhichdependsonlyon themultiplicity
oflettersconcerned,and noton theparticular formula at hand.It tendsin consequence
to be more
elaboratethanthetableofprimeimplicants.
528 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS [October

(iv) Delete any ordinateswhosecrosseshave all been lostthroughthecan-

cellingofabscissasin (ii) and (iii).
The reduced tableofprimeimplicantsthusachievedcan nowbe subjectedto
theprocess,describedearlier,ofcanvassingthewaysofselectingordinatesand
singlingout the mosteconomical.Each end resultthusobtainedmustbe sup-
plemented by adjoiningthecoreto it,in alternation.
Example:pqrv prv pqs v P5rv pqfS.
The tableofprimeimplicants turnsoutas follows:
pqrs pqrs pqfs pq?g pqrs pqfr i3qrs iqrs Mqrs Pqr3 Miqi
pq X X X X
qr X X X X
pr x x x x
fir X X X X
fi?S X
~~~~~~~X
qrA ~~~~~X X
Now we apply (i); i.e., observing thatthefifthand ninthcolumnscontainonly
one cross apiece, we record the alternation
of theordinatesofthosetwocrosses;
viz.,'pi v fir'.This is thecore. Then,applying(ii), we cancelthe ordinates'pr'
and 'fir'of the table,and also the eightcolumns(viz.,thirdthroughtenth)in
whichthosecancelledrowscontainedcrosses.To what is leftof the table,we
apply (iii); thisenablesus to cancelthe firstor secondcolumnat will,say the
second.We findno way of applying(iv), so we are now downto our reduced
table of primeimplicants, whichis just this:
pqrs Rn
pq x
qr x

qn
grs ~~~~x
~~~X
ofordinatesrepre-
Inspectionofthistableshowsjust fourshortestalternations
sentingbothabscissas.They are:
pq v fiq, pq v qrt qr v fiqt, qrv qrf.
to thecore'prv fir'givesa simplestnor-
Adjoiningany oftheseby alternation
mal equivalentoftheoriginalformula.We thusend up withfoursimplestnor-
mal equivalents:
prvfirvpqvfiq, pfvfirvpqvqfg,
pr vPrvqr v f, pv firvqrv7qf.

Sometimesthe reducedtable of primeimplicantsturnsout to be an utter

blank,so thatthecorestandsaloneas thesimplestnormalequivalent.An exam-
v M"' Here the table of primeimplicantsis:
ple is 'p? v fiqrs
1952] THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS 529

pqfs pqrs pq7s pqF. Piqr3 pfiqs pqrs

pf X X X X
qr X X X X
fi2S x x

Applying (i) to this, we obtain 'pfv q fiq' as core. All rows and columns
disappear under (ii), so that we are leftwith 'prv qrv Miq' itselfas the simplest
normal equivalent of 'pf v fiqrgv fqr.
The method admits of one furtherrefinementwhich, though irrelevantto
all the foregoingexamples,saves much labor whereapplicable. I am indebtedfor
it in part to Nelson Goodman. Given a formulafor which a simplest normal
equivalent is wanted, the new tactic begins by transformingthe formulanot
into a developed normalformula,but ratherinto an irredundantnormalformula
by the routineof the early pages of this paper. This irredundantalternationis
thenseparated into as many subsidiaryalternationsas possiblesuch that no two
of them have lettersin common. (E.g.,' pq v fsv Jiqv t' would be separated into
'pq v fiq', 'fs', and 't'.) Then we expand each of these subsidiary alternations
independentlyinto developed normal formand proceed to finda simplestnor-
mal equivalent forit, by use of a reduced table of primeimplicantsas hitherto
explained. Finally we make a single alternationof the several results,and this
is a simplestnormalequivalent of the originalformula.
The value of this separation expedient,whereapplicable, is evident: it saves
the exorbitant development of all clauses with respect to all missing letters.
But we must prove that the modifiedmethodalways leads to the simplestnor-
mal equivalents. This will be proved as Theorem 8 below; the two intervening
theoremsare needed as lemmas.
THEOREM 6. The only.irredundantnormalformulaswhichare valid are 'p v
'qv ', etc.
Proof.Let 4? v' be a valid normal formula.Consider then any assignment
of truthvalues to letterswhich makes 45true. It makes ? vTi true, since this
is valid; moreoverc, being true under this assignment,can be deleted from
0D v' and the resultr vii will still be true.Thus everyassignmentwhichmakes
0 true makes r vi true; i.e., c implies r vii. But this implicationwas seen, in
early pages of the paper, to be the criterionof superfluousnessof the occurrence
of r in 0' v 'k. We see thereforethat no valid irredundantnormal formulacan
have the formf0 'vt. Still every valid normal formulais obviously an alterna-
tion of at least two clauses; any singleclause is falsifiable.Thereforeeveryvalid
irredundantnormal formulamust be an alternationof clauses none of which is
of the formOr; each of which, in other words, is a single literal. Every valid
irredundantnormalformulahas, in short,the formPj v ... v Pn. But obviously
twoof 1, * * * , Pn must,forvalidityof Pj v - * * v n, be negationsone of the
other.But theneach of 1, * * - , Pn otherthan those two is superfluous;or rather
thereare no others,since P1v ... v . is supposedto be irredundant. So
530 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS [October

1 V
. . . V P is just 'p v ', or perhaps 'q v q', etc.
7. If no twoof (, * * *, (. havelettersin common,and 4 is a prime
THEOREM
implicantof 4J1v * * * v (D., then4 containslettersexclusivelyof (Difor somei.
Proof. By Theorem 2, thereis an i such that some of the lettersof 4 appear
in (Di. Now suppose (which will be proved impossible) that thereare also letters
in 4 foreignto 4?i; i.e., that 4 is 4lxwhere all the lettersof 4' but none of the
lettersof Xare lettersof (D. Since 4)is a primeimplicant,neither4'nor Ximplies
)1 v * .. v 4y. Hence 4' does not imply 4i, and X does not imply (D v . . .
V 4X-1V lcp+lV * * v 4 . Hence there is an assignmentof truthvalues to the
letters of -4 which makes 4' true and 4?i false, and there is an assignmentof
truthvalues to the restof the alphabet whichmakes X trueand (P v . . . v (D-,
v 4i+i v . . . v 4bnfalse. Pooling the two assignments(which we can do since
the sets of letters concerned are mutually exclusive), we have an assignment
which makes 4)true and (D v ... v 4?nfalse. But this is impossible,since 4 by
hypothesisimplied (D v * v (D..
THEOREM 8. If 4P V ... V 1b(n > 1) is irredundantand no twoof-D, *,n
havelettersin common,thenany simplestnormalequivalentof bhv . . . v (D will
be of theformTlLV . V vT,, whereTi, * , P are equivalentrespectively
to

Proof. Let ' be a simplestnormal equivalent of (1 v * V n. Then (D,

foreach i, implies I. Now suppose that (Di has no lettersin common with T.
Implication can occur withoutcommon lettersonly in the extremecases where
the implyingformulais inconsistentor the implied one is valid. But 'i5, being
normal,is consistent.Sot would have to be valid. Then its equivalent 1i v * * .
v (% would be valid, and hence, by Theorem 6, would be simply 'p v f' or
qv q or the like. But by hypothesis this is impossible; for by hypothesis
n > 1, and therefore(D v . . v (% contains two or more distinctletters.We
conclude,therefore,that (i foreach i has lettersin commonwithP. Conversely,
by Theorems 1 and 7, each clause of P contains letters exclusively of Ii for
some i. Therefore ' has the form Pf v . . . vPn where Ti, for each i, contains
lettersexclusivelyof C. It remains to show that (Di impliesPX and vice versa.
We saw that (Di v . .. v ( is not valid; neither, therefore, is its equivalent
T, v . . . vP,, valid. So thereis an assignment2f,of truthvalues to the letters
of Pi v . . . vTi- vT+i v . . . vTP, which makes the latter formula false.
Consider now any assignment23, of truth values to the letters of (i, which
makes (D true. We can combine e with X, since the sets of lettersconcernedare
mutuallyexclusive; and the combined assignmentmakes (i true and P1 v . . .
vP*i_1vP1 v . . . vPn false. Since the combined assignmentmakes (i true,
it must make T1 v . . . vPn true (for this latter is equivalent to (1 v . . .
v ;n). More particularlythen it must make TP true (for we just noted that it
made the rest ofP1 v . . . vPn false). But the lettersofTi receive truthvalues
1952] THE DIFFERENTIAL EQUATION OF A CONIC 531

only from 3, not W; and e3 was any assignmentwhich makes (i true. There-
fore (Di implies Ti. An exactly parallel argument,interchangingthe roles of
bl, * * * , (b with those of 'Il, * * *, T', shows converselythat 'J' implies (Di,
thus completingthe proofof Theorem 8.
Summarized, our results are as follows. We found, to begin with, a fairly
rapid method of reducing any normal formula (and thereforeany consistent
formula) to the extent of locating and cancelling any redundancies. But we
foundalso that an irredundantnormalequivalent was not necessarilya simplest
normal equivalent. Accordingly,taking a freshstart, we worked out a routine
which could be depended upon to reveal a simplest normal equivalent, and
indeed all the simplest normal equivalents. This routine,though not unman-
ageable, turnedout to be farmorelaborious than the methodof merelylocating
and cancellingredundancies. Moreover,the two methods are almost independ-
ent. The laborious method of findingsimplestnormalequivalents depends on a
preliminaryexpansion into a developed normal formula,and this expansion is
not affectedby any previouscancellingof redundancies.The only way in which
the cancelling of redundanciescontributesto the ultimate technique is in con-
nection with the auxiliary expedient of separation developed in these last few
pages. Clearly it would be desirable to finda quicker way of gettingsimplest
normal equivalents, say by gearing the whole routineto irredundantformulas
ratherthan to developed formulas.I have not seen how to manage this.
It may be usefulto note one particularclass of normal formulaswhich can
be exempted fromthe foregoingprocedures altogether; viz., those normal for-
mulas in which no one letteroccurs both affirmatively and negatively. Such a
formulais already reduced to simplestnormal formas soon as we have merely
deleted those of its clauses that subsume others of its clauses. I have proved
thisfactelsewhere,*forthe case whereall lettersare affirmative;and the present
extensionthen followedby substitutionof negationsof lettersforletters.
* Dos teoremassobrefuncionesde verdad,Memoriadel CongresoCientffico
Mexicano,(ahlo de
1951),vol. 1 (cienciasfisicas y matemdticas).At press.

THE DIFFERENTIAL EQUATION OF A CONIC AND ITS

RELATION TO THE ABERRANCY
A. W. WALKER, University
ofToronto
1. Introduction.
(i) Generalremarks.In thispaper,0 tan-' (y') is the angle whichthe tangent
at a general point of a plane curve y = y(x) makes with the x-axis; accents and
dots denote differentiation with respect to x and 0 respectively.The notation
t52 _p-213 iS used, where p is the radius of curvature; any equation relating