In

^{''n''} 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 ^{''n''} lines, which quickly becomes infeasible as ''n'' increases). Proof systems are also required for the study of intuitionistic propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed.

^{''k''}, where ''k'' 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.
The problem of determining whether there is any valuation that makes a formula true is the

mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

, a tautology (from el, ταυτολογία) is a formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a '' chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betw ...

or assertion that is true in every possible interpretation. An example is "x=y or x≠y". Similarly, "either the ball is green, or the ball is not green" is always true, regardless of the colour of the ball.
The philosopher Ludwig Wittgenstein
Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrian- British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He is consid ...

first applied the term to redundancies of propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...

in 1921, borrowing from rhetoric
Rhetoric () is the art of persuasion, which along with grammar and logic (or dialectic), is one of the three ancient arts of discourse. Rhetoric aims to study the techniques writers or speakers utilize to inform, persuade, or motivate p ...

, where a tautology is a repetitive statement. In logic, a formula is satisfiable
In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...

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. It cannot be untrue.
Unsatisfiable statements, both through negation and affirmation, are known formally as contradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

s. A formula that is neither a tautology nor a contradiction is said to be logically contingent.
Such a formula can be made either true or false based on the values assigned to its propositional variables. The double turnstile notation $\backslash vDash\; S$ is used to indicate that ''S'' is a tautology. Tautology is sometimes symbolized by "V''pq''", and contradiction by "O''pq''". The tee symbol $\backslash top$ is sometimes used to denote an arbitrary tautology, with the dual symbol $\backslash bot$ (falsum
The up tack or falsum (⊥, \bot in LaTeX, U+22A5 in Unicode) is a constant symbol used to represent:
* The truth value 'false', or a logical constant denoting a proposition in logic that is always false (often called "falsum" or "absurdum").
* T ...

) representing an arbitrary contradiction; in any symbolism, a tautology may be substituted for the truth value "true
True most commonly refers to truth, the state of being in congruence with fact or reality.
True may also refer to:
Places
* True, West Virginia, an unincorporated community in the United States
* True, Wisconsin, a town in the United States
* ...

", as symbolized, for instance, by "1".
Tautologies are a key concept in propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...

, where a tautology is defined as a propositional formula that is true under any possible Boolean valuation of its propositional variable
In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of proposit ...

s. A key property of tautologies in propositional logic is that an effective method
In logic, mathematics and computer science, especially metalogic and computability theory, an effective method Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971 or ...

exists for testing whether a given formula is always satisfied (equiv., whether its negation is unsatisfiable).
The definition of tautology can be extended to sentences in predicate logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

, which may contain quantifiers—a feature absent from sentences of propositional logic.
Indeed, in propositional logic, there is no distinction between a tautology and a logically valid 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 formulas is a proper subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...

of the set of logically valid sentences of predicate logic (i.e., sentences that are true in every model
A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure.
Models ...

).
History

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, apejorative
A pejorative or slur is a word or grammatical form expressing a negative or a disrespectful connotation, a low opinion, or a lack of respect toward someone or something. It is also used to express criticism, hostility, or disregard. Sometimes, a ...

meaning that is still used for rhetorical tautologies. Between 1800 and 1940, the word gained new meaning in logic, and is currently used in mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

to denote a certain type of propositional formula, without the pejorative connotations it originally possessed.
In 1800, Immanuel Kant
Immanuel Kant (, , ; 22 April 1724 – 12 February 1804) was a German philosopher and one of the central Enlightenment thinkers. Born in Königsberg, Kant's comprehensive and systematic works in epistemology, metaphysics, ethics, and ...

wrote in his book ''Logic'':
Here, ''analytic proposition'' refers to an analytic truth, a statement in natural language that is true solely because of the terms involved.
In 1884, Gottlob Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic phi ...

proposed in his ''Grundlagen'' 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).
In his ''Tractatus Logico-Philosophicus
The ''Tractatus Logico-Philosophicus'' (widely abbreviated and cited as TLP) is a book-length philosophical work by the Austrian philosopher Ludwig Wittgenstein which deals with the relationship between language and reality and aims to define th ...

'' 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. Henri Poincaré
Jules Henri Poincaré ( S: stress final syllable ; 29 April 1854 – 17 July 1912) was a French mathematician, theoretical physicist, engineer, and philosopher of science. He is often described as a polymath, and in mathematics as "The ...

had made similar remarks in '' Science and Hypothesis'' in 1905. Although Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, a ...

