7182:
5798:
6337:
608:
6813:
7171:
6731:
6224:
221:
formula. In the context of predicate logic, many authors define a tautology to be a sentence that can be obtained by taking a tautology of propositional logic, and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). The set of such
1973:(i.e., proof system) for propositional logic, as a simpler variant of the deductive systems employed for first-order logic (see Kleene 1967, Sec 1.9 for one such system). A proof of a tautology in an appropriate deduction system may be much shorter than a complete truth table (a formula with
3239:
2884:
is the number of variables in the formula. This exponential growth in the computation length renders the truth table method useless for formulas with thousands of propositional variables, as contemporary computing hardware cannot execute the algorithm in a feasible time period.
54:
having a fixed meaning. For example, a formula that states, "the ball is green or the ball is not green," is always true, regardless of what a ball is and regardless of its colour. Tautology is usually, though not always, used to refer to valid formulas of
2958:
A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). For example, because
339:
Everything that is a proposition of logic has got to be in some sense or the other like a tautology. It has got to be something that has some peculiar quality, which I do not know how to define, that belongs to logical propositions but not to
2869:, which means that given unlimited computational resources it can always be used to mechanistically determine whether a sentence is a tautology. This means, in particular, the set of tautologies over a fixed finite or countable alphabet is a
307:
that a truth is analytic exactly if it can be derived using logic. However, he maintained a distinction between analytic truths (i.e., truths based only on the meanings of their terms) and tautologies (i.e., statements devoid of content).
1463:, represented by the first three columns of the following table. The remaining columns show the truth of subformulas of the formula above, culminating in a column showing the truth value of the original formula under each valuation.
1356:
variables occurring in a formula then there are 2 distinct valuations for the formula. Therefore, the task of determining whether or not the formula is a tautology is a finite and mechanical one: one needs only to evaluate the
2813:
3083:
1032:
374:
Modern textbooks more commonly restrict the use of 'tautology' to valid sentences of propositional logic, or valid sentences of predicate logic that can be reduced to propositional tautologies by substitution.
1446:
3466:
1747:
945:
1238:
852:
3063:
3528:
541:
1128:
2846:
The problem of constructing practical algorithms to determine whether sentences with large numbers of propositional variables are tautologies is an area of contemporary research in the area of
2639:
397:
consists of propositional variables connected by logical connectives, built up in such a way that the truth of the overall formula can be deduced from the truth or falsity of each variable. A
2135:
1315:
6522:
371:
followed this usage and it appears in textbooks such as that of Lewis and
Langford. This broad use of the term is less common today, though some textbooks continue to use it.
3343:
6551:
3604:
4177:
1606:
743:
3567:
Whether a given formula is a tautology depends on the formal system of logic that is in use. For example, the following formula is a tautology of classical logic but not of
6627:
2986:
2274:
1672:
6652:
6427:
6598:
6398:
3392:
3291:
2348:
2043:
584:
6373:
594:
must be assigned F, which will make one of the following disjunct to be assigned T. In natural language, either both A and B are true or at least one of them is false.
6900:
4852:
2322:
1567:
121:
2917:
2676:
317:
in 1921, Ludwig
Wittgenstein proposed that statements that can be deduced by logical deduction are tautological (empty of meaning), as well as being analytic truths.
6681:
3557:
2709:
2069:
1633:
1341:
791:
705:
475:
447:
6718:
6493:
6456:
6327:
427:
177:
157:
6281:
3363:
3311:
3262:
2526:
2504:
2482:
2460:
2438:
2413:
2391:
2369:
2295:
2244:
2222:
2200:
2178:
2156:
2093:
1538:
1513:
1488:
4935:
4076:
2943:. These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between
2865:, and the valuation corresponding to that row is a valuation that does not satisfy the sentence being tested. This method for verifying tautologies is an
1361:
of the formula under each of its possible valuations. One algorithmic method for verifying that every valuation makes the formula to be true is to make a
238:
The word tautology was used by the ancient Greeks to describe a statement that was asserted to be true merely by virtue of saying the same thing twice, a
82:
if it is true under at least one interpretation, and thus a tautology is a formula whose negation is unsatisfiable. In other words, it cannot be false.
2720:
2931:
can solve the satisfiability problem, although some algorithms perform well on special classes of formulas, or terminate quickly on many instances.
6766:
5249:
3234:{\displaystyle (((\exists xRx)\land \lnot (\exists xSx))\to \forall xTx)\Leftrightarrow ((\exists xRx)\to ((\lnot \exists xSx)\to \forall xTx)).}
5407:
2939:
The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in
331:
at first argued against these remarks by
Wittgenstein and Poincaré, claiming that mathematical truths were not only non-tautologous but were
4195:
6893:
5262:
4585:
978:
401:
is a function that assigns each propositional variable to either T (for truth) or F (for falsity). So by using the propositional variables
217:—a feature absent from sentences of propositional logic. Indeed, in propositional logic, there is no distinction between a tautology and a
5880:
6242:
6009:
4847:
1374:
5267:
5257:
4994:
4200:
3397:
1678:
4745:
4191:
2955:), which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide.
879:
6274:
6158:
5403:
4002:
3984:
3962:
1985:
propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed.
351:
Many logicians in the early 20th century used the term 'tautology' for any formula that is universally valid, whether a formula of
1163:
801:
5500:
5244:
4069:
2991:
4805:
4498:
4239:
7220:
6886:
5834:
3477:
6163:
5761:
5463:
5226:
5221:
5046:
4467:
4151:
2889:
2880:, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2, where
313:
227:
6238:
554:
either T or F. But no matter how this assignment is made, the overall formula will come out true. For if the first disjunct
484:
5756:
5539:
5456:
5169:
5100:
4977:
4219:
4047:
1059:
973:. For instance, "If it's not bound, we know it's a book, if it's not bound, we know it's also not a book, so it is bound".
4827:
7205:
6267:
5681:
5507:
5193:
4426:
2594:
4832:
7215:
6827:
6759:
5164:
4903:
4161:
4062:
4042:
1158:. "If it's bound, then it's a book and if it's a book, then it's on that shelf, so if it's bound, it's on that shelf".
79:
5559:
5554:
3920:
1054:. "If it is not both a book and bound, then we are sure that it's not a book or that it's not bound" and vice versa.
7235:
7151:
7146:
6189:
5488:
5078:
4472:
4440:
4131:
20:
4205:
6168:
6093:
5875:
5778:
5727:
5624:
5122:
5083:
4560:
2928:
2847:
2547:, that allows additional tautologies to be constructed from a given tautology (Kleene 1967 sec. 3). Suppose that
183:) representing an arbitrary contradiction; in any symbolism, a tautology may be substituted for the truth value "
5619:
4234:
1352:
The problem of determining whether a formula is a tautology is fundamental in propositional logic. If there are
250:
to denote a certain type of propositional formula, without the pejorative connotations it originally possessed.
206:
exists for testing whether a given formula is always satisfied (equiv., whether its negation is unsatisfiable).
7135:
6066:
5549:
5088:
4940:
4923:
4646:
4126:
1994:
93:. Such a formula can be made either true or false based on the values assigned to its propositional variables.
90:
6631:
6602:
6150:
5451:
5428:
5389:
5275:
5216:
4862:
4782:
4626:
4570:
4183:
3630:
3625:
2099:
1270:
6507:
7210:
6752:
5741:
5468:
5446:
5413:
5306:
5152:
5137:
5110:
5061:
4945:
4880:
4705:
4671:
4666:
4540:
4371:
4348:
1155:
754:
651:
360:
323:
214:
199:
35:
7225:
6910:
6526:
6472:
6204:
5671:
5524:
5316:
5034:
4770:
4676:
4535:
4520:
4401:
4376:
3682:
3620:
3065:
is a tautology in first order logic. Similarly, in a first-order language with a unary relation symbols
2861:, while the truth table for a sentence that is not a tautology will contain a row whose final column is
2538:
7181:
5797:
3316:
2892:; the problem of checking tautologies is equivalent to this problem, because verifying that a sentence
2857:
illustrated above is provably correct – the truth table for a tautology will end in a column with only
6536:
6336:
3577:
7083:
7071:
6402:
6123:
5969:
5644:
5606:
5483:
5287:
5127:
5051:
5029:
4857:
4815:
4714:
4681:
4545:
4333:
4244:
3950:
3568:
2831:
1982:
1573:
1260:. "Bound things and books are on that shelf. If it's either a book or it's blue, it's on that shelf".
969:
713:
243:
75:
2485:
to be true, and so the definition of tautological implication is trivially satisfied. Similarly, if
7037:
7013:
6939:
6656:
6612:
6431:
6078:
6061:
6041:
6004:
5953:
5948:
5890:
5827:
5773:
5664:
5649:
5629:
5586:
5473:
5423:
5349:
5294:
5231:
5024:
5019:
4967:
4735:
4724:
4396:
4296:
4224:
4215:
4211:
4146:
4141:
4007:
3696:
2962:
2877:
2866:
2250:
1639:
454:
450:
384:
352:
226:
of the set of logically valid sentences of predicate logic (i.e., sentences that are true in every
191:
67:
63:
56:
43:
6637:
6412:
7230:
7186:
7079:
6985:
6981:
6583:
6383:
6291:
6014:
5943:
5900:
5802:
5571:
5534:
5519:
5512:
5495:
5281:
5147:
5073:
5056:
5009:
4822:
4731:
4565:
4550:
4510:
4462:
4447:
4435:
4391:
4366:
4136:
4085:
3976:
3635:
3368:
3267:
1977:
propositional variables requires a truth table with 2 lines, which quickly becomes infeasible as
874:. For instance, "If it's bound, it is a book; if it's not a book, it's not bound" and vice versa.
247:
27:
5299:
4755:
2327:
2022:
1051:
557:
6358:
4037:
7175:
6735:
6555:
6228:
6199:
6194:
6184:
6118:
6046:
5931:
5737:
5544:
5354:
5344:
5236:
5117:
4952:
4928:
4709:
4693:
4598:
4575:
4452:
4421:
4386:
4116:
3998:
3980:
3958:
3899:
2940:
2301:
1546:
356:
318:
195:
103:
2899:
2655:
626:
620:
6999:
6995:
6666:
6377:
6133:
5859:
5854:
5751:
5746:
5639:
5596:
5418:
5379:
5374:
5359:
5185:
5142:
5039:
4837:
4787:
4361:
4323:
3990:
3942:
3891:
3662:
3536:
3533:
is true in any first-order interpretation, but it corresponds to the propositional sentence
3471:
Not all logical validities are tautologies in first-order logic. For example, the sentence:
2827:
2688:
2048:
1970:
1612:
1320:
776:
684:
460:
432:
328:
218:
203:
97:
51:
6703:
6478:
6441:
6312:
2888:
The problem of determining whether there is any valuation that makes a formula true is the
412:
162:
142:
5979:
5921:
5732:
5722:
5676:
5659:
5614:
5576:
5478:
5398:
5205:
5132:
5105:
5093:
4999:
4913:
4887:
4842:
4810:
4611:
4413:
4356:
4306:
4271:
4229:
3691:
3652:
332:
210:
194:, where a tautology is defined as a propositional formula that is true under any possible
3879:
246:. Between 1800 and 1940, the word gained new meaning in logic, and is currently used in
7122:
7118:
7110:
7096:
7067:
7025:
7021:
7009:
6925:
6796:
6559:
6348:
6233:
5926:
5905:
5820:
5717:
5696:
5654:
5634:
5529:
5384:
4982:
4972:
4962:
4957:
4891:
4765:
4641:
4530:
4525:
4503:
4104:
3968:
3954:
3895:
3657:
3348:
3296:
3247:
2924:
2511:
2489:
2467:
2445:
2423:
2398:
2376:
2354:
2280:
2229:
2207:
2185:
2163:
2141:
2078:
1523:
1498:
1473:
1257:
871:
607:
85:
Unsatisfiable statements, both through negation and affirmation, are known formally as
2463:
tautologically implies every formula, because there is no truth valuation that causes
7199:
6973:
6968:
6862:
6857:
6776:
6697:
6693:
6306:
6083:
6024:
5691:
5369:
4876:
4661:
4651:
4621:
4606:
4276:
4019:
3932:
3711:
3706:
3701:
3672:
3667:
2870:
368:
364:
300:
296:, a statement in natural language that is true solely because of the terms involved.
293:
254:
223:
184:
86:
1264:
A minimal tautology is a tautology that is not the instance of a shorter tautology.
650:
if the formula itself is always true, regardless of which valuation is used for the
7033:
6951:
6947:
6832:
6497:
6073:
5895:
5591:
5438:
5339:
5331:
5211:
5159:
5068:
5004:
4987:
4918:
4777:
4636:
4338:
4121:
2854:
136:
47:
6867:
6791:
6606:
6573:
6108:
6103:
6056:
5701:
5581:
4760:
4750:
4697:
4381:
4301:
4286:
4166:
4111:
2920:
2896:
is a tautology is equivalent to verifying that there is no valuation satisfying
2834:
if every tautology is a theorem (derivable from axioms). An axiomatic system is
2808:{\displaystyle ((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)}
1362:
1358:
796:
the other truth value. For instance, "The cat is black or the cat is not black".
3740:
7106:
6406:
6051:
6019:
5984:
4631:
4486:
4457:
4263:
3866:
239:
6259:
3903:
3767:
6935:
6530:
6352:
6113:
5974:
5885:
5783:
5686:
4739:
4656:
4616:
4580:
4516:
4328:
4318:
4291:
3936:
3928:
3677:
2927:. It is widely believed that (equivalently for all NP-complete problems) no
2835:
89:. A formula that is neither a tautology nor a contradiction is said to be
7130:
7059:
7045:
6878:
6660:
6577:
6501:
6468:
6034:
5768:
5566:
5014:
4719:
4313:
1317:
is a tautology, but not a minimal one, because it is an instantiation of
478:
159:
is sometimes used to denote an arbitrary tautology, with the dual symbol
71:
4014:(Leipzig), v. 14, pp. 185–262, reprinted in English translation as
6964:
6837:
6435:
6098:
6029:
5364:
4156:
359:. In this broad sense, a tautology is a formula that is true under all
363:, or that is logically equivalent to the negation of a contradiction.
7088:
5936:
4054:
4023:
1027:{\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}
180:
19:
This article is about tautology in formal logic. For other uses, see
6812:
6744:
7055:
6128:
5843:
4908:
4254:
4099:
348:
refers to a proposition that is provable using the laws of logic.
202:. A key property of tautologies in propositional logic is that an
2566:
is chosen. Then the sentence obtained by replacing each variable
1441:{\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).}
6088:
3461:{\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}
1742:{\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}
1451:
There are 8 possible valuations for the propositional variables
6882:
6748:
6263:
5816:
4058:
3927:, translated from the French and German editions by Otto Bird,
940:{\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A}
265:
The identity of concepts in analytical judgments can be either
46:
that is true regardless of the interpretation of its component
601:
2842:
Efficient verification and the
Boolean satisfiability problem
1981:
increases). Proof systems are also required for the study of
761:. Any valuation for this formula must, by definition, assign
707:
corresponds to the proposition "all bound things are books".
629:
it by defining technical terminology, and by adding examples.
3646:
1233:{\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}
847:{\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}
209:
The definition of tautology can be extended to sentences in
3058:{\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}
1966:, the sentence in question is verified to be a tautology.
2714:
It follows from the substitution rule that the sentence:
5812:
3523:{\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx}
1256:
must be true as well"), which is the principle known as
6248:
393:, atomic units that represent concrete propositions. A
127:
is a tautology. Tautology is sometimes symbolized by "V
536:{\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}
6706:
6669:
6640:
6615:
6586:
6539:
6510:
6481:
6444:
6415:
6386:
6361:
6315:
3580:
3539:
3480:
3400:
3371:
3351:
3319:
3299:
3270:
3250:
3086:
2994:
2965:
2902:
2723:
2691:
2658:
2597:
2514:
2492:
2470:
2448:
2426:
2401:
2379:
2357:
2330:
2304:
2283:
2253:
2232:
2210:
2188:
2166:
2159:
is not a tautology, because any valuation that makes
2144:
2102:
2081:
2051:
2025:
1681:
1642:
1615:
1576:
1549:
1526:
1501:
1476:
1377:
1323:
1273:
1166:
1062:
981:
882:
804:
779:
716:
687:
677:
is on the shelf". Without a specific referent object
560:
487:
463:
435:
415:
165:
145:
106:
1123:{\displaystyle ((A\to B)\land (B\to C))\to (A\to C)}
757:. This formula has only one propositional variable,
6846:
6820:
6784:
6177:
6149:
6142:
5997:
5962:
5914:
5868:
5710:
5605:
5437:
5330:
5182:
4875:
4798:
4692:
4596:
4485:
4412:
4347:
4262:
4253:
4175:
4092:
2551:is a tautology and for each propositional variable
6712:
6675:
6646:
6621:
6592:
6545:
6516:
6487:
6450:
6421:
6392:
6367:
6321:
3598:
3551:
3522:
3460:
3386:
3357:
3337:
3305:
3285:
3256:
3233:
3057:
2980:
2935:Tautologies versus validities in first-order logic
2911:
2807:
2703:
2670:
2634:{\displaystyle (A\land B)\lor \lnot A\lor \lnot B}
2633:
2520:
2498:
2476:
2454:
2432:
2407:
2385:
2363:
2342:
2316:
2289:
2268:
2238:
2216:
2194:
2172:
2150:
2129:
2087:
2063:
2037:
1741:
1666:
1627:
1600:
1561:
1532:
1507:
1482:
1440:
1335:
1309:
1232:
1122:
1026:
939:
846:
785:
737:
699:
578:
535:
469:
441:
421:
171:
151:
115:
78:is a repetitive statement. In logic, a formula is
3559:which is not a tautology of propositional logic.
2419:It follows from the definition that if a formula
586:is not satisfied by a particular valuation, then
967:must be true"), which is the principle known as
281:). In the former case analytic propositions are
870:", and vice versa), which expresses the law of
615:This article may be written in a style that is
337:
263:
2947:, sentences that are true in every model, and
6894:
6760:
6275:
5828:
4070:
8:
4010:(1921). "Logisch-philosophiche Abhandlung",
3823:A Concise Introduction to Mathematical Logic
2529:is tautologically implied by every formula.
2071:being a tautology (Kleene 1967 p. 27).
1962:Because each row of the final column shows
335:, he later spoke in favor of them in 1918:
6919:
6901:
6887:
6879:
6767:
6753:
6745:
6282:
6268:
6260:
6146:
5911:
5835:
5821:
5813:
4896:
4491:
4259:
4077:
4063:
4055:
654:. There are infinitely many tautologies.
66:first applied the term to redundancies of
16:In logic, a statement which is always true
6705:
6668:
6639:
6614:
6585:
6538:
6509:
6480:
6443:
6414:
6385:
6360:
6314:
3579:
3538:
3479:
3399:
3370:
3350:
3318:
3298:
3269:
3249:
3085:
3077:, the following sentence is a tautology:
2993:
2964:
2901:
2722:
2690:
2657:
2596:
2513:
2491:
2469:
2447:
2425:
2400:
2378:
2356:
2329:
2303:
2282:
2252:
2231:
2209:
2187:
2165:
2143:
2101:
2080:
2050:
2024:
1680:
1641:
1614:
1575:
1548:
1525:
1500:
1475:
1376:
1322:
1272:
1165:
1061:
980:
881:
803:
778:
715:
686:
559:
486:
462:
434:
414:
164:
144:
105:
2919:. The Boolean satisfiability problem is
1465:
1365:that includes every possible valuation.
546:A valuation here must assign to each of
481:, the following formula can be obtained:
187:", as symbolized, for instance, by "1".
3731:
2988:is a tautology of propositional logic,
457:respectively, and the unary connective
3810:. Oxford University Press. p. 63.
2130:{\displaystyle A\land (B\lor \lnot B)}
2019:to be true. This situation is denoted
1310:{\displaystyle (A\lor B)\to (A\lor B)}
1050:", and vice versa), which is known as
646:A formula of propositional logic is a
6517:{\displaystyle \not \leftrightarrow }
673:is a book", and C represents "object
7:
3947:A Mathematical Introduction to Logic
3768:"tautology | Definition & Facts"
3762:
3760:
2203:false. But any valuation that makes
1154:"), which is the principle known as
6010:Analytic and synthetic propositions
5881:Formal semantics (natural language)
3563:Tautologies in Non-Classical Logics
2822:Semantic completeness and soundness
2350:, because any valuation satisfying
6707:
6482:
6316:
3896:10.1111/j.1559-3584.2002.tb00103.x
3853:Fundamentals of Mathematical Logic
3838:Mathematical Introduction to Logic
3791:Lewis, C I; Langford, C H (1959).
3584:
3581:
3511:
3505:
3502:
3484:
3372:
3323:
3320:
3271:
3210:
3192:
3189:
3165:
3141:
3120:
3114:
3096:
3031:
3028:
2998:
2972:
2903:
2787:
2766:
2625:
2616:
2543:There is a general procedure, the
2260:
2118:
2045:. It is equivalent to the formula
1368:For example, consider the formula
1015:
1006:
982:
919:
910:
889:
835:
826:
780:
726:
657:In many of the following examples
524:
509:
464:
166:
146:
14:
3338:{\displaystyle \lnot \exists xSx}
2923:, and consequently, tautology is
2838:if every theorem is a tautology.
661:represents the statement "object
190:Tautologies are a key concept in
7180:
7169:
6811:
6729:
6546:{\displaystyle \leftrightarrow }
6335:
6222:
5796:
3599:{\displaystyle \neg \neg A\to A}
3394:in the propositional tautology:
2574:with the corresponding sentence
1969:It is also possible to define a
619:to be readily understandable by
606:
389:Propositional logic begins with
2011:if every valuation that causes
1601:{\displaystyle (A\land B)\to C}
738:{\displaystyle (A\lor \lnot A)}
242:meaning that is still used for
6587:
6540:
6416:
6387:
6362:
4016:Tractatus logico-philosophicus
3590:
3543:
3499:
3496:
3481:
3455:
3452:
3446:
3440:
3437:
3431:
3428:
3425:
3419:
3416:
3404:
3401:
3225:
3222:
3207:
3204:
3186:
3183:
3180:
3177:
3162:
3159:
3156:
3153:
3138:
3135:
3132:
3117:
3108:
3093:
3090:
3087:
3052:
3049:
3037:
3025:
3019:
3016:
3004:
2995:
2890:Boolean satisfiability problem
2802:
2796:
2790:
2781:
2769:
2760:
2757:
2751:
2745:
2739:
2727:
2724:
2695:
2610:
2598:
2124:
2109:
2055:
1736:
1733:
1727:
1721:
1718:
1712:
1709:
1706:
1700:
1697:
1685:
1682:
1661:
1655:
1649:
1646:
1619:
1592:
1589:
1577:
1432:
1429:
1423:
1417:
1414:
1408:
1405:
1402:
1396:
1393:
1381:
1378:
1327:
1304:
1292:
1289:
1286:
1274:
1224:
1221:
1218:
1212:
1206:
1200:
1194:
1188:
1182:
1170:
1167:
1117:
1111:
1105:
1102:
1099:
1096:
1090:
1084:
1078:
1072:
1066:
1063:
1021:
1003:
1000:
997:
985:
931:
928:
925:
916:
907:
901:
895:
886:
883:
841:
832:
823:
820:
817:
811:
805:
732:
717:
691:
573:
561:
530:
521:
515:
506:
500:
488:
314:Tractatus Logico-Philosophicus
1:
6622:{\displaystyle \nrightarrow }
5757:History of mathematical logic
3840:. Academic Press. p. 88.
3821:Rautenberg, Wolfgang (2010).
2981:{\displaystyle A\lor \lnot A}
2269:{\displaystyle B\lor \lnot B}
1667:{\displaystyle A\to (B\to C)}
6647:{\displaystyle \nleftarrow }
6422:{\displaystyle \rightarrow }
5682:Primitive recursive function
4012:Annalen der Naturphilosophie
3925:Précis of Mathematical Logic
3244:It is obtained by replacing
321:had made similar remarks in
6593:{\displaystyle \downarrow }
6393:{\displaystyle \leftarrow }
4043:Encyclopedia of Mathematics
3387:{\displaystyle \forall xTx}
3286:{\displaystyle \exists xRx}
7252:
4746:Schröder–Bernstein theorem
4473:Monadic predicate calculus
4132:Foundations of mathematics
3995:Elements of Symbolic Logic
3890:(1): 17–18. January 2002.
3836:Enderton, Herbert (2001).
2536:
2343:{\displaystyle R\models S}
2038:{\displaystyle R\models S}
1992:
1248:is true, and each implies
579:{\displaystyle (A\land B)}
382:
131:", and contradiction by "O
39:
21:Tautology (disambiguation)
18:
7166:
6917:
6809:
6726:
6689:
6569:
6464:
6368:{\displaystyle \uparrow }
6344:
6333:
6298:
6217:
6094:Necessity and sufficiency
5850:
5792:
5779:Philosophy of mathematics
5728:Automated theorem proving
4899:
4853:Von Neumann–Bernays–Gödel
4494:
3997:, reprinted 1980, Dover,
2929:polynomial-time algorithm
2848:automated theorem proving
2441:is a contradiction, then
409:, the binary connectives
123:is used to indicate that
2317:{\displaystyle A\land C}
1995:Tautological consequence
1989:Tautological implication
1562:{\displaystyle A\land B}
765:one of the truth values
116:{\displaystyle \vDash S}
70:in 1921, borrowing from
6632:Converse nonimplication
5429:Self-verifying theories
5250:Tarski's axiomatization
4201:Tarski's undefinability
4196:incompleteness theorems
3884:Naval Engineers Journal
3855:. Springer. p. 98.
3825:. Springer. p. 64.
3808:A First Course in Logic
3772:Encyclopedia Britannica
3631:Disjunctive normal form
3626:Conjunctive normal form
2953:tautological validities
2912:{\displaystyle \lnot S}
2671:{\displaystyle C\lor D}
2015:to be true also causes
652:propositional variables
598:Definition and examples
391:propositional variables
200:propositional variables
7221:Propositional calculus
7187:Mathematics portal
6714:
6677:
6676:{\displaystyle \land }
6648:
6623:
6594:
6547:
6518:
6489:
6452:
6423:
6394:
6369:
6323:
5803:Mathematics portal
5414:Proof of impossibility
5062:propositional variable
4372:Propositional calculus
3851:Hinman, Peter (2010).
3806:Hedman, Shawn (2004).
3795:(2nd ed.). Dover.
3642:Related logical topics
3600:
3553:
3552:{\displaystyle A\to B}
3524:
3462:
3388:
3359:
3339:
3307:
3287:
3258:
3235:
3059:
2982:
2913:
2809:
2705:
2704:{\displaystyle C\to E}
2672:
2635:
2522:
2500:
2478:
2456:
2434:
2409:
2387:
2365:
2344:
2318:
2291:
2270:
2240:
2218:
2196:
2174:
2152:
2131:
2089:
2065:
2064:{\displaystyle R\to S}
2039:
1743:
1668:
1629:
1628:{\displaystyle B\to C}
1602:
1563:
1534:
1509:
1484:
1442:
1337:
1336:{\displaystyle C\to C}
1311:
1234:
1156:hypothetical syllogism
1124:
1028:
941:
848:
787:
786:{\displaystyle \lnot }
755:law of excluded middle
739:
701:
700:{\displaystyle A\to B}
580:
537:
471:
470:{\displaystyle \lnot }
443:
442:{\displaystyle \land }
423:
342:
324:Science and Hypothesis
286:
244:rhetorical tautologies
173:
153:
117:
7176:Philosophy portal
6736:Philosophy portal
6715:
6713:{\displaystyle \bot }
6678:
6649:
6624:
6595:
6548:
6519:
6490:
6488:{\displaystyle \neg }
6453:
6451:{\displaystyle \lor }
6424:
6395:
6370:
6324:
6322:{\displaystyle \top }
6229:Philosophy portal
5672:Kolmogorov complexity
5625:Computably enumerable
5525:Model complete theory
5317:Principia Mathematica
4377:Propositional formula
4206:Banach–Tarski paradox
3745:mathworld.wolfram.com
3683:List of logic symbols
3621:Algebraic normal form
3601:
3554:
3525:
3463:
3389:
3360:
3340:
3308:
3288:
3259:
3236:
3060:
2983:
2914:
2818:is also a tautology.
2810:
2706:
2673:
2636:
2581:is also a tautology.
2539:Substitution instance
2523:
2507:is a tautology, then
2501:
2479:
2457:
2435:
2410:
2388:
2366:
2345:
2319:
2292:
2271:
2241:
2219:
2197:
2175:
2153:
2132:
2090:
2066:
2040:
1744:
1669:
1630:
1603:
1564:
1535:
1510:
1485:
1443:
1348:Verifying tautologies
1338:
1312:
1240:("if at least one of
1235:
1125:
1029:
955:and its negation not-
942:
849:
788:
740:
702:
581:
538:
472:
444:
424:
422:{\displaystyle \lor }
174:
172:{\displaystyle \bot }
154:
152:{\displaystyle \top }
118:
6704:
6667:
6638:
6613:
6584:
6537:
6508:
6479:
6442:
6413:
6384:
6378:Converse implication
6359:
6313:
5620:Church–Turing thesis
5607:Computability theory
4816:continuum hypothesis
4334:Square of opposition
4192:Gödel's completeness
3578:
3569:intuitionistic logic
3537:
3478:
3398:
3369:
3349:
3317:
3297:
3268:
3248:
3084:
2992:
2963:
2900:
2721:
2689:
2656:
2595:
2512:
2490:
2468:
2446:
2424:
2399:
2394:true—and thus makes
2377:
2355:
2328:
2302:
2281:
2276:is a tautology. Let
2251:
2230:
2208:
2186:
2164:
2142:
2100:
2079:
2049:
2023:
2005:tautologically imply
1679:
1640:
1613:
1574:
1547:
1524:
1499:
1474:
1375:
1321:
1271:
1164:
1060:
979:
970:reductio ad absurdum
963:must be false, then
880:
802:
777:
714:
685:
558:
485:
461:
433:
413:
290:analytic proposition
213:, which may contain
163:
143:
104:
91:logically contingent
7206:Logical expressions
6292:logical connectives
5891:Philosophy of logic
5774:Mathematical object
5665:P versus NP problem
5630:Computable function
5424:Reverse mathematics
5350:Logical consequence
5227:primitive recursive
5222:elementary function
4995:Free/bound variable
4848:Tarski–Grothendieck
4367:Logical connectives
4297:Logical equivalence
4147:Logical consequence
3739:Weisstein, Eric W.
3697:Logical consequence
2878:efficient procedure
2867:effective procedure
669:represents "object
385:Propositional logic
353:propositional logic
346:logical proposition
192:propositional logic
68:propositional logic
64:Ludwig Wittgenstein
57:propositional logic
7216:Mathematical logic
6710:
6673:
6644:
6619:
6590:
6543:
6514:
6485:
6448:
6419:
6390:
6365:
6349:Alternative denial
6319:
6190:Rules of inference
6159:Mathematical logic
5901:Semantics of logic
5572:Transfer principle
5535:Semantics of logic
5520:Categorical theory
5496:Non-standard model
5010:Logical connective
4137:Information theory
4086:Mathematical logic
3977:Dover Publications
3975:, reprinted 2002,
3973:Mathematical Logic
3636:Logic optimization
3596:
3549:
3520:
3458:
3384:
3355:
3335:
3303:
3283:
3254:
3231:
3055:
2978:
2945:logical validities
2909:
2805:
2701:
2668:
2631:
2588:be the tautology:
2518:
2496:
2474:
2452:
2430:
2405:
2383:
2361:
2340:
2314:
2287:
2266:
2236:
2214:
2192:
2170:
2148:
2127:
2085:
2061:
2035:
1739:
1664:
1625:
1598:
1559:
1530:
1505:
1480:
1438:
1333:
1307:
1230:
1120:
1024:
937:
844:
783:
735:
697:
576:
533:
467:
439:
419:
327:in 1905. Although
257:wrote in his book
248:mathematical logic
169:
149:
113:
28:mathematical logic
7236:Sentences by type
7193:
7192:
7161:
7160:
6876:
6875:
6742:
6741:
6257:
6256:
6213:
6212:
6047:Deductive closure
5993:
5992:
5932:Critical thinking
5810:
5809:
5742:Abstract category
5545:Theories of truth
5355:Rule of inference
5345:Natural deduction
5326:
5325:
4871:
4870:
4576:Cartesian product
4481:
4480:
4387:Many-valued logic
4362:Boolean functions
4245:Russell's paradox
4220:diagonal argument
4117:First-order logic
3722:
3721:
3358:{\displaystyle C}
3306:{\displaystyle B}
3257:{\displaystyle A}
2941:first-order logic
2584:For example, let
2559:a fixed sentence
2545:substitution rule
2521:{\displaystyle S}
2499:{\displaystyle S}
2477:{\displaystyle R}
2455:{\displaystyle R}
2433:{\displaystyle R}
2408:{\displaystyle S}
2386:{\displaystyle A}
2364:{\displaystyle R}
2290:{\displaystyle R}
2239:{\displaystyle S}
2217:{\displaystyle A}
2195:{\displaystyle S}
2173:{\displaystyle A}
2151:{\displaystyle S}
2088:{\displaystyle S}
2074:For example, let
1960:
1959:
1533:{\displaystyle C}
1508:{\displaystyle B}
1483:{\displaystyle A}
644:
643:
621:general audiences
196:Boolean valuation
52:logical constants
7243:
7185:
7184:
7174:
7173:
7172:
7104:
7053:
6933:
6920:
6903:
6896:
6889:
6880:
6815:
6769:
6762:
6755:
6746:
6734:
6733:
6732:
6719:
6717:
6716:
6711:
6682:
6680:
6679:
6674:
6653:
6651:
6650:
6645:
6628:
6626:
6625:
6620:
6599:
6597:
6596:
6591:
6552:
6550:
6549:
6544:
6523:
6521:
6520:
6515:
6494:
6492:
6491:
6486:
6457:
6455:
6454:
6449:
6428:
6426:
6425:
6420:
6399:
6397:
6396:
6391:
6374:
6372:
6371:
6366:
6339:
6328:
6326:
6325:
6320:
6284:
6277:
6270:
6261:
6227:
6226:
6225:
6147:
5912:
5876:Computer science
5837:
5830:
5823:
5814:
5801:
5800:
5752:History of logic
5747:Category of sets
5640:Decision problem
5419:Ordinal analysis
5360:Sequent calculus
5258:Boolean algebras
5198:
5197:
5172:
5143:logical/constant
4897:
4883:
4806:Zermelo–Fraenkel
4557:Set operations:
4492:
4429:
4260:
4240:Löwenheim–Skolem
4127:Formal semantics
4079:
4072:
4065:
4056:
4051:
4008:Wittgenstein, L.
3921:Bocheński, J. M.
3908:
3907:
3876:
3870:
3863:
3857:
3856:
3848:
3842:
3841:
3833:
3827:
3826:
3818:
3812:
3811:
3803:
3797:
3796:
3788:
3782:
3781:
3779:
3778:
3764:
3755:
3754:
3752:
3751:
3736:
3663:Boolean function
3647:
3605:
3603:
3602:
3597:
3558:
3556:
3555:
3550:
3529:
3527:
3526:
3521:
3467:
3465:
3464:
3459:
3393:
3391:
3390:
3385:
3364:
3362:
3361:
3356:
3344:
3342:
3341:
3336:
3312:
3310:
3309:
3304:
3292:
3290:
3289:
3284:
3263:
3261:
3260:
3255:
3240:
3238:
3237:
3232:
3064:
3062:
3061:
3056:
2987:
2985:
2984:
2979:
2918:
2916:
2915:
2910:
2828:axiomatic system
2814:
2812:
2811:
2806:
2710:
2708:
2707:
2702:
2684:
2677:
2675:
2674:
2669:
2651:
2640:
2638:
2637:
2632:
2587:
2580:
2573:
2569:
2565:
2558:
2554:
2550:
2527:
2525:
2524:
2519:
2505:
2503:
2502:
2497:
2483:
2481:
2480:
2475:
2461:
2459:
2458:
2453:
2439:
2437:
2436:
2431:
2414:
2412:
2411:
2406:
2392:
2390:
2389:
2384:
2370:
2368:
2367:
2362:
2349:
2347:
2346:
2341:
2323:
2321:
2320:
2315:
2296:
2294:
2293:
2288:
2275:
2273:
2272:
2267:
2245:
2243:
2242:
2237:
2223:
2221:
2220:
2215:
2201:
2199:
2198:
2193:
2181:false will make
2179:
2177:
2176:
2171:
2157:
2155:
2154:
2149:
2136:
2134:
2133:
2128:
2094:
2092:
2091:
2086:
2070:
2068:
2067:
2062:
2044:
2042:
2041:
2036:
1971:deductive system
1748:
1746:
1745:
1740:
1673:
1671:
1670:
1665:
1634:
1632:
1631:
1626:
1607:
1605:
1604:
1599:
1568:
1566:
1565:
1560:
1541:
1539:
1537:
1536:
1531:
1516:
1514:
1512:
1511:
1506:
1491:
1489:
1487:
1486:
1481:
1466:
1447:
1445:
1444:
1439:
1342:
1340:
1339:
1334:
1316:
1314:
1313:
1308:
1239:
1237:
1236:
1231:
1129:
1127:
1126:
1121:
1033:
1031:
1030:
1025:
946:
944:
943:
938:
853:
851:
850:
845:
792:
790:
789:
784:
744:
742:
741:
736:
706:
704:
703:
698:
639:
636:
630:
610:
602:
585:
583:
582:
577:
542:
540:
539:
534:
476:
474:
473:
468:
448:
446:
445:
440:
428:
426:
425:
420:
329:Bertrand Russell
303:proposed in his
204:effective method
178:
176:
175:
170:
158:
156:
155:
150:
122:
120:
119:
114:
98:double turnstile
62:The philosopher
50:, with only the
41:
7251:
7250:
7246:
7245:
7244:
7242:
7241:
7240:
7196:
7195:
7194:
7189:
7179:
7178:
7170:
7168:
7162:
7157:
7156:
7153:
7149:
7141:
7140:
7137:
7133:
7125:
7121:
7113:
7109:
7100:
7091:
7087:
7082:
7074:
7070:
7062:
7058:
7049:
7040:
7036:
7028:
7024:
7016:
7012:
7004:
7001:
6998:
6990:
6987:
6984:
6976:
6972:
6967:
6959:
6955:
6950:
6942:
6938:
6929:
6913:
6911:logical symbols
6907:
6877:
6872:
6842:
6816:
6807:
6780:
6773:
6743:
6738:
6730:
6728:
6722:
6702:
6701:
6685:
6665:
6664:
6636:
6635:
6611:
6610:
6582:
6581:
6565:
6535:
6534:
6506:
6505:
6477:
6476:
6460:
6440:
6439:
6411:
6410:
6382:
6381:
6357:
6356:
6340:
6331:
6311:
6310:
6294:
6288:
6258:
6253:
6223:
6221:
6209:
6173:
6164:Boolean algebra
6138:
5989:
5980:Metamathematics
5958:
5910:
5864:
5846:
5841:
5811:
5806:
5795:
5788:
5733:Category theory
5723:Algebraic logic
5706:
5677:Lambda calculus
5615:Church encoding
5601:
5577:Truth predicate
5433:
5399:Complete theory
5322:
5191:
5187:
5183:
5178:
5170:
4890: and
4886:
4881:
4867:
4843:New Foundations
4811:axiom of choice
4794:
4756:Gödel numbering
4696: and
4688:
4592:
4477:
4427:
4408:
4357:Boolean algebra
4343:
4307:Equiconsistency
4272:Classical logic
4249:
4230:Halting problem
4218: and
4194: and
4182: and
4181:
4176:Theorems (
4171:
4088:
4083:
4036:
4033:
3991:Reichenbach, H.
3943:Enderton, H. B.
3917:
3915:Further reading
3912:
3911:
3878:
3877:
3873:
3869:for references.
3864:
3860:
3850:
3849:
3845:
3835:
3834:
3830:
3820:
3819:
3815:
3805:
3804:
3800:
3790:
3789:
3785:
3776:
3774:
3766:
3765:
3758:
3749:
3747:
3738:
3737:
3733:
3728:
3723:
3692:Logic synthesis
3653:Boolean algebra
3644:
3617:
3612:
3576:
3575:
3565:
3535:
3534:
3476:
3475:
3396:
3395:
3367:
3366:
3347:
3346:
3315:
3314:
3295:
3294:
3266:
3265:
3246:
3245:
3082:
3081:
2990:
2989:
2961:
2960:
2937:
2898:
2897:
2844:
2824:
2719:
2718:
2687:
2686:
2683:
2679:
2654:
2653:
2650:
2646:
2593:
2592:
2585:
2579:
2575:
2571:
2567:
2564:
2560:
2556:
2552:
2548:
2541:
2535:
2510:
2509:
2488:
2487:
2466:
2465:
2444:
2443:
2422:
2421:
2397:
2396:
2375:
2374:
2353:
2352:
2326:
2325:
2300:
2299:
2298:be the formula
2279:
2278:
2249:
2248:
2228:
2227:
2225:true will make
2206:
2205:
2184:
2183:
2162:
2161:
2140:
2139:
2098:
2097:
2077:
2076:
2047:
2046:
2021:
2020:
1997:
1991:
1677:
1676:
1638:
1637:
1611:
1610:
1572:
1571:
1545:
1544:
1522:
1521:
1519:
1497:
1496:
1494:
1472:
1471:
1469:
1373:
1372:
1350:
1319:
1318:
1269:
1268:
1162:
1161:
1058:
1057:
1052:De Morgan's law
977:
976:
878:
877:
800:
799:
775:
774:
712:
711:
683:
682:
640:
634:
631:
624:
611:
600:
556:
555:
483:
482:
459:
458:
431:
430:
411:
410:
387:
381:
361:interpretations
357:predicate logic
236:
219:logically valid
211:predicate logic
161:
160:
141:
140:
102:
101:
24:
17:
12:
11:
5:
7249:
7247:
7239:
7238:
7233:
7228:
7223:
7218:
7213:
7208:
7198:
7197:
7191:
7190:
7167:
7164:
7163:
7159:
7158:
7154:quantification
7150:
7145:
7144:
7142:
7138:quantification
7134:
7129:
7128:
7126:
7117:
7116:
7114:
7095:
7094:
7092:
7078:
7077:
7075:
7066:
7065:
7063:
7044:
7043:
7041:
7032:
7031:
7029:
7020:
7019:
7017:
7008:
7007:
7005:
6994:
6993:
6991:
6980:
6979:
6977:
6963:
6962:
6960:
6946:
6945:
6943:
6924:
6923:
6918:
6915:
6914:
6908:
6906:
6905:
6898:
6891:
6883:
6874:
6873:
6871:
6870:
6865:
6860:
6850:
6848:
6847:Negation
6844:
6843:
6841:
6840:
6835:
6830:
6824:
6822:
6818:
6817:
6810:
6808:
6806:
6805:
6799:
6797:truth function
6794:
6788:
6786:
6782:
6781:
6774:
6772:
6771:
6764:
6757:
6749:
6740:
6739:
6727:
6724:
6723:
6721:
6720:
6709:
6690:
6687:
6686:
6684:
6683:
6672:
6654:
6643:
6629:
6618:
6603:Nonimplication
6600:
6589:
6570:
6567:
6566:
6564:
6563:
6560:Digital buffer
6553:
6542:
6524:
6513:
6495:
6484:
6465:
6462:
6461:
6459:
6458:
6447:
6429:
6418:
6400:
6389:
6375:
6364:
6345:
6342:
6341:
6334:
6332:
6330:
6329:
6318:
6299:
6296:
6295:
6289:
6287:
6286:
6279:
6272:
6264:
6255:
6254:
6252:
6251:
6246:
6236:
6231:
6218:
6215:
6214:
6211:
6210:
6208:
6207:
6202:
6197:
6192:
6187:
6181:
6179:
6175:
6174:
6172:
6171:
6166:
6161:
6155:
6153:
6144:
6140:
6139:
6137:
6136:
6131:
6126:
6121:
6116:
6111:
6106:
6101:
6096:
6091:
6086:
6081:
6076:
6071:
6070:
6069:
6059:
6054:
6049:
6044:
6039:
6038:
6037:
6032:
6022:
6017:
6012:
6007:
6001:
5999:
5995:
5994:
5991:
5990:
5988:
5987:
5982:
5977:
5972:
5966:
5964:
5960:
5959:
5957:
5956:
5951:
5946:
5941:
5940:
5939:
5934:
5924:
5918:
5916:
5909:
5908:
5903:
5898:
5893:
5888:
5883:
5878:
5872:
5870:
5866:
5865:
5863:
5862:
5857:
5851:
5848:
5847:
5842:
5840:
5839:
5832:
5825:
5817:
5808:
5807:
5793:
5790:
5789:
5787:
5786:
5781:
5776:
5771:
5766:
5765:
5764:
5754:
5749:
5744:
5735:
5730:
5725:
5720:
5718:Abstract logic
5714:
5712:
5708:
5707:
5705:
5704:
5699:
5697:Turing machine
5694:
5689:
5684:
5679:
5674:
5669:
5668:
5667:
5662:
5657:
5652:
5647:
5637:
5635:Computable set
5632:
5627:
5622:
5617:
5611:
5609:
5603:
5602:
5600:
5599:
5594:
5589:
5584:
5579:
5574:
5569:
5564:
5563:
5562:
5557:
5552:
5542:
5537:
5532:
5530:Satisfiability
5527:
5522:
5517:
5516:
5515:
5505:
5504:
5503:
5493:
5492:
5491:
5486:
5481:
5476:
5471:
5461:
5460:
5459:
5454:
5447:Interpretation
5443:
5441:
5435:
5434:
5432:
5431:
5426:
5421:
5416:
5411:
5401:
5396:
5395:
5394:
5393:
5392:
5382:
5377:
5367:
5362:
5357:
5352:
5347:
5342:
5336:
5334:
5328:
5327:
5324:
5323:
5321:
5320:
5312:
5311:
5310:
5309:
5304:
5303:
5302:
5297:
5292:
5272:
5271:
5270:
5268:minimal axioms
5265:
5254:
5253:
5252:
5241:
5240:
5239:
5234:
5229:
5224:
5219:
5214:
5201:
5199:
5180:
5179:
5177:
5176:
5175:
5174:
5162:
5157:
5156:
5155:
5150:
5145:
5140:
5130:
5125:
5120:
5115:
5114:
5113:
5108:
5098:
5097:
5096:
5091:
5086:
5081:
5071:
5066:
5065:
5064:
5059:
5054:
5044:
5043:
5042:
5037:
5032:
5027:
5022:
5017:
5007:
5002:
4997:
4992:
4991:
4990:
4985:
4980:
4975:
4965:
4960:
4958:Formation rule
4955:
4950:
4949:
4948:
4943:
4933:
4932:
4931:
4921:
4916:
4911:
4906:
4900:
4894:
4877:Formal systems
4873:
4872:
4869:
4868:
4866:
4865:
4860:
4855:
4850:
4845:
4840:
4835:
4830:
4825:
4820:
4819:
4818:
4813:
4802:
4800:
4796:
4795:
4793:
4792:
4791:
4790:
4780:
4775:
4774:
4773:
4766:Large cardinal
4763:
4758:
4753:
4748:
4743:
4729:
4728:
4727:
4722:
4717:
4702:
4700:
4690:
4689:
4687:
4686:
4685:
4684:
4679:
4674:
4664:
4659:
4654:
4649:
4644:
4639:
4634:
4629:
4624:
4619:
4614:
4609:
4603:
4601:
4594:
4593:
4591:
4590:
4589:
4588:
4583:
4578:
4573:
4568:
4563:
4555:
4554:
4553:
4548:
4538:
4533:
4531:Extensionality
4528:
4526:Ordinal number
4523:
4513:
4508:
4507:
4506:
4495:
4489:
4483:
4482:
4479:
4478:
4476:
4475:
4470:
4465:
4460:
4455:
4450:
4445:
4444:
4443:
4433:
4432:
4431:
4418:
4416:
4410:
4409:
4407:
4406:
4405:
4404:
4399:
4394:
4384:
4379:
4374:
4369:
4364:
4359:
4353:
4351:
4345:
4344:
4342:
4341:
4336:
4331:
4326:
4321:
4316:
4311:
4310:
4309:
4299:
4294:
4289:
4284:
4279:
4274:
4268:
4266:
4257:
4251:
4250:
4248:
4247:
4242:
4237:
4232:
4227:
4222:
4210:Cantor's
4208:
4203:
4198:
4188:
4186:
4173:
4172:
4170:
4169:
4164:
4159:
4154:
4149:
4144:
4139:
4134:
4129:
4124:
4119:
4114:
4109:
4108:
4107:
4096:
4094:
4090:
4089:
4084:
4082:
4081:
4074:
4067:
4059:
4053:
4052:
4032:
4031:External links
4029:
4028:
4027:
4005:
3988:
3966:
3955:Academic Press
3940:
3916:
3913:
3910:
3909:
3871:
3858:
3843:
3828:
3813:
3798:
3793:Symbolic Logic
3783:
3756:
3730:
3729:
3727:
3724:
3720:
3719:
3715:
3714:
3709:
3704:
3699:
3694:
3687:
3686:
3685:
3680:
3675:
3670:
3665:
3660:
3658:Boolean domain
3655:
3645:
3643:
3640:
3639:
3638:
3633:
3628:
3623:
3616:
3613:
3611:
3608:
3607:
3606:
3595:
3592:
3589:
3586:
3583:
3564:
3561:
3548:
3545:
3542:
3531:
3530:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3498:
3495:
3492:
3489:
3486:
3483:
3457:
3454:
3451:
3448:
3445:
3442:
3439:
3436:
3433:
3430:
3427:
3424:
3421:
3418:
3415:
3412:
3409:
3406:
3403:
3383:
3380:
3377:
3374:
3354:
3334:
3331:
3328:
3325:
3322:
3302:
3282:
3279:
3276:
3273:
3253:
3242:
3241:
3230:
3227:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3033:
3030:
3027:
3024:
3021:
3018:
3015:
3012:
3009:
3006:
3003:
3000:
2997:
2977:
2974:
2971:
2968:
2936:
2933:
2925:co-NP-complete
2908:
2905:
2853:The method of
2843:
2840:
2823:
2820:
2816:
2815:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2700:
2697:
2694:
2681:
2667:
2664:
2661:
2648:
2643:
2642:
2630:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2606:
2603:
2600:
2577:
2562:
2537:Main article:
2534:
2531:
2517:
2495:
2473:
2451:
2429:
2404:
2382:
2360:
2339:
2336:
2333:
2313:
2310:
2307:
2286:
2265:
2262:
2259:
2256:
2247:true, because
2235:
2213:
2191:
2169:
2147:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2084:
2060:
2057:
2054:
2034:
2031:
2028:
1993:Main article:
1990:
1987:
1983:intuitionistic
1958:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1932:
1931:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1906:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1880:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1854:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1828:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1802:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1776:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1750:
1749:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1674:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1635:
1624:
1621:
1618:
1608:
1597:
1594:
1591:
1588:
1585:
1582:
1579:
1569:
1558:
1555:
1552:
1542:
1529:
1517:
1504:
1492:
1479:
1449:
1448:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1349:
1346:
1345:
1344:
1332:
1329:
1326:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1262:
1261:
1258:proof by cases
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1159:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1055:
1034:("if not both
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
974:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
875:
872:contraposition
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
797:
782:
734:
731:
728:
725:
722:
719:
696:
693:
690:
642:
641:
614:
612:
605:
599:
596:
575:
572:
569:
566:
563:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
466:
438:
418:
383:Main article:
380:
377:
319:Henri Poincaré
294:analytic truth
235:
232:
222:formulas is a
168:
148:
112:
109:
87:contradictions
15:
13:
10:
9:
6:
4:
3:
2:
7248:
7237:
7234:
7232:
7229:
7227:
7224:
7222:
7219:
7217:
7214:
7212:
7211:Logical truth
7209:
7207:
7204:
7203:
7201:
7188:
7183:
7177:
7165:
7155:
7148:
7143:
7139:
7132:
7127:
7124:
7120:
7115:
7112:
7108:
7103:
7098:
7093:
7090:
7085:
7081:
7076:
7073:
7069:
7064:
7061:
7057:
7052:
7047:
7042:
7039:
7035:
7030:
7027:
7023:
7018:
7015:
7011:
7006:
7003:
6997:
6992:
6989:
6983:
6978:
6975:
6974:contradiction
6970:
6966:
6961:
6958:
6953:
6949:
6944:
6941:
6937:
6932:
6927:
6922:
6921:
6916:
6912:
6904:
6899:
6897:
6892:
6890:
6885:
6884:
6881:
6869:
6868:inconsistency
6866:
6864:
6863:contradiction
6861:
6859:
6855:
6852:
6851:
6849:
6845:
6839:
6836:
6834:
6831:
6829:
6826:
6825:
6823:
6819:
6814:
6804:
6801:⊨
6800:
6798:
6795:
6793:
6790:
6789:
6787:
6783:
6778:
6777:Logical truth
6770:
6765:
6763:
6758:
6756:
6751:
6750:
6747:
6737:
6725:
6699:
6695:
6694:Contradiction
6692:
6691:
6688:
6670:
6662:
6658:
6655:
6641:
6633:
6630:
6616:
6608:
6604:
6601:
6579:
6575:
6572:
6571:
6568:
6561:
6557:
6554:
6532:
6528:
6527:Biconditional
6525:
6511:
6503:
6499:
6496:
6474:
6470:
6467:
6466:
6463:
6445:
6437:
6433:
6430:
6408:
6404:
6401:
6379:
6376:
6354:
6350:
6347:
6346:
6343:
6338:
6308:
6304:
6301:
6300:
6297:
6293:
6285:
6280:
6278:
6273:
6271:
6266:
6265:
6262:
6250:
6247:
6244:
6240:
6237:
6235:
6232:
6230:
6220:
6219:
6216:
6206:
6205:Logic symbols
6203:
6201:
6198:
6196:
6193:
6191:
6188:
6186:
6183:
6182:
6180:
6176:
6170:
6167:
6165:
6162:
6160:
6157:
6156:
6154:
6152:
6148:
6145:
6141:
6135:
6132:
6130:
6127:
6125:
6122:
6120:
6117:
6115:
6112:
6110:
6107:
6105:
6102:
6100:
6097:
6095:
6092:
6090:
6087:
6085:
6084:Logical truth
6082:
6080:
6077:
6075:
6072:
6068:
6065:
6064:
6063:
6060:
6058:
6055:
6053:
6050:
6048:
6045:
6043:
6040:
6036:
6033:
6031:
6028:
6027:
6026:
6025:Contradiction
6023:
6021:
6018:
6016:
6013:
6011:
6008:
6006:
6003:
6002:
6000:
5996:
5986:
5983:
5981:
5978:
5976:
5973:
5971:
5970:Argumentation
5968:
5967:
5965:
5961:
5955:
5954:Philosophical
5952:
5950:
5949:Non-classical
5947:
5945:
5942:
5938:
5935:
5933:
5930:
5929:
5928:
5925:
5923:
5920:
5919:
5917:
5913:
5907:
5904:
5902:
5899:
5897:
5894:
5892:
5889:
5887:
5884:
5882:
5879:
5877:
5874:
5873:
5871:
5867:
5861:
5858:
5856:
5853:
5852:
5849:
5845:
5838:
5833:
5831:
5826:
5824:
5819:
5818:
5815:
5805:
5804:
5799:
5791:
5785:
5782:
5780:
5777:
5775:
5772:
5770:
5767:
5763:
5760:
5759:
5758:
5755:
5753:
5750:
5748:
5745:
5743:
5739:
5736:
5734:
5731:
5729:
5726:
5724:
5721:
5719:
5716:
5715:
5713:
5709:
5703:
5700:
5698:
5695:
5693:
5692:Recursive set
5690:
5688:
5685:
5683:
5680:
5678:
5675:
5673:
5670:
5666:
5663:
5661:
5658:
5656:
5653:
5651:
5648:
5646:
5643:
5642:
5641:
5638:
5636:
5633:
5631:
5628:
5626:
5623:
5621:
5618:
5616:
5613:
5612:
5610:
5608:
5604:
5598:
5595:
5593:
5590:
5588:
5585:
5583:
5580:
5578:
5575:
5573:
5570:
5568:
5565:
5561:
5558:
5556:
5553:
5551:
5548:
5547:
5546:
5543:
5541:
5538:
5536:
5533:
5531:
5528:
5526:
5523:
5521:
5518:
5514:
5511:
5510:
5509:
5506:
5502:
5501:of arithmetic
5499:
5498:
5497:
5494:
5490:
5487:
5485:
5482:
5480:
5477:
5475:
5472:
5470:
5467:
5466:
5465:
5462:
5458:
5455:
5453:
5450:
5449:
5448:
5445:
5444:
5442:
5440:
5436:
5430:
5427:
5425:
5422:
5420:
5417:
5415:
5412:
5409:
5408:from ZFC
5405:
5402:
5400:
5397:
5391:
5388:
5387:
5386:
5383:
5381:
5378:
5376:
5373:
5372:
5371:
5368:
5366:
5363:
5361:
5358:
5356:
5353:
5351:
5348:
5346:
5343:
5341:
5338:
5337:
5335:
5333:
5329:
5319:
5318:
5314:
5313:
5308:
5307:non-Euclidean
5305:
5301:
5298:
5296:
5293:
5291:
5290:
5286:
5285:
5283:
5280:
5279:
5277:
5273:
5269:
5266:
5264:
5261:
5260:
5259:
5255:
5251:
5248:
5247:
5246:
5242:
5238:
5235:
5233:
5230:
5228:
5225:
5223:
5220:
5218:
5215:
5213:
5210:
5209:
5207:
5203:
5202:
5200:
5195:
5189:
5184:Example
5181:
5173:
5168:
5167:
5166:
5163:
5161:
5158:
5154:
5151:
5149:
5146:
5144:
5141:
5139:
5136:
5135:
5134:
5131:
5129:
5126:
5124:
5121:
5119:
5116:
5112:
5109:
5107:
5104:
5103:
5102:
5099:
5095:
5092:
5090:
5087:
5085:
5082:
5080:
5077:
5076:
5075:
5072:
5070:
5067:
5063:
5060:
5058:
5055:
5053:
5050:
5049:
5048:
5045:
5041:
5038:
5036:
5033:
5031:
5028:
5026:
5023:
5021:
5018:
5016:
5013:
5012:
5011:
5008:
5006:
5003:
5001:
4998:
4996:
4993:
4989:
4986:
4984:
4981:
4979:
4976:
4974:
4971:
4970:
4969:
4966:
4964:
4961:
4959:
4956:
4954:
4951:
4947:
4944:
4942:
4941:by definition
4939:
4938:
4937:
4934:
4930:
4927:
4926:
4925:
4922:
4920:
4917:
4915:
4912:
4910:
4907:
4905:
4902:
4901:
4898:
4895:
4893:
4889:
4884:
4878:
4874:
4864:
4861:
4859:
4856:
4854:
4851:
4849:
4846:
4844:
4841:
4839:
4836:
4834:
4831:
4829:
4828:Kripke–Platek
4826:
4824:
4821:
4817:
4814:
4812:
4809:
4808:
4807:
4804:
4803:
4801:
4797:
4789:
4786:
4785:
4784:
4781:
4779:
4776:
4772:
4769:
4768:
4767:
4764:
4762:
4759:
4757:
4754:
4752:
4749:
4747:
4744:
4741:
4737:
4733:
4730:
4726:
4723:
4721:
4718:
4716:
4713:
4712:
4711:
4707:
4704:
4703:
4701:
4699:
4695:
4691:
4683:
4680:
4678:
4675:
4673:
4672:constructible
4670:
4669:
4668:
4665:
4663:
4660:
4658:
4655:
4653:
4650:
4648:
4645:
4643:
4640:
4638:
4635:
4633:
4630:
4628:
4625:
4623:
4620:
4618:
4615:
4613:
4610:
4608:
4605:
4604:
4602:
4600:
4595:
4587:
4584:
4582:
4579:
4577:
4574:
4572:
4569:
4567:
4564:
4562:
4559:
4558:
4556:
4552:
4549:
4547:
4544:
4543:
4542:
4539:
4537:
4534:
4532:
4529:
4527:
4524:
4522:
4518:
4514:
4512:
4509:
4505:
4502:
4501:
4500:
4497:
4496:
4493:
4490:
4488:
4484:
4474:
4471:
4469:
4466:
4464:
4461:
4459:
4456:
4454:
4451:
4449:
4446:
4442:
4439:
4438:
4437:
4434:
4430:
4425:
4424:
4423:
4420:
4419:
4417:
4415:
4411:
4403:
4400:
4398:
4395:
4393:
4390:
4389:
4388:
4385:
4383:
4380:
4378:
4375:
4373:
4370:
4368:
4365:
4363:
4360:
4358:
4355:
4354:
4352:
4350:
4349:Propositional
4346:
4340:
4337:
4335:
4332:
4330:
4327:
4325:
4322:
4320:
4317:
4315:
4312:
4308:
4305:
4304:
4303:
4300:
4298:
4295:
4293:
4290:
4288:
4285:
4283:
4280:
4278:
4277:Logical truth
4275:
4273:
4270:
4269:
4267:
4265:
4261:
4258:
4256:
4252:
4246:
4243:
4241:
4238:
4236:
4233:
4231:
4228:
4226:
4223:
4221:
4217:
4213:
4209:
4207:
4204:
4202:
4199:
4197:
4193:
4190:
4189:
4187:
4185:
4179:
4174:
4168:
4165:
4163:
4160:
4158:
4155:
4153:
4150:
4148:
4145:
4143:
4140:
4138:
4135:
4133:
4130:
4128:
4125:
4123:
4120:
4118:
4115:
4113:
4110:
4106:
4103:
4102:
4101:
4098:
4097:
4095:
4091:
4087:
4080:
4075:
4073:
4068:
4066:
4061:
4060:
4057:
4049:
4045:
4044:
4039:
4035:
4034:
4030:
4025:
4021:
4020:New York City
4017:
4013:
4009:
4006:
4004:
4003:0-486-24004-5
4000:
3996:
3992:
3989:
3986:
3985:0-486-42533-9
3982:
3978:
3974:
3970:
3969:Kleene, S. C.
3967:
3964:
3963:0-12-238452-0
3960:
3956:
3952:
3948:
3944:
3941:
3938:
3934:
3933:South Holland
3930:
3926:
3922:
3919:
3918:
3914:
3905:
3901:
3897:
3893:
3889:
3885:
3881:
3880:"New Members"
3875:
3872:
3868:
3862:
3859:
3854:
3847:
3844:
3839:
3832:
3829:
3824:
3817:
3814:
3809:
3802:
3799:
3794:
3787:
3784:
3773:
3769:
3763:
3761:
3757:
3746:
3742:
3735:
3732:
3725:
3718:
3713:
3712:Vacuous truth
3710:
3708:
3707:Logical truth
3705:
3703:
3702:Logical graph
3700:
3698:
3695:
3693:
3690:
3689:
3688:
3684:
3681:
3679:
3676:
3674:
3673:False (logic)
3671:
3669:
3668:Contradiction
3666:
3664:
3661:
3659:
3656:
3654:
3651:
3650:
3649:
3648:
3641:
3637:
3634:
3632:
3629:
3627:
3624:
3622:
3619:
3618:
3614:
3609:
3593:
3587:
3574:
3573:
3572:
3570:
3562:
3560:
3546:
3540:
3517:
3514:
3508:
3493:
3490:
3487:
3474:
3473:
3472:
3469:
3449:
3443:
3434:
3422:
3413:
3410:
3407:
3381:
3378:
3375:
3352:
3332:
3329:
3326:
3300:
3280:
3277:
3274:
3251:
3228:
3219:
3216:
3213:
3201:
3198:
3195:
3174:
3171:
3168:
3150:
3147:
3144:
3129:
3126:
3123:
3111:
3105:
3102:
3099:
3080:
3079:
3078:
3076:
3072:
3068:
3046:
3043:
3040:
3034:
3022:
3013:
3010:
3007:
3001:
2975:
2969:
2966:
2956:
2954:
2950:
2946:
2942:
2934:
2932:
2930:
2926:
2922:
2906:
2895:
2891:
2886:
2883:
2879:
2874:
2872:
2871:decidable set
2868:
2864:
2860:
2856:
2851:
2849:
2841:
2839:
2837:
2833:
2829:
2821:
2819:
2799:
2793:
2784:
2778:
2775:
2772:
2763:
2754:
2748:
2742:
2736:
2733:
2730:
2717:
2716:
2715:
2712:
2698:
2692:
2665:
2662:
2659:
2628:
2622:
2619:
2613:
2607:
2604:
2601:
2591:
2590:
2589:
2582:
2546:
2540:
2532:
2530:
2528:
2515:
2506:
2493:
2484:
2471:
2462:
2449:
2440:
2427:
2417:
2415:
2402:
2393:
2380:
2371:
2358:
2337:
2334:
2331:
2311:
2308:
2305:
2297:
2284:
2263:
2257:
2254:
2246:
2233:
2224:
2211:
2202:
2189:
2180:
2167:
2158:
2145:
2121:
2115:
2112:
2106:
2103:
2095:
2082:
2072:
2058:
2052:
2032:
2029:
2026:
2018:
2014:
2010:
2006:
2002:
1996:
1988:
1986:
1984:
1980:
1976:
1972:
1967:
1965:
1955:
1952:
1949:
1946:
1943:
1940:
1937:
1934:
1933:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1907:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1881:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1855:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1829:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1803:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1777:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1751:
1730:
1724:
1715:
1703:
1694:
1691:
1688:
1675:
1658:
1652:
1643:
1636:
1622:
1616:
1609:
1595:
1586:
1583:
1580:
1570:
1556:
1553:
1550:
1543:
1527:
1518:
1502:
1493:
1477:
1468:
1467:
1464:
1462:
1458:
1454:
1435:
1426:
1420:
1411:
1399:
1390:
1387:
1384:
1371:
1370:
1369:
1366:
1364:
1360:
1355:
1347:
1330:
1324:
1301:
1298:
1295:
1283:
1280:
1277:
1267:
1266:
1265:
1259:
1255:
1251:
1247:
1243:
1227:
1215:
1209:
1203:
1197:
1191:
1185:
1179:
1176:
1173:
1160:
1157:
1153:
1149:
1145:
1141:
1137:
1133:
1114:
1108:
1093:
1087:
1081:
1075:
1069:
1056:
1053:
1049:
1045:
1041:
1037:
1018:
1012:
1009:
994:
991:
988:
975:
972:
971:
966:
962:
958:
954:
951:implies both
950:
934:
922:
913:
904:
898:
892:
876:
873:
869:
865:
861:
857:
838:
829:
814:
808:
798:
795:
773:, and assign
772:
768:
764:
760:
756:
752:
748:
729:
723:
720:
710:
709:
708:
694:
688:
680:
676:
672:
668:
664:
660:
655:
653:
649:
638:
628:
622:
618:
613:
609:
604:
603:
597:
595:
593:
589:
570:
567:
564:
553:
549:
544:
527:
518:
512:
503:
497:
494:
491:
480:
477:representing
456:
452:
449:representing
436:
416:
408:
404:
400:
396:
392:
386:
378:
376:
372:
370:
366:
362:
358:
354:
349:
347:
341:
336:
334:
330:
326:
325:
320:
316:
315:
309:
306:
302:
301:Gottlob Frege
297:
295:
292:refers to an
291:
285:
284:
283:tautological.
280:
276:
272:
268:
262:
260:
256:
255:Immanuel Kant
251:
249:
245:
241:
233:
231:
229:
225:
224:proper subset
220:
216:
212:
207:
205:
201:
197:
193:
188:
186:
182:
138:
134:
130:
126:
110:
107:
99:
94:
92:
88:
83:
81:
77:
73:
69:
65:
60:
58:
53:
49:
45:
37:
36:Ancient Greek
33:
29:
22:
7226:Propositions
7101:
7050:
6956:
6930:
6853:
6833:formal proof
6802:
6574:Joint denial
6498:Exclusive or
6302:
6124:Substitution
5944:Mathematical
5869:Major fields
5794:
5592:Ultraproduct
5439:Model theory
5404:Independence
5340:Formal proof
5332:Proof theory
5315:
5288:
5245:real numbers
5217:second-order
5128:Substitution
5005:Metalanguage
4946:conservative
4919:Axiom schema
4863:Constructive
4833:Morse–Kelley
4799:Set theories
4778:Aleph number
4771:inaccessible
4677:Grothendieck
4561:intersection
4448:Higher-order
4436:Second-order
4382:Truth tables
4339:Venn diagram
4281:
4122:Formal proof
4041:
4015:
4011:
3994:
3972:
3946:
3924:
3887:
3883:
3874:
3861:
3852:
3846:
3837:
3831:
3822:
3816:
3807:
3801:
3792:
3786:
3775:. Retrieved
3771:
3748:. Retrieved
3744:
3734:
3716:
3615:Normal forms
3566:
3532:
3470:
3243:
3074:
3070:
3066:
2957:
2952:
2948:
2944:
2938:
2893:
2887:
2881:
2875:
2862:
2858:
2855:truth tables
2852:
2845:
2825:
2817:
2713:
2644:
2583:
2544:
2542:
2533:Substitution
2508:
2486:
2464:
2442:
2420:
2418:
2395:
2373:
2351:
2277:
2226:
2204:
2182:
2160:
2138:
2075:
2073:
2016:
2012:
2008:
2004:
2000:
1998:
1978:
1974:
1968:
1963:
1961:
1460:
1456:
1452:
1450:
1367:
1353:
1351:
1263:
1253:
1249:
1245:
1241:
1151:
1147:
1143:
1139:
1135:
1131:
1047:
1043:
1039:
1035:
968:
964:
960:
956:
952:
948:
867:
866:implies not-
863:
859:
855:
793:
770:
766:
762:
758:
750:
746:
678:
674:
670:
666:
662:
658:
656:
647:
645:
632:
617:too abstract
616:
591:
587:
551:
547:
545:
406:
402:
398:
394:
390:
388:
373:
350:
345:
343:
338:
322:
312:
310:
304:
298:
289:
287:
282:
278:
275:non-explicit
274:
270:
266:
264:
258:
252:
237:
208:
189:
132:
128:
124:
95:
84:
61:
31:
25:
7152:existential
6792:truth value
6785:Functional:
6657:Conjunction
6607:NIMPLY gate
6432:Disjunction
6403:Implication
6239:WikiProject
6109:Proposition
6104:Probability
6057:Description
5998:Foundations
5702:Type theory
5650:undecidable
5582:Truth value
5469:equivalence
5148:non-logical
4761:Enumeration
4751:Isomorphism
4698:cardinality
4682:Von Neumann
4647:Ultrafilter
4612:Uncountable
4546:equivalence
4463:Quantifiers
4453:Fixed-point
4422:First-order
4302:Consistency
4287:Proposition
4264:Traditional
4235:Lindström's
4225:Compactness
4167:Type theory
4112:Cardinality
4038:"Tautology"
3741:"Tautology"
2949:tautologies
2921:NP-complete
2003:is said to
1363:truth table
1359:truth value
1042:, then not-
959:, then not-
862:, then not-
665:is bound",
455:conjunction
451:disjunction
215:quantifiers
80:satisfiable
7200:Categories
6407:IMPLY gate
6169:Set theory
6067:Linguistic
6062:Entailment
6052:Definition
6020:Consequent
6015:Antecedent
5513:elementary
5206:arithmetic
5074:Quantifier
5052:functional
4924:Expression
4642:Transitive
4586:identities
4571:complement
4504:hereditary
4487:Set theory
3867:SAT solver
3777:2020-08-14
3750:2020-08-14
3726:References
2372:will make
2007:a formula
1999:A formula
379:Background
305:Grundlagen
240:pejorative
74:, where a
40:ταυτολογία
7231:Semantics
7136:universal
7014:therefore
7002:therefore
6957:tautology
6803:tautology
6708:⊥
6671:∧
6642:↚
6617:↛
6588:↓
6556:Statement
6541:↔
6531:XNOR gate
6483:¬
6446:∨
6417:→
6388:←
6363:↑
6353:NAND gate
6317:⊤
6303:Tautology
6200:Fallacies
6195:Paradoxes
6185:Logicians
6119:Statement
6114:Reference
6079:Induction
6042:Deduction
6005:Abduction
5975:Metalogic
5922:Classical
5886:Inference
5784:Supertask
5687:Recursion
5645:decidable
5479:saturated
5457:of models
5380:deductive
5375:axiomatic
5295:Hilbert's
5282:Euclidean
5263:canonical
5186:axiomatic
5118:Signature
5047:Predicate
4936:Extension
4858:Ackermann
4783:Operation
4662:Universal
4652:Recursive
4627:Singleton
4622:Inhabited
4607:Countable
4597:Types of
4581:power set
4551:partition
4468:Predicate
4414:Predicate
4329:Syllogism
4319:Soundness
4292:Inference
4282:Tautology
4184:paradoxes
4048:EMS Press
3937:D. Reidel
3929:Dordrecht
3904:0028-1425
3678:Syllogism
3591:→
3585:¬
3582:¬
3544:→
3512:¬
3506:∃
3503:¬
3500:→
3485:∀
3447:→
3438:→
3429:⇔
3420:→
3411:∧
3373:∀
3324:∃
3321:¬
3272:∃
3211:∀
3208:→
3193:∃
3190:¬
3181:→
3166:∃
3157:⇔
3142:∀
3139:→
3121:∃
3115:¬
3112:∧
3097:∃
3032:∀
3029:¬
3023:∨
2999:∀
2973:¬
2970:∨
2904:¬
2797:→
2788:¬
2785:∨
2776:∨
2767:¬
2764:∨
2752:→
2743:∧
2734:∨
2696:→
2663:∨
2626:¬
2623:∨
2617:¬
2614:∨
2605:∧
2335:⊨
2309:∧
2261:¬
2258:∨
2119:¬
2116:∨
2107:∧
2056:→
2030:⊨
1728:→
1719:→
1710:⇔
1701:→
1692:∧
1656:→
1647:→
1620:→
1593:→
1584:∧
1554:∧
1424:→
1415:→
1406:⇔
1397:→
1388:∧
1328:→
1299:∨
1290:→
1281:∨
1225:→
1213:→
1204:∧
1195:→
1186:∧
1177:∨
1112:→
1103:→
1091:→
1082:∧
1073:→
1016:¬
1013:∨
1007:¬
1001:⇔
992:∧
983:¬
947:("if not-
932:→
920:¬
917:→
911:¬
905:∧
896:→
890:¬
836:¬
833:→
827:¬
821:⇔
812:→
781:¬
727:¬
724:∨
692:→
648:tautology
568:∧
525:¬
519:∨
510:¬
504:∨
495:∧
465:¬
437:∧
417:∨
399:valuation
333:synthetic
299:In 1884,
279:implicita
271:explicita
253:In 1800,
167:⊥
147:⊤
108:⊨
100:notation
76:tautology
32:tautology
7089:superset
7000:entails,
6986:entails,
6661:AND gate
6578:NOR gate
6512:↮
6502:XOR gate
6473:NOT gate
6469:Negation
6234:Category
6134:Validity
6035:Antinomy
5963:Theories
5927:Informal
5769:Logicism
5762:timeline
5738:Concrete
5597:Validity
5567:T-schema
5560:Kripke's
5555:Tarski's
5550:semantic
5540:Strength
5489:submodel
5484:spectrum
5452:function
5300:Tarski's
5289:Elements
5276:geometry
5232:Robinson
5153:variable
5138:function
5111:spectrum
5101:Sentence
5057:variable
5000:Language
4953:Relation
4914:Automata
4904:Alphabet
4888:language
4742:-jection
4720:codomain
4706:Function
4667:Universe
4637:Infinite
4541:Relation
4324:Validity
4314:Argument
4212:theorem,
3993:(1947).
3951:Harcourt
3610:See also
2832:complete
2678:and let
1150:implies
1142:implies
1134:implies
858:implies
753:"), the
635:May 2020
479:negation
267:explicit
72:rhetoric
7105:
7084:implies
7072:implies
7054:
7026:because
6934:
6909:Common
6838:theorem
6821:Formal:
6779: ⊤
6663:)
6659: (
6609:)
6605: (
6580:)
6576: (
6558: (
6533:)
6529: (
6504:)
6500: (
6475:)
6471: (
6438:)
6436:OR gate
6434: (
6409:)
6405: (
6355:)
6351: (
6290:Common
6249:changes
6241: (
6099:Premise
6030:Paradox
5860:History
5855:Outline
5711:Related
5508:Diagram
5406: (
5385:Hilbert
5370:Systems
5365:Theorem
5243:of the
5188:systems
4968:Formula
4963:Grammar
4879: (
4823:General
4536:Forcing
4521:Element
4441:Monadic
4216:paradox
4157:Theorem
4093:General
4050:, 2001
4026:, 1922.
3971:(1967)
3945:(2002)
3923:(1959)
2324:. Then
2137:. Then
1540:
1520:
1515:
1495:
1490:
1470:
1252:, then
1146:, then
1046:or not-
749:or not
627:improve
625:Please
395:formula
340:others.
311:In his
234:History
198:of its
139:symbol
135:". The
44:formula
42:) is a
7099:
7048:
6988:proves
6928:
6856:
6828:theory
6700:
6634:
6380:
6309:
6151:topics
5937:Reason
5915:Logics
5906:Syntax
5474:finite
5237:Skolem
5190:
5165:Theory
5133:Symbol
5123:String
5106:atomic
4983:ground
4978:closed
4973:atomic
4929:ground
4892:syntax
4788:binary
4715:domain
4632:Finite
4397:finite
4255:Logics
4214:
4162:Theory
4024:London
4001:
3983:
3961:
3902:
3717:
3345:, and
2876:As an
2416:true.
365:Tarski
355:or of
344:Here,
288:Here,
181:falsum
34:(from
6969:false
6936:&
6858:false
6698:False
6178:other
6143:Lists
6129:Truth
5896:Proof
5844:Logic
5464:Model
5212:Peano
5069:Proof
4909:Arity
4838:Naive
4725:image
4657:Fuzzy
4617:Empty
4566:union
4511:Class
4152:Model
4142:Lemma
4100:Axiom
3365:with
3313:with
3264:with
2951:(or,
2836:sound
1130:("if
854:("if
771:false
369:Gödel
273:) or
259:Logic
228:model
48:terms
7123:nand
6952:true
6307:True
6243:talk
6089:Name
6074:Form
5587:Type
5390:list
5194:list
5171:list
5160:Term
5094:rank
4988:open
4882:list
4694:Maps
4599:sets
4458:Free
4428:list
4178:list
4105:list
4022:and
3999:ISBN
3981:ISBN
3959:ISBN
3900:ISSN
3865:See
2645:Let
1138:and
1038:and
767:true
550:and
453:and
429:and
405:and
367:and
185:true
96:The
30:, a
7111:iff
7060:not
6940:and
5985:Set
5274:of
5256:of
5204:of
4736:Sur
4710:Map
4517:Ur-
4499:Set
3892:doi
3888:114
2830:is
2826:An
2685:be
2652:be
2570:in
2555:in
2096:be
1244:or
769:or
590:or
230:).
137:tee
26:In
7202::
7102:or
7051:or
7038:or
6931:or
5660:NP
5284::
5278::
5208::
4885:),
4740:Bi
4732:In
4046:,
4040:,
4018:,
3979:,
3957:,
3949:,
3935::
3931:,
3898:.
3886:.
3882:.
3770:.
3759:^
3743:.
3571::
3468:.
3293:,
2873:.
2850:.
2711:.
1956:T
1930:T
1904:T
1878:T
1852:T
1826:T
1800:T
1774:T
1459:,
1455:,
745:("
681:,
543:.
261::
133:pq
129:pq
59:.
38::
7147:∃
7131:∀
7119:|
7107:≡
7097:↔
7086:,
7080:⊃
7068:→
7056:~
7046:¬
7034:∨
7022:∵
7010:∴
6996:⊨
6982:⊢
6971:,
6965:⊥
6954:,
6948:⊤
6926:∧
6902:e
6895:t
6888:v
6854:⊥
6775:
6768:e
6761:t
6754:v
6696:/
6562:)
6305:/
6283:e
6276:t
6269:v
6245:)
5836:e
5829:t
5822:v
5740:/
5655:P
5410:)
5196:)
5192:(
5089:∀
5084:!
5079:∃
5040:=
5035:↔
5030:→
5025:∧
5020:∨
5015:¬
4738:/
4734:/
4708:/
4519:)
4515:(
4402:∞
4392:3
4180:)
4078:e
4071:t
4064:v
3987:.
3965:.
3953:/
3939:.
3906:.
3894::
3780:.
3753:.
3594:A
3588:A
3547:B
3541:A
3518:x
3515:R
3509:x
3497:)
3494:x
3491:R
3488:x
3482:(
3456:)
3453:)
3450:C
3444:B
3441:(
3435:A
3432:(
3426:)
3423:C
3417:)
3414:B
3408:A
3405:(
3402:(
3382:x
3379:T
3376:x
3353:C
3333:x
3330:S
3327:x
3301:B
3281:x
3278:R
3275:x
3252:A
3229:.
3226:)
3223:)
3220:x
3217:T
3214:x
3205:)
3202:x
3199:S
3196:x
3187:(
3184:(
3178:)
3175:x
3172:R
3169:x
3163:(
3160:(
3154:)
3151:x
3148:T
3145:x
3136:)
3133:)
3130:x
3127:S
3124:x
3118:(
3109:)
3106:x
3103:R
3100:x
3094:(
3091:(
3088:(
3075:T
3073:,
3071:S
3069:,
3067:R
3053:)
3050:)
3047:x
3044:=
3041:x
3038:(
3035:x
3026:(
3020:)
3017:)
3014:x
3011:=
3008:x
3005:(
3002:x
2996:(
2976:A
2967:A
2907:S
2894:S
2882:k
2863:F
2859:T
2803:)
2800:E
2794:C
2791:(
2782:)
2779:D
2773:C
2770:(
2761:)
2758:)
2755:E
2749:C
2746:(
2740:)
2737:D
2731:C
2728:(
2725:(
2699:E
2693:C
2682:B
2680:S
2666:D
2660:C
2649:A
2647:S
2641:.
2629:B
2620:A
2611:)
2608:B
2602:A
2599:(
2586:S
2578:A
2576:S
2572:S
2568:A
2563:A
2561:S
2557:S
2553:A
2549:S
2516:S
2494:S
2472:R
2450:R
2428:R
2403:S
2381:A
2359:R
2338:S
2332:R
2312:C
2306:A
2285:R
2264:B
2255:B
2234:S
2212:A
2190:S
2168:A
2146:S
2125:)
2122:B
2113:B
2110:(
2104:A
2083:S
2059:S
2053:R
2033:S
2027:R
2017:S
2013:R
2009:S
2001:R
1979:n
1975:n
1964:T
1953:T
1950:T
1947:T
1944:F
1941:F
1938:F
1935:F
1927:T
1924:T
1921:T
1918:F
1915:T
1912:F
1909:F
1901:T
1898:F
1895:T
1892:F
1889:F
1886:T
1883:F
1875:T
1872:T
1869:T
1866:F
1863:T
1860:T
1857:F
1849:T
1846:T
1843:T
1840:F
1837:F
1834:F
1831:T
1823:T
1820:T
1817:T
1814:F
1811:T
1808:F
1805:T
1797:F
1794:F
1791:F
1788:T
1785:F
1782:T
1779:T
1771:T
1768:T
1765:T
1762:T
1759:T
1756:T
1753:T
1737:)
1734:)
1731:C
1725:B
1722:(
1716:A
1713:(
1707:)
1704:C
1698:)
1695:B
1689:A
1686:(
1683:(
1662:)
1659:C
1653:B
1650:(
1644:A
1623:C
1617:B
1596:C
1590:)
1587:B
1581:A
1578:(
1557:B
1551:A
1528:C
1503:B
1478:A
1461:C
1457:B
1453:A
1436:.
1433:)
1430:)
1427:C
1421:B
1418:(
1412:A
1409:(
1403:)
1400:C
1394:)
1391:B
1385:A
1382:(
1379:(
1354:n
1343:.
1331:C
1325:C
1305:)
1302:B
1296:A
1293:(
1287:)
1284:B
1278:A
1275:(
1254:C
1250:C
1246:B
1242:A
1228:C
1222:)
1219:)
1216:C
1210:B
1207:(
1201:)
1198:C
1192:A
1189:(
1183:)
1180:B
1174:A
1171:(
1168:(
1152:C
1148:A
1144:C
1140:B
1136:B
1132:A
1118:)
1115:C
1109:A
1106:(
1100:)
1097:)
1094:C
1088:B
1085:(
1079:)
1076:B
1070:A
1067:(
1064:(
1048:B
1044:A
1040:B
1036:A
1022:)
1019:B
1010:A
1004:(
998:)
995:B
989:A
986:(
965:A
961:A
957:B
953:B
949:A
935:A
929:)
926:)
923:B
914:A
908:(
902:)
899:B
893:A
887:(
884:(
868:A
864:B
860:B
856:A
842:)
839:A
830:B
824:(
818:)
815:B
809:A
806:(
794:A
763:A
759:A
751:A
747:A
733:)
730:A
721:A
718:(
695:B
689:A
679:X
675:X
671:X
667:B
663:X
659:A
637:)
633:(
623:.
592:B
588:A
574:)
571:B
565:A
562:(
552:B
548:A
531:)
528:B
522:(
516:)
513:A
507:(
501:)
498:B
492:A
489:(
407:B
403:A
277:(
269:(
179:(
125:S
111:S
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.