2612:
1921:
2607:{\displaystyle {\begin{aligned}\phi &\leftrightarrow \lnot \lnot \phi _{DNF}\\&=\lnot \{(p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)\}\\&\leftrightarrow {\underline {\lnot (p\land q\land r)}}\land {\underline {\lnot (p\land q\land \lnot r)}}\land {\underline {\lnot (p\land \lnot q\land \lnot r)}}\land {\underline {\lnot (\lnot p\land q\land \lnot r)}}&&{\text{// generalized D.M. }}\\&\leftrightarrow (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor \lnot \lnot r)\land (\lnot p\lor \lnot \lnot q\lor \lnot \lnot r)\land (\lnot \lnot p\lor \lnot q\lor \lnot \lnot r)&&{\text{// generalized D.M. }}(4\times )\\&\leftrightarrow (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor r)\land (\lnot p\lor q\lor r)\land (p\lor \lnot q\lor r)&&{\text{// remove all }}\lnot \lnot \\&=\phi _{CNF}\end{aligned}}}
5477:
5082:
16573:
1462:
5472:{\displaystyle {\begin{array}{lcl}(\lnot p)\land (p)\land (\lnot q)\land (q)\land \\(\lnot p\lor p)\land {\underline {(\lnot p\lor \lnot q)}}\land {\underline {(\lnot p\lor q)}}\land {\underline {(p\lor \lnot q)}}\land {\underline {(p\lor q)}}\land (\lnot q\lor q)\land \\(\lnot p\lor p\lor \lnot q)\land (\lnot p\lor p\lor q)\land (\lnot p\lor \lnot q\lor q)\land (p\lor \lnot q\lor q)\land \\(\lnot p\lor p\lor \lnot q\lor q)\end{array}}}
1239:
4028:
1665:
3755:
1467:
1457:{\displaystyle {\begin{aligned}\phi &\leftrightarrow \lnot \lnot \phi _{DNF}\\&=\lnot (C_{1}\lor C_{2}\lor \ldots \lor C_{i}\lor \ldots \lor C_{m})\\&\leftrightarrow \lnot C_{1}\land \lnot C_{2}\land \ldots \land \lnot C_{i}\land \ldots \land \lnot C_{m}&&{\text{// (generalized) D.M.}}\end{aligned}}}
4364:
3602:
Since all propositional formulas can be converted into an equivalent formula in conjunctive normal form, proofs are often based on the assumption that all formulae are CNF. However, in some cases this conversion to CNF can lead to an exponential explosion of the formula. For example, translating the
1915:
15610:
3498:
4168:
5548:
Typical problems in this case involve formulas in "3CNF": conjunctive normal form with no more than three variables per conjunct. Examples of such formulas encountered in practice can be very large, for example with 100,000 variables and 1,000,000 conjuncts.
4023:{\displaystyle (X_{1}\vee X_{2}\vee \ldots \vee X_{n})\wedge (Y_{1}\vee X_{2}\vee \ldots \vee X_{n})\wedge (X_{1}\vee Y_{2}\vee \ldots \vee X_{n})\wedge (Y_{1}\vee Y_{2}\vee \ldots \vee X_{n})\wedge \ldots \wedge (Y_{1}\vee Y_{2}\vee \ldots \vee Y_{n}).}
1660:{\displaystyle {\begin{aligned}\lnot C_{i}&=\lnot (l_{i1}\land l_{i2}\land \ldots \land l_{in_{i}})\\&\leftrightarrow (\lnot l_{i1}\lor \lnot l_{i2}\lor \ldots \lor \lnot l_{in_{i}})&&{\text{// (generalized) D.M.}}\end{aligned}}}
3719:
1063:
2709:
1764:
4876:
3372:
490:
8254:
1773:
4484:
are not mentioned in the original formula, their values are irrelevant to satisfaction of it, which is not the case in the last formula. This means that the original formula and the result of the translation are
8160:
5627:
15413:
16013:
1168:
4117:. These transformations are guaranteed to only linearly increase the size of the formula, but introduce new variables. For example, the above formula can be transformed into CNF by adding variables
5740:
15928:
6795:
7306:
5685:
4557:
1926:
1472:
1244:
16494:
15071:
14548:
4610:
8441:
13304:
12815:
12381:
11285:
9589:
735:
15151:
14630:
9296:
8634:
8394:
6921:
7000:
7897:
7850:
7709:
7662:
3608:
7991:
7944:
7803:
7756:
7172:
7090:
683:
12127:
11592:
5077:
13929:
13500:
13041:
12558:
11995:
11462:
10927:
10337:
9766:
9208:
8680:
7210:
7128:
4161:
14757:
14465:
14230:
13864:
13790:
13372:
12913:
12430:
11867:
11334:
10799:
10758:
10735:
10226:
10141:
9657:
9534:
9099:
8569:
6739:
535:
16156:
15772:
14887:
14571:
14362:
14318:
14070:
14026:
13630:
13171:
12690:
12646:
12188:
12083:
11653:
11114:
10543:
10291:
9953:
9397:
8867:
4677:
4359:{\displaystyle (Z_{1}\vee \ldots \vee Z_{n})\wedge (\neg Z_{1}\vee X_{1})\wedge (\neg Z_{1}\vee Y_{1})\wedge \ldots \wedge (\neg Z_{n}\vee X_{n})\wedge (\neg Z_{n}\vee Y_{n}).}
1210:
865:
8344:
6956:
6835:
2902:
6877:
640:
7604:
7455:
6684:
2628:
12150:
11615:
7026:
6713:
16114:
15703:
8766:
6815:
921:
3001:
898:
823:
6585:
6348:
6149:
5912:
4940:
2860:
13266:
12845:
12785:
12326:
12302:
11818:
11767:
11228:
10708:
10657:
10118:
10067:
9511:
9031:
8980:
8520:
8469:
2968:
568:
384:
11055:
10484:
9894:
9338:
8808:
6526:
6411:
6289:
6090:
5975:
5853:
4731:
3568:
2947:
170:
16061:
13885:
13456:
13435:
12997:
12976:
12514:
12493:
11951:
11930:
11418:
11397:
10883:
10862:
10185:
9616:
9058:
8071:
8051:
7230:
6484:
6247:
6048:
5996:
5954:
5811:
2827:
1230:
962:
240:
16041:
15825:
15795:
15726:
13586:
13127:
11548:
11013:
10442:
9852:
9720:
9162:
8091:
6111:
6069:
5874:
5832:
4973:
4637:
4482:
4451:
4424:
4397:
4084:
4057:
3748:
3520:
3367:
1093:
949:
800:
318:
281:
194:
146:
15403:
15354:
15283:
15234:
14917:
14787:
14392:
14260:
14100:
13959:
13820:
13660:
14944:
14419:
14127:
13687:
13219:
12738:
12236:
11701:
11162:
10591:
10001:
9445:
8915:
595:
15193:
15172:
15009:
14967:
14704:
14683:
6627:
6606:
6453:
6369:
6219:
6198:
4757:
15374:
15325:
15303:
15254:
15092:
14988:
14843:
14808:
14651:
14486:
14442:
14281:
14177:
14001:
13980:
13841:
13745:
13563:
13542:
13521:
13414:
13393:
13327:
13192:
13104:
13083:
13062:
12955:
12934:
12868:
12711:
12623:
12600:
12579:
12472:
12451:
12351:
12257:
12209:
12104:
12060:
12037:
12016:
11909:
11888:
11794:
11722:
11674:
11569:
11527:
11504:
11483:
11376:
11355:
11255:
11183:
11135:
11076:
11034:
10992:
10969:
10948:
10841:
10820:
10684:
10612:
10564:
10505:
10463:
10421:
10400:
10379:
10358:
10268:
10247:
10162:
10094:
10022:
9974:
9915:
9873:
9831:
9808:
9787:
9699:
9678:
9559:
9466:
9418:
9359:
9317:
9273:
9250:
9229:
9141:
9120:
9007:
8936:
8888:
8829:
8787:
8745:
8722:
8701:
8611:
8590:
8496:
8294:
8274:
8031:
8011:
7046:
6547:
6505:
6432:
6390:
6310:
6268:
6170:
6017:
5933:
5783:
5023:
5003:
4898:
4705:
4104:
3591:
3542:
3022:
2923:
2881:
2806:
2783:
2762:
2741:
404:
1683:
16382:
5754:
In first order logic, conjunctive normal form can be taken further to yield the clausal normal form of a logical formula, which can be then used to perform
4457:
that satisfies this formula also satisfies the original one. On the other hand, only some of the models of the original formula satisfy this one: since the
4762:
7308:
which use the same variable name twice, change the name of one of the variables. This avoids confusion later when dropping quantifiers. For example,
412:
1910:{\displaystyle \lnot \phi _{DNF}=(p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)}
8165:
16501:
5501:-SAT problem is the problem of finding a satisfying assignment to a boolean formula expressed in CNF in which each disjunction contains at most
5497:
involves finding assignments to the variables of a boolean formula expressed in conjunctive normal form, such that the formula is true. The
15605:{\displaystyle (\mathrm {Animal} (f(x))\lor \mathrm {Loves} (g(x),x))\land (\lnot \mathrm {Loves} (x,f(x))\lor \mathrm {Loves} (g(x),x))}
8099:
3493:{\displaystyle (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor r)\land (\lnot p\lor q\lor r)\land (p\lor \lnot q\lor r)}
5567:
17:
16307:. Revised Selected Papers. Lecture Notes in Computer Science. Vol. 3542. Vancouver, BC, Canada: Springer 2005. pp. 183–198.
15944:
1098:
8300:". This is the only step that preserves only satisfiability rather than equivalence. It eliminates all existential quantifiers.
16423:
16376:
16345:
16320:
16282:
5690:
15874:
6744:
16461:
16405:
Structures in
Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics (translated from Russian)
7243:
5632:
4503:
100:" is often used in a narrower sense, meaning a particular representation of a CNF formula as a set of sets of literals.
16258:
5755:
16413:
16331:
16272:
15015:
14492:
16510:
16201:
4562:
16230:
15774:
15705:
16627:
15626:
8033:. After these replacements, a quantifier may occur only in the initial prefix of the formula, but never inside a
5494:
8420:
16653:
16487:
13280:
12791:
12357:
11261:
9565:
5506:
4110:
690:
15098:
14577:
9279:
8617:
8349:
6882:
16648:
16451:
16441:
15658:
6961:
7855:
7808:
7667:
7620:
15648:
7949:
7902:
7761:
7714:
7133:
7051:
647:
117:
70:
42:
12110:
11575:
5031:
16446:
13891:
13462:
13003:
12520:
11957:
11424:
10889:
10299:
9728:
9170:
8642:
7993:. These replacements preserve equivalence, since the previous variable standardization step ensured that
7177:
7095:
5542:
4120:
1233:
763:
16363:
14722:
14448:
14195:
13847:
13755:
13337:
12878:
12395:
11832:
11299:
10764:
10741:
10718:
10191:
10124:
9622:
9517:
9064:
8534:
6718:
496:
16337:
16122:
15738:
14855:
14554:
14330:
14301:
14038:
14009:
13598:
13139:
12658:
12629:
12156:
12066:
11621:
11082:
10511:
10274:
9921:
9365:
8835:
4642:
1179:
834:
8311:
6926:
6820:
2887:
6847:
610:
86:
7460:
7311:
6663:
12133:
11598:
7005:
6689:
5538:
16090:
15679:
8751:
6800:
903:
16537:
16073:
15631:
5530:
2974:
870:
826:
805:
121:
6553:
6316:
6117:
5880:
4903:
2833:
16519:
13248:
12827:
12767:
12308:
12284:
11800:
11749:
11210:
10690:
10639:
10100:
10049:
9493:
9013:
8962:
8502:
8451:
4497:
4369:
3714:{\displaystyle (X_{1}\wedge Y_{1})\vee (X_{2}\wedge Y_{2})\vee \ldots \vee (X_{n}\wedge Y_{n})}
2953:
1058:{\displaystyle \lnot \phi _{DNF}=(C_{1}\lor C_{2}\lor \ldots \lor C_{i}\lor \ldots \lor C_{m})}
541:
345:
201:
16293:
11040:
10469:
9879:
9323:
8793:
4372:
satisfies this formula only if at least one of the new variables is true. If this variable is
4109:
There exist transformations into CNF that avoid an exponential increase in size by preserving
16557:
16542:
16077:
15621:
6511:
6396:
6274:
6075:
5960:
5838:
5545:, is also NP-hard; hence equivalence-preserving conversion into DNF or CNF is again NP-hard.
4710:
3550:
2929:
751:
155:
82:
16397:
16046:
13870:
13441:
13420:
12982:
12961:
12499:
12478:
11936:
11915:
11403:
11382:
10868:
10847:
10170:
9601:
9043:
8056:
8036:
7215:
6459:
6225:
6023:
5981:
5939:
5789:
2812:
1215:
225:
16552:
16546:
16527:
16026:
16020:
16016:
15810:
15780:
15711:
13571:
13112:
11533:
10998:
10427:
9837:
9705:
9147:
8076:
6654:
6096:
6054:
5859:
5817:
4951:
4615:
4460:
4429:
4402:
4375:
4062:
4035:
3726:
3505:
3352:
1071:
934:
785:
303:
266:
208:
179:
131:
15379:
15330:
15259:
15210:
14893:
14763:
14368:
14236:
14076:
13935:
13796:
13636:
8:
15835:
14923:
14398:
14106:
13666:
13198:
12717:
12215:
11680:
11141:
10570:
9980:
9424:
8894:
4490:
4114:
767:
759:
755:
574:
149:
125:
113:
109:
66:
58:
31:
15178:
15157:
14994:
14952:
14689:
14668:
6612:
6591:
6438:
6354:
6204:
6183:
4739:
16622:
16599:
16589:
15359:
15310:
15288:
15239:
15077:
14973:
14828:
14793:
14636:
14471:
14427:
14266:
14162:
13986:
13965:
13826:
13730:
13548:
13527:
13506:
13399:
13378:
13312:
13177:
13089:
13068:
13047:
12940:
12919:
12853:
12696:
12608:
12585:
12564:
12457:
12436:
12336:
12242:
12194:
12089:
12045:
12022:
12001:
11894:
11873:
11779:
11707:
11659:
11554:
11512:
11489:
11468:
11361:
11340:
11240:
11168:
11120:
11061:
11019:
10977:
10954:
10933:
10826:
10805:
10669:
10597:
10549:
10490:
10448:
10406:
10385:
10364:
10343:
10253:
10232:
10147:
10079:
10007:
9959:
9900:
9858:
9816:
9793:
9772:
9684:
9663:
9544:
9451:
9403:
9344:
9302:
9258:
9235:
9214:
9126:
9105:
8992:
8921:
8873:
8814:
8772:
8730:
8707:
8686:
8596:
8575:
8481:
8297:
8279:
8259:
8016:
7996:
7611:
7031:
6841:
6532:
6490:
6417:
6375:
6295:
6253:
6155:
6002:
5918:
5768:
5008:
4988:
4883:
4690:
4486:
4089:
3576:
3527:
3007:
2908:
2866:
2791:
2768:
2747:
2726:
2704:{\displaystyle \phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))}
1759:{\displaystyle \phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))}
389:
200:
operator can only be used as part of a literal, which means that it can only precede a
16305:
7th
International Conference on Theory and Applications of Satisfiability Testing, SAT
16581:
16419:
16372:
16355:
16341:
16316:
16278:
16254:
6646:
5087:
900:
by swapping ANDs with ORs and vice versa while negating all the literals. Remove all
16617:
16609:
16308:
5522:
4871:{\displaystyle L=\{p_{1},\lnot p_{1},p_{2},\lnot p_{2},\ldots ,p_{n},\lnot p_{n}\}}
771:
16304:
16594:
16393:
5526:
747:
15853:
15841:
15640:
15198:
8410:
485:{\displaystyle (A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F\lor D\lor F)}
90:
62:
16642:
16251:
An
Introduction to Mathematical Logic and Type Theory: To Truth Through Proof
5482:
38:
8249:{\displaystyle \forall x_{1}\ldots \forall x_{n}\;P(f(x_{1},\ldots ,x_{n}))}
16572:
16359:
16268:
4454:
782:
The algorithm to compute a CNF-equivalent of a given propositional formula
16562:
15644:
15636:
5510:
2715:
2622:
16479:
16312:
16239:, pp. 345–347, 9.5.1 Conjunctive normal form for first-order logic.
16072:
since one way to check a CNF for satisfiability is to convert it into a
5552:
A formula in CNF can be converted into an equisatisfiable formula in "
758:
formula that is in CNF. This transformation is based on rules about
15847:
15829:
15652:
173:
8155:{\displaystyle \forall x_{1}\ldots \forall x_{n}\;\exists y\;P(y)}
16465:
8413:
form in the last line) as follows (highlighting replacement rule
5622:{\displaystyle X_{1}\vee \ldots \vee X_{k}\vee \ldots \vee X_{n}}
5534:
5758:. In resolution-based automated theorem-proving, a CNF formula
16008:{\displaystyle (a\land b)\lor (b\land a)\lor (a\land b\land b)}
3502:
Each disjunction reflects an assignment of variables for which
1163:{\displaystyle l_{i1}\land l_{i2}\land \ldots \land l_{in_{i}}}
8414:
6660:
Eliminate implications and equivalences: repeatedly replace
5529:. As a consequence, the task of converting a formula into a
16398:"On the Complexity of Derivation in Propositional Calculus"
8407:"Anyone who loves all animals, is in turn loved by someone"
4945:
This is the maximum number of disjunctions a CNF can have.
16218:
16462:"Java tool for converting a truth table into CNF and DNF"
16330:
Kleine Büning, Hans; Lettmann, Theodor (28 August 1999).
15859:
15305:
doesn't love. The 3rd last line from below then reads as
4948:
All truth-functional combinations can be expressed with
108:
A logical formula is considered to be in CNF if it is a
16371:(3rd ed.). Upper Saddle River, NJ: Prentice Hall.
16179:
16177:
5735:{\displaystyle \neg Z\vee X_{k}\lor \ldots \vee X_{n}}
2621:
A CNF equivalent of a formula can be derived from its
16329:
16125:
16093:
16049:
16029:
15947:
15923:{\displaystyle \left|{\mathcal {P}}(L)\right|=2^{2n}}
15877:
15813:
15783:
15741:
15714:
15682:
15416:
15382:
15362:
15333:
15313:
15291:
15262:
15242:
15213:
15181:
15160:
15101:
15080:
15018:
14997:
14976:
14955:
14926:
14896:
14858:
14831:
14796:
14766:
14725:
14692:
14671:
14639:
14580:
14557:
14495:
14474:
14451:
14430:
14401:
14371:
14333:
14304:
14269:
14239:
14198:
14165:
14109:
14079:
14041:
14012:
13989:
13968:
13938:
13894:
13873:
13850:
13829:
13799:
13758:
13733:
13669:
13639:
13601:
13574:
13551:
13530:
13509:
13465:
13444:
13423:
13402:
13381:
13340:
13315:
13283:
13251:
13201:
13180:
13142:
13115:
13092:
13071:
13050:
13006:
12985:
12964:
12943:
12922:
12881:
12856:
12830:
12794:
12770:
12720:
12699:
12661:
12632:
12611:
12588:
12567:
12523:
12502:
12481:
12460:
12439:
12398:
12360:
12339:
12311:
12287:
12245:
12218:
12197:
12159:
12136:
12113:
12092:
12069:
12048:
12025:
12004:
11960:
11939:
11918:
11897:
11876:
11835:
11803:
11782:
11752:
11710:
11683:
11662:
11624:
11601:
11578:
11557:
11536:
11515:
11492:
11471:
11427:
11406:
11385:
11364:
11343:
11302:
11264:
11243:
11213:
11171:
11144:
11123:
11085:
11064:
11043:
11022:
11001:
10980:
10957:
10936:
10892:
10871:
10850:
10829:
10808:
10767:
10744:
10721:
10693:
10672:
10642:
10600:
10573:
10552:
10514:
10493:
10472:
10451:
10430:
10409:
10388:
10367:
10346:
10302:
10277:
10256:
10235:
10194:
10173:
10150:
10127:
10103:
10082:
10052:
10010:
9983:
9962:
9924:
9903:
9882:
9861:
9840:
9819:
9796:
9775:
9731:
9708:
9687:
9666:
9625:
9604:
9568:
9547:
9520:
9496:
9454:
9427:
9406:
9368:
9347:
9326:
9305:
9282:
9261:
9238:
9217:
9173:
9150:
9129:
9108:
9067:
9046:
9016:
8995:
8965:
8924:
8897:
8876:
8838:
8817:
8796:
8775:
8754:
8733:
8710:
8689:
8645:
8620:
8599:
8578:
8537:
8505:
8484:
8454:
8423:
8352:
8314:
8308:
Distribute ORs inwards over ANDs: repeatedly replace
8282:
8262:
8168:
8102:
8079:
8059:
8039:
8019:
7999:
7952:
7905:
7858:
7811:
7764:
7717:
7670:
7623:
7463:
7314:
7246:
7232:
may occur only immediately before a predicate symbol.
7218:
7180:
7136:
7098:
7054:
7034:
7008:
6964:
6929:
6885:
6850:
6823:
6803:
6797:. Eventually, this will eliminate all occurrences of
6747:
6721:
6692:
6666:
6615:
6594:
6556:
6535:
6514:
6493:
6462:
6441:
6420:
6399:
6378:
6357:
6319:
6298:
6277:
6256:
6228:
6207:
6186:
6158:
6120:
6099:
6078:
6057:
6026:
6005:
5984:
5963:
5942:
5921:
5883:
5862:
5841:
5820:
5792:
5771:
5746:
a new variable, and repeating as often as necessary.
5693:
5635:
5570:
5085:
5034:
5011:
4991:
4954:
4906:
4886:
4765:
4742:
4713:
4693:
4645:
4618:
4565:
4506:
4463:
4432:
4405:
4378:
4171:
4123:
4092:
4065:
4038:
3758:
3729:
3611:
3579:
3553:
3530:
3508:
3375:
3355:
3010:
2977:
2956:
2932:
2911:
2890:
2869:
2836:
2815:
2794:
2771:
2750:
2729:
2631:
1924:
1776:
1686:
1470:
1242:
1218:
1182:
1101:
1074:
965:
937:
906:
873:
837:
808:
788:
693:
650:
613:
577:
544:
499:
415:
392:
348:
306:
269:
228:
182:
158:
134:
15941:
It is assumed that repetitions and variations (like
6790:{\displaystyle (P\lor \lnot Q)\land (\lnot P\lor Q)}
6640:
5560:≥3) by replacing each conjunct with more than
957:: Convert its negation to disjunctive normal form.
16407:. Steklov Mathematical Institute. pp. 115–125.
16274:
Logic with trees: an introduction to symbolic logic
16174:
7301:{\displaystyle (\forall xP(x))\lor (\exists xQ(x))}
5680:{\displaystyle X_{1}\vee \ldots \vee X_{k-1}\vee Z}
4552:{\displaystyle Z_{i}\vee \neg X_{i}\vee \neg Y_{i}}
124:(DNF), the only propositional operators in CNF are
16206:
16150:
16108:
16055:
16035:
16007:
15922:
15819:
15789:
15766:
15720:
15697:
15604:
15397:
15368:
15348:
15319:
15297:
15277:
15248:
15228:
15187:
15166:
15145:
15086:
15065:
15003:
14982:
14961:
14938:
14911:
14881:
14837:
14802:
14781:
14751:
14698:
14677:
14645:
14624:
14565:
14542:
14480:
14459:
14436:
14413:
14386:
14356:
14312:
14275:
14254:
14224:
14171:
14121:
14094:
14064:
14020:
13995:
13974:
13953:
13923:
13879:
13858:
13835:
13814:
13784:
13739:
13681:
13654:
13624:
13580:
13557:
13536:
13515:
13494:
13450:
13429:
13408:
13387:
13366:
13321:
13298:
13260:
13213:
13186:
13165:
13121:
13098:
13077:
13056:
13035:
12991:
12970:
12949:
12928:
12907:
12862:
12839:
12809:
12779:
12732:
12705:
12684:
12640:
12617:
12594:
12573:
12552:
12508:
12487:
12466:
12445:
12424:
12375:
12345:
12320:
12296:
12251:
12230:
12203:
12182:
12144:
12121:
12098:
12077:
12054:
12031:
12010:
11989:
11945:
11924:
11903:
11882:
11861:
11812:
11788:
11761:
11716:
11695:
11668:
11647:
11609:
11586:
11563:
11542:
11521:
11498:
11477:
11456:
11412:
11391:
11370:
11349:
11328:
11279:
11249:
11222:
11177:
11156:
11129:
11108:
11070:
11049:
11028:
11007:
10986:
10963:
10942:
10921:
10877:
10856:
10835:
10814:
10793:
10752:
10729:
10702:
10678:
10651:
10606:
10585:
10558:
10537:
10499:
10478:
10457:
10436:
10415:
10394:
10373:
10352:
10331:
10285:
10262:
10241:
10220:
10179:
10156:
10135:
10112:
10088:
10061:
10016:
9995:
9968:
9947:
9909:
9888:
9867:
9846:
9825:
9802:
9781:
9760:
9714:
9693:
9672:
9651:
9610:
9583:
9553:
9528:
9505:
9460:
9439:
9412:
9391:
9353:
9332:
9311:
9290:
9267:
9244:
9223:
9202:
9156:
9135:
9114:
9093:
9052:
9025:
9001:
8974:
8930:
8909:
8882:
8861:
8823:
8802:
8781:
8760:
8739:
8716:
8695:
8674:
8628:
8605:
8584:
8563:
8514:
8490:
8463:
8435:
8388:
8338:
8288:
8268:
8248:
8154:
8085:
8065:
8045:
8025:
8005:
7985:
7938:
7891:
7844:
7797:
7750:
7703:
7656:
7598:
7449:
7300:
7224:
7204:
7166:
7122:
7084:
7040:
7020:
6994:
6950:
6915:
6871:
6829:
6809:
6789:
6733:
6707:
6678:
6621:
6600:
6579:
6541:
6520:
6499:
6478:
6447:
6426:
6405:
6384:
6363:
6342:
6304:
6283:
6262:
6241:
6213:
6192:
6164:
6143:
6105:
6084:
6063:
6042:
6011:
5990:
5969:
5948:
5927:
5906:
5868:
5847:
5826:
5805:
5777:
5734:
5679:
5621:
5471:
5071:
5017:
4997:
4975:disjunctions, one for each row of the truth table.
4967:
4934:
4892:
4870:
4751:
4725:
4699:
4671:
4631:
4604:
4551:
4476:
4445:
4418:
4391:
4358:
4155:
4098:
4078:
4051:
4022:
3742:
3713:
3585:
3562:
3536:
3514:
3492:
3361:
3016:
2995:
2962:
2941:
2917:
2896:
2875:
2854:
2821:
2800:
2777:
2756:
2735:
2703:
2606:
1909:
1758:
1659:
1456:
1224:
1204:
1162:
1087:
1057:
943:
915:
892:
859:
817:
794:
729:
677:
634:
589:
562:
529:
484:
398:
378:
312:
275:
234:
188:
164:
140:
16301:Theory and Applications of Satisfiability Testing
16299:. In Hoos, Holger H.; Mitchell, David G. (eds.).
15236:can be thought of as yielding the person by whom
4682:
16640:
16365:Artificial Intelligence : A Modern Approach
16202:Disjunctive normal form § Conversion to DNF
16076:, the satisfiability of which can be checked in
926:
16292:Jackson, Paul; Sheridan, Daniel (10 May 2004).
16291:
16224:
2616:
342:All of the following formulas in the variables
16294:"Clause Form Conversions for Boolean Circuits"
15066:{\displaystyle \lnot \mathrm {Loves} (x,f(x))}
14543:{\displaystyle \lnot \mathrm {Loves} (x,f(x))}
7617:Move quantifiers outwards: repeatedly replace
16495:
16333:Propositional Logic: Deduction and Algorithms
8409:is converted into CNF (and subsequently into
4612:; this formula is often regarded to "define"
4605:{\displaystyle Z_{i}\equiv X_{i}\wedge Y_{i}}
16354:
16236:
15804:
15802:
15182:
15161:
14998:
14956:
14693:
14672:
6616:
6595:
6442:
6358:
6208:
6187:
4865:
4772:
2085:
1974:
1769:The (full) DNF equivalent of its negation is
6176:, is commonly represented as a set of sets
5488:
16502:
16488:
8436:{\displaystyle {\color {red}{\text{red}}}}
8198:
8139:
8132:
4977:In the example below they are underlined.
4559:. With these clauses, the formula implies
96:In automated theorem proving, the notion "
16509:
16411:
15799:
13299:{\displaystyle {\color {red}{\exists y}}}
12810:{\displaystyle {\color {red}{\exists z}}}
12376:{\displaystyle {\color {red}{\exists y}}}
11280:{\displaystyle {\color {red}{\exists y}}}
9584:{\displaystyle {\color {red}{\forall y}}}
6840:Move NOTs inwards by repeatedly applying
1680:Convert to CNF the propositional formula
931:Convert to CNF the propositional formula
730:{\displaystyle A\land (B\lor (D\land E))}
15937:
15935:
15146:{\displaystyle \mathrm {Loves} (g(x),x)}
14625:{\displaystyle \mathrm {Loves} (g(x),x)}
9291:{\displaystyle \color {red}\rightarrow }
8629:{\displaystyle \color {red}\rightarrow }
8389:{\displaystyle (P\lor Q)\land (P\lor R)}
6916:{\displaystyle (\lnot P)\land (\lnot Q)}
4453:are true as well. This means that every
16392:
16248:
16212:
6995:{\displaystyle (\lnot P)\lor (\lnot Q)}
3573:is F(alse), then the literal is set to
14:
16641:
16267:
16183:
7892:{\displaystyle \exists x(P\land Q(x))}
7845:{\displaystyle P\land (\exists xQ(x))}
7704:{\displaystyle \forall x(P\land Q(x))}
7657:{\displaystyle P\land (\forall xQ(x))}
4985:Consider a formula with two variables
4687:Consider a propositional formula with
3547:is T(rue), then the literal is set to
1234:(generalized) De Morgan's equivalences
16483:
16196:
16194:
16192:
16158:
16116:
15932:
7986:{\displaystyle \exists x(P\lor Q(x))}
7939:{\displaystyle P\lor (\exists xQ(x))}
7798:{\displaystyle \forall x(P\lor Q(x))}
7751:{\displaystyle P\lor (\forall xQ(x))}
7167:{\displaystyle \lnot (\exists xP(x))}
7085:{\displaystyle \lnot (\forall xP(x))}
737:, since an AND is nested within an OR
678:{\displaystyle \neg (A\lor B)\land C}
642:, since an AND is nested within a NOT
16415:Boolean Algebra and Its Applications
16412:Whitesitt, J. Eldon (24 May 2012) .
16388:from the original on 31 August 2017.
12122:{\displaystyle \color {red}\exists }
11587:{\displaystyle \color {red}\exists }
5749:
5072:{\displaystyle 2^{(2\times 2)}-1=15}
3524:If in such an assignment a variable
741:
685:, since an OR is nested within a NOT
13924:{\displaystyle \mathrm {Loves} (x,}
13495:{\displaystyle \mathrm {Loves} (x,}
13036:{\displaystyle \mathrm {Loves} (x,}
12553:{\displaystyle \mathrm {Loves} (x,}
11990:{\displaystyle \mathrm {Loves} (x,}
11457:{\displaystyle \mathrm {Loves} (x,}
10922:{\displaystyle \mathrm {Loves} (x,}
10332:{\displaystyle \mathrm {Loves} (x,}
9761:{\displaystyle \mathrm {Loves} (x,}
9203:{\displaystyle \mathrm {Loves} (x,}
8675:{\displaystyle \mathrm {Loves} (x,}
8296:-ary function symbol, a so-called "
7205:{\displaystyle \forall x\lnot P(x)}
7123:{\displaystyle \exists x\lnot P(x)}
4156:{\displaystyle Z_{1},\ldots ,Z_{n}}
3597:
24:
16189:
15885:
15651:) with at most one positive, i.e.
15571:
15568:
15565:
15562:
15559:
15527:
15524:
15521:
15518:
15515:
15511:
15474:
15471:
15468:
15465:
15462:
15436:
15433:
15430:
15427:
15424:
15421:
15115:
15112:
15109:
15106:
15103:
15035:
15032:
15029:
15026:
15023:
15019:
14872:
14869:
14866:
14863:
14860:
14752:{\displaystyle \mathrm {Animal} (}
14742:
14739:
14736:
14733:
14730:
14727:
14594:
14591:
14588:
14585:
14582:
14512:
14509:
14506:
14503:
14500:
14496:
14460:{\displaystyle \color {red}\land }
14347:
14344:
14341:
14338:
14335:
14225:{\displaystyle \mathrm {Animal} (}
14215:
14212:
14209:
14206:
14203:
14200:
14055:
14052:
14049:
14046:
14043:
13908:
13905:
13902:
13899:
13896:
13874:
13859:{\displaystyle \color {red}\land }
13785:{\displaystyle \mathrm {Animal} (}
13775:
13772:
13769:
13766:
13763:
13760:
13615:
13612:
13609:
13606:
13603:
13479:
13476:
13473:
13470:
13467:
13445:
13367:{\displaystyle \mathrm {Animal} (}
13357:
13354:
13351:
13348:
13345:
13342:
13287:
13252:
13156:
13153:
13150:
13147:
13144:
13020:
13017:
13014:
13011:
13008:
12986:
12908:{\displaystyle \mathrm {Animal} (}
12898:
12895:
12892:
12889:
12886:
12883:
12831:
12798:
12771:
12675:
12672:
12669:
12666:
12663:
12537:
12534:
12531:
12528:
12525:
12503:
12425:{\displaystyle \mathrm {Animal} (}
12415:
12412:
12409:
12406:
12403:
12400:
12364:
12312:
12288:
12173:
12170:
12167:
12164:
12161:
12115:
11974:
11971:
11968:
11965:
11962:
11940:
11862:{\displaystyle \mathrm {Animal} (}
11852:
11849:
11846:
11843:
11840:
11837:
11804:
11753:
11638:
11635:
11632:
11629:
11626:
11580:
11441:
11438:
11435:
11432:
11429:
11407:
11329:{\displaystyle \mathrm {Animal} (}
11319:
11316:
11313:
11310:
11307:
11304:
11268:
11214:
11099:
11096:
11093:
11090:
11087:
11044:
10906:
10903:
10900:
10897:
10894:
10872:
10794:{\displaystyle \mathrm {Animal} (}
10784:
10781:
10778:
10775:
10772:
10769:
10753:{\displaystyle \color {red}\lnot }
10746:
10730:{\displaystyle \color {red}\lnot }
10723:
10694:
10643:
10528:
10525:
10522:
10519:
10516:
10473:
10316:
10313:
10310:
10307:
10304:
10221:{\displaystyle \mathrm {Animal} (}
10211:
10208:
10205:
10202:
10199:
10196:
10174:
10136:{\displaystyle \color {red}\lnot }
10129:
10104:
10053:
9938:
9935:
9932:
9929:
9926:
9883:
9745:
9742:
9739:
9736:
9733:
9652:{\displaystyle \mathrm {Animal} (}
9642:
9639:
9636:
9633:
9630:
9627:
9605:
9572:
9529:{\displaystyle \color {red}\lnot }
9522:
9497:
9382:
9379:
9376:
9373:
9370:
9327:
9187:
9184:
9181:
9178:
9175:
9094:{\displaystyle \mathrm {Animal} (}
9084:
9081:
9078:
9075:
9072:
9069:
9047:
9017:
8966:
8852:
8849:
8846:
8843:
8840:
8797:
8659:
8656:
8653:
8650:
8647:
8564:{\displaystyle \mathrm {Animal} (}
8554:
8551:
8548:
8545:
8542:
8539:
8506:
8455:
8405:As an example, the formula saying
8185:
8169:
8133:
8119:
8103:
8040:
7953:
7915:
7859:
7821:
7765:
7727:
7671:
7633:
7574:
7571:
7568:
7565:
7562:
7555:
7527:
7524:
7521:
7518:
7515:
7511:
7495:
7492:
7489:
7486:
7483:
7480:
7473:
7464:
7425:
7422:
7419:
7416:
7413:
7406:
7378:
7375:
7372:
7369:
7366:
7362:
7346:
7343:
7340:
7337:
7334:
7331:
7324:
7315:
7277:
7250:
7219:
7187:
7181:
7143:
7137:
7105:
7099:
7061:
7055:
7012:
7009:
6983:
6968:
6930:
6904:
6889:
6851:
6772:
6757:
6734:{\displaystyle P\leftrightarrow Q}
6693:
5694:
5541:, converting into CNF, preserving
5450:
5435:
5410:
5383:
5374:
5347:
5332:
5317:
5292:
5244:
5208:
5184:
5175:
5151:
5120:
5093:
4852:
4817:
4788:
4536:
4520:
4324:
4289:
4248:
4213:
3554:
3475:
3442:
3421:
3412:
3397:
3388:
3379:
2933:
2816:
2671:
2644:
2571:
2568:
2545:
2512:
2491:
2482:
2467:
2458:
2449:
2407:
2404:
2395:
2386:
2383:
2368:
2365:
2356:
2353:
2344:
2329:
2326:
2317:
2308:
2293:
2284:
2275:
2239:
2224:
2218:
2197:
2188:
2176:
2155:
2137:
2101:
2076:
2061:
2046:
2037:
2016:
1971:
1942:
1939:
1898:
1883:
1868:
1859:
1838:
1777:
1726:
1699:
1619:
1594:
1575:
1495:
1475:
1429:
1407:
1385:
1369:
1289:
1260:
1257:
1219:
1183:
966:
910:
907:
838:
809:
777:
651:
614:
530:{\displaystyle (A\lor B)\land (C)}
449:
434:
425:
307:
183:
25:
16665:
16434:
16151:{\displaystyle 1\leq in_{i}\leq }
15767:{\displaystyle 1\leq in_{i}\leq }
15639:– A Horn clause is a disjunctive
14882:{\displaystyle \mathrm {Loves} (}
14566:{\displaystyle \color {red}\lor }
14558:
14452:
14357:{\displaystyle \mathrm {Loves} (}
14313:{\displaystyle \color {red}\lor }
14305:
14065:{\displaystyle \mathrm {Loves} (}
14021:{\displaystyle \color {red}\lor }
14013:
13851:
13625:{\displaystyle \mathrm {Loves} (}
13285:
13166:{\displaystyle \mathrm {Loves} (}
12796:
12685:{\displaystyle \mathrm {Loves} (}
12641:{\displaystyle \color {red}\lor }
12633:
12362:
12183:{\displaystyle \mathrm {Loves} (}
12137:
12114:
12078:{\displaystyle \color {red}\lor }
12070:
11648:{\displaystyle \mathrm {Loves} (}
11602:
11579:
11266:
11109:{\displaystyle \mathrm {Loves} (}
10745:
10722:
10538:{\displaystyle \mathrm {Loves} (}
10286:{\displaystyle \color {red}\lor }
10278:
10128:
9948:{\displaystyle \mathrm {Loves} (}
9570:
9521:
9392:{\displaystyle \mathrm {Loves} (}
9283:
8862:{\displaystyle \mathrm {Loves} (}
8621:
8425:
6641:Converting from first-order logic
4672:{\displaystyle X_{i}\wedge Y_{i}}
3723:into CNF produces a formula with
1205:{\displaystyle \lnot \phi _{DNF}}
860:{\displaystyle \lnot \phi _{DNF}}
27:Standard form of Boolean function
16571:
15285:yields the animal (if any) that
15207:Informally, the Skolem function
8339:{\displaystyle P\lor (Q\land R)}
6951:{\displaystyle \lnot (P\land Q)}
6830:{\displaystyle \leftrightarrow }
5533:, preserving satisfiability, is
5493:An important set of problems in
4496:An alternative translation, the
2897:{\displaystyle \leftrightarrow }
406:are in conjunctive normal form:
16628:Normal form (natural deduction)
16082:
16066:
15659:Quine–McCluskey algorithm
15627:Conjunction/disjunction duality
8305:Drop all universal quantifiers.
6872:{\displaystyle \lnot (P\lor Q)}
1672:: Remove all double negations.
635:{\displaystyle \neg (A\land B)}
16117:maximum number of disjunctions
16002:
15984:
15978:
15966:
15960:
15948:
15896:
15890:
15866:
15730:
15706:maximum number of conjunctions
15671:
15599:
15596:
15587:
15581:
15575:
15552:
15549:
15543:
15531:
15508:
15502:
15499:
15490:
15484:
15478:
15455:
15452:
15446:
15440:
15417:
15410:The 2nd last line from above,
15392:
15386:
15343:
15337:
15272:
15266:
15223:
15217:
15140:
15131:
15125:
15119:
15060:
15057:
15051:
15039:
14933:
14906:
14900:
14876:
14797:
14776:
14770:
14746:
14640:
14619:
14610:
14604:
14598:
14537:
14534:
14528:
14516:
14475:
14431:
14408:
14381:
14375:
14351:
14270:
14249:
14243:
14219:
14166:
14116:
14089:
14083:
14059:
13990:
13969:
13948:
13942:
13912:
13830:
13809:
13803:
13779:
13734:
13676:
13649:
13643:
13619:
13552:
13531:
13483:
13403:
13361:
13316:
13208:
13160:
13093:
13072:
13024:
12944:
12902:
12857:
12727:
12679:
12612:
12589:
12541:
12461:
12419:
12340:
12246:
12225:
12177:
12093:
12049:
12026:
11978:
11898:
11856:
11783:
11711:
11690:
11642:
11558:
11516:
11493:
11445:
11365:
11323:
11244:
11172:
11151:
11103:
11023:
10981:
10958:
10910:
10830:
10788:
10673:
10601:
10580:
10532:
10452:
10410:
10389:
10368:
10320:
10257:
10215:
10151:
10083:
10011:
9990:
9942:
9862:
9820:
9797:
9749:
9688:
9646:
9548:
9455:
9434:
9386:
9306:
9284:
9262:
9239:
9191:
9130:
9088:
8996:
8925:
8904:
8856:
8776:
8755:
8734:
8711:
8663:
8622:
8600:
8558:
8485:
8383:
8371:
8365:
8353:
8333:
8321:
8243:
8240:
8208:
8202:
8149:
8143:
7980:
7977:
7971:
7959:
7933:
7930:
7924:
7912:
7886:
7883:
7877:
7865:
7839:
7836:
7830:
7818:
7792:
7789:
7783:
7771:
7745:
7742:
7736:
7724:
7698:
7695:
7689:
7677:
7651:
7648:
7642:
7630:
7599:{\displaystyle \forall x\lor }
7593:
7590:
7578:
7552:
7546:
7543:
7531:
7505:
7499:
7470:
7450:{\displaystyle \forall x\lor }
7444:
7441:
7429:
7403:
7397:
7394:
7382:
7356:
7350:
7321:
7295:
7292:
7286:
7274:
7268:
7265:
7259:
7247:
7199:
7193:
7161:
7158:
7152:
7140:
7117:
7111:
7079:
7076:
7070:
7058:
6989:
6980:
6974:
6965:
6945:
6933:
6910:
6901:
6895:
6886:
6866:
6854:
6824:
6804:
6784:
6769:
6763:
6748:
6725:
6679:{\displaystyle P\rightarrow Q}
6670:
6159:
6006:
5922:
5772:
5525:is known to have solutions in
5462:
5432:
5422:
5401:
5395:
5371:
5365:
5344:
5338:
5314:
5304:
5289:
5277:
5265:
5250:
5235:
5220:
5205:
5190:
5172:
5163:
5148:
5138:
5132:
5126:
5117:
5111:
5105:
5099:
5090:
5052:
5040:
4929:
4907:
4683:Maximum number of disjunctions
4350:
4321:
4315:
4286:
4274:
4245:
4239:
4210:
4204:
4172:
4014:
3969:
3957:
3912:
3906:
3861:
3855:
3810:
3804:
3759:
3708:
3682:
3670:
3644:
3638:
3612:
3487:
3466:
3460:
3439:
3433:
3409:
3403:
3376:
3011:
2990:
2978:
2957:
2912:
2891:
2870:
2849:
2837:
2795:
2698:
2695:
2692:
2680:
2677:
2668:
2665:
2662:
2659:
2647:
2641:
2638:
2625:. Again, consider the formula
2557:
2536:
2530:
2509:
2503:
2479:
2473:
2446:
2443:
2433:
2424:
2413:
2380:
2374:
2341:
2335:
2305:
2299:
2272:
2269:
2245:
2221:
2203:
2179:
2161:
2140:
2122:
2104:
2095:
2082:
2058:
2052:
2028:
2022:
2001:
1995:
1977:
1936:
1904:
1880:
1874:
1850:
1844:
1823:
1817:
1799:
1753:
1750:
1747:
1735:
1732:
1723:
1720:
1717:
1714:
1702:
1696:
1693:
1642:
1572:
1569:
1559:
1498:
1366:
1356:
1292:
1254:
1052:
988:
724:
721:
709:
700:
666:
654:
629:
617:
584:
578:
557:
545:
524:
518:
512:
500:
479:
446:
440:
416:
13:
1:
16167:
12145:{\displaystyle \color {red}z}
11610:{\displaystyle \color {red}y}
7021:{\displaystyle \lnot \lnot P}
6708:{\displaystyle \lnot P\lor Q}
5028:The longest possible CNF has
1095:is a conjunction of literals
927:Conversion by syntactic means
827:disjunctive normal form (DNF)
103:
16109:{\displaystyle 1\leq m\leq }
15698:{\displaystyle 1\leq m\leq }
8761:{\displaystyle \rightarrow }
6810:{\displaystyle \rightarrow }
4500:, includes also the clauses
4032:Each clause contains either
2617:Conversion by semantic means
916:{\displaystyle \lnot \lnot }
604:in conjunctive normal form:
7:
16447:Encyclopedia of Mathematics
16403:. In Slisenko, A.O. (ed.).
16225:Jackson & Sheridan 2004
15615:
2996:{\displaystyle (p\oplus q)}
893:{\displaystyle \phi _{CNF}}
818:{\displaystyle \lnot \phi }
764:double negation elimination
600:The following formulas are
10:
16670:
16338:Cambridge University Press
16249:Andrews, Peter B. (2013).
16159:maximum number of literals
15775:maximum number of literals
6637:See below for an example.
6580:{\displaystyle l_{mn_{m}}}
6343:{\displaystyle l_{1n_{1}}}
6144:{\displaystyle l_{mn_{m}}}
5907:{\displaystyle l_{1n_{1}}}
4935:{\displaystyle (2^{2n}-1)}
2855:{\displaystyle (p\land q)}
1236:until no longer possible.
29:
18:Product-of-sums expression
16608:
16580:
16569:
16518:
16442:"Conjunctive normal form"
13261:{\displaystyle \forall x}
12840:{\displaystyle \exists y}
12780:{\displaystyle \forall x}
12321:{\displaystyle \exists z}
12297:{\displaystyle \forall x}
11813:{\displaystyle \exists y}
11762:{\displaystyle \forall x}
11223:{\displaystyle \forall x}
10703:{\displaystyle \exists y}
10652:{\displaystyle \forall x}
10113:{\displaystyle \exists y}
10062:{\displaystyle \forall x}
9506:{\displaystyle \forall x}
9026:{\displaystyle \forall y}
8975:{\displaystyle \forall x}
8515:{\displaystyle \forall y}
8464:{\displaystyle \forall x}
2963:{\displaystyle \uparrow }
2421:// generalized D.M.
2259:// generalized D.M.
563:{\displaystyle (A\lor B)}
379:{\displaystyle A,B,C,D,E}
87:automated theorem proving
73:; otherwise put, it is a
16237:Russel & Norvig 2010
15664:
15327:doesn't love the animal
11050:{\displaystyle \exists }
10479:{\displaystyle \exists }
9889:{\displaystyle \exists }
9333:{\displaystyle \exists }
8803:{\displaystyle \exists }
6844:. Specifically, replace
5495:computational complexity
5489:Computational complexity
1232:inwards by applying the
30:Not to be confused with
16538:Disjunctive normal form
16533:Conjunctive normal form
16418:. Courier Corporation.
15632:Disjunctive normal form
6521:{\displaystyle \ldots }
6406:{\displaystyle \ldots }
6284:{\displaystyle \ldots }
6085:{\displaystyle \ldots }
5970:{\displaystyle \ldots }
5848:{\displaystyle \ldots }
4726:{\displaystyle n\geq 1}
3563:{\displaystyle \lnot V}
2942:{\displaystyle \lnot r}
754:can be converted to an
165:{\displaystyle \wedge }
122:disjunctive normal form
47:conjunctive normal form
16152:
16110:
16057:
16056:{\displaystyle \land }
16037:
16009:
15924:
15821:
15791:
15768:
15722:
15699:
15606:
15399:
15370:
15350:
15321:
15299:
15279:
15250:
15230:
15189:
15168:
15147:
15088:
15067:
15005:
14984:
14963:
14940:
14913:
14883:
14839:
14804:
14783:
14753:
14700:
14679:
14647:
14626:
14567:
14544:
14482:
14461:
14438:
14415:
14388:
14358:
14314:
14277:
14256:
14226:
14173:
14123:
14096:
14066:
14022:
13997:
13976:
13955:
13925:
13881:
13880:{\displaystyle \lnot }
13860:
13837:
13816:
13786:
13741:
13683:
13656:
13626:
13582:
13559:
13538:
13517:
13496:
13452:
13451:{\displaystyle \lnot }
13431:
13430:{\displaystyle \land }
13410:
13389:
13368:
13323:
13300:
13262:
13215:
13188:
13167:
13123:
13100:
13079:
13058:
13037:
12993:
12992:{\displaystyle \lnot }
12972:
12971:{\displaystyle \land }
12951:
12930:
12909:
12864:
12841:
12811:
12781:
12734:
12707:
12686:
12642:
12619:
12596:
12575:
12554:
12510:
12509:{\displaystyle \lnot }
12489:
12488:{\displaystyle \land }
12468:
12447:
12426:
12377:
12347:
12322:
12298:
12253:
12232:
12205:
12184:
12146:
12123:
12100:
12079:
12056:
12033:
12012:
11991:
11947:
11946:{\displaystyle \lnot }
11926:
11925:{\displaystyle \land }
11905:
11884:
11863:
11814:
11790:
11763:
11718:
11697:
11670:
11649:
11611:
11588:
11565:
11544:
11523:
11500:
11479:
11458:
11414:
11413:{\displaystyle \lnot }
11393:
11392:{\displaystyle \land }
11372:
11351:
11330:
11281:
11251:
11224:
11179:
11158:
11131:
11110:
11072:
11051:
11030:
11009:
10988:
10965:
10944:
10923:
10879:
10878:{\displaystyle \lnot }
10858:
10857:{\displaystyle \land }
10837:
10816:
10795:
10754:
10731:
10704:
10680:
10653:
10608:
10587:
10560:
10539:
10501:
10480:
10459:
10438:
10417:
10396:
10375:
10354:
10333:
10287:
10264:
10243:
10222:
10181:
10180:{\displaystyle \lnot }
10158:
10137:
10114:
10090:
10063:
10018:
9997:
9970:
9949:
9911:
9890:
9869:
9848:
9827:
9804:
9783:
9762:
9716:
9695:
9674:
9653:
9612:
9611:{\displaystyle \lnot }
9585:
9555:
9530:
9507:
9462:
9441:
9414:
9393:
9355:
9334:
9313:
9292:
9269:
9246:
9225:
9204:
9158:
9137:
9116:
9095:
9054:
9053:{\displaystyle \lnot }
9027:
9003:
8976:
8932:
8911:
8884:
8863:
8825:
8804:
8783:
8762:
8741:
8718:
8697:
8676:
8630:
8607:
8586:
8565:
8516:
8492:
8465:
8437:
8390:
8340:
8290:
8270:
8250:
8156:
8087:
8067:
8066:{\displaystyle \land }
8047:
8046:{\displaystyle \lnot }
8027:
8007:
7987:
7940:
7893:
7846:
7799:
7752:
7705:
7658:
7600:
7451:
7302:
7237:Standardize variables
7226:
7225:{\displaystyle \lnot }
7206:
7168:
7124:
7086:
7042:
7022:
6996:
6952:
6917:
6873:
6831:
6811:
6791:
6735:
6709:
6680:
6623:
6602:
6581:
6543:
6522:
6501:
6480:
6479:{\displaystyle l_{m1}}
6449:
6428:
6407:
6386:
6365:
6344:
6306:
6285:
6264:
6243:
6242:{\displaystyle l_{11}}
6215:
6194:
6166:
6145:
6107:
6086:
6065:
6044:
6043:{\displaystyle l_{m1}}
6013:
5992:
5991:{\displaystyle \land }
5971:
5950:
5949:{\displaystyle \land }
5929:
5908:
5870:
5849:
5828:
5807:
5806:{\displaystyle l_{11}}
5779:
5756:first-order resolution
5736:
5681:
5623:
5473:
5073:
5019:
4999:
4969:
4936:
4894:
4872:
4753:
4727:
4701:
4673:
4633:
4606:
4553:
4498:Tseitin transformation
4478:
4447:
4420:
4393:
4360:
4157:
4100:
4080:
4053:
4024:
3744:
3715:
3587:
3564:
3538:
3516:
3494:
3363:
3018:
2997:
2964:
2943:
2919:
2898:
2877:
2856:
2823:
2822:{\displaystyle \lnot }
2802:
2779:
2758:
2737:
2705:
2608:
1911:
1760:
1661:
1458:
1226:
1225:{\displaystyle \lnot }
1206:
1164:
1089:
1059:
945:
917:
894:
861:
819:
796:
731:
679:
636:
591:
564:
531:
486:
400:
380:
314:
277:
236:
235:{\displaystyle \land }
202:propositional variable
190:
166:
142:
65:, where a clause is a
16654:Knowledge compilation
16558:Canonical normal form
16543:Algebraic normal form
16153:
16111:
16058:
16038:
16036:{\displaystyle \lor }
16010:
15925:
15822:
15820:{\displaystyle \phi }
15792:
15790:{\displaystyle \phi }
15769:
15723:
15721:{\displaystyle \phi }
15700:
15622:Algebraic normal form
15607:
15400:
15371:
15351:
15322:
15300:
15280:
15251:
15231:
15190:
15169:
15148:
15089:
15068:
15006:
14985:
14964:
14941:
14914:
14884:
14840:
14805:
14784:
14754:
14701:
14680:
14648:
14627:
14568:
14545:
14483:
14462:
14439:
14416:
14389:
14359:
14315:
14278:
14257:
14227:
14174:
14124:
14097:
14067:
14023:
13998:
13977:
13956:
13926:
13882:
13861:
13838:
13817:
13787:
13742:
13684:
13657:
13627:
13583:
13581:{\displaystyle \lor }
13560:
13539:
13518:
13497:
13453:
13432:
13411:
13390:
13369:
13324:
13301:
13263:
13216:
13189:
13168:
13124:
13122:{\displaystyle \lor }
13101:
13080:
13059:
13038:
12994:
12973:
12952:
12931:
12910:
12865:
12842:
12812:
12782:
12735:
12708:
12687:
12643:
12620:
12597:
12576:
12555:
12511:
12490:
12469:
12448:
12427:
12378:
12348:
12323:
12299:
12254:
12233:
12206:
12185:
12147:
12124:
12101:
12080:
12057:
12034:
12013:
11992:
11948:
11927:
11906:
11885:
11864:
11815:
11791:
11764:
11719:
11698:
11671:
11650:
11612:
11589:
11566:
11545:
11543:{\displaystyle \lor }
11524:
11501:
11480:
11459:
11415:
11394:
11373:
11352:
11331:
11282:
11252:
11225:
11180:
11159:
11132:
11111:
11073:
11052:
11031:
11010:
11008:{\displaystyle \lor }
10989:
10966:
10945:
10924:
10880:
10859:
10838:
10817:
10796:
10755:
10732:
10705:
10681:
10654:
10609:
10588:
10561:
10540:
10502:
10481:
10460:
10439:
10437:{\displaystyle \lor }
10418:
10397:
10376:
10355:
10334:
10288:
10265:
10244:
10223:
10182:
10159:
10138:
10115:
10091:
10064:
10019:
9998:
9971:
9950:
9912:
9891:
9870:
9849:
9847:{\displaystyle \lor }
9828:
9805:
9784:
9763:
9717:
9715:{\displaystyle \lor }
9696:
9675:
9654:
9613:
9586:
9556:
9531:
9508:
9463:
9442:
9415:
9394:
9356:
9335:
9314:
9293:
9270:
9247:
9226:
9205:
9159:
9157:{\displaystyle \lor }
9138:
9117:
9096:
9055:
9028:
9004:
8977:
8933:
8912:
8885:
8864:
8826:
8805:
8784:
8763:
8742:
8719:
8698:
8677:
8631:
8608:
8587:
8566:
8517:
8493:
8466:
8438:
8391:
8341:
8291:
8271:
8251:
8157:
8088:
8086:{\displaystyle \lor }
8068:
8048:
8028:
8008:
7988:
7941:
7894:
7847:
7800:
7753:
7706:
7659:
7601:
7452:
7303:
7227:
7207:
7169:
7125:
7087:
7043:
7023:
6997:
6953:
6918:
6874:
6832:
6812:
6792:
6736:
6710:
6681:
6624:
6603:
6582:
6544:
6523:
6502:
6481:
6450:
6429:
6408:
6387:
6366:
6345:
6307:
6286:
6265:
6244:
6216:
6195:
6167:
6146:
6108:
6106:{\displaystyle \lor }
6087:
6066:
6064:{\displaystyle \lor }
6045:
6014:
5993:
5972:
5951:
5930:
5909:
5871:
5869:{\displaystyle \lor }
5850:
5829:
5827:{\displaystyle \lor }
5808:
5780:
5737:
5682:
5624:
5474:
5074:
5020:
5000:
4970:
4968:{\displaystyle 2^{n}}
4937:
4895:
4873:
4754:
4728:
4702:
4674:
4634:
4632:{\displaystyle Z_{i}}
4607:
4554:
4479:
4477:{\displaystyle Z_{i}}
4448:
4446:{\displaystyle Y_{i}}
4421:
4419:{\displaystyle X_{i}}
4394:
4392:{\displaystyle Z_{i}}
4361:
4158:
4101:
4081:
4079:{\displaystyle Y_{i}}
4054:
4052:{\displaystyle X_{i}}
4025:
3745:
3743:{\displaystyle 2^{n}}
3716:
3588:
3565:
3539:
3522:evaluates to F(alse).
3517:
3515:{\displaystyle \phi }
3495:
3364:
3362:{\displaystyle \phi }
3019:
2998:
2965:
2944:
2920:
2899:
2878:
2857:
2824:
2803:
2780:
2759:
2738:
2706:
2609:
1912:
1761:
1662:
1650:// (generalized) D.M.
1459:
1447:// (generalized) D.M.
1227:
1207:
1165:
1090:
1088:{\displaystyle C_{i}}
1060:
946:
944:{\displaystyle \phi }
918:
895:
862:
820:
797:
795:{\displaystyle \phi }
752:propositional formula
732:
680:
637:
592:
565:
532:
487:
401:
381:
315:
313:{\displaystyle \neg }
278:
276:{\displaystyle \lor }
237:
191:
189:{\displaystyle \neg }
167:
143:
141:{\displaystyle \vee }
83:canonical normal form
16649:Normal forms (logic)
16553:Blake canonical form
16547:Zhegalkin polynomial
16528:Negation normal form
16271:(11 October 2005) .
16123:
16091:
16047:
16027:
15945:
15875:
15811:
15781:
15739:
15712:
15680:
15414:
15398:{\displaystyle g(x)}
15380:
15360:
15349:{\displaystyle f(x)}
15331:
15311:
15289:
15278:{\displaystyle f(x)}
15260:
15240:
15229:{\displaystyle g(x)}
15211:
15179:
15158:
15099:
15078:
15016:
14995:
14974:
14953:
14924:
14912:{\displaystyle g(x)}
14894:
14856:
14829:
14794:
14782:{\displaystyle f(x)}
14764:
14723:
14690:
14669:
14637:
14578:
14555:
14493:
14472:
14449:
14428:
14399:
14387:{\displaystyle g(x)}
14369:
14331:
14302:
14267:
14255:{\displaystyle f(x)}
14237:
14196:
14163:
14107:
14095:{\displaystyle g(x)}
14077:
14039:
14010:
13987:
13966:
13954:{\displaystyle f(x)}
13936:
13892:
13871:
13848:
13827:
13815:{\displaystyle f(x)}
13797:
13756:
13731:
13667:
13655:{\displaystyle g(x)}
13637:
13599:
13572:
13549:
13528:
13507:
13463:
13442:
13421:
13400:
13379:
13338:
13313:
13281:
13249:
13199:
13178:
13140:
13113:
13090:
13069:
13048:
13004:
12983:
12962:
12941:
12920:
12879:
12854:
12828:
12792:
12768:
12718:
12697:
12659:
12630:
12609:
12586:
12565:
12521:
12500:
12479:
12458:
12437:
12396:
12358:
12337:
12309:
12285:
12243:
12216:
12195:
12157:
12134:
12111:
12090:
12067:
12046:
12023:
12002:
11958:
11937:
11916:
11895:
11874:
11833:
11801:
11780:
11750:
11708:
11681:
11660:
11622:
11599:
11576:
11555:
11534:
11513:
11490:
11469:
11425:
11404:
11383:
11362:
11341:
11300:
11262:
11241:
11211:
11169:
11142:
11121:
11083:
11062:
11041:
11020:
10999:
10978:
10955:
10934:
10890:
10869:
10848:
10827:
10806:
10765:
10742:
10719:
10691:
10670:
10640:
10598:
10571:
10550:
10512:
10491:
10470:
10449:
10428:
10407:
10386:
10365:
10344:
10300:
10275:
10254:
10233:
10192:
10171:
10148:
10125:
10101:
10080:
10050:
10008:
9981:
9960:
9922:
9901:
9880:
9859:
9838:
9817:
9794:
9773:
9729:
9706:
9685:
9664:
9623:
9602:
9566:
9545:
9518:
9494:
9452:
9425:
9404:
9366:
9345:
9324:
9303:
9280:
9259:
9236:
9215:
9171:
9148:
9127:
9106:
9065:
9044:
9014:
8993:
8963:
8922:
8895:
8874:
8836:
8815:
8794:
8773:
8752:
8731:
8708:
8687:
8643:
8618:
8597:
8576:
8535:
8503:
8482:
8452:
8421:
8350:
8312:
8280:
8260:
8166:
8100:
8077:
8057:
8037:
8017:
7997:
7950:
7903:
7856:
7809:
7762:
7715:
7668:
7621:
7461:
7312:
7244:
7216:
7178:
7134:
7096:
7052:
7032:
7006:
6962:
6927:
6883:
6848:
6821:
6801:
6745:
6719:
6690:
6664:
6655:negation normal form
6613:
6592:
6554:
6533:
6512:
6491:
6460:
6439:
6418:
6397:
6376:
6355:
6317:
6296:
6275:
6254:
6226:
6205:
6184:
6156:
6118:
6097:
6076:
6055:
6024:
6003:
5982:
5961:
5940:
5919:
5881:
5860:
5839:
5818:
5790:
5769:
5691:
5633:
5568:
5083:
5032:
5009:
4989:
4952:
4904:
4884:
4763:
4740:
4711:
4691:
4643:
4616:
4563:
4504:
4461:
4430:
4403:
4376:
4169:
4121:
4090:
4063:
4036:
3756:
3727:
3609:
3577:
3551:
3528:
3506:
3373:
3353:
3349:A CNF equivalent of
3008:
2975:
2954:
2930:
2909:
2888:
2867:
2834:
2813:
2792:
2769:
2748:
2727:
2629:
1922:
1774:
1684:
1468:
1240:
1216:
1180:
1099:
1072:
963:
935:
904:
871:
835:
806:
786:
760:logical equivalences
691:
648:
611:
575:
542:
497:
413:
390:
346:
304:
267:
226:
209:context-free grammar
180:
156:
132:
16520:Propositional logic
16466:Universität Marburg
16394:Tseitin, Grigori S.
16313:10.1007/11527695_15
14939:{\displaystyle ,x)}
14414:{\displaystyle ,x)}
14122:{\displaystyle ,x)}
13682:{\displaystyle ,x)}
13214:{\displaystyle ,x)}
12733:{\displaystyle ,x)}
12231:{\displaystyle ,x)}
11696:{\displaystyle ,x)}
11157:{\displaystyle ,x)}
10586:{\displaystyle ,x)}
9996:{\displaystyle ,x)}
9440:{\displaystyle ,x)}
8910:{\displaystyle ,x)}
8096:Repeatedly replace
7240:For sentences like
4942:non-empty subsets.
4759:possible literals:
3593:in the disjunction.
3570:in the disjunction,
2565:// remove all
590:{\displaystyle (A)}
207:The following is a
98:clausal normal form
55:clausal normal form
32:Chomsky normal form
16623:Modal clausal form
16600:Prenex normal form
16590:Skolem normal form
16148:
16106:
16053:
16033:
16005:
15920:
15817:
15787:
15764:
15718:
15695:
15602:
15395:
15366:
15346:
15317:
15295:
15275:
15246:
15226:
15188:{\displaystyle \}}
15185:
15167:{\displaystyle \}}
15164:
15143:
15084:
15063:
15004:{\displaystyle \{}
15001:
14980:
14962:{\displaystyle \}}
14959:
14936:
14909:
14879:
14835:
14800:
14779:
14749:
14699:{\displaystyle \{}
14696:
14678:{\displaystyle \{}
14675:
14643:
14622:
14563:
14562:
14540:
14478:
14457:
14456:
14434:
14411:
14384:
14354:
14310:
14309:
14273:
14252:
14222:
14169:
14119:
14092:
14062:
14018:
14017:
13993:
13972:
13951:
13921:
13877:
13856:
13855:
13833:
13812:
13782:
13737:
13679:
13652:
13622:
13578:
13555:
13534:
13513:
13492:
13448:
13427:
13406:
13385:
13364:
13319:
13296:
13294:
13258:
13211:
13184:
13163:
13119:
13096:
13075:
13054:
13033:
12989:
12968:
12947:
12926:
12905:
12860:
12837:
12807:
12805:
12777:
12730:
12703:
12682:
12638:
12637:
12615:
12592:
12571:
12550:
12506:
12485:
12464:
12443:
12422:
12373:
12371:
12343:
12318:
12294:
12249:
12228:
12201:
12180:
12142:
12141:
12119:
12118:
12096:
12075:
12074:
12052:
12029:
12008:
11987:
11943:
11922:
11901:
11880:
11859:
11810:
11786:
11759:
11714:
11693:
11666:
11645:
11607:
11606:
11584:
11583:
11561:
11540:
11519:
11496:
11475:
11454:
11410:
11389:
11368:
11347:
11326:
11277:
11275:
11247:
11220:
11175:
11154:
11127:
11106:
11068:
11047:
11026:
11005:
10984:
10961:
10940:
10919:
10875:
10854:
10833:
10812:
10791:
10750:
10749:
10727:
10726:
10700:
10676:
10649:
10604:
10583:
10556:
10535:
10497:
10476:
10455:
10434:
10413:
10392:
10371:
10350:
10329:
10283:
10282:
10260:
10239:
10218:
10177:
10154:
10133:
10132:
10110:
10086:
10059:
10014:
9993:
9966:
9945:
9907:
9886:
9865:
9844:
9823:
9800:
9779:
9758:
9712:
9691:
9670:
9649:
9608:
9581:
9579:
9551:
9526:
9525:
9503:
9458:
9437:
9410:
9389:
9351:
9330:
9309:
9288:
9287:
9265:
9242:
9221:
9200:
9154:
9133:
9112:
9091:
9050:
9023:
8999:
8972:
8928:
8907:
8880:
8859:
8821:
8800:
8779:
8758:
8737:
8714:
8693:
8672:
8626:
8625:
8603:
8582:
8561:
8512:
8488:
8461:
8433:
8431:
8386:
8336:
8286:
8266:
8246:
8152:
8083:
8063:
8043:
8023:
8003:
7983:
7936:
7889:
7842:
7795:
7748:
7701:
7654:
7596:
7447:
7298:
7222:
7202:
7164:
7120:
7082:
7038:
7018:
6992:
6948:
6913:
6869:
6827:
6807:
6787:
6731:
6705:
6676:
6622:{\displaystyle \}}
6619:
6601:{\displaystyle \}}
6598:
6577:
6539:
6518:
6497:
6476:
6448:{\displaystyle \{}
6445:
6424:
6403:
6382:
6364:{\displaystyle \}}
6361:
6340:
6302:
6281:
6260:
6239:
6214:{\displaystyle \{}
6211:
6193:{\displaystyle \{}
6190:
6162:
6141:
6103:
6082:
6061:
6040:
6009:
5988:
5967:
5946:
5925:
5904:
5866:
5845:
5824:
5803:
5775:
5732:
5677:
5619:
5517:-SAT problem with
5481:This formula is a
5469:
5467:
5284:
5257:
5227:
5197:
5069:
5015:
4995:
4965:
4932:
4890:
4868:
4752:{\displaystyle 2n}
4749:
4723:
4697:
4669:
4629:
4602:
4549:
4474:
4443:
4416:
4389:
4356:
4153:
4096:
4076:
4049:
4020:
3740:
3711:
3583:
3560:
3534:
3512:
3490:
3359:
3014:
2993:
2960:
2939:
2915:
2894:
2873:
2852:
2819:
2798:
2775:
2754:
2733:
2714:The corresponding
2701:
2604:
2602:
2252:
2210:
2168:
2129:
1907:
1756:
1657:
1655:
1454:
1452:
1222:
1202:
1160:
1085:
1055:
941:
913:
890:
857:
815:
792:
727:
675:
632:
587:
560:
527:
482:
396:
376:
310:
273:
232:
186:
162:
138:
85:, it is useful in
16636:
16635:
16425:978-0-486-15816-7
16378:978-0-13-604259-4
16347:978-0-521-63017-7
16322:978-3-540-31580-3
16284:978-1-134-78550-6
15369:{\displaystyle x}
15320:{\displaystyle x}
15298:{\displaystyle x}
15249:{\displaystyle x}
15205:
15204:
15087:{\displaystyle ,}
14983:{\displaystyle ,}
14838:{\displaystyle ,}
14803:{\displaystyle )}
14646:{\displaystyle )}
14481:{\displaystyle (}
14437:{\displaystyle )}
14276:{\displaystyle )}
14172:{\displaystyle (}
13996:{\displaystyle )}
13975:{\displaystyle )}
13836:{\displaystyle )}
13740:{\displaystyle (}
13558:{\displaystyle )}
13537:{\displaystyle )}
13516:{\displaystyle y}
13409:{\displaystyle )}
13388:{\displaystyle y}
13322:{\displaystyle (}
13187:{\displaystyle z}
13099:{\displaystyle )}
13078:{\displaystyle )}
13057:{\displaystyle y}
12950:{\displaystyle )}
12929:{\displaystyle y}
12863:{\displaystyle (}
12706:{\displaystyle z}
12618:{\displaystyle )}
12595:{\displaystyle )}
12574:{\displaystyle y}
12467:{\displaystyle )}
12446:{\displaystyle y}
12346:{\displaystyle (}
12252:{\displaystyle )}
12204:{\displaystyle z}
12099:{\displaystyle (}
12055:{\displaystyle )}
12032:{\displaystyle )}
12011:{\displaystyle y}
11904:{\displaystyle )}
11883:{\displaystyle y}
11789:{\displaystyle (}
11717:{\displaystyle )}
11669:{\displaystyle y}
11564:{\displaystyle (}
11522:{\displaystyle )}
11499:{\displaystyle )}
11478:{\displaystyle y}
11371:{\displaystyle )}
11350:{\displaystyle y}
11250:{\displaystyle (}
11178:{\displaystyle )}
11130:{\displaystyle y}
11071:{\displaystyle y}
11029:{\displaystyle (}
10987:{\displaystyle )}
10964:{\displaystyle )}
10943:{\displaystyle y}
10836:{\displaystyle )}
10815:{\displaystyle y}
10679:{\displaystyle (}
10607:{\displaystyle )}
10559:{\displaystyle y}
10500:{\displaystyle y}
10458:{\displaystyle (}
10416:{\displaystyle )}
10395:{\displaystyle )}
10374:{\displaystyle )}
10353:{\displaystyle y}
10263:{\displaystyle )}
10242:{\displaystyle y}
10157:{\displaystyle (}
10089:{\displaystyle (}
10017:{\displaystyle )}
9969:{\displaystyle y}
9910:{\displaystyle y}
9868:{\displaystyle (}
9826:{\displaystyle )}
9803:{\displaystyle )}
9782:{\displaystyle y}
9694:{\displaystyle )}
9673:{\displaystyle y}
9554:{\displaystyle (}
9461:{\displaystyle )}
9413:{\displaystyle y}
9354:{\displaystyle y}
9312:{\displaystyle (}
9268:{\displaystyle )}
9245:{\displaystyle )}
9224:{\displaystyle y}
9136:{\displaystyle )}
9115:{\displaystyle y}
9002:{\displaystyle (}
8931:{\displaystyle )}
8883:{\displaystyle y}
8824:{\displaystyle y}
8782:{\displaystyle (}
8740:{\displaystyle )}
8717:{\displaystyle )}
8696:{\displaystyle y}
8606:{\displaystyle )}
8585:{\displaystyle y}
8491:{\displaystyle (}
8429:
8289:{\displaystyle n}
8269:{\displaystyle f}
8026:{\displaystyle P}
8013:doesn't occur in
8006:{\displaystyle x}
7041:{\displaystyle P}
6647:first-order logic
6635:
6634:
6542:{\displaystyle ,}
6500:{\displaystyle ,}
6427:{\displaystyle ,}
6385:{\displaystyle ,}
6305:{\displaystyle ,}
6263:{\displaystyle ,}
6165:{\displaystyle )}
6012:{\displaystyle (}
5928:{\displaystyle )}
5778:{\displaystyle (}
5750:First-order logic
5629:by two conjuncts
5263:
5233:
5203:
5170:
5018:{\displaystyle q}
4998:{\displaystyle p}
4893:{\displaystyle L}
4700:{\displaystyle n}
4639:to be a name for
4099:{\displaystyle i}
3586:{\displaystyle V}
3537:{\displaystyle V}
3347:
3346:
3017:{\displaystyle )}
2918:{\displaystyle (}
2876:{\displaystyle )}
2801:{\displaystyle (}
2778:{\displaystyle r}
2757:{\displaystyle q}
2736:{\displaystyle p}
2566:
2422:
2260:
2216:
2174:
2135:
2099:
1651:
1448:
742:Conversion to CNF
399:{\displaystyle F}
339:is any variable.
16:(Redirected from
16661:
16618:Beta normal form
16575:
16504:
16497:
16490:
16481:
16480:
16476:
16474:
16472:
16455:
16429:
16408:
16402:
16389:
16387:
16370:
16362:, eds. (2010) .
16351:
16326:
16298:
16288:
16264:
16240:
16234:
16228:
16222:
16216:
16210:
16204:
16198:
16187:
16181:
16161:
16157:
16155:
16154:
16149:
16144:
16143:
16115:
16113:
16112:
16107:
16086:
16080:
16070:
16064:
16062:
16060:
16059:
16054:
16042:
16040:
16039:
16034:
16014:
16012:
16011:
16006:
15939:
15930:
15929:
15927:
15926:
15921:
15919:
15918:
15903:
15899:
15889:
15888:
15870:
15864:
15826:
15824:
15823:
15818:
15806:
15797:
15796:
15794:
15793:
15788:
15773:
15771:
15770:
15765:
15760:
15759:
15734:
15728:
15727:
15725:
15724:
15719:
15704:
15702:
15701:
15696:
15675:
15611:
15609:
15608:
15603:
15574:
15530:
15477:
15439:
15404:
15402:
15401:
15396:
15375:
15373:
15372:
15367:
15355:
15353:
15352:
15347:
15326:
15324:
15323:
15318:
15304:
15302:
15301:
15296:
15284:
15282:
15281:
15276:
15256:is loved, while
15255:
15253:
15252:
15247:
15235:
15233:
15232:
15227:
15201:representation)
15194:
15192:
15191:
15186:
15173:
15171:
15170:
15165:
15152:
15150:
15149:
15144:
15118:
15093:
15091:
15090:
15085:
15072:
15070:
15069:
15064:
15038:
15010:
15008:
15007:
15002:
14989:
14987:
14986:
14981:
14968:
14966:
14965:
14960:
14945:
14943:
14942:
14937:
14918:
14916:
14915:
14910:
14888:
14886:
14885:
14880:
14875:
14844:
14842:
14841:
14836:
14809:
14807:
14806:
14801:
14788:
14786:
14785:
14780:
14758:
14756:
14755:
14750:
14745:
14705:
14703:
14702:
14697:
14684:
14682:
14681:
14676:
14652:
14650:
14649:
14644:
14631:
14629:
14628:
14623:
14597:
14572:
14570:
14569:
14564:
14549:
14547:
14546:
14541:
14515:
14487:
14485:
14484:
14479:
14466:
14464:
14463:
14458:
14443:
14441:
14440:
14435:
14420:
14418:
14417:
14412:
14393:
14391:
14390:
14385:
14363:
14361:
14360:
14355:
14350:
14319:
14317:
14316:
14311:
14282:
14280:
14279:
14274:
14261:
14259:
14258:
14253:
14231:
14229:
14228:
14223:
14218:
14178:
14176:
14175:
14170:
14128:
14126:
14125:
14120:
14101:
14099:
14098:
14093:
14071:
14069:
14068:
14063:
14058:
14027:
14025:
14024:
14019:
14002:
14000:
13999:
13994:
13981:
13979:
13978:
13973:
13960:
13958:
13957:
13952:
13930:
13928:
13927:
13922:
13911:
13886:
13884:
13883:
13878:
13865:
13863:
13862:
13857:
13842:
13840:
13839:
13834:
13821:
13819:
13818:
13813:
13791:
13789:
13788:
13783:
13778:
13746:
13744:
13743:
13738:
13688:
13686:
13685:
13680:
13661:
13659:
13658:
13653:
13631:
13629:
13628:
13623:
13618:
13587:
13585:
13584:
13579:
13564:
13562:
13561:
13556:
13543:
13541:
13540:
13535:
13522:
13520:
13519:
13514:
13501:
13499:
13498:
13493:
13482:
13457:
13455:
13454:
13449:
13436:
13434:
13433:
13428:
13415:
13413:
13412:
13407:
13394:
13392:
13391:
13386:
13373:
13371:
13370:
13365:
13360:
13328:
13326:
13325:
13320:
13305:
13303:
13302:
13297:
13295:
13293:
13267:
13265:
13264:
13259:
13220:
13218:
13217:
13212:
13193:
13191:
13190:
13185:
13172:
13170:
13169:
13164:
13159:
13128:
13126:
13125:
13120:
13105:
13103:
13102:
13097:
13084:
13082:
13081:
13076:
13063:
13061:
13060:
13055:
13042:
13040:
13039:
13034:
13023:
12998:
12996:
12995:
12990:
12977:
12975:
12974:
12969:
12956:
12954:
12953:
12948:
12935:
12933:
12932:
12927:
12914:
12912:
12911:
12906:
12901:
12869:
12867:
12866:
12861:
12846:
12844:
12843:
12838:
12816:
12814:
12813:
12808:
12806:
12804:
12786:
12784:
12783:
12778:
12739:
12737:
12736:
12731:
12712:
12710:
12709:
12704:
12691:
12689:
12688:
12683:
12678:
12647:
12645:
12644:
12639:
12624:
12622:
12621:
12616:
12601:
12599:
12598:
12593:
12580:
12578:
12577:
12572:
12559:
12557:
12556:
12551:
12540:
12515:
12513:
12512:
12507:
12494:
12492:
12491:
12486:
12473:
12471:
12470:
12465:
12452:
12450:
12449:
12444:
12431:
12429:
12428:
12423:
12418:
12382:
12380:
12379:
12374:
12372:
12370:
12352:
12350:
12349:
12344:
12327:
12325:
12324:
12319:
12303:
12301:
12300:
12295:
12258:
12256:
12255:
12250:
12237:
12235:
12234:
12229:
12210:
12208:
12207:
12202:
12189:
12187:
12186:
12181:
12176:
12151:
12149:
12148:
12143:
12128:
12126:
12125:
12120:
12105:
12103:
12102:
12097:
12084:
12082:
12081:
12076:
12061:
12059:
12058:
12053:
12038:
12036:
12035:
12030:
12017:
12015:
12014:
12009:
11996:
11994:
11993:
11988:
11977:
11952:
11950:
11949:
11944:
11931:
11929:
11928:
11923:
11910:
11908:
11907:
11902:
11889:
11887:
11886:
11881:
11868:
11866:
11865:
11860:
11855:
11819:
11817:
11816:
11811:
11795:
11793:
11792:
11787:
11768:
11766:
11765:
11760:
11723:
11721:
11720:
11715:
11702:
11700:
11699:
11694:
11675:
11673:
11672:
11667:
11654:
11652:
11651:
11646:
11641:
11616:
11614:
11613:
11608:
11593:
11591:
11590:
11585:
11570:
11568:
11567:
11562:
11549:
11547:
11546:
11541:
11528:
11526:
11525:
11520:
11505:
11503:
11502:
11497:
11484:
11482:
11481:
11476:
11463:
11461:
11460:
11455:
11444:
11419:
11417:
11416:
11411:
11398:
11396:
11395:
11390:
11377:
11375:
11374:
11369:
11356:
11354:
11353:
11348:
11335:
11333:
11332:
11327:
11322:
11286:
11284:
11283:
11278:
11276:
11274:
11256:
11254:
11253:
11248:
11229:
11227:
11226:
11221:
11184:
11182:
11181:
11176:
11163:
11161:
11160:
11155:
11136:
11134:
11133:
11128:
11115:
11113:
11112:
11107:
11102:
11077:
11075:
11074:
11069:
11056:
11054:
11053:
11048:
11035:
11033:
11032:
11027:
11014:
11012:
11011:
11006:
10993:
10991:
10990:
10985:
10970:
10968:
10967:
10962:
10949:
10947:
10946:
10941:
10928:
10926:
10925:
10920:
10909:
10884:
10882:
10881:
10876:
10863:
10861:
10860:
10855:
10842:
10840:
10839:
10834:
10821:
10819:
10818:
10813:
10800:
10798:
10797:
10792:
10787:
10759:
10757:
10756:
10751:
10736:
10734:
10733:
10728:
10709:
10707:
10706:
10701:
10685:
10683:
10682:
10677:
10658:
10656:
10655:
10650:
10613:
10611:
10610:
10605:
10592:
10590:
10589:
10584:
10565:
10563:
10562:
10557:
10544:
10542:
10541:
10536:
10531:
10506:
10504:
10503:
10498:
10485:
10483:
10482:
10477:
10464:
10462:
10461:
10456:
10443:
10441:
10440:
10435:
10422:
10420:
10419:
10414:
10401:
10399:
10398:
10393:
10380:
10378:
10377:
10372:
10359:
10357:
10356:
10351:
10338:
10336:
10335:
10330:
10319:
10292:
10290:
10289:
10284:
10269:
10267:
10266:
10261:
10248:
10246:
10245:
10240:
10227:
10225:
10224:
10219:
10214:
10186:
10184:
10183:
10178:
10163:
10161:
10160:
10155:
10142:
10140:
10139:
10134:
10119:
10117:
10116:
10111:
10095:
10093:
10092:
10087:
10068:
10066:
10065:
10060:
10023:
10021:
10020:
10015:
10002:
10000:
9999:
9994:
9975:
9973:
9972:
9967:
9954:
9952:
9951:
9946:
9941:
9916:
9914:
9913:
9908:
9895:
9893:
9892:
9887:
9874:
9872:
9871:
9866:
9853:
9851:
9850:
9845:
9832:
9830:
9829:
9824:
9809:
9807:
9806:
9801:
9788:
9786:
9785:
9780:
9767:
9765:
9764:
9759:
9748:
9721:
9719:
9718:
9713:
9700:
9698:
9697:
9692:
9679:
9677:
9676:
9671:
9658:
9656:
9655:
9650:
9645:
9617:
9615:
9614:
9609:
9590:
9588:
9587:
9582:
9580:
9578:
9560:
9558:
9557:
9552:
9535:
9533:
9532:
9527:
9512:
9510:
9509:
9504:
9467:
9465:
9464:
9459:
9446:
9444:
9443:
9438:
9419:
9417:
9416:
9411:
9398:
9396:
9395:
9390:
9385:
9360:
9358:
9357:
9352:
9339:
9337:
9336:
9331:
9318:
9316:
9315:
9310:
9297:
9295:
9294:
9289:
9274:
9272:
9271:
9266:
9251:
9249:
9248:
9243:
9230:
9228:
9227:
9222:
9209:
9207:
9206:
9201:
9190:
9163:
9161:
9160:
9155:
9142:
9140:
9139:
9134:
9121:
9119:
9118:
9113:
9100:
9098:
9097:
9092:
9087:
9059:
9057:
9056:
9051:
9032:
9030:
9029:
9024:
9008:
9006:
9005:
9000:
8981:
8979:
8978:
8973:
8937:
8935:
8934:
8929:
8916:
8914:
8913:
8908:
8889:
8887:
8886:
8881:
8868:
8866:
8865:
8860:
8855:
8830:
8828:
8827:
8822:
8809:
8807:
8806:
8801:
8788:
8786:
8785:
8780:
8767:
8765:
8764:
8759:
8746:
8744:
8743:
8738:
8723:
8721:
8720:
8715:
8702:
8700:
8699:
8694:
8681:
8679:
8678:
8673:
8662:
8635:
8633:
8632:
8627:
8612:
8610:
8609:
8604:
8591:
8589:
8588:
8583:
8570:
8568:
8567:
8562:
8557:
8521:
8519:
8518:
8513:
8497:
8495:
8494:
8489:
8470:
8468:
8467:
8462:
8446:
8445:
8442:
8440:
8439:
8434:
8432:
8430:
8427:
8395:
8393:
8392:
8387:
8345:
8343:
8342:
8337:
8295:
8293:
8292:
8287:
8275:
8273:
8272:
8267:
8255:
8253:
8252:
8247:
8239:
8238:
8220:
8219:
8197:
8196:
8181:
8180:
8161:
8159:
8158:
8153:
8131:
8130:
8115:
8114:
8092:
8090:
8089:
8084:
8072:
8070:
8069:
8064:
8052:
8050:
8049:
8044:
8032:
8030:
8029:
8024:
8012:
8010:
8009:
8004:
7992:
7990:
7989:
7984:
7945:
7943:
7942:
7937:
7898:
7896:
7895:
7890:
7851:
7849:
7848:
7843:
7804:
7802:
7801:
7796:
7757:
7755:
7754:
7749:
7710:
7708:
7707:
7702:
7663:
7661:
7660:
7655:
7605:
7603:
7602:
7597:
7577:
7530:
7498:
7456:
7454:
7453:
7448:
7428:
7381:
7349:
7307:
7305:
7304:
7299:
7231:
7229:
7228:
7223:
7212:. After that, a
7211:
7209:
7208:
7203:
7173:
7171:
7170:
7165:
7129:
7127:
7126:
7121:
7091:
7089:
7088:
7083:
7047:
7045:
7044:
7039:
7027:
7025:
7024:
7019:
7001:
6999:
6998:
6993:
6957:
6955:
6954:
6949:
6922:
6920:
6919:
6914:
6878:
6876:
6875:
6870:
6836:
6834:
6833:
6828:
6816:
6814:
6813:
6808:
6796:
6794:
6793:
6788:
6740:
6738:
6737:
6732:
6714:
6712:
6711:
6706:
6685:
6683:
6682:
6677:
6628:
6626:
6625:
6620:
6607:
6605:
6604:
6599:
6586:
6584:
6583:
6578:
6576:
6575:
6574:
6573:
6548:
6546:
6545:
6540:
6527:
6525:
6524:
6519:
6506:
6504:
6503:
6498:
6485:
6483:
6482:
6477:
6475:
6474:
6454:
6452:
6451:
6446:
6433:
6431:
6430:
6425:
6412:
6410:
6409:
6404:
6391:
6389:
6388:
6383:
6370:
6368:
6367:
6362:
6349:
6347:
6346:
6341:
6339:
6338:
6337:
6336:
6311:
6309:
6308:
6303:
6290:
6288:
6287:
6282:
6269:
6267:
6266:
6261:
6248:
6246:
6245:
6240:
6238:
6237:
6220:
6218:
6217:
6212:
6199:
6197:
6196:
6191:
6171:
6169:
6168:
6163:
6150:
6148:
6147:
6142:
6140:
6139:
6138:
6137:
6112:
6110:
6109:
6104:
6091:
6089:
6088:
6083:
6070:
6068:
6067:
6062:
6049:
6047:
6046:
6041:
6039:
6038:
6018:
6016:
6015:
6010:
5997:
5995:
5994:
5989:
5976:
5974:
5973:
5968:
5955:
5953:
5952:
5947:
5934:
5932:
5931:
5926:
5913:
5911:
5910:
5905:
5903:
5902:
5901:
5900:
5875:
5873:
5872:
5867:
5854:
5852:
5851:
5846:
5833:
5831:
5830:
5825:
5812:
5810:
5809:
5804:
5802:
5801:
5784:
5782:
5781:
5776:
5761:
5760:
5745:
5741:
5739:
5738:
5733:
5731:
5730:
5712:
5711:
5686:
5684:
5683:
5678:
5670:
5669:
5645:
5644:
5628:
5626:
5625:
5620:
5618:
5617:
5599:
5598:
5580:
5579:
5513:(like any other
5478:
5476:
5475:
5470:
5468:
5285:
5280:
5258:
5253:
5228:
5223:
5198:
5193:
5078:
5076:
5075:
5070:
5056:
5055:
5024:
5022:
5021:
5016:
5004:
5002:
5001:
4996:
4974:
4972:
4971:
4966:
4964:
4963:
4941:
4939:
4938:
4933:
4922:
4921:
4899:
4897:
4896:
4891:
4877:
4875:
4874:
4869:
4864:
4863:
4848:
4847:
4829:
4828:
4813:
4812:
4800:
4799:
4784:
4783:
4758:
4756:
4755:
4750:
4732:
4730:
4729:
4724:
4706:
4704:
4703:
4698:
4678:
4676:
4675:
4670:
4668:
4667:
4655:
4654:
4638:
4636:
4635:
4630:
4628:
4627:
4611:
4609:
4608:
4603:
4601:
4600:
4588:
4587:
4575:
4574:
4558:
4556:
4555:
4550:
4548:
4547:
4532:
4531:
4516:
4515:
4483:
4481:
4480:
4475:
4473:
4472:
4452:
4450:
4449:
4444:
4442:
4441:
4425:
4423:
4422:
4417:
4415:
4414:
4398:
4396:
4395:
4390:
4388:
4387:
4365:
4363:
4362:
4357:
4349:
4348:
4336:
4335:
4314:
4313:
4301:
4300:
4273:
4272:
4260:
4259:
4238:
4237:
4225:
4224:
4203:
4202:
4184:
4183:
4162:
4160:
4159:
4154:
4152:
4151:
4133:
4132:
4105:
4103:
4102:
4097:
4085:
4083:
4082:
4077:
4075:
4074:
4058:
4056:
4055:
4050:
4048:
4047:
4029:
4027:
4026:
4021:
4013:
4012:
3994:
3993:
3981:
3980:
3956:
3955:
3937:
3936:
3924:
3923:
3905:
3904:
3886:
3885:
3873:
3872:
3854:
3853:
3835:
3834:
3822:
3821:
3803:
3802:
3784:
3783:
3771:
3770:
3749:
3747:
3746:
3741:
3739:
3738:
3720:
3718:
3717:
3712:
3707:
3706:
3694:
3693:
3669:
3668:
3656:
3655:
3637:
3636:
3624:
3623:
3603:non-CNF formula
3598:Other approaches
3592:
3590:
3589:
3584:
3569:
3567:
3566:
3561:
3543:
3541:
3540:
3535:
3521:
3519:
3518:
3513:
3499:
3497:
3496:
3491:
3368:
3366:
3365:
3360:
3023:
3021:
3020:
3015:
3002:
3000:
2999:
2994:
2969:
2967:
2966:
2961:
2948:
2946:
2945:
2940:
2924:
2922:
2921:
2916:
2903:
2901:
2900:
2895:
2882:
2880:
2879:
2874:
2861:
2859:
2858:
2853:
2828:
2826:
2825:
2820:
2807:
2805:
2804:
2799:
2784:
2782:
2781:
2776:
2763:
2761:
2760:
2755:
2742:
2740:
2739:
2734:
2721:
2720:
2710:
2708:
2707:
2702:
2613:
2611:
2610:
2605:
2603:
2599:
2598:
2577:
2567:
2564:
2561:
2439:
2423:
2420:
2417:
2265:
2261:
2258:
2255:
2253:
2248:
2211:
2206:
2169:
2164:
2130:
2125:
2091:
1964:
1960:
1959:
1916:
1914:
1913:
1908:
1795:
1794:
1765:
1763:
1762:
1757:
1666:
1664:
1663:
1658:
1656:
1652:
1649:
1646:
1641:
1640:
1639:
1638:
1609:
1608:
1590:
1589:
1565:
1558:
1557:
1556:
1555:
1529:
1528:
1513:
1512:
1487:
1486:
1463:
1461:
1460:
1455:
1453:
1449:
1446:
1443:
1441:
1440:
1419:
1418:
1397:
1396:
1381:
1380:
1362:
1355:
1354:
1336:
1335:
1317:
1316:
1304:
1303:
1282:
1278:
1277:
1231:
1229:
1228:
1223:
1211:
1209:
1208:
1203:
1201:
1200:
1169:
1167:
1166:
1161:
1159:
1158:
1157:
1156:
1130:
1129:
1114:
1113:
1094:
1092:
1091:
1086:
1084:
1083:
1064:
1062:
1061:
1056:
1051:
1050:
1032:
1031:
1013:
1012:
1000:
999:
984:
983:
950:
948:
947:
942:
922:
920:
919:
914:
899:
897:
896:
891:
889:
888:
867:is converted to
866:
864:
863:
858:
856:
855:
824:
822:
821:
816:
801:
799:
798:
793:
772:distributive law
768:De Morgan's laws
736:
734:
733:
728:
684:
682:
681:
676:
641:
639:
638:
633:
596:
594:
593:
588:
569:
567:
566:
561:
536:
534:
533:
528:
491:
489:
488:
483:
405:
403:
402:
397:
385:
383:
382:
377:
319:
317:
316:
311:
282:
280:
279:
274:
241:
239:
238:
233:
195:
193:
192:
187:
171:
169:
168:
163:
147:
145:
144:
139:
21:
16669:
16668:
16664:
16663:
16662:
16660:
16659:
16658:
16639:
16638:
16637:
16632:
16604:
16595:Herbrandization
16582:Predicate logic
16576:
16567:
16514:
16508:
16470:
16468:
16460:
16440:
16437:
16432:
16426:
16400:
16385:
16379:
16368:
16348:
16323:
16296:
16285:
16261:
16244:
16243:
16235:
16231:
16223:
16219:
16211:
16207:
16199:
16190:
16182:
16175:
16170:
16165:
16164:
16139:
16135:
16124:
16121:
16120:
16119:
16092:
16089:
16088:
16087:
16083:
16071:
16067:
16048:
16045:
16044:
16028:
16025:
16024:
16015:) based on the
15946:
15943:
15942:
15940:
15933:
15911:
15907:
15884:
15883:
15882:
15878:
15876:
15873:
15872:
15871:
15867:
15812:
15809:
15808:
15807:
15800:
15782:
15779:
15778:
15755:
15751:
15740:
15737:
15736:
15735:
15731:
15713:
15710:
15709:
15681:
15678:
15677:
15676:
15672:
15667:
15618:
15558:
15514:
15461:
15420:
15415:
15412:
15411:
15381:
15378:
15377:
15361:
15358:
15357:
15332:
15329:
15328:
15312:
15309:
15308:
15290:
15287:
15286:
15261:
15258:
15257:
15241:
15238:
15237:
15212:
15209:
15208:
15180:
15177:
15176:
15159:
15156:
15155:
15102:
15100:
15097:
15096:
15079:
15076:
15075:
15022:
15017:
15014:
15013:
14996:
14993:
14992:
14975:
14972:
14971:
14954:
14951:
14950:
14925:
14922:
14921:
14895:
14892:
14891:
14859:
14857:
14854:
14853:
14830:
14827:
14826:
14795:
14792:
14791:
14765:
14762:
14761:
14726:
14724:
14721:
14720:
14691:
14688:
14687:
14670:
14667:
14666:
14638:
14635:
14634:
14581:
14579:
14576:
14575:
14556:
14553:
14552:
14499:
14494:
14491:
14490:
14473:
14470:
14469:
14450:
14447:
14446:
14429:
14426:
14425:
14400:
14397:
14396:
14370:
14367:
14366:
14334:
14332:
14329:
14328:
14303:
14300:
14299:
14268:
14265:
14264:
14238:
14235:
14234:
14199:
14197:
14194:
14193:
14164:
14161:
14160:
14108:
14105:
14104:
14078:
14075:
14074:
14042:
14040:
14037:
14036:
14011:
14008:
14007:
13988:
13985:
13984:
13967:
13964:
13963:
13937:
13934:
13933:
13895:
13893:
13890:
13889:
13872:
13869:
13868:
13849:
13846:
13845:
13828:
13825:
13824:
13798:
13795:
13794:
13759:
13757:
13754:
13753:
13732:
13729:
13728:
13668:
13665:
13664:
13638:
13635:
13634:
13602:
13600:
13597:
13596:
13573:
13570:
13569:
13550:
13547:
13546:
13529:
13526:
13525:
13508:
13505:
13504:
13466:
13464:
13461:
13460:
13443:
13440:
13439:
13422:
13419:
13418:
13401:
13398:
13397:
13380:
13377:
13376:
13341:
13339:
13336:
13335:
13314:
13311:
13310:
13286:
13284:
13282:
13279:
13278:
13250:
13247:
13246:
13200:
13197:
13196:
13179:
13176:
13175:
13143:
13141:
13138:
13137:
13114:
13111:
13110:
13091:
13088:
13087:
13070:
13067:
13066:
13049:
13046:
13045:
13007:
13005:
13002:
13001:
12984:
12981:
12980:
12963:
12960:
12959:
12942:
12939:
12938:
12921:
12918:
12917:
12882:
12880:
12877:
12876:
12855:
12852:
12851:
12829:
12826:
12825:
12797:
12795:
12793:
12790:
12789:
12769:
12766:
12765:
12719:
12716:
12715:
12698:
12695:
12694:
12662:
12660:
12657:
12656:
12631:
12628:
12627:
12610:
12607:
12606:
12587:
12584:
12583:
12566:
12563:
12562:
12524:
12522:
12519:
12518:
12501:
12498:
12497:
12480:
12477:
12476:
12459:
12456:
12455:
12438:
12435:
12434:
12399:
12397:
12394:
12393:
12363:
12361:
12359:
12356:
12355:
12338:
12335:
12334:
12310:
12307:
12306:
12286:
12283:
12282:
12244:
12241:
12240:
12217:
12214:
12213:
12196:
12193:
12192:
12160:
12158:
12155:
12154:
12135:
12132:
12131:
12112:
12109:
12108:
12091:
12088:
12087:
12068:
12065:
12064:
12047:
12044:
12043:
12024:
12021:
12020:
12003:
12000:
11999:
11961:
11959:
11956:
11955:
11938:
11935:
11934:
11917:
11914:
11913:
11896:
11893:
11892:
11875:
11872:
11871:
11836:
11834:
11831:
11830:
11802:
11799:
11798:
11781:
11778:
11777:
11751:
11748:
11747:
11709:
11706:
11705:
11682:
11679:
11678:
11661:
11658:
11657:
11625:
11623:
11620:
11619:
11600:
11597:
11596:
11577:
11574:
11573:
11556:
11553:
11552:
11535:
11532:
11531:
11514:
11511:
11510:
11491:
11488:
11487:
11470:
11467:
11466:
11428:
11426:
11423:
11422:
11405:
11402:
11401:
11384:
11381:
11380:
11363:
11360:
11359:
11342:
11339:
11338:
11303:
11301:
11298:
11297:
11267:
11265:
11263:
11260:
11259:
11242:
11239:
11238:
11212:
11209:
11208:
11170:
11167:
11166:
11143:
11140:
11139:
11122:
11119:
11118:
11086:
11084:
11081:
11080:
11063:
11060:
11059:
11042:
11039:
11038:
11021:
11018:
11017:
11000:
10997:
10996:
10979:
10976:
10975:
10956:
10953:
10952:
10935:
10932:
10931:
10893:
10891:
10888:
10887:
10870:
10867:
10866:
10849:
10846:
10845:
10828:
10825:
10824:
10807:
10804:
10803:
10768:
10766:
10763:
10762:
10743:
10740:
10739:
10720:
10717:
10716:
10692:
10689:
10688:
10671:
10668:
10667:
10641:
10638:
10637:
10599:
10596:
10595:
10572:
10569:
10568:
10551:
10548:
10547:
10515:
10513:
10510:
10509:
10492:
10489:
10488:
10471:
10468:
10467:
10450:
10447:
10446:
10429:
10426:
10425:
10408:
10405:
10404:
10387:
10384:
10383:
10366:
10363:
10362:
10345:
10342:
10341:
10303:
10301:
10298:
10297:
10276:
10273:
10272:
10255:
10252:
10251:
10234:
10231:
10230:
10195:
10193:
10190:
10189:
10172:
10169:
10168:
10149:
10146:
10145:
10126:
10123:
10122:
10102:
10099:
10098:
10081:
10078:
10077:
10051:
10048:
10047:
10009:
10006:
10005:
9982:
9979:
9978:
9961:
9958:
9957:
9925:
9923:
9920:
9919:
9902:
9899:
9898:
9881:
9878:
9877:
9860:
9857:
9856:
9839:
9836:
9835:
9818:
9815:
9814:
9795:
9792:
9791:
9774:
9771:
9770:
9732:
9730:
9727:
9726:
9707:
9704:
9703:
9686:
9683:
9682:
9665:
9662:
9661:
9626:
9624:
9621:
9620:
9603:
9600:
9599:
9571:
9569:
9567:
9564:
9563:
9546:
9543:
9542:
9519:
9516:
9515:
9495:
9492:
9491:
9453:
9450:
9449:
9426:
9423:
9422:
9405:
9402:
9401:
9369:
9367:
9364:
9363:
9346:
9343:
9342:
9325:
9322:
9321:
9304:
9301:
9300:
9281:
9278:
9277:
9260:
9257:
9256:
9237:
9234:
9233:
9216:
9213:
9212:
9174:
9172:
9169:
9168:
9149:
9146:
9145:
9128:
9125:
9124:
9107:
9104:
9103:
9068:
9066:
9063:
9062:
9045:
9042:
9041:
9015:
9012:
9011:
8994:
8991:
8990:
8964:
8961:
8960:
8923:
8920:
8919:
8896:
8893:
8892:
8875:
8872:
8871:
8839:
8837:
8834:
8833:
8816:
8813:
8812:
8795:
8792:
8791:
8774:
8771:
8770:
8753:
8750:
8749:
8732:
8729:
8728:
8709:
8706:
8705:
8688:
8685:
8684:
8646:
8644:
8641:
8640:
8619:
8616:
8615:
8598:
8595:
8594:
8577:
8574:
8573:
8538:
8536:
8533:
8532:
8504:
8501:
8500:
8483:
8480:
8479:
8453:
8450:
8449:
8426:
8424:
8422:
8419:
8418:
8351:
8348:
8347:
8313:
8310:
8309:
8298:Skolem function
8281:
8278:
8277:
8261:
8258:
8257:
8234:
8230:
8215:
8211:
8192:
8188:
8176:
8172:
8167:
8164:
8163:
8126:
8122:
8110:
8106:
8101:
8098:
8097:
8078:
8075:
8074:
8058:
8055:
8054:
8038:
8035:
8034:
8018:
8015:
8014:
7998:
7995:
7994:
7951:
7948:
7947:
7904:
7901:
7900:
7857:
7854:
7853:
7810:
7807:
7806:
7763:
7760:
7759:
7716:
7713:
7712:
7669:
7666:
7665:
7622:
7619:
7618:
7561:
7514:
7479:
7462:
7459:
7458:
7412:
7365:
7330:
7313:
7310:
7309:
7245:
7242:
7241:
7217:
7214:
7213:
7179:
7176:
7175:
7135:
7132:
7131:
7097:
7094:
7093:
7053:
7050:
7049:
7033:
7030:
7029:
7007:
7004:
7003:
6963:
6960:
6959:
6928:
6925:
6924:
6884:
6881:
6880:
6849:
6846:
6845:
6842:De Morgan's law
6822:
6819:
6818:
6802:
6799:
6798:
6746:
6743:
6742:
6720:
6717:
6716:
6691:
6688:
6687:
6665:
6662:
6661:
6643:
6614:
6611:
6610:
6593:
6590:
6589:
6569:
6565:
6561:
6557:
6555:
6552:
6551:
6534:
6531:
6530:
6513:
6510:
6509:
6492:
6489:
6488:
6467:
6463:
6461:
6458:
6457:
6440:
6437:
6436:
6419:
6416:
6415:
6398:
6395:
6394:
6377:
6374:
6373:
6356:
6353:
6352:
6332:
6328:
6324:
6320:
6318:
6315:
6314:
6297:
6294:
6293:
6276:
6273:
6272:
6255:
6252:
6251:
6233:
6229:
6227:
6224:
6223:
6206:
6203:
6202:
6185:
6182:
6181:
6157:
6154:
6153:
6133:
6129:
6125:
6121:
6119:
6116:
6115:
6098:
6095:
6094:
6077:
6074:
6073:
6056:
6053:
6052:
6031:
6027:
6025:
6022:
6021:
6004:
6001:
6000:
5983:
5980:
5979:
5962:
5959:
5958:
5941:
5938:
5937:
5920:
5917:
5916:
5896:
5892:
5888:
5884:
5882:
5879:
5878:
5861:
5858:
5857:
5840:
5837:
5836:
5819:
5816:
5815:
5797:
5793:
5791:
5788:
5787:
5770:
5767:
5766:
5752:
5743:
5726:
5722:
5707:
5703:
5692:
5689:
5688:
5659:
5655:
5640:
5636:
5634:
5631:
5630:
5613:
5609:
5594:
5590:
5575:
5571:
5569:
5566:
5565:
5527:polynomial time
5491:
5466:
5465:
5429:
5428:
5311:
5310:
5264:
5262:
5234:
5232:
5204:
5202:
5171:
5169:
5145:
5144:
5086:
5084:
5081:
5080:
5039:
5035:
5033:
5030:
5029:
5010:
5007:
5006:
4990:
4987:
4986:
4976:
4959:
4955:
4953:
4950:
4949:
4914:
4910:
4905:
4902:
4901:
4885:
4882:
4881:
4859:
4855:
4843:
4839:
4824:
4820:
4808:
4804:
4795:
4791:
4779:
4775:
4764:
4761:
4760:
4741:
4738:
4737:
4712:
4709:
4708:
4692:
4689:
4688:
4685:
4663:
4659:
4650:
4646:
4644:
4641:
4640:
4623:
4619:
4617:
4614:
4613:
4596:
4592:
4583:
4579:
4570:
4566:
4564:
4561:
4560:
4543:
4539:
4527:
4523:
4511:
4507:
4505:
4502:
4501:
4487:equisatisfiable
4468:
4464:
4462:
4459:
4458:
4437:
4433:
4431:
4428:
4427:
4410:
4406:
4404:
4401:
4400:
4383:
4379:
4377:
4374:
4373:
4344:
4340:
4331:
4327:
4309:
4305:
4296:
4292:
4268:
4264:
4255:
4251:
4233:
4229:
4220:
4216:
4198:
4194:
4179:
4175:
4170:
4167:
4166:
4147:
4143:
4128:
4124:
4122:
4119:
4118:
4091:
4088:
4087:
4070:
4066:
4064:
4061:
4060:
4043:
4039:
4037:
4034:
4033:
4008:
4004:
3989:
3985:
3976:
3972:
3951:
3947:
3932:
3928:
3919:
3915:
3900:
3896:
3881:
3877:
3868:
3864:
3849:
3845:
3830:
3826:
3817:
3813:
3798:
3794:
3779:
3775:
3766:
3762:
3757:
3754:
3753:
3734:
3730:
3728:
3725:
3724:
3702:
3698:
3689:
3685:
3664:
3660:
3651:
3647:
3632:
3628:
3619:
3615:
3610:
3607:
3606:
3600:
3578:
3575:
3574:
3552:
3549:
3548:
3529:
3526:
3525:
3523:
3507:
3504:
3503:
3374:
3371:
3370:
3354:
3351:
3350:
3009:
3006:
3005:
2976:
2973:
2972:
2955:
2952:
2951:
2931:
2928:
2927:
2910:
2907:
2906:
2889:
2886:
2885:
2868:
2865:
2864:
2835:
2832:
2831:
2814:
2811:
2810:
2793:
2790:
2789:
2770:
2767:
2766:
2749:
2746:
2745:
2728:
2725:
2724:
2630:
2627:
2626:
2619:
2601:
2600:
2588:
2584:
2575:
2574:
2563:
2560:
2437:
2436:
2419:
2416:
2263:
2262:
2257:
2254:
2217:
2215:
2175:
2173:
2136:
2134:
2100:
2098:
2089:
2088:
1962:
1961:
1949:
1945:
1932:
1925:
1923:
1920:
1919:
1784:
1780:
1775:
1772:
1771:
1770:
1685:
1682:
1681:
1654:
1653:
1648:
1645:
1634:
1630:
1626:
1622:
1601:
1597:
1582:
1578:
1563:
1562:
1551:
1547:
1543:
1539:
1521:
1517:
1505:
1501:
1488:
1482:
1478:
1471:
1469:
1466:
1465:
1451:
1450:
1445:
1442:
1436:
1432:
1414:
1410:
1392:
1388:
1376:
1372:
1360:
1359:
1350:
1346:
1331:
1327:
1312:
1308:
1299:
1295:
1280:
1279:
1267:
1263:
1250:
1243:
1241:
1238:
1237:
1217:
1214:
1213:
1190:
1186:
1181:
1178:
1177:
1152:
1148:
1144:
1140:
1122:
1118:
1106:
1102:
1100:
1097:
1096:
1079:
1075:
1073:
1070:
1069:
1046:
1042:
1027:
1023:
1008:
1004:
995:
991:
973:
969:
964:
961:
960:
936:
933:
932:
929:
905:
902:
901:
878:
874:
872:
869:
868:
845:
841:
836:
833:
832:
830:
807:
804:
803:
787:
784:
783:
780:
778:Basic algorithm
748:classical logic
744:
692:
689:
688:
649:
646:
645:
612:
609:
608:
576:
573:
572:
543:
540:
539:
498:
495:
494:
414:
411:
410:
391:
388:
387:
347:
344:
343:
305:
302:
301:
268:
265:
264:
227:
224:
223:
181:
178:
177:
157:
154:
153:
133:
130:
129:
116:of one or more
112:of one or more
106:
75:product of sums
61:of one or more
35:
28:
23:
22:
15:
12:
11:
5:
16667:
16657:
16656:
16651:
16634:
16633:
16631:
16630:
16625:
16620:
16614:
16612:
16606:
16605:
16603:
16602:
16597:
16592:
16586:
16584:
16578:
16577:
16570:
16568:
16566:
16565:
16560:
16555:
16550:
16540:
16535:
16530:
16524:
16522:
16516:
16515:
16507:
16506:
16499:
16492:
16484:
16478:
16477:
16457:
16456:
16436:
16435:External links
16433:
16431:
16430:
16424:
16409:
16390:
16377:
16356:Russel, Stuart
16352:
16346:
16327:
16321:
16289:
16283:
16265:
16260:978-9401599344
16259:
16245:
16242:
16241:
16229:
16217:
16205:
16188:
16172:
16171:
16169:
16166:
16163:
16162:
16147:
16142:
16138:
16134:
16131:
16128:
16105:
16102:
16099:
16096:
16081:
16065:
16052:
16032:
16004:
16001:
15998:
15995:
15992:
15989:
15986:
15983:
15980:
15977:
15974:
15971:
15968:
15965:
15962:
15959:
15956:
15953:
15950:
15931:
15917:
15914:
15910:
15906:
15902:
15898:
15895:
15892:
15887:
15881:
15865:
15816:
15798:
15786:
15763:
15758:
15754:
15750:
15747:
15744:
15729:
15717:
15694:
15691:
15688:
15685:
15669:
15668:
15666:
15663:
15662:
15661:
15656:
15634:
15629:
15624:
15617:
15614:
15612:, is the CNF.
15601:
15598:
15595:
15592:
15589:
15586:
15583:
15580:
15577:
15573:
15570:
15567:
15564:
15561:
15557:
15554:
15551:
15548:
15545:
15542:
15539:
15536:
15533:
15529:
15526:
15523:
15520:
15517:
15513:
15510:
15507:
15504:
15501:
15498:
15495:
15492:
15489:
15486:
15483:
15480:
15476:
15473:
15470:
15467:
15464:
15460:
15457:
15454:
15451:
15448:
15445:
15442:
15438:
15435:
15432:
15429:
15426:
15423:
15419:
15394:
15391:
15388:
15385:
15365:
15345:
15342:
15339:
15336:
15316:
15294:
15274:
15271:
15268:
15265:
15245:
15225:
15222:
15219:
15216:
15203:
15202:
15195:
15184:
15174:
15163:
15153:
15142:
15139:
15136:
15133:
15130:
15127:
15124:
15121:
15117:
15114:
15111:
15108:
15105:
15094:
15083:
15073:
15062:
15059:
15056:
15053:
15050:
15047:
15044:
15041:
15037:
15034:
15031:
15028:
15025:
15021:
15011:
15000:
14990:
14979:
14969:
14958:
14948:
14946:
14935:
14932:
14929:
14919:
14908:
14905:
14902:
14899:
14889:
14878:
14874:
14871:
14868:
14865:
14862:
14851:
14849:
14847:
14845:
14834:
14824:
14822:
14820:
14818:
14816:
14814:
14812:
14810:
14799:
14789:
14778:
14775:
14772:
14769:
14759:
14748:
14744:
14741:
14738:
14735:
14732:
14729:
14718:
14716:
14714:
14712:
14710:
14708:
14706:
14695:
14685:
14674:
14664:
14662:
14659:
14658:
14655:
14653:
14642:
14632:
14621:
14618:
14615:
14612:
14609:
14606:
14603:
14600:
14596:
14593:
14590:
14587:
14584:
14573:
14561:
14550:
14539:
14536:
14533:
14530:
14527:
14524:
14521:
14518:
14514:
14511:
14508:
14505:
14502:
14498:
14488:
14477:
14467:
14455:
14444:
14433:
14423:
14421:
14410:
14407:
14404:
14394:
14383:
14380:
14377:
14374:
14364:
14353:
14349:
14346:
14343:
14340:
14337:
14326:
14324:
14322:
14320:
14308:
14297:
14295:
14293:
14291:
14289:
14287:
14285:
14283:
14272:
14262:
14251:
14248:
14245:
14242:
14232:
14221:
14217:
14214:
14211:
14208:
14205:
14202:
14191:
14189:
14187:
14185:
14183:
14181:
14179:
14168:
14158:
14156:
14154:
14151:
14150:
14147:
14145:
14143:
14141:
14139:
14137:
14135:
14133:
14131:
14129:
14118:
14115:
14112:
14102:
14091:
14088:
14085:
14082:
14072:
14061:
14057:
14054:
14051:
14048:
14045:
14034:
14032:
14030:
14028:
14016:
14005:
14003:
13992:
13982:
13971:
13961:
13950:
13947:
13944:
13941:
13931:
13920:
13917:
13914:
13910:
13907:
13904:
13901:
13898:
13887:
13876:
13866:
13854:
13843:
13832:
13822:
13811:
13808:
13805:
13802:
13792:
13781:
13777:
13774:
13771:
13768:
13765:
13762:
13751:
13749:
13747:
13736:
13726:
13724:
13722:
13720:
13718:
13716:
13714:
13711:
13710:
13707:
13705:
13703:
13701:
13699:
13697:
13695:
13693:
13691:
13689:
13678:
13675:
13672:
13662:
13651:
13648:
13645:
13642:
13632:
13621:
13617:
13614:
13611:
13608:
13605:
13594:
13592:
13590:
13588:
13577:
13567:
13565:
13554:
13544:
13533:
13523:
13512:
13502:
13491:
13488:
13485:
13481:
13478:
13475:
13472:
13469:
13458:
13447:
13437:
13426:
13416:
13405:
13395:
13384:
13374:
13363:
13359:
13356:
13353:
13350:
13347:
13344:
13333:
13331:
13329:
13318:
13308:
13306:
13292:
13289:
13276:
13274:
13272:
13270:
13268:
13257:
13254:
13243:
13242:
13239:
13237:
13235:
13233:
13231:
13229:
13227:
13225:
13223:
13221:
13210:
13207:
13204:
13194:
13183:
13173:
13162:
13158:
13155:
13152:
13149:
13146:
13135:
13133:
13131:
13129:
13118:
13108:
13106:
13095:
13085:
13074:
13064:
13053:
13043:
13032:
13029:
13026:
13022:
13019:
13016:
13013:
13010:
12999:
12988:
12978:
12967:
12957:
12946:
12936:
12925:
12915:
12904:
12900:
12897:
12894:
12891:
12888:
12885:
12874:
12872:
12870:
12859:
12849:
12847:
12836:
12833:
12823:
12821:
12819:
12817:
12803:
12800:
12787:
12776:
12773:
12762:
12761:
12758:
12756:
12754:
12752:
12750:
12748:
12746:
12744:
12742:
12740:
12729:
12726:
12723:
12713:
12702:
12692:
12681:
12677:
12674:
12671:
12668:
12665:
12654:
12652:
12650:
12648:
12636:
12625:
12614:
12604:
12602:
12591:
12581:
12570:
12560:
12549:
12546:
12543:
12539:
12536:
12533:
12530:
12527:
12516:
12505:
12495:
12484:
12474:
12463:
12453:
12442:
12432:
12421:
12417:
12414:
12411:
12408:
12405:
12402:
12391:
12389:
12387:
12385:
12383:
12369:
12366:
12353:
12342:
12332:
12330:
12328:
12317:
12314:
12304:
12293:
12290:
12279:
12278:
12275:
12273:
12271:
12269:
12267:
12265:
12263:
12261:
12259:
12248:
12238:
12227:
12224:
12221:
12211:
12200:
12190:
12179:
12175:
12172:
12169:
12166:
12163:
12152:
12140:
12129:
12117:
12106:
12095:
12085:
12073:
12062:
12051:
12041:
12039:
12028:
12018:
12007:
11997:
11986:
11983:
11980:
11976:
11973:
11970:
11967:
11964:
11953:
11942:
11932:
11921:
11911:
11900:
11890:
11879:
11869:
11858:
11854:
11851:
11848:
11845:
11842:
11839:
11828:
11826:
11824:
11822:
11820:
11809:
11806:
11796:
11785:
11775:
11773:
11771:
11769:
11758:
11755:
11744:
11743:
11740:
11738:
11736:
11734:
11732:
11730:
11728:
11726:
11724:
11713:
11703:
11692:
11689:
11686:
11676:
11665:
11655:
11644:
11640:
11637:
11634:
11631:
11628:
11617:
11605:
11594:
11582:
11571:
11560:
11550:
11539:
11529:
11518:
11508:
11506:
11495:
11485:
11474:
11464:
11453:
11450:
11447:
11443:
11440:
11437:
11434:
11431:
11420:
11409:
11399:
11388:
11378:
11367:
11357:
11346:
11336:
11325:
11321:
11318:
11315:
11312:
11309:
11306:
11295:
11293:
11291:
11289:
11287:
11273:
11270:
11257:
11246:
11236:
11234:
11232:
11230:
11219:
11216:
11205:
11204:
11201:
11199:
11197:
11195:
11193:
11191:
11189:
11187:
11185:
11174:
11164:
11153:
11150:
11147:
11137:
11126:
11116:
11105:
11101:
11098:
11095:
11092:
11089:
11078:
11067:
11057:
11046:
11036:
11025:
11015:
11004:
10994:
10983:
10973:
10971:
10960:
10950:
10939:
10929:
10918:
10915:
10912:
10908:
10905:
10902:
10899:
10896:
10885:
10874:
10864:
10853:
10843:
10832:
10822:
10811:
10801:
10790:
10786:
10783:
10780:
10777:
10774:
10771:
10760:
10748:
10737:
10725:
10714:
10712:
10710:
10699:
10696:
10686:
10675:
10665:
10663:
10661:
10659:
10648:
10645:
10634:
10633:
10630:
10628:
10626:
10624:
10622:
10620:
10618:
10616:
10614:
10603:
10593:
10582:
10579:
10576:
10566:
10555:
10545:
10534:
10530:
10527:
10524:
10521:
10518:
10507:
10496:
10486:
10475:
10465:
10454:
10444:
10433:
10423:
10412:
10402:
10391:
10381:
10370:
10360:
10349:
10339:
10328:
10325:
10322:
10318:
10315:
10312:
10309:
10306:
10295:
10293:
10281:
10270:
10259:
10249:
10238:
10228:
10217:
10213:
10210:
10207:
10204:
10201:
10198:
10187:
10176:
10166:
10164:
10153:
10143:
10131:
10120:
10109:
10106:
10096:
10085:
10075:
10073:
10071:
10069:
10058:
10055:
10044:
10043:
10040:
10038:
10036:
10034:
10032:
10030:
10028:
10026:
10024:
10013:
10003:
9992:
9989:
9986:
9976:
9965:
9955:
9944:
9940:
9937:
9934:
9931:
9928:
9917:
9906:
9896:
9885:
9875:
9864:
9854:
9843:
9833:
9822:
9812:
9810:
9799:
9789:
9778:
9768:
9757:
9754:
9751:
9747:
9744:
9741:
9738:
9735:
9724:
9722:
9711:
9701:
9690:
9680:
9669:
9659:
9648:
9644:
9641:
9638:
9635:
9632:
9629:
9618:
9607:
9597:
9595:
9593:
9591:
9577:
9574:
9561:
9550:
9540:
9538:
9536:
9524:
9513:
9502:
9499:
9488:
9487:
9484:
9482:
9480:
9478:
9476:
9474:
9472:
9470:
9468:
9457:
9447:
9436:
9433:
9430:
9420:
9409:
9399:
9388:
9384:
9381:
9378:
9375:
9372:
9361:
9350:
9340:
9329:
9319:
9308:
9298:
9286:
9275:
9264:
9254:
9252:
9241:
9231:
9220:
9210:
9199:
9196:
9193:
9189:
9186:
9183:
9180:
9177:
9166:
9164:
9153:
9143:
9132:
9122:
9111:
9101:
9090:
9086:
9083:
9080:
9077:
9074:
9071:
9060:
9049:
9039:
9037:
9035:
9033:
9022:
9019:
9009:
8998:
8988:
8986:
8984:
8982:
8971:
8968:
8957:
8956:
8954:
8952:
8950:
8948:
8946:
8944:
8942:
8940:
8938:
8927:
8917:
8906:
8903:
8900:
8890:
8879:
8869:
8858:
8854:
8851:
8848:
8845:
8842:
8831:
8820:
8810:
8799:
8789:
8778:
8768:
8757:
8747:
8736:
8726:
8724:
8713:
8703:
8692:
8682:
8671:
8668:
8665:
8661:
8658:
8655:
8652:
8649:
8638:
8636:
8624:
8613:
8602:
8592:
8581:
8571:
8560:
8556:
8553:
8550:
8547:
8544:
8541:
8530:
8528:
8526:
8524:
8522:
8511:
8508:
8498:
8487:
8477:
8475:
8473:
8471:
8460:
8457:
8398:
8397:
8385:
8382:
8379:
8376:
8373:
8370:
8367:
8364:
8361:
8358:
8355:
8335:
8332:
8329:
8326:
8323:
8320:
8317:
8306:
8303:
8302:
8301:
8285:
8265:
8245:
8242:
8237:
8233:
8229:
8226:
8223:
8218:
8214:
8210:
8207:
8204:
8201:
8195:
8191:
8187:
8184:
8179:
8175:
8171:
8151:
8148:
8145:
8142:
8138:
8135:
8129:
8125:
8121:
8118:
8113:
8109:
8105:
8094:
8082:
8062:
8042:
8022:
8002:
7982:
7979:
7976:
7973:
7970:
7967:
7964:
7961:
7958:
7955:
7935:
7932:
7929:
7926:
7923:
7920:
7917:
7914:
7911:
7908:
7888:
7885:
7882:
7879:
7876:
7873:
7870:
7867:
7864:
7861:
7841:
7838:
7835:
7832:
7829:
7826:
7823:
7820:
7817:
7814:
7794:
7791:
7788:
7785:
7782:
7779:
7776:
7773:
7770:
7767:
7747:
7744:
7741:
7738:
7735:
7732:
7729:
7726:
7723:
7720:
7700:
7697:
7694:
7691:
7688:
7685:
7682:
7679:
7676:
7673:
7653:
7650:
7647:
7644:
7641:
7638:
7635:
7632:
7629:
7626:
7614:the statement
7609:
7608:
7607:
7595:
7592:
7589:
7586:
7583:
7580:
7576:
7573:
7570:
7567:
7564:
7560:
7557:
7554:
7551:
7548:
7545:
7542:
7539:
7536:
7533:
7529:
7526:
7523:
7520:
7517:
7513:
7510:
7507:
7504:
7501:
7497:
7494:
7491:
7488:
7485:
7482:
7478:
7475:
7472:
7469:
7466:
7457:is renamed to
7446:
7443:
7440:
7437:
7434:
7431:
7427:
7424:
7421:
7418:
7415:
7411:
7408:
7405:
7402:
7399:
7396:
7393:
7390:
7387:
7384:
7380:
7377:
7374:
7371:
7368:
7364:
7361:
7358:
7355:
7352:
7348:
7345:
7342:
7339:
7336:
7333:
7329:
7326:
7323:
7320:
7317:
7297:
7294:
7291:
7288:
7285:
7282:
7279:
7276:
7273:
7270:
7267:
7264:
7261:
7258:
7255:
7252:
7249:
7235:
7234:
7233:
7221:
7201:
7198:
7195:
7192:
7189:
7186:
7183:
7163:
7160:
7157:
7154:
7151:
7148:
7145:
7142:
7139:
7119:
7116:
7113:
7110:
7107:
7104:
7101:
7081:
7078:
7075:
7072:
7069:
7066:
7063:
7060:
7057:
7037:
7017:
7014:
7011:
7002:; and replace
6991:
6988:
6985:
6982:
6979:
6976:
6973:
6970:
6967:
6947:
6944:
6941:
6938:
6935:
6932:
6912:
6909:
6906:
6903:
6900:
6897:
6894:
6891:
6888:
6868:
6865:
6862:
6859:
6856:
6853:
6838:
6826:
6806:
6786:
6783:
6780:
6777:
6774:
6771:
6768:
6765:
6762:
6759:
6756:
6753:
6750:
6730:
6727:
6724:
6704:
6701:
6698:
6695:
6675:
6672:
6669:
6642:
6639:
6633:
6632:
6629:
6618:
6608:
6597:
6587:
6572:
6568:
6564:
6560:
6549:
6538:
6528:
6517:
6507:
6496:
6486:
6473:
6470:
6466:
6455:
6444:
6434:
6423:
6413:
6402:
6392:
6381:
6371:
6360:
6350:
6335:
6331:
6327:
6323:
6312:
6301:
6291:
6280:
6270:
6259:
6249:
6236:
6232:
6221:
6210:
6200:
6189:
6178:
6177:
6174:
6172:
6161:
6151:
6136:
6132:
6128:
6124:
6113:
6102:
6092:
6081:
6071:
6060:
6050:
6037:
6034:
6030:
6019:
6008:
5998:
5987:
5977:
5966:
5956:
5945:
5935:
5924:
5914:
5899:
5895:
5891:
5887:
5876:
5865:
5855:
5844:
5834:
5823:
5813:
5800:
5796:
5785:
5774:
5764:
5751:
5748:
5729:
5725:
5721:
5718:
5715:
5710:
5706:
5702:
5699:
5696:
5676:
5673:
5668:
5665:
5662:
5658:
5654:
5651:
5648:
5643:
5639:
5616:
5612:
5608:
5605:
5602:
5597:
5593:
5589:
5586:
5583:
5578:
5574:
5490:
5487:
5464:
5461:
5458:
5455:
5452:
5449:
5446:
5443:
5440:
5437:
5434:
5431:
5430:
5427:
5424:
5421:
5418:
5415:
5412:
5409:
5406:
5403:
5400:
5397:
5394:
5391:
5388:
5385:
5382:
5379:
5376:
5373:
5370:
5367:
5364:
5361:
5358:
5355:
5352:
5349:
5346:
5343:
5340:
5337:
5334:
5331:
5328:
5325:
5322:
5319:
5316:
5313:
5312:
5309:
5306:
5303:
5300:
5297:
5294:
5291:
5288:
5283:
5279:
5276:
5273:
5270:
5267:
5261:
5256:
5252:
5249:
5246:
5243:
5240:
5237:
5231:
5226:
5222:
5219:
5216:
5213:
5210:
5207:
5201:
5196:
5192:
5189:
5186:
5183:
5180:
5177:
5174:
5168:
5165:
5162:
5159:
5156:
5153:
5150:
5147:
5146:
5143:
5140:
5137:
5134:
5131:
5128:
5125:
5122:
5119:
5116:
5113:
5110:
5107:
5104:
5101:
5098:
5095:
5092:
5089:
5088:
5079:disjunctions:
5068:
5065:
5062:
5059:
5054:
5051:
5048:
5045:
5042:
5038:
5014:
4994:
4962:
4958:
4931:
4928:
4925:
4920:
4917:
4913:
4909:
4889:
4867:
4862:
4858:
4854:
4851:
4846:
4842:
4838:
4835:
4832:
4827:
4823:
4819:
4816:
4811:
4807:
4803:
4798:
4794:
4790:
4787:
4782:
4778:
4774:
4771:
4768:
4748:
4745:
4722:
4719:
4716:
4696:
4684:
4681:
4666:
4662:
4658:
4653:
4649:
4626:
4622:
4599:
4595:
4591:
4586:
4582:
4578:
4573:
4569:
4546:
4542:
4538:
4535:
4530:
4526:
4522:
4519:
4514:
4510:
4471:
4467:
4440:
4436:
4413:
4409:
4386:
4382:
4370:interpretation
4355:
4352:
4347:
4343:
4339:
4334:
4330:
4326:
4323:
4320:
4317:
4312:
4308:
4304:
4299:
4295:
4291:
4288:
4285:
4282:
4279:
4276:
4271:
4267:
4263:
4258:
4254:
4250:
4247:
4244:
4241:
4236:
4232:
4228:
4223:
4219:
4215:
4212:
4209:
4206:
4201:
4197:
4193:
4190:
4187:
4182:
4178:
4174:
4150:
4146:
4142:
4139:
4136:
4131:
4127:
4111:satisfiability
4095:
4073:
4069:
4046:
4042:
4019:
4016:
4011:
4007:
4003:
4000:
3997:
3992:
3988:
3984:
3979:
3975:
3971:
3968:
3965:
3962:
3959:
3954:
3950:
3946:
3943:
3940:
3935:
3931:
3927:
3922:
3918:
3914:
3911:
3908:
3903:
3899:
3895:
3892:
3889:
3884:
3880:
3876:
3871:
3867:
3863:
3860:
3857:
3852:
3848:
3844:
3841:
3838:
3833:
3829:
3825:
3820:
3816:
3812:
3809:
3806:
3801:
3797:
3793:
3790:
3787:
3782:
3778:
3774:
3769:
3765:
3761:
3737:
3733:
3710:
3705:
3701:
3697:
3692:
3688:
3684:
3681:
3678:
3675:
3672:
3667:
3663:
3659:
3654:
3650:
3646:
3643:
3640:
3635:
3631:
3627:
3622:
3618:
3614:
3599:
3596:
3595:
3594:
3582:
3571:
3559:
3556:
3533:
3511:
3489:
3486:
3483:
3480:
3477:
3474:
3471:
3468:
3465:
3462:
3459:
3456:
3453:
3450:
3447:
3444:
3441:
3438:
3435:
3432:
3429:
3426:
3423:
3420:
3417:
3414:
3411:
3408:
3405:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3358:
3345:
3344:
3342:
3339:
3336:
3333:
3331:
3328:
3326:
3323:
3320:
3318:
3316:
3313:
3310:
3306:
3305:
3303:
3300:
3297:
3294:
3292:
3289:
3287:
3284:
3281:
3279:
3277:
3274:
3271:
3267:
3266:
3264:
3261:
3258:
3255:
3253:
3248:
3246:
3243:
3240:
3238:
3236:
3233:
3230:
3226:
3225:
3223:
3220:
3217:
3214:
3212:
3209:
3207:
3204:
3201:
3199:
3197:
3194:
3191:
3187:
3186:
3184:
3181:
3178:
3175:
3173:
3168:
3166:
3163:
3160:
3158:
3156:
3153:
3150:
3146:
3145:
3143:
3140:
3137:
3134:
3132:
3129:
3127:
3124:
3121:
3119:
3117:
3114:
3111:
3107:
3106:
3104:
3101:
3098:
3095:
3093:
3088:
3086:
3083:
3080:
3078:
3076:
3073:
3070:
3066:
3065:
3063:
3060:
3057:
3054:
3052:
3047:
3045:
3042:
3039:
3037:
3035:
3032:
3029:
3025:
3024:
3013:
3003:
2992:
2989:
2986:
2983:
2980:
2970:
2959:
2949:
2938:
2935:
2925:
2914:
2904:
2893:
2883:
2872:
2862:
2851:
2848:
2845:
2842:
2839:
2829:
2818:
2808:
2797:
2787:
2785:
2774:
2764:
2753:
2743:
2732:
2700:
2697:
2694:
2691:
2688:
2685:
2682:
2679:
2676:
2673:
2670:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2618:
2615:
2597:
2594:
2591:
2587:
2583:
2580:
2578:
2576:
2573:
2570:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2526:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2440:
2438:
2435:
2432:
2429:
2426:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2370:
2367:
2364:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2266:
2264:
2256:
2251:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2214:
2209:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2172:
2167:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2139:
2133:
2128:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2103:
2097:
2094:
2092:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1965:
1963:
1958:
1955:
1952:
1948:
1944:
1941:
1938:
1935:
1933:
1931:
1928:
1927:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1798:
1793:
1790:
1787:
1783:
1779:
1755:
1752:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1647:
1644:
1637:
1633:
1629:
1625:
1621:
1618:
1615:
1612:
1607:
1604:
1600:
1596:
1593:
1588:
1585:
1581:
1577:
1574:
1571:
1568:
1566:
1564:
1561:
1554:
1550:
1546:
1542:
1538:
1535:
1532:
1527:
1524:
1520:
1516:
1511:
1508:
1504:
1500:
1497:
1494:
1491:
1489:
1485:
1481:
1477:
1474:
1473:
1444:
1439:
1435:
1431:
1428:
1425:
1422:
1417:
1413:
1409:
1406:
1403:
1400:
1395:
1391:
1387:
1384:
1379:
1375:
1371:
1368:
1365:
1363:
1361:
1358:
1353:
1349:
1345:
1342:
1339:
1334:
1330:
1326:
1323:
1320:
1315:
1311:
1307:
1302:
1298:
1294:
1291:
1288:
1285:
1283:
1281:
1276:
1273:
1270:
1266:
1262:
1259:
1256:
1253:
1251:
1249:
1246:
1245:
1221:
1199:
1196:
1193:
1189:
1185:
1155:
1151:
1147:
1143:
1139:
1136:
1133:
1128:
1125:
1121:
1117:
1112:
1109:
1105:
1082:
1078:
1054:
1049:
1045:
1041:
1038:
1035:
1030:
1026:
1022:
1019:
1016:
1011:
1007:
1003:
998:
994:
990:
987:
982:
979:
976:
972:
968:
940:
928:
925:
912:
909:
887:
884:
881:
877:
854:
851:
848:
844:
840:
814:
811:
791:
779:
776:
743:
740:
739:
738:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
686:
674:
671:
668:
665:
662:
659:
656:
653:
643:
631:
628:
625:
622:
619:
616:
598:
597:
586:
583:
580:
570:
559:
556:
553:
550:
547:
537:
526:
523:
520:
517:
514:
511:
508:
505:
502:
492:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
395:
375:
372:
369:
366:
363:
360:
357:
354:
351:
333:
332:
323:
309:
295:
286:
272:
255:
245:
231:
185:
161:
137:
105:
102:
91:circuit theory
26:
9:
6:
4:
3:
2:
16666:
16655:
16652:
16650:
16647:
16646:
16644:
16629:
16626:
16624:
16621:
16619:
16616:
16615:
16613:
16611:
16607:
16601:
16598:
16596:
16593:
16591:
16588:
16587:
16585:
16583:
16579:
16574:
16564:
16561:
16559:
16556:
16554:
16551:
16548:
16544:
16541:
16539:
16536:
16534:
16531:
16529:
16526:
16525:
16523:
16521:
16517:
16512:
16505:
16500:
16498:
16493:
16491:
16486:
16485:
16482:
16467:
16463:
16459:
16458:
16453:
16449:
16448:
16443:
16439:
16438:
16427:
16421:
16417:
16416:
16410:
16406:
16399:
16395:
16391:
16384:
16380:
16374:
16367:
16366:
16361:
16360:Norvig, Peter
16357:
16353:
16349:
16343:
16339:
16335:
16334:
16328:
16324:
16318:
16314:
16310:
16306:
16302:
16295:
16290:
16286:
16280:
16277:. Routledge.
16276:
16275:
16270:
16269:Howson, Colin
16266:
16262:
16256:
16252:
16247:
16246:
16238:
16233:
16226:
16221:
16214:
16209:
16203:
16197:
16195:
16193:
16186:, p. 46.
16185:
16180:
16178:
16173:
16160:
16145:
16140:
16136:
16132:
16129:
16126:
16118:
16103:
16100:
16097:
16094:
16085:
16079:
16075:
16069:
16063:do not occur.
16050:
16030:
16022:
16021:associativity
16018:
16017:commutativity
15999:
15996:
15993:
15990:
15987:
15981:
15975:
15972:
15969:
15963:
15957:
15954:
15951:
15938:
15936:
15915:
15912:
15908:
15904:
15900:
15893:
15879:
15869:
15862:
15861:
15856:
15855:
15850:
15849:
15844:
15843:
15838:
15837:
15832:
15831:
15814:
15805:
15803:
15784:
15776:
15761:
15756:
15752:
15748:
15745:
15742:
15733:
15715:
15707:
15692:
15689:
15686:
15683:
15674:
15670:
15660:
15657:
15654:
15650:
15646:
15642:
15638:
15635:
15633:
15630:
15628:
15625:
15623:
15620:
15619:
15613:
15593:
15590:
15584:
15578:
15555:
15546:
15540:
15537:
15534:
15505:
15496:
15493:
15487:
15481:
15458:
15449:
15443:
15408:
15406:
15389:
15383:
15363:
15340:
15334:
15314:
15292:
15269:
15263:
15243:
15220:
15214:
15200:
15196:
15175:
15154:
15137:
15134:
15128:
15122:
15095:
15081:
15074:
15054:
15048:
15045:
15042:
15012:
14991:
14977:
14970:
14949:
14947:
14930:
14927:
14920:
14903:
14897:
14890:
14852:
14850:
14848:
14846:
14832:
14825:
14823:
14821:
14819:
14817:
14815:
14813:
14811:
14790:
14773:
14767:
14760:
14719:
14717:
14715:
14713:
14711:
14709:
14707:
14686:
14665:
14663:
14661:
14660:
14656:
14654:
14633:
14616:
14613:
14607:
14601:
14574:
14559:
14551:
14531:
14525:
14522:
14519:
14489:
14468:
14453:
14445:
14424:
14422:
14405:
14402:
14395:
14378:
14372:
14365:
14327:
14325:
14323:
14321:
14306:
14298:
14296:
14294:
14292:
14290:
14288:
14286:
14284:
14263:
14246:
14240:
14233:
14192:
14190:
14188:
14186:
14184:
14182:
14180:
14159:
14157:
14155:
14153:
14152:
14148:
14146:
14144:
14142:
14140:
14138:
14136:
14134:
14132:
14130:
14113:
14110:
14103:
14086:
14080:
14073:
14035:
14033:
14031:
14029:
14014:
14006:
14004:
13983:
13962:
13945:
13939:
13932:
13918:
13915:
13888:
13867:
13852:
13844:
13823:
13806:
13800:
13793:
13752:
13750:
13748:
13727:
13725:
13723:
13721:
13719:
13717:
13715:
13713:
13712:
13708:
13706:
13704:
13702:
13700:
13698:
13696:
13694:
13692:
13690:
13673:
13670:
13663:
13646:
13640:
13633:
13595:
13593:
13591:
13589:
13575:
13568:
13566:
13545:
13524:
13510:
13503:
13489:
13486:
13459:
13438:
13424:
13417:
13396:
13382:
13375:
13334:
13332:
13330:
13309:
13307:
13290:
13277:
13275:
13273:
13271:
13269:
13255:
13245:
13244:
13240:
13238:
13236:
13234:
13232:
13230:
13228:
13226:
13224:
13222:
13205:
13202:
13195:
13181:
13174:
13136:
13134:
13132:
13130:
13116:
13109:
13107:
13086:
13065:
13051:
13044:
13030:
13027:
13000:
12979:
12965:
12958:
12937:
12923:
12916:
12875:
12873:
12871:
12850:
12848:
12834:
12824:
12822:
12820:
12818:
12801:
12788:
12774:
12764:
12763:
12759:
12757:
12755:
12753:
12751:
12749:
12747:
12745:
12743:
12741:
12724:
12721:
12714:
12700:
12693:
12655:
12653:
12651:
12649:
12634:
12626:
12605:
12603:
12582:
12568:
12561:
12547:
12544:
12517:
12496:
12482:
12475:
12454:
12440:
12433:
12392:
12390:
12388:
12386:
12384:
12367:
12354:
12333:
12331:
12329:
12315:
12305:
12291:
12281:
12280:
12276:
12274:
12272:
12270:
12268:
12266:
12264:
12262:
12260:
12239:
12222:
12219:
12212:
12198:
12191:
12153:
12138:
12130:
12107:
12086:
12071:
12063:
12042:
12040:
12019:
12005:
11998:
11984:
11981:
11954:
11933:
11919:
11912:
11891:
11877:
11870:
11829:
11827:
11825:
11823:
11821:
11807:
11797:
11776:
11774:
11772:
11770:
11756:
11746:
11745:
11741:
11739:
11737:
11735:
11733:
11731:
11729:
11727:
11725:
11704:
11687:
11684:
11677:
11663:
11656:
11618:
11603:
11595:
11572:
11551:
11537:
11530:
11509:
11507:
11486:
11472:
11465:
11451:
11448:
11421:
11400:
11386:
11379:
11358:
11344:
11337:
11296:
11294:
11292:
11290:
11288:
11271:
11258:
11237:
11235:
11233:
11231:
11217:
11207:
11206:
11202:
11200:
11198:
11196:
11194:
11192:
11190:
11188:
11186:
11165:
11148:
11145:
11138:
11124:
11117:
11079:
11065:
11058:
11037:
11016:
11002:
10995:
10974:
10972:
10951:
10937:
10930:
10916:
10913:
10886:
10865:
10851:
10844:
10823:
10809:
10802:
10761:
10738:
10715:
10713:
10711:
10697:
10687:
10666:
10664:
10662:
10660:
10646:
10636:
10635:
10631:
10629:
10627:
10625:
10623:
10621:
10619:
10617:
10615:
10594:
10577:
10574:
10567:
10553:
10546:
10508:
10494:
10487:
10466:
10445:
10431:
10424:
10403:
10382:
10361:
10347:
10340:
10326:
10323:
10296:
10294:
10279:
10271:
10250:
10236:
10229:
10188:
10167:
10165:
10144:
10121:
10107:
10097:
10076:
10074:
10072:
10070:
10056:
10046:
10045:
10041:
10039:
10037:
10035:
10033:
10031:
10029:
10027:
10025:
10004:
9987:
9984:
9977:
9963:
9956:
9918:
9904:
9897:
9876:
9855:
9841:
9834:
9813:
9811:
9790:
9776:
9769:
9755:
9752:
9725:
9723:
9709:
9702:
9681:
9667:
9660:
9619:
9598:
9596:
9594:
9592:
9575:
9562:
9541:
9539:
9537:
9514:
9500:
9490:
9489:
9485:
9483:
9481:
9479:
9477:
9475:
9473:
9471:
9469:
9448:
9431:
9428:
9421:
9407:
9400:
9362:
9348:
9341:
9320:
9299:
9276:
9255:
9253:
9232:
9218:
9211:
9197:
9194:
9167:
9165:
9151:
9144:
9123:
9109:
9102:
9061:
9040:
9038:
9036:
9034:
9020:
9010:
8989:
8987:
8985:
8983:
8969:
8959:
8958:
8955:
8953:
8951:
8949:
8947:
8945:
8943:
8941:
8939:
8918:
8901:
8898:
8891:
8877:
8870:
8832:
8818:
8811:
8790:
8769:
8748:
8727:
8725:
8704:
8690:
8683:
8669:
8666:
8639:
8637:
8614:
8593:
8579:
8572:
8531:
8529:
8527:
8525:
8523:
8509:
8499:
8478:
8476:
8474:
8472:
8458:
8448:
8447:
8444:
8416:
8412:
8408:
8403:
8402:
8380:
8377:
8374:
8368:
8362:
8359:
8356:
8330:
8327:
8324:
8318:
8315:
8307:
8304:
8299:
8283:
8263:
8235:
8231:
8227:
8224:
8221:
8216:
8212:
8205:
8199:
8193:
8189:
8182:
8177:
8173:
8146:
8140:
8136:
8127:
8123:
8116:
8111:
8107:
8095:
8080:
8060:
8020:
8000:
7974:
7968:
7965:
7962:
7956:
7927:
7921:
7918:
7909:
7906:
7880:
7874:
7871:
7868:
7862:
7833:
7827:
7824:
7815:
7812:
7786:
7780:
7777:
7774:
7768:
7739:
7733:
7730:
7721:
7718:
7692:
7686:
7683:
7680:
7674:
7645:
7639:
7636:
7627:
7624:
7616:
7615:
7613:
7610:
7587:
7584:
7581:
7558:
7549:
7540:
7537:
7534:
7508:
7502:
7476:
7467:
7438:
7435:
7432:
7409:
7400:
7391:
7388:
7385:
7359:
7353:
7327:
7318:
7289:
7283:
7280:
7271:
7262:
7256:
7253:
7239:
7238:
7236:
7196:
7190:
7184:
7155:
7149:
7146:
7114:
7108:
7102:
7073:
7067:
7064:
7035:
7015:
6986:
6977:
6971:
6942:
6939:
6936:
6907:
6898:
6892:
6863:
6860:
6857:
6843:
6839:
6781:
6778:
6775:
6766:
6760:
6754:
6751:
6728:
6722:
6702:
6699:
6696:
6673:
6667:
6659:
6658:
6656:
6652:
6651:
6650:
6648:
6638:
6630:
6609:
6588:
6570:
6566:
6562:
6558:
6550:
6536:
6529:
6515:
6508:
6494:
6487:
6471:
6468:
6464:
6456:
6435:
6421:
6414:
6400:
6393:
6379:
6372:
6351:
6333:
6329:
6325:
6321:
6313:
6299:
6292:
6278:
6271:
6257:
6250:
6234:
6230:
6222:
6201:
6180:
6179:
6175:
6173:
6152:
6134:
6130:
6126:
6122:
6114:
6100:
6093:
6079:
6072:
6058:
6051:
6035:
6032:
6028:
6020:
5999:
5985:
5978:
5964:
5957:
5943:
5936:
5915:
5897:
5893:
5889:
5885:
5877:
5863:
5856:
5842:
5835:
5821:
5814:
5798:
5794:
5786:
5765:
5763:
5762:
5759:
5757:
5747:
5727:
5723:
5719:
5716:
5713:
5708:
5704:
5700:
5697:
5674:
5671:
5666:
5663:
5660:
5656:
5652:
5649:
5646:
5641:
5637:
5614:
5610:
5606:
5603:
5600:
5595:
5591:
5587:
5584:
5581:
5576:
5572:
5563:
5559:
5555:
5550:
5546:
5544:
5540:
5536:
5532:
5528:
5524:
5521:>2) while
5520:
5516:
5512:
5508:
5504:
5500:
5496:
5486:
5484:
5483:contradiction
5479:
5459:
5456:
5453:
5447:
5444:
5441:
5438:
5425:
5419:
5416:
5413:
5407:
5404:
5398:
5392:
5389:
5386:
5380:
5377:
5368:
5362:
5359:
5356:
5353:
5350:
5341:
5335:
5329:
5326:
5323:
5320:
5307:
5301:
5298:
5295:
5286:
5281:
5274:
5271:
5268:
5259:
5254:
5247:
5241:
5238:
5229:
5224:
5217:
5214:
5211:
5199:
5194:
5187:
5181:
5178:
5166:
5160:
5157:
5154:
5141:
5135:
5129:
5123:
5114:
5108:
5102:
5096:
5066:
5063:
5060:
5057:
5049:
5046:
5043:
5036:
5026:
5012:
4992:
4983:
4982:
4978:
4960:
4956:
4946:
4943:
4926:
4923:
4918:
4915:
4911:
4887:
4879:
4860:
4856:
4849:
4844:
4840:
4836:
4833:
4830:
4825:
4821:
4814:
4809:
4805:
4801:
4796:
4792:
4785:
4780:
4776:
4769:
4766:
4746:
4743:
4734:
4720:
4717:
4714:
4694:
4680:
4664:
4660:
4656:
4651:
4647:
4624:
4620:
4597:
4593:
4589:
4584:
4580:
4576:
4571:
4567:
4544:
4540:
4533:
4528:
4524:
4517:
4512:
4508:
4499:
4494:
4492:
4488:
4469:
4465:
4456:
4438:
4434:
4411:
4407:
4384:
4380:
4371:
4366:
4353:
4345:
4341:
4337:
4332:
4328:
4318:
4310:
4306:
4302:
4297:
4293:
4283:
4280:
4277:
4269:
4265:
4261:
4256:
4252:
4242:
4234:
4230:
4226:
4221:
4217:
4207:
4199:
4195:
4191:
4188:
4185:
4180:
4176:
4164:
4148:
4144:
4140:
4137:
4134:
4129:
4125:
4116:
4112:
4107:
4093:
4071:
4067:
4044:
4040:
4030:
4017:
4009:
4005:
4001:
3998:
3995:
3990:
3986:
3982:
3977:
3973:
3966:
3963:
3960:
3952:
3948:
3944:
3941:
3938:
3933:
3929:
3925:
3920:
3916:
3909:
3901:
3897:
3893:
3890:
3887:
3882:
3878:
3874:
3869:
3865:
3858:
3850:
3846:
3842:
3839:
3836:
3831:
3827:
3823:
3818:
3814:
3807:
3799:
3795:
3791:
3788:
3785:
3780:
3776:
3772:
3767:
3763:
3751:
3735:
3731:
3721:
3703:
3699:
3695:
3690:
3686:
3679:
3676:
3673:
3665:
3661:
3657:
3652:
3648:
3641:
3633:
3629:
3625:
3620:
3616:
3604:
3580:
3572:
3557:
3546:
3545:
3544:
3531:
3509:
3500:
3484:
3481:
3478:
3472:
3469:
3463:
3457:
3454:
3451:
3448:
3445:
3436:
3430:
3427:
3424:
3418:
3415:
3406:
3400:
3394:
3391:
3385:
3382:
3356:
3343:
3340:
3337:
3334:
3332:
3329:
3327:
3324:
3321:
3319:
3317:
3314:
3311:
3308:
3307:
3304:
3301:
3298:
3295:
3293:
3290:
3288:
3285:
3282:
3280:
3278:
3275:
3272:
3269:
3268:
3265:
3262:
3259:
3256:
3254:
3252:
3249:
3247:
3244:
3241:
3239:
3237:
3234:
3231:
3228:
3227:
3224:
3221:
3218:
3215:
3213:
3210:
3208:
3205:
3202:
3200:
3198:
3195:
3192:
3189:
3188:
3185:
3182:
3179:
3176:
3174:
3172:
3169:
3167:
3164:
3161:
3159:
3157:
3154:
3151:
3148:
3147:
3144:
3141:
3138:
3135:
3133:
3130:
3128:
3125:
3122:
3120:
3118:
3115:
3112:
3109:
3108:
3105:
3102:
3099:
3096:
3094:
3092:
3089:
3087:
3084:
3081:
3079:
3077:
3074:
3071:
3068:
3067:
3064:
3061:
3058:
3055:
3053:
3051:
3048:
3046:
3043:
3040:
3038:
3036:
3033:
3030:
3027:
3026:
3004:
2987:
2984:
2981:
2971:
2950:
2936:
2926:
2905:
2884:
2863:
2846:
2843:
2840:
2830:
2809:
2788:
2786:
2772:
2765:
2751:
2744:
2730:
2723:
2722:
2719:
2717:
2712:
2689:
2686:
2683:
2674:
2656:
2653:
2650:
2635:
2632:
2624:
2614:
2595:
2592:
2589:
2585:
2581:
2579:
2554:
2551:
2548:
2542:
2539:
2533:
2527:
2524:
2521:
2518:
2515:
2506:
2500:
2497:
2494:
2488:
2485:
2476:
2470:
2464:
2461:
2455:
2452:
2441:
2430:
2427:
2410:
2401:
2398:
2392:
2389:
2377:
2371:
2362:
2359:
2350:
2347:
2338:
2332:
2323:
2320:
2314:
2311:
2302:
2296:
2290:
2287:
2281:
2278:
2267:
2249:
2242:
2236:
2233:
2230:
2227:
2212:
2207:
2200:
2194:
2191:
2185:
2182:
2170:
2165:
2158:
2152:
2149:
2146:
2143:
2131:
2126:
2119:
2116:
2113:
2110:
2107:
2093:
2079:
2073:
2070:
2067:
2064:
2055:
2049:
2043:
2040:
2034:
2031:
2025:
2019:
2013:
2010:
2007:
2004:
1998:
1992:
1989:
1986:
1983:
1980:
1968:
1966:
1956:
1953:
1950:
1946:
1934:
1929:
1917:
1901:
1895:
1892:
1889:
1886:
1877:
1871:
1865:
1862:
1856:
1853:
1847:
1841:
1835:
1832:
1829:
1826:
1820:
1814:
1811:
1808:
1805:
1802:
1796:
1791:
1788:
1785:
1781:
1767:
1744:
1741:
1738:
1729:
1711:
1708:
1705:
1690:
1687:
1678:
1677:
1673:
1671:
1667:
1635:
1631:
1627:
1623:
1616:
1613:
1610:
1605:
1602:
1598:
1591:
1586:
1583:
1579:
1567:
1552:
1548:
1544:
1540:
1536:
1533:
1530:
1525:
1522:
1518:
1514:
1509:
1506:
1502:
1492:
1490:
1483:
1479:
1437:
1433:
1426:
1423:
1420:
1415:
1411:
1404:
1401:
1398:
1393:
1389:
1382:
1377:
1373:
1364:
1351:
1347:
1343:
1340:
1337:
1332:
1328:
1324:
1321:
1318:
1313:
1309:
1305:
1300:
1296:
1286:
1284:
1274:
1271:
1268:
1264:
1252:
1247:
1235:
1212:. Then shift
1197:
1194:
1191:
1187:
1175:
1171:
1153:
1149:
1145:
1141:
1137:
1134:
1131:
1126:
1123:
1119:
1115:
1110:
1107:
1103:
1080:
1076:
1066:
1047:
1043:
1039:
1036:
1033:
1028:
1024:
1020:
1017:
1014:
1009:
1005:
1001:
996:
992:
985:
980:
977:
974:
970:
958:
956:
952:
938:
924:
885:
882:
879:
875:
852:
849:
846:
842:
828:
812:
789:
775:
773:
769:
765:
761:
757:
753:
749:
718:
715:
712:
706:
703:
697:
694:
687:
672:
669:
663:
660:
657:
644:
626:
623:
620:
607:
606:
605:
603:
581:
571:
554:
551:
548:
538:
521:
515:
509:
506:
503:
493:
476:
473:
470:
467:
464:
461:
458:
455:
452:
443:
437:
431:
428:
422:
419:
409:
408:
407:
393:
373:
370:
367:
364:
361:
358:
355:
352:
349:
340:
338:
331:
327:
324:
322:
299:
296:
294:
290:
287:
285:
270:
263:
259:
256:
253:
249:
246:
244:
229:
221:
217:
214:
213:
212:
210:
205:
203:
199:
175:
159:
151:
135:
127:
123:
119:
115:
111:
101:
99:
94:
92:
88:
84:
80:
79:an AND of ORs
76:
72:
68:
64:
60:
56:
52:
48:
44:
40:
39:Boolean logic
33:
19:
16532:
16511:Normal forms
16469:. Retrieved
16445:
16414:
16404:
16364:
16332:
16300:
16273:
16253:. Springer.
16250:
16232:
16220:
16213:Tseitin 1968
16208:
16084:
16068:
15868:
15858:
15852:
15846:
15840:
15834:
15828:
15732:
15673:
15409:
15376:is loved by
15306:
15206:
8406:
8404:
8400:
8399:
6644:
6636:
5753:
5561:
5557:
5553:
5551:
5547:
5518:
5514:
5502:
5498:
5492:
5480:
5027:
4984:
4980:
4979:
4947:
4944:
4880:
4735:
4686:
4495:
4399:, then both
4367:
4165:
4163:as follows:
4113:rather than
4108:
4031:
3752:
3722:
3605:
3601:
3501:
3348:
3250:
3170:
3090:
3049:
2713:
2620:
1918:
1768:
1679:
1675:
1674:
1669:
1668:
1173:
1172:
1067:
959:
954:
953:
930:
802:builds upon
781:
745:
601:
599:
341:
336:
334:
329:
325:
320:
297:
292:
288:
283:
261:
257:
251:
247:
242:
219:
215:
206:
197:
114:disjunctions
107:
97:
95:
78:
74:
54:
50:
46:
36:
16563:Horn clause
16471:31 December
16184:Howson 2005
16078:linear time
15645:disjunction
15637:Horn clause
6653:Convert to
6645:To convert
5511:NP-complete
5505:variables.
4707:variables,
4115:equivalence
2716:truth table
2623:truth table
1068:where each
289:Disjunction
284:Disjunction
258:Disjunction
252:Disjunction
220:Disjunction
110:conjunction
67:disjunction
59:conjunction
57:if it is a
16643:Categories
16168:References
15655:, literal.
15356:, or else
7899:; replace
7805:; replace
7711:; replace
7048:; replace
6923:; replace
6715:; replace
5564:variables
5556:CNF" (for
4736:There are
4491:equivalent
770:, and the
756:equivalent
104:Definition
16452:EMS Press
16146:≤
16130:≤
16104:≤
16098:≤
16051:∧
16031:∨
15997:∧
15991:∧
15982:∨
15973:∧
15964:∨
15955:∧
15815:ϕ
15785:ϕ
15762:≤
15746:≤
15716:ϕ
15693:≤
15687:≤
15653:unnegated
15556:∨
15512:¬
15506:∧
15459:∨
15020:¬
14560:∨
14497:¬
14454:∧
14307:∨
14015:∨
13875:¬
13853:∧
13576:∨
13446:¬
13425:∧
13288:∃
13253:∀
13117:∨
12987:¬
12966:∧
12832:∃
12799:∃
12772:∀
12635:∨
12504:¬
12483:∧
12365:∃
12313:∃
12289:∀
12116:∃
12072:∨
11941:¬
11920:∧
11805:∃
11754:∀
11581:∃
11538:∨
11408:¬
11387:∧
11269:∃
11215:∀
11045:∃
11003:∨
10873:¬
10852:∧
10747:¬
10724:¬
10695:∃
10644:∀
10474:∃
10432:∨
10280:∨
10175:¬
10130:¬
10105:∃
10054:∀
9884:∃
9842:∨
9710:∨
9606:¬
9573:∀
9523:¬
9498:∀
9328:∃
9285:→
9152:∨
9048:¬
9018:∀
8967:∀
8798:∃
8756:→
8623:→
8507:∀
8456:∀
8378:∨
8369:∧
8360:∨
8328:∧
8319:∨
8276:is a new
8225:…
8186:∀
8183:…
8170:∀
8134:∃
8120:∀
8117:…
8104:∀
8081:∨
8061:∧
8041:¬
7966:∨
7954:∃
7916:∃
7910:∨
7872:∧
7860:∃
7822:∃
7816:∧
7778:∨
7766:∀
7728:∀
7722:∨
7684:∧
7672:∀
7634:∀
7628:∧
7612:Skolemize
7556:∃
7550:∨
7512:¬
7509:∧
7474:∃
7465:∀
7407:∃
7401:∨
7363:¬
7360:∧
7325:∃
7316:∀
7278:∃
7272:∨
7251:∀
7220:¬
7188:¬
7182:∀
7144:∃
7138:¬
7106:¬
7100:∃
7062:∀
7056:¬
7013:¬
7010:¬
6984:¬
6978:∨
6969:¬
6940:∧
6931:¬
6905:¬
6899:∧
6890:¬
6861:∨
6852:¬
6825:↔
6805:→
6779:∨
6773:¬
6767:∧
6758:¬
6755:∨
6726:↔
6700:∨
6694:¬
6671:→
6516:…
6401:…
6279:…
6101:∨
6080:…
6059:∨
5986:∧
5965:…
5944:∧
5864:∨
5843:…
5822:∨
5720:∨
5717:…
5714:∨
5701:∨
5695:¬
5672:∨
5664:−
5653:∨
5650:…
5647:∨
5607:∨
5604:…
5601:∨
5588:∨
5585:…
5582:∨
5457:∨
5451:¬
5448:∨
5442:∨
5436:¬
5426:∧
5417:∨
5411:¬
5408:∨
5399:∧
5390:∨
5384:¬
5381:∨
5375:¬
5369:∧
5360:∨
5354:∨
5348:¬
5342:∧
5333:¬
5330:∨
5324:∨
5318:¬
5308:∧
5299:∨
5293:¬
5287:∧
5282:_
5272:∨
5260:∧
5255:_
5245:¬
5242:∨
5230:∧
5225:_
5215:∨
5209:¬
5200:∧
5195:_
5185:¬
5182:∨
5176:¬
5167:∧
5158:∨
5152:¬
5142:∧
5130:∧
5121:¬
5115:∧
5103:∧
5094:¬
5058:−
5047:×
4924:−
4853:¬
4834:…
4818:¬
4789:¬
4718:≥
4657:∧
4590:∧
4577:≡
4537:¬
4534:∨
4521:¬
4518:∨
4338:∨
4325:¬
4319:∧
4303:∨
4290:¬
4284:∧
4281:…
4278:∧
4262:∨
4249:¬
4243:∧
4227:∨
4214:¬
4208:∧
4192:∨
4189:…
4186:∨
4138:…
4086:for each
4002:∨
3999:…
3996:∨
3983:∨
3967:∧
3964:…
3961:∧
3945:∨
3942:…
3939:∨
3926:∨
3910:∧
3894:∨
3891:…
3888:∨
3875:∨
3859:∧
3843:∨
3840:…
3837:∨
3824:∨
3808:∧
3792:∨
3789:…
3786:∨
3773:∨
3750:clauses:
3696:∧
3680:∨
3677:…
3674:∨
3658:∧
3642:∨
3626:∧
3555:¬
3510:ϕ
3482:∨
3476:¬
3473:∨
3464:∧
3455:∨
3449:∨
3443:¬
3437:∧
3428:∨
3422:¬
3419:∨
3413:¬
3407:∧
3398:¬
3395:∨
3389:¬
3386:∨
3380:¬
3357:ϕ
2985:⊕
2958:↑
2934:¬
2892:↔
2844:∧
2817:¬
2687:⊕
2678:↑
2672:¬
2666:↔
2654:∧
2645:¬
2633:ϕ
2586:ϕ
2572:¬
2569:¬
2552:∨
2546:¬
2543:∨
2534:∧
2525:∨
2519:∨
2513:¬
2507:∧
2498:∨
2492:¬
2489:∨
2483:¬
2477:∧
2468:¬
2465:∨
2459:¬
2456:∨
2450:¬
2444:↔
2431:×
2408:¬
2405:¬
2402:∨
2396:¬
2393:∨
2387:¬
2384:¬
2378:∧
2369:¬
2366:¬
2363:∨
2357:¬
2354:¬
2351:∨
2345:¬
2339:∧
2330:¬
2327:¬
2324:∨
2318:¬
2315:∨
2309:¬
2303:∧
2294:¬
2291:∨
2285:¬
2282:∨
2276:¬
2270:↔
2250:_
2240:¬
2237:∧
2231:∧
2225:¬
2219:¬
2213:∧
2208:_
2198:¬
2195:∧
2189:¬
2186:∧
2177:¬
2171:∧
2166:_
2156:¬
2153:∧
2147:∧
2138:¬
2132:∧
2127:_
2117:∧
2111:∧
2102:¬
2096:↔
2077:¬
2074:∧
2068:∧
2062:¬
2056:∨
2047:¬
2044:∧
2038:¬
2035:∧
2026:∨
2017:¬
2014:∧
2008:∧
1999:∨
1990:∧
1984:∧
1972:¬
1947:ϕ
1943:¬
1940:¬
1937:↔
1930:ϕ
1899:¬
1896:∧
1890:∧
1884:¬
1878:∨
1869:¬
1866:∧
1860:¬
1857:∧
1848:∨
1839:¬
1836:∧
1830:∧
1821:∨
1812:∧
1806:∧
1782:ϕ
1778:¬
1742:⊕
1733:↑
1727:¬
1721:↔
1709:∧
1700:¬
1688:ϕ
1620:¬
1617:∨
1614:…
1611:∨
1595:¬
1592:∨
1576:¬
1570:↔
1537:∧
1534:…
1531:∧
1515:∧
1496:¬
1476:¬
1430:¬
1427:∧
1424:…
1421:∧
1408:¬
1405:∧
1402:…
1399:∧
1386:¬
1383:∧
1370:¬
1367:↔
1344:∨
1341:…
1338:∨
1325:∨
1322:…
1319:∨
1306:∨
1290:¬
1265:ϕ
1261:¬
1258:¬
1255:↔
1248:ϕ
1220:¬
1188:ϕ
1184:¬
1176:: Negate
1138:∧
1135:…
1132:∧
1116:∧
1040:∨
1037:…
1034:∨
1021:∨
1018:…
1015:∨
1002:∨
971:ϕ
967:¬
939:ϕ
911:¬
908:¬
876:ϕ
843:ϕ
839:¬
829:: step 1.
813:ϕ
810:¬
790:ϕ
716:∧
707:∨
698:∧
670:∧
661:∨
652:¬
624:∧
615:¬
552:∨
516:∧
507:∨
474:∨
468:∨
462:∨
456:∨
450:¬
444:∧
435:¬
432:∨
426:¬
423:∨
308:¬
271:∨
230:∧
211:for CNF:
184:¬
160:∧
136:∨
16513:in logic
16396:(1968).
16383:Archived
15649:literals
15616:See also
8256:, where
6649:to CNF:
5543:validity
4489:but not
337:Variable
330:Variable
321:Variable
120:. As in
118:literals
71:literals
16454:, 2001
13709:by 3.2
13241:by 3.1
12760:by 3.1
11742:by 1.2
11203:by 1.2
10632:by 1.2
10042:by 1.1
9486:by 1.1
8415:redexes
8401:Example
5535:NP-hard
4981:Example
1676:Example
326:Literal
298:Literal
293:Literal
262:Literal
196:). The
172:), and
81:. As a
63:clauses
43:formula
16422:
16375:
16344:
16319:
16281:
16257:
15641:clause
15199:clause
8411:clause
5539:dually
1670:Step 3
1174:Step 2
955:Step 1
386:, and
335:Where
45:is in
16610:Other
16401:(PDF)
16386:(PDF)
16369:(PDF)
16297:(PDF)
15665:Notes
14657:by 5
14149:by 4
12277:by 2
8346:with
8162:with
8073:, or
7946:with
7852:with
7758:with
7664:with
7174:with
7092:with
7028:with
6958:with
6879:with
6741:with
6686:with
5742:with
5523:2-SAT
5507:3-SAT
4455:model
1464:where
831:Then
750:each
53:) or
16473:2023
16420:ISBN
16373:ISBN
16342:ISBN
16317:ISBN
16279:ISBN
16255:ISBN
16200:see
16043:and
16019:and
15863:q)))
15854:NAND
15839:q))
15827:= ((
15777:for
15708:for
6817:and
5687:and
5005:and
4900:has
4426:and
89:and
41:, a
16309:doi
16074:DNF
16023:of
15860:XOR
15857:(p
15851:r)
15848:NOT
15842:IFF
15836:AND
15833:(p
15830:NOT
15647:of
15643:(a
8443:):
8428:red
8417:in
5531:DNF
5509:is
4368:An
4059:or
3369:is
2718:is
825:in
746:In
602:not
250:→ (
248:CNF
243:CNF
218:→ (
216:CNF
198:not
174:not
150:and
148:),
77:or
69:of
51:CNF
37:In
16645::
16464:.
16450:,
16444:,
16381:.
16358:;
16340:.
16336:.
16315:.
16303:.
16191:^
16176:^
15934:^
15845:((
15801:^
15407:.
8053:,
7130:;
6657:.
6631:.
6235:11
5799:11
5537:;
5485:.
5067:15
5025:.
4878:.
4733:.
4679:.
4493:.
4106:.
2711:.
1766:.
1170:.
1065:,
951:.
923:.
774:.
766:,
762::
328:→
300:→
291:→
260:→
222:)
204:.
126:or
93:.
16549:)
16545:(
16503:e
16496:t
16489:v
16475:.
16428:.
16350:.
16325:.
16311::
16287:.
16263:.
16227:.
16215:.
16141:i
16137:n
16133:i
16127:1
16101:m
16095:1
16003:)
16000:b
15994:b
15988:a
15985:(
15979:)
15976:a
15970:b
15967:(
15961:)
15958:b
15952:a
15949:(
15916:n
15913:2
15909:2
15905:=
15901:|
15897:)
15894:L
15891:(
15886:P
15880:|
15757:i
15753:n
15749:i
15743:1
15690:m
15684:1
15600:)
15597:)
15594:x
15591:,
15588:)
15585:x
15582:(
15579:g
15576:(
15572:s
15569:e
15566:v
15563:o
15560:L
15553:)
15550:)
15547:x
15544:(
15541:f
15538:,
15535:x
15532:(
15528:s
15525:e
15522:v
15519:o
15516:L
15509:(
15503:)
15500:)
15497:x
15494:,
15491:)
15488:x
15485:(
15482:g
15479:(
15475:s
15472:e
15469:v
15466:o
15463:L
15456:)
15453:)
15450:x
15447:(
15444:f
15441:(
15437:l
15434:a
15431:m
15428:i
15425:n
15422:A
15418:(
15405:"
15393:)
15390:x
15387:(
15384:g
15364:x
15344:)
15341:x
15338:(
15335:f
15315:x
15307:"
15293:x
15273:)
15270:x
15267:(
15264:f
15244:x
15224:)
15221:x
15218:(
15215:g
15197:(
15183:}
15162:}
15141:)
15138:x
15135:,
15132:)
15129:x
15126:(
15123:g
15120:(
15116:s
15113:e
15110:v
15107:o
15104:L
15082:,
15061:)
15058:)
15055:x
15052:(
15049:f
15046:,
15043:x
15040:(
15036:s
15033:e
15030:v
15027:o
15024:L
14999:{
14978:,
14957:}
14934:)
14931:x
14928:,
14907:)
14904:x
14901:(
14898:g
14877:(
14873:s
14870:e
14867:v
14864:o
14861:L
14833:,
14798:)
14777:)
14774:x
14771:(
14768:f
14747:(
14743:l
14740:a
14737:m
14734:i
14731:n
14728:A
14694:{
14673:{
14641:)
14620:)
14617:x
14614:,
14611:)
14608:x
14605:(
14602:g
14599:(
14595:s
14592:e
14589:v
14586:o
14583:L
14538:)
14535:)
14532:x
14529:(
14526:f
14523:,
14520:x
14517:(
14513:s
14510:e
14507:v
14504:o
14501:L
14476:(
14432:)
14409:)
14406:x
14403:,
14382:)
14379:x
14376:(
14373:g
14352:(
14348:s
14345:e
14342:v
14339:o
14336:L
14271:)
14250:)
14247:x
14244:(
14241:f
14220:(
14216:l
14213:a
14210:m
14207:i
14204:n
14201:A
14167:(
14117:)
14114:x
14111:,
14090:)
14087:x
14084:(
14081:g
14060:(
14056:s
14053:e
14050:v
14047:o
14044:L
13991:)
13970:)
13949:)
13946:x
13943:(
13940:f
13919:,
13916:x
13913:(
13909:s
13906:e
13903:v
13900:o
13897:L
13831:)
13810:)
13807:x
13804:(
13801:f
13780:(
13776:l
13773:a
13770:m
13767:i
13764:n
13761:A
13735:(
13677:)
13674:x
13671:,
13650:)
13647:x
13644:(
13641:g
13620:(
13616:s
13613:e
13610:v
13607:o
13604:L
13553:)
13532:)
13511:y
13490:,
13487:x
13484:(
13480:s
13477:e
13474:v
13471:o
13468:L
13404:)
13383:y
13362:(
13358:l
13355:a
13352:m
13349:i
13346:n
13343:A
13317:(
13291:y
13256:x
13209:)
13206:x
13203:,
13182:z
13161:(
13157:s
13154:e
13151:v
13148:o
13145:L
13094:)
13073:)
13052:y
13031:,
13028:x
13025:(
13021:s
13018:e
13015:v
13012:o
13009:L
12945:)
12924:y
12903:(
12899:l
12896:a
12893:m
12890:i
12887:n
12884:A
12858:(
12835:y
12802:z
12775:x
12728:)
12725:x
12722:,
12701:z
12680:(
12676:s
12673:e
12670:v
12667:o
12664:L
12613:)
12590:)
12569:y
12548:,
12545:x
12542:(
12538:s
12535:e
12532:v
12529:o
12526:L
12462:)
12441:y
12420:(
12416:l
12413:a
12410:m
12407:i
12404:n
12401:A
12368:y
12341:(
12316:z
12292:x
12247:)
12226:)
12223:x
12220:,
12199:z
12178:(
12174:s
12171:e
12168:v
12165:o
12162:L
12139:z
12094:(
12050:)
12027:)
12006:y
11985:,
11982:x
11979:(
11975:s
11972:e
11969:v
11966:o
11963:L
11899:)
11878:y
11857:(
11853:l
11850:a
11847:m
11844:i
11841:n
11838:A
11808:y
11784:(
11757:x
11712:)
11691:)
11688:x
11685:,
11664:y
11643:(
11639:s
11636:e
11633:v
11630:o
11627:L
11604:y
11559:(
11517:)
11494:)
11473:y
11452:,
11449:x
11446:(
11442:s
11439:e
11436:v
11433:o
11430:L
11366:)
11345:y
11324:(
11320:l
11317:a
11314:m
11311:i
11308:n
11305:A
11272:y
11245:(
11218:x
11173:)
11152:)
11149:x
11146:,
11125:y
11104:(
11100:s
11097:e
11094:v
11091:o
11088:L
11066:y
11024:(
10982:)
10959:)
10938:y
10917:,
10914:x
10911:(
10907:s
10904:e
10901:v
10898:o
10895:L
10831:)
10810:y
10789:(
10785:l
10782:a
10779:m
10776:i
10773:n
10770:A
10698:y
10674:(
10647:x
10602:)
10581:)
10578:x
10575:,
10554:y
10533:(
10529:s
10526:e
10523:v
10520:o
10517:L
10495:y
10453:(
10411:)
10390:)
10369:)
10348:y
10327:,
10324:x
10321:(
10317:s
10314:e
10311:v
10308:o
10305:L
10258:)
10237:y
10216:(
10212:l
10209:a
10206:m
10203:i
10200:n
10197:A
10152:(
10108:y
10084:(
10057:x
10012:)
9991:)
9988:x
9985:,
9964:y
9943:(
9939:s
9936:e
9933:v
9930:o
9927:L
9905:y
9863:(
9821:)
9798:)
9777:y
9756:,
9753:x
9750:(
9746:s
9743:e
9740:v
9737:o
9734:L
9689:)
9668:y
9647:(
9643:l
9640:a
9637:m
9634:i
9631:n
9628:A
9576:y
9549:(
9501:x
9456:)
9435:)
9432:x
9429:,
9408:y
9387:(
9383:s
9380:e
9377:v
9374:o
9371:L
9349:y
9307:(
9263:)
9240:)
9219:y
9198:,
9195:x
9192:(
9188:s
9185:e
9182:v
9179:o
9176:L
9131:)
9110:y
9089:(
9085:l
9082:a
9079:m
9076:i
9073:n
9070:A
9021:y
8997:(
8970:x
8926:)
8905:)
8902:x
8899:,
8878:y
8857:(
8853:s
8850:e
8847:v
8844:o
8841:L
8819:y
8777:(
8735:)
8712:)
8691:y
8670:,
8667:x
8664:(
8660:s
8657:e
8654:v
8651:o
8648:L
8601:)
8580:y
8559:(
8555:l
8552:a
8549:m
8546:i
8543:n
8540:A
8510:y
8486:(
8459:x
8396:.
8384:)
8381:R
8375:P
8372:(
8366:)
8363:Q
8357:P
8354:(
8334:)
8331:R
8325:Q
8322:(
8316:P
8284:n
8264:f
8244:)
8241:)
8236:n
8232:x
8228:,
8222:,
8217:1
8213:x
8209:(
8206:f
8203:(
8200:P
8194:n
8190:x
8178:1
8174:x
8150:)
8147:y
8144:(
8141:P
8137:y
8128:n
8124:x
8112:1
8108:x
8093:.
8021:P
8001:x
7981:)
7978:)
7975:x
7972:(
7969:Q
7963:P
7960:(
7957:x
7934:)
7931:)
7928:x
7925:(
7922:Q
7919:x
7913:(
7907:P
7887:)
7884:)
7881:x
7878:(
7875:Q
7869:P
7866:(
7863:x
7840:)
7837:)
7834:x
7831:(
7828:Q
7825:x
7819:(
7813:P
7793:)
7790:)
7787:x
7784:(
7781:Q
7775:P
7772:(
7769:x
7746:)
7743:)
7740:x
7737:(
7734:Q
7731:x
7725:(
7719:P
7699:)
7696:)
7693:x
7690:(
7687:Q
7681:P
7678:(
7675:x
7652:)
7649:)
7646:x
7643:(
7640:Q
7637:x
7631:(
7625:P
7606:.
7594:]
7591:)
7588:x
7585:,
7582:z
7579:(
7575:s
7572:e
7569:v
7566:o
7563:L
7559:z
7553:[
7547:]
7544:)
7541:y
7538:,
7535:x
7532:(
7528:s
7525:e
7522:v
7519:o
7516:L
7506:)
7503:y
7500:(
7496:l
7493:a
7490:m
7487:i
7484:n
7481:A
7477:y
7471:[
7468:x
7445:]
7442:)
7439:x
7436:,
7433:y
7430:(
7426:s
7423:e
7420:v
7417:o
7414:L
7410:y
7404:[
7398:]
7395:)
7392:y
7389:,
7386:x
7383:(
7379:s
7376:e
7373:v
7370:o
7367:L
7357:)
7354:y
7351:(
7347:l
7344:a
7341:m
7338:i
7335:n
7332:A
7328:y
7322:[
7319:x
7296:)
7293:)
7290:x
7287:(
7284:Q
7281:x
7275:(
7269:)
7266:)
7263:x
7260:(
7257:P
7254:x
7248:(
7200:)
7197:x
7194:(
7191:P
7185:x
7162:)
7159:)
7156:x
7153:(
7150:P
7147:x
7141:(
7118:)
7115:x
7112:(
7109:P
7103:x
7080:)
7077:)
7074:x
7071:(
7068:P
7065:x
7059:(
7036:P
7016:P
6990:)
6987:Q
6981:(
6975:)
6972:P
6966:(
6946:)
6943:Q
6937:P
6934:(
6911:)
6908:Q
6902:(
6896:)
6893:P
6887:(
6867:)
6864:Q
6858:P
6855:(
6837:.
6785:)
6782:Q
6776:P
6770:(
6764:)
6761:Q
6752:P
6749:(
6729:Q
6723:P
6703:Q
6697:P
6674:Q
6668:P
6617:}
6596:}
6571:m
6567:n
6563:m
6559:l
6537:,
6495:,
6472:1
6469:m
6465:l
6443:{
6422:,
6380:,
6359:}
6334:1
6330:n
6326:1
6322:l
6300:,
6258:,
6231:l
6209:{
6188:{
6160:)
6135:m
6131:n
6127:m
6123:l
6036:1
6033:m
6029:l
6007:(
5923:)
5898:1
5894:n
5890:1
5886:l
5795:l
5773:(
5744:Z
5728:n
5724:X
5709:k
5705:X
5698:Z
5675:Z
5667:1
5661:k
5657:X
5642:1
5638:X
5615:n
5611:X
5596:k
5592:X
5577:1
5573:X
5562:k
5558:k
5554:k
5519:k
5515:k
5503:k
5499:k
5463:)
5460:q
5454:q
5445:p
5439:p
5433:(
5423:)
5420:q
5414:q
5405:p
5402:(
5396:)
5393:q
5387:q
5378:p
5372:(
5366:)
5363:q
5357:p
5351:p
5345:(
5339:)
5336:q
5327:p
5321:p
5315:(
5305:)
5302:q
5296:q
5290:(
5278:)
5275:q
5269:p
5266:(
5251:)
5248:q
5239:p
5236:(
5221:)
5218:q
5212:p
5206:(
5191:)
5188:q
5179:p
5173:(
5164:)
5161:p
5155:p
5149:(
5139:)
5136:q
5133:(
5127:)
5124:q
5118:(
5112:)
5109:p
5106:(
5100:)
5097:p
5091:(
5064:=
5061:1
5053:)
5050:2
5044:2
5041:(
5037:2
5013:q
4993:p
4961:n
4957:2
4930:)
4927:1
4919:n
4916:2
4912:2
4908:(
4888:L
4866:}
4861:n
4857:p
4850:,
4845:n
4841:p
4837:,
4831:,
4826:2
4822:p
4815:,
4810:2
4806:p
4802:,
4797:1
4793:p
4786:,
4781:1
4777:p
4773:{
4770:=
4767:L
4747:n
4744:2
4721:1
4715:n
4695:n
4665:i
4661:Y
4652:i
4648:X
4625:i
4621:Z
4598:i
4594:Y
4585:i
4581:X
4572:i
4568:Z
4545:i
4541:Y
4529:i
4525:X
4513:i
4509:Z
4470:i
4466:Z
4439:i
4435:Y
4412:i
4408:X
4385:i
4381:Z
4354:.
4351:)
4346:n
4342:Y
4333:n
4329:Z
4322:(
4316:)
4311:n
4307:X
4298:n
4294:Z
4287:(
4275:)
4270:1
4266:Y
4257:1
4253:Z
4246:(
4240:)
4235:1
4231:X
4222:1
4218:Z
4211:(
4205:)
4200:n
4196:Z
4181:1
4177:Z
4173:(
4149:n
4145:Z
4141:,
4135:,
4130:1
4126:Z
4094:i
4072:i
4068:Y
4045:i
4041:X
4018:.
4015:)
4010:n
4006:Y
3991:2
3987:Y
3978:1
3974:Y
3970:(
3958:)
3953:n
3949:X
3934:2
3930:Y
3921:1
3917:Y
3913:(
3907:)
3902:n
3898:X
3883:2
3879:Y
3870:1
3866:X
3862:(
3856:)
3851:n
3847:X
3832:2
3828:X
3819:1
3815:Y
3811:(
3805:)
3800:n
3796:X
3781:2
3777:X
3768:1
3764:X
3760:(
3736:n
3732:2
3709:)
3704:n
3700:Y
3691:n
3687:X
3683:(
3671:)
3666:2
3662:Y
3653:2
3649:X
3645:(
3639:)
3634:1
3630:Y
3621:1
3617:X
3613:(
3581:V
3558:V
3532:V
3488:)
3485:r
3479:q
3470:p
3467:(
3461:)
3458:r
3452:q
3446:p
3440:(
3434:)
3431:r
3425:q
3416:p
3410:(
3404:)
3401:r
3392:q
3383:p
3377:(
3341:F
3338:T
3335:T
3330:T
3325:F
3322:T
3315:F
3312:F
3309:F
3302:F
3299:T
3296:F
3291:T
3286:F
3283:T
3276:T
3273:F
3270:F
3263:T
3260:F
3257:T
3251:F
3245:F
3242:T
3235:F
3232:T
3229:F
3222:T
3219:T
3216:F
3211:T
3206:F
3203:T
3196:T
3193:T
3190:F
3183:T
3180:F
3177:T
3171:F
3165:F
3162:T
3155:F
3152:F
3149:T
3142:T
3139:T
3136:F
3131:T
3126:F
3123:T
3116:T
3113:F
3110:T
3103:F
3100:T
3097:T
3091:F
3085:T
3082:F
3075:F
3072:T
3069:T
3062:F
3059:T
3056:F
3050:F
3044:T
3041:F
3034:T
3031:T
3028:T
3012:)
2991:)
2988:q
2982:p
2979:(
2937:r
2913:(
2871:)
2850:)
2847:q
2841:p
2838:(
2796:(
2773:r
2752:q
2731:p
2699:)
2696:)
2693:)
2690:q
2684:p
2681:(
2675:r
2669:(
2663:)
2660:)
2657:q
2651:p
2648:(
2642:(
2639:(
2636:=
2596:F
2593:N
2590:C
2582:=
2558:)
2555:r
2549:q
2540:p
2537:(
2531:)
2528:r
2522:q
2516:p
2510:(
2504:)
2501:r
2495:q
2486:p
2480:(
2474:)
2471:r
2462:q
2453:p
2447:(
2434:)
2428:4
2425:(
2414:)
2411:r
2399:q
2390:p
2381:(
2375:)
2372:r
2360:q
2348:p
2342:(
2336:)
2333:r
2321:q
2312:p
2306:(
2300:)
2297:r
2288:q
2279:p
2273:(
2246:)
2243:r
2234:q
2228:p
2222:(
2204:)
2201:r
2192:q
2183:p
2180:(
2162:)
2159:r
2150:q
2144:p
2141:(
2123:)
2120:r
2114:q
2108:p
2105:(
2086:}
2083:)
2080:r
2071:q
2065:p
2059:(
2053:)
2050:r
2041:q
2032:p
2029:(
2023:)
2020:r
2011:q
2005:p
2002:(
1996:)
1993:r
1987:q
1981:p
1978:(
1975:{
1969:=
1957:F
1954:N
1951:D
1905:)
1902:r
1893:q
1887:p
1881:(
1875:)
1872:r
1863:q
1854:p
1851:(
1845:)
1842:r
1833:q
1827:p
1824:(
1818:)
1815:r
1809:q
1803:p
1800:(
1797:=
1792:F
1789:N
1786:D
1754:)
1751:)
1748:)
1745:q
1739:p
1736:(
1730:r
1724:(
1718:)
1715:)
1712:q
1706:p
1703:(
1697:(
1694:(
1691:=
1643:)
1636:i
1632:n
1628:i
1624:l
1606:2
1603:i
1599:l
1587:1
1584:i
1580:l
1573:(
1560:)
1553:i
1549:n
1545:i
1541:l
1526:2
1523:i
1519:l
1510:1
1507:i
1503:l
1499:(
1493:=
1484:i
1480:C
1438:m
1434:C
1416:i
1412:C
1394:2
1390:C
1378:1
1374:C
1357:)
1352:m
1348:C
1333:i
1329:C
1314:2
1310:C
1301:1
1297:C
1293:(
1287:=
1275:F
1272:N
1269:D
1198:F
1195:N
1192:D
1154:i
1150:n
1146:i
1142:l
1127:2
1124:i
1120:l
1111:1
1108:i
1104:l
1081:i
1077:C
1053:)
1048:m
1044:C
1029:i
1025:C
1010:2
1006:C
997:1
993:C
989:(
986:=
981:F
978:N
975:D
886:F
883:N
880:C
853:F
850:N
847:D
725:)
722:)
719:E
713:D
710:(
704:B
701:(
695:A
673:C
667:)
664:B
658:A
655:(
630:)
627:B
621:A
618:(
585:)
582:A
579:(
558:)
555:B
549:A
546:(
525:)
522:C
519:(
513:)
510:B
504:A
501:(
480:)
477:F
471:D
465:F
459:E
453:D
447:(
441:)
438:C
429:B
420:A
417:(
394:F
374:E
371:,
368:D
365:,
362:C
359:,
356:B
353:,
350:A
254:)
176:(
152:(
128:(
49:(
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.