at first argued against these remarks by Wittgenstein and Poincaré, claiming that mathematical truths were not only non-tautologous but were synthetic, he later spoke in favor of them in 1918:
Here, ''logical proposition'' refers to a proposition that is provable using the laws of logic.
During the 1930s, the formalization of the semantics of propositional logic in terms of truth assignments was developed. The term "tautology" began to be applied to those propositional formulas that are true regardless of the truth or falsity of their propositional variables. Some early books on logic (such as ''Symbolic Logic'' by C. I. Lewis and Langford, 1932) used the term for any proposition (in any formal logic) that is universally valid. It is common in presentations after this (such as Stephen Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch ...

1967 and Herbert Enderton 2002) to use tautology to refer to a logically valid propositional formula, but to maintain a distinction between "tautology" and "logically valid" in the context of first-order logic .
Background

Propositional logic begins with propositional variables, atomic units that represent concrete propositions. A formula 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 valuation is a function that assigns each propositional variable to either T (for truth) or F (for falsity). So by using the propositional variables ''A'' and ''B'', the binary connectives $\backslash lor$ and $\backslash land$ representingdisjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...

and conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy)
In astronomy
Astronomy ...

respectively, and the unary connective $\backslash lnot$ representing negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fal ...

, the following formula can be obtained:$(A\; \backslash land\; B)\; \backslash lor\; (\backslash lnot\; A)\; \backslash lor\; (\backslash lnot\; B)$.
A valuation here must assign to each of ''A'' and ''B'' either T or F. But no matter how this assignment is made, the overall formula will come out true. For if the first conjunction $(A\; \backslash land\; B)$ is not satisfied by a particular valuation, then one of ''A'' and ''B'' is assigned F, which will make one of the following disjunct to be assigned T.
Definition and examples

A formula of propositional logic is a ''tautology'' if the formula itself is always true, regardless of which valuation is used for thepropositional variable
In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of proposit ...

s. There are infinitely many tautologies. Examples include:
* $(A\; \backslash lor\; \backslash lnot\; A)$ ("''A'' or not ''A''"), the law of excluded middle
In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncon ...

. This formula has only one propositional variable, ''A''. Any valuation for this formula must, by definition, assign ''A'' one of the truth values ''true'' or ''false'', and assign $\backslash lnot$''A'' the other truth value. For instance, "The cat is black or the cat is not black".
* $(A\; \backslash to\; B)\; \backslash Leftrightarrow\; (\backslash lnot\; B\; \backslash to\; \backslash lnot\; A)$ ("if ''A'' implies ''B'', then not-''B'' implies not-''A''", and vice versa), which expresses the law of contraposition
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stateme ...

. For instance, "If it's a book, it is blue; if it's not blue, it's not a book."
* $((\backslash lnot\; A\; \backslash to\; B)\; \backslash land\; (\backslash lnot\; A\; \backslash to\; \backslash lnot\; B))\; \backslash to\; A$ ("if not-''A'' implies both ''B'' and its negation not-''B'', then not-''A'' must be false, then ''A'' must be true"), which is the principle known as ''reductio ad absurdum
In logic, (Latin for "reduction to absurdity"), also known as (Latin for "argument to absurdity") or ''apagogical arguments'', is the form of argument that attempts to establish a claim by showing that the opposite scenario would lead to absu ...

''. For instance, "If it's not blue, it's a book, if it's not blue, it's also not a book, so it is blue."
* $\backslash lnot(A\; \backslash land\; B)\; \backslash Leftrightarrow\; (\backslash lnot\; A\; \backslash lor\; \backslash lnot\; B)$ ("if not both ''A'' and ''B'', then not-''A'' or not-''B''", and vice versa), which is known as De Morgan's law
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathe ...

. "If it is not both blue and a book, then it's either not a book or it's not blue"
* $((A\; \backslash to\; B)\; \backslash land\; (B\; \backslash to\; C))\; \backslash to\; (A\; \backslash to\; C)$ ("if ''A'' implies ''B'' and ''B'' implies ''C'', then ''A'' implies ''C''"), which is the principle known as syllogism
A syllogism ( grc-gre, συλλογισμός, ''syllogismos'', 'conclusion, inference') is a kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two propositions that are asserted or assumed to be true ...

. "If it's a book, then it's blue and if it's blue, then it's on that shelf, then if it's a book, it's on that shelf."
* $((A\; \backslash lor\; B)\; \backslash land\; (A\; \backslash to\; C)\; \backslash land\; (B\; \backslash to\; C))\; \backslash to\; C$ ("if at least one of ''A'' or ''B'' is true, and each implies ''C'', then ''C'' must be true as well"), which is the principle known as proof by cases
Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equiv ...

. "Books and blue things are on that shelf. If it's either a book or it's blue, it's on that shelf."
A minimal tautology is a tautology that is not the instance of a shorter tautology.
* $(A\; \backslash lor\; B)\; \backslash to\; (A\; \backslash lor\; B)$ is a tautology, but not a minimal one, because it is an instantiation of $C\; \backslash to\; C$.
Verifying tautologies

The problem of determining whether a formula is a tautology is fundamental in propositional logic. If there are ''n'' variables occurring in a formula then there are 2truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false'').
Computing
In some progra ...

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 truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...

that includes every possible valuation.
For example, consider the formula
:$((A\; \backslash land\; B)\; \backslash to\; C)\; \backslash Leftrightarrow\; (A\; \backslash to\; (B\; \backslash to\; C)).$
There are 8 possible valuations for the propositional variables ''A'', ''B'', ''C'', 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.
Because each row of the final column shows ''T'', the sentence in question is verified to be a tautology.
It is also possible to define a deductive system (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 ''n'' propositional variables requires a truth table with 2Tautological implication

A formula ''R'' is said to tautologically imply a formula ''S'' if every valuation that causes ''R'' to be true also causes ''S'' to be true. This situation is denoted $R\; \backslash models\; S$. It is equivalent to the formula $R\; \backslash to\; S$ being a tautology (Kleene 1967 p. 27). For example, let ''$S$'' be $A\; \backslash land\; (B\; \backslash lor\; \backslash lnot\; B)$. Then ''$S$'' is not a tautology, because any valuation that makes ''$A$'' false will make ''$S$'' false. But any valuation that makes ''$A$'' true will make ''$S$'' true, because $B\; \backslash lor\; \backslash lnot\; B$ is a tautology. Let ''$R$'' be the formula $A\; \backslash land\; C$. Then $R\; \backslash models\; S$, because any valuation satisfying ''$R$'' will make ''$A$'' true—and thus makes ''$S$'' true. It follows from the definition that if a formula ''$R$'' is a contradiction, then ''$R$'' tautologically implies every formula, because there is no truth valuation that causes ''$R$'' to be true, and so the definition of tautological implication is trivially satisfied. Similarly, if ''$S$'' is a tautology, then ''$S$'' is tautologically implied by every formula.Substitution

There is a general procedure, the substitution rule, that allows additional tautologies to be constructed from a given tautology (Kleene 1967 sec. 3). Suppose that is a tautology and for each propositional variable in a fixed sentence is chosen. Then the sentence obtained by replacing each variable in with the corresponding sentence is also a tautology. For example, let be the tautology :$(A\; \backslash land\; B)\; \backslash lor\; \backslash lnot\; A\; \backslash lor\; \backslash lnot\; B$. Let be $C\; \backslash lor\; D$ and let be $C\; \backslash to\; E$. It follows from the substitution rule that the sentence :$((C\; \backslash lor\; D)\; \backslash land\; (C\; \backslash to\; E))\; \backslash lor\; \backslash lnot\; (C\; \backslash lor\; D)\; \backslash lor\; \backslash lnot\; (C\; \backslash to\; E)$Semantic completeness and soundness

An axiomatic system is complete if every tautology is a theorem (derivable from axioms). An axiomatic system issound
In physics, sound is a vibration that propagates as an acoustic wave, through a transmission medium such as a gas, liquid or solid.
In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' by ...

if every theorem is a tautology.
Efficient verification and the Boolean satisfiability problem

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 ofautomated theorem proving
Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a ma ...

.
The method of truth tables illustrated above is provably correct – the truth table for a tautology will end in a column with only ''T'', while the truth table for a sentence that is not a tautology will contain a row whose final column is ''F'', 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 effective procedure, 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 decidable set.
As an efficient procedure, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

; the problem of checking tautologies is equivalent to this problem, because verifying that a sentence ''S'' is a tautology is equivalent to verifying that there is no valuation satisfying $\backslash lnot\; S$. It is known that the Boolean satisfiability problem is NP complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

, and widely believed that there is no polynomial-time algorithm that can perform it. Consequently, tautology is co-NP-complete
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial ...

. Current research focuses on finding algorithms that perform well on special classes of formulas, or terminate quickly on average even though some inputs may cause them to take much longer.
Tautologies versus validities in first-order logic

The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences infirst-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...

. These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between ''logical validities'', sentences that are true in every model, and ''tautologies'' (or, ''tautological validities''), which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide.
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 $A\; \backslash lor\; \backslash lnot\; A$ is a tautology of propositional logic, $(\backslash forall\; x\; (\; x\; =\; x))\; \backslash lor\; (\backslash lnot\; \backslash forall\; x\; (x\; =\; x))$ is a tautology in first order logic. Similarly, in a first-order language with a unary relation symbols ''R'',''S'',''T'', the following sentence is a tautology:
:$(((\backslash exists\; x\; Rx)\; \backslash land\; \backslash lnot\; (\backslash exists\; x\; Sx))\; \backslash to\; \backslash forall\; x\; Tx)\; \backslash Leftrightarrow\; ((\backslash exists\; x\; Rx)\; \backslash to\; ((\backslash lnot\; \backslash exists\; x\; Sx)\; \backslash to\; \backslash forall\; x\; Tx)).$
It is obtained by replacing $A$ with $\backslash exists\; x\; Rx$, $B$ with $\backslash lnot\; \backslash exists\; x\; Sx$, and $C$ with $\backslash forall\; x\; Tx$ in the propositional tautology $((A\; \backslash land\; B)\; \backslash to\; C)\; \backslash Leftrightarrow\; (A\; \backslash to\; (B\; \backslash to\; C))$.
Not all logical validities are tautologies in first-order logic. For example, the sentence
:$(\backslash forall\; x\; Rx)\; \backslash to\; \backslash lnot\; \backslash exists\; x\; \backslash lnot\; Rx$
is true in any first-order interpretation, but it corresponds to the propositional sentence $A\; \backslash to\; B$ which is not a tautology of propositional logic.
See also

Normal forms

*Algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...

* Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a ...

* Disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster ...

* Logic optimization
Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit ...

Related logical topics

*Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...

* Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written ...

* Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...

* Contradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

* False (logic)
In logic, false or untrue is the state of possessing negative truth value or a nullary logical connective. In a truth-functional system of propositional logic, it is one of two postulated truth values, along with its negation, truth. Usual ...

* Syllogism
A syllogism ( grc-gre, συλλογισμός, ''syllogismos'', 'conclusion, inference') is a kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two propositions that are asserted or assumed to be true ...

* List of logic symbols
In logic, a set of symbols is commonly used to express logical representation. The following table lists many common symbols, together with their name, how they should be read out loud, and the related field of mathematics. Additionally, the subs ...

* Logic synthesis
In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a com ...

* Logical consequence
Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is on ...

* Logical graph
* Logical truth
Logical truth is one of the most fundamental concepts in logic. Broadly speaking, a logical truth is a statement which is true regardless of the truth or falsity of its constituent propositions. In other words, a logical truth is a statement whi ...

* Vacuous truth
In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "s ...

References

Further reading

* Bocheński, J. M. (1959) ''Précis of Mathematical Logic'', translated from the French and German editions by Otto Bird,Dordrecht
Dordrecht (), historically known in English as Dordt (still colloquially used in Dutch, ) or Dort, is a city and municipality in the Western Netherlands, located in the province of South Holland. It is the province's fifth-largest city after Ro ...

, South Holland
South Holland ( nl, Zuid-Holland ) is a province of the Netherlands with a population of over 3.7 million as of October 2021 and a population density of about , making it the country's most populous province and one of the world's most densely ...

: D. Reidel.
* Enderton, H. B. (2002) ''A Mathematical Introduction to Logic'', Harcourt/Academic Press
Academic Press (AP) is an academic book publisher founded in 1941. It was acquired by Harcourt, Brace & World in 1969. Reed Elsevier bought Harcourt in 2000, and Academic Press is now an imprint of Elsevier.
Academic Press publishes refe ...

, .
* Kleene, S. C. (1967) ''Mathematical Logic'', reprinted 2002, Dover Publications
Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward and Blanche Cirker. It primarily reissues books that are out of print from their original publishers. These are often, but not always, book ...

, .
* Reichenbach, H. (1947). ''Elements of Symbolic Logic'', reprinted 1980, Dover,
* Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung", ''Annalen der Naturphilosophie'' (Leipzig), v. 14, pp. 185–262, reprinted in English translation as ''Tractatus logico-philosophicus'', New York City
New York, often called New York City or NYC, is the most populous city in the United States. With a 2020 population of 8,804,190 distributed over , New York City is also the most densely populated major city in the U ...

and London
London is the capital and largest city of England and the United Kingdom, with a population of just under 9 million. It stands on the River Thames in south-east England at the head of a estuary down to the North Sea, and has been a ma ...

, 1922.
External links

* {{DEFAULTSORT:Tautology (Logic) Logical expressions Logical truth Mathematical logic Propositional calculus Propositions Semantics Sentences by type