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: [Link] .
Accessed: 18/07/2012 11:46

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .
[Link]

.
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 support@[Link].

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

[Link]
 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 [Link] formulaimpliesanotherifthereis no assign-
mentof truthvalues whichmakesthe firstformulatrueand the secondfalse.
Two formulas are equivalent iftheyimplyeach [Link] 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 [Link] one speaksofa conjunction oftwoor more
formulas; but I shallspeakalso ofa conjunction ofoneformula, meaningthereby
[Link] everyformulais a conjunction at leastofitself.
Correspondingly foralternation.
Lettersand negationsof letterswillbe spokenof collectively as literals.A
conjunction ofliteralswillbe called a fundamental formulaifno letterappears
in it [Link] 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 [Link]
countas normal,in view of mybroad use of the word'alternation';a funda-
mentalformulais a [Link] 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-
[Link] 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. [Link]. of
ElectricalEngineers, vol. 57, 1938,pp. 713-723.
521
522 THE PROBLEM OF SIMPLIFYING TRUTH FUNCTIONS [October

a techniqueforsimplifying [Link] 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 [Link] for-
mula,we can, in principle,survey-thetotalityofsimplerformulas involvingno
additionalletters;forthistotalityis [Link] truthtablesor otherwise, we can
testeach of thesesimplerformulasforequivalenceto the givenformula,and
thus pick out the [Link] 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 [Link] factwe maylimitour problemto normalfor-
mulasfromstartto finish, sincethepreliminary stepofconverting a givenfor-
mula into some normalequivalent,not necessarilya simplest,presentsno
[Link] 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
[Link] is notthe mostgeneralformofthesimplifica-
tionproblemfromthepointofviewofengineering, sinceitcan happenthatsome
shortnon-normal formula represents a still cheaper electriccircuitthan any
[Link] 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 [Link] 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 [Link] 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 [Link]
implement thissortofreduction,all we needare convenienttechniquesforspot-
tingsuperfluous clausesand [Link] 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 [Link] the4 in eitherprob-
lemis a fundamental formula;and any questionofimplication on thepartofa
fundamental formula 4 is [Link] 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 [Link] nowhave a mechanicalroutine
forreducingany normalformulato an irredundant [Link], it
runsas [Link] clause in turnto see whetherit impliesthe rest
of the formula;wheneverany clause is foundwhichdoes implythe restofthe
formula, deleteit onceand forall beforecontinuing [Link] reduc-
tionsofthistypeare at an end,thentryeach "immediatesubclause"(a clause
minusone ofits literals)to see whetherit impliestherestoftheformula;ifit
does,deletethesuperfluous [Link] 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
[Link] 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 [Link] thisformulahas simplernormal

equivalents,indeedtwo:both'pq V Pr v qf' and 'Sq v prv qr',as can be checked
by [Link]
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 [Link] it doesnotassureus alwaysofa [Link] remain-
der of thispaperwillbe devotedto presenting a generalprocedureforfinding
a [Link] 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 [Link] 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.
[Link] normalequivalentI of ( implies'I and therefore
([Link], 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
[Link] +? 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.
[Link] y6has a completion 4"'whichis nota clauseof 4I,theneach clause
of '1 containsa letteraffirmatively whichis negatedin i1' or vice [Link]
theassignment of truthvaluesto letterswhichmakesy6'truemakesall clauses
of 4 false,thoughmakingy1true;so y6does not imply([Link], 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 [Link] 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 [Link] 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 [Link] theoriginalsix entries,all but thesecondreceivecheck
marksin the [Link] 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 [Link] 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 [Link]
we list the primeimplicants, as seen [Link] we surveythe varioussub-
setsofthe list,such that4$ foreach i subsumesa [Link]
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$[Link] 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
[Link] settleupon a selectionsuch that the alternationof the selected
ordinateswillbe as simpleas [Link] theabove examplethereis no choice;
no selectionofrows,shortofall three,exhibitscrossesin all [Link] 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 [Link]
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 [Link] 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 [Link] 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, [Link]-
ing chartsand the tablesof the presentpaper thereare profound however,beyond
differences,
thatofduality.A minimizing chartbeginsas a fixedformwhichdependsonlyon themultiplicity
oflettersconcerned,and noton theparticular formula at [Link] 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 [Link] 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
[Link] what is leftof the table,we
apply (iii); thisenablesus to cancelthe firstor secondcolumnat will,say the
[Link] 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
[Link] are:
pq v fiq, pq v qrt qr v fiqt, qrv qrf.
to thecore'prv fir'givesa simplestnor-
Adjoiningany oftheseby alternation
mal [Link] thusend up withfoursimplestnor-
mal equivalents:
prvfirvpqvfiq, pfvfirvpqvqfg,
pr vPrvqr v f, pv firvqrv7qf.

Sometimesthe reducedtable of primeimplicantsturnsout to be an utter

blank,so thatthecorestandsaloneas [Link] 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 [Link] valid are 'p v
'qv ', etc.
[Link] 4? v' be a valid normal [Link] 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 [Link] 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 [Link]
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
[Link] 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 [Link] 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 [Link]
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 [Link] 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) [Link] 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 [Link] notation
t52 _p-213 iS used, where p is the radius of curvature; any equation relating