Tautology (logic)

Logically, a tautology is an identically true statement that is invariant with respect to the values of its components.

The fact that formula A is a tautology is denoted by $\vDash A$ ${\ displaystyle \ vDash A}$ $\ vDash A$ . Each logical calculus has its own many tautologies.

Building Tautologies

To find out if a given formula is a tautology, there is a simple way in the propositional algebra - constructing a truth table . In the calculus of propositions, tautologies are axioms (more precisely, axiom schemes), as well as all formulas that can be obtained from known tautologies using the specified inference rules (most often it is Modus ponens and the substitution rule ). Checking whether a given formula in the calculus of propositions is a tautology is more complicated and also depends on the system of axioms and the available inference rules.
The problem of determining whether an arbitrary formula in predicate logic is a tautology is algorithmically unsolvable.

Tautology Examples

Tautologies of propositional calculus (and propositional algebra)

$A\rightarrow A$ ${\ displaystyle A \ rightarrow A}$ $A\rightarrow A$ (“ A follows from A ”) - the law of identity
$(A)\lor (\lnot A)$ ${\ displaystyle (A) \ lor (\ lnot A)}$ $(A)\lor (\lnot A)$ (“ A or non- A ”) - the law of the excluded third
$\neg (P\land \neg P)$ ${\ displaystyle \ neg (P \ land \ neg P)}$ $\neg (P\land \neg P)$ - law of negation of contradiction
$\neg \neg P\rightarrow P$ ${\ displaystyle \ neg \ neg P \ rightarrow P}$ $\neg \neg P\rightarrow P$ - the law of double negation
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ ${\ displaystyle (P \ leftrightarrow Q) \ leftrightarrow (\ neg Q \ leftrightarrow \ neg P)}$ $(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - the law of opposites
$(P\land Q)\leftrightarrow (Q\land P)$ ${\ displaystyle (P \ land Q) \ leftrightarrow (Q \ land P)}$ $(P\land Q)\leftrightarrow (Q\land P)$ - commutativity of conjunction
$(P\lor Q)\leftrightarrow (Q\lor P)$ ${\ displaystyle (P \ lor Q) \ leftrightarrow (Q \ lor P)}$ $(P\lor Q)\leftrightarrow (Q\lor P)$ - commutativity of disjunction
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ ${\ displaystyle [(P \ land Q) \ land R] \ leftrightarrow [P \ land (Q \ land R)]}$ $[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - associativity of conjunction
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ ${\ displaystyle [(P \ lor Q) \ lor R] \ leftrightarrow [P \ lor (Q \ lor R)]}$ $[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - associativity of disjunction
$(P\land (P\rightarrow Q))\rightarrow Q$ ${\ displaystyle (P \ land (P \ rightarrow Q)) \ rightarrow Q}$ $(P\land (P\rightarrow Q))\rightarrow Q$
$A\rightarrow (B\rightarrow A)$ ${\ displaystyle A \ rightarrow (B \ rightarrow A)}$ $A\rightarrow (B\rightarrow A)$ (truth follows from anything)
$A\leftrightarrow \neg \neg A$ ${\ displaystyle A \ leftrightarrow \ neg \ neg A}$ (law of double negation)
$(A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)$ ${\ displaystyle (A \ rightarrow B) \ wedge (B \ rightarrow C) \ rightarrow (A \ rightarrow C)}$ - chain conclusion rule
$(A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)$ ${\ displaystyle (A \ vee B) \ wedge C \ leftrightarrow (A \ wedge C) \ vee (B \ wedge C)}$ - distributivity of conjunction relative to disjunction
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ ${\ displaystyle (A \ wedge B) \ vee C \ leftrightarrow (A \ vee C) \ wedge (B \ vee C)}$ - distributivity of disjunction relative to conjunction
$(P\land P)\leftrightarrow P$ ${\ displaystyle (P \ land P) \ leftrightarrow P}$ - idempotency of conjunction
$(P\lor P)\leftrightarrow P$ ${\ displaystyle (P \ lor P) \ leftrightarrow P}$ - idempotency of disjunction
$(P\rightarrow Q)\leftrightarrow (\neg P\lor Q)$ ${\ displaystyle (P \ rightarrow Q) \ leftrightarrow (\ neg P \ lor Q)}$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$ ${\ displaystyle (P \ leftrightarrow Q) \ leftrightarrow ((P \ leftrightarrow Q) \ land (Q \ leftrightarrow P))}$
$(P\land (Q\lor P)\leftrightarrow P$ ${\ displaystyle (P \ land (Q \ lor P) \ leftrightarrow P}$ - the first law of absorption
$(P\lor (Q\land P)\leftrightarrow P$ ${\ displaystyle (P \ lor (Q \ land P) \ leftrightarrow P}$ - second absorption law
$\neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)$ ${\ displaystyle \ neg (A \ wedge B) \ leftrightarrow (\ neg A \ vee \ neg B)}$ - de Morgan's first law
$\neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)$ ${\ displaystyle \ neg (A \ vee B) \ leftrightarrow (\ neg A \ wedge \ neg B)}$ - de Morgan’s second law
$(A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)$ ${\ displaystyle (A \ rightarrow B) \ leftrightarrow (\ neg B \ rightarrow \ neg A)}$ - the law of contraposition
If a $\vDash F(X_{1},...,X_{n})$ ${\ displaystyle \ vDash F (X_ {1}, ..., X_ {n})}$ and $H_{1},...,H_{n}$ ${\ displaystyle H_ {1}, ..., H_ {n}}$ Are formulas then $\vDash F(H_{1},...,H_{n})$ ${\ displaystyle \ vDash F (H_ {1}, ..., H_ {n})}$ ( substitution rule )

Tautology of predicate calculus (and predicate algebra)

If a $F(X_{1},...,X_{n})$ ${\ displaystyle F (X_ {1}, ..., X_ {n})}$ - tautology in the calculus of statements and $P_{1},...,P_{n}$ ${\ displaystyle P_ {1}, ..., P_ {n}}$ are predicates then $F(P_{1},...,P_{n})$ ${\ displaystyle F (P_ {1}, ..., P_ {n})}$ - tautology in predicate calculus
$\neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)$ ${\ displaystyle \ neg (\ forall x) P (x) \ leftrightarrow (\ exists x) \ neg P (x)}$

$\neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)$ ${\ displaystyle \ neg (\ exists x) P (x) \ leftrightarrow (\ forall x) \ neg P (x)}$ ( de Morgan law )

$(\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)$ ${\ displaystyle (\ forall x) (P (x) \ wedge Q (x)) \ leftrightarrow (\ forall x) P (x) \ wedge (\ forall x) Q (x)}$
$(\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)$ ${\ displaystyle (\ exists x) (P (x) \ vee Q (x)) \ leftrightarrow (\ exists x) P (x) \ vee (\ exists x) Q (x)}$
$Q\leftrightarrow (\exists x)Q$ ${\ displaystyle Q \ leftrightarrow (\ exists x) Q}$
$Q\leftrightarrow (\forall x)Q$ ${\ displaystyle Q \ leftrightarrow (\ forall x) Q}$
$(\forall x)P(x)\rightarrow P(y)$ ${\ displaystyle (\ forall x) P (x) \ rightarrow P (y)}$
$P(y)\rightarrow (\exists x)P(x)$ ${\ displaystyle P (y) \ rightarrow (\ exists x) P (x)}$
$(\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)$ ${\ displaystyle (\ forall x) (\ forall y) P (x, y) \ leftrightarrow (\ forall y) (\ forall x) P (x, y)}$
$(\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)$ ${\ displaystyle (\ exists x) (\ exists y) P (x, y) \ leftrightarrow (\ exists y) (\ exists x) P (x, y)}$
$(\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)$ ${\ displaystyle (\ exists x) (\ forall y) P (x, y) \ rightarrow (\ forall y) (\ exists x) P (x, y)}$

An example of a tautology in the literature

Consider the saying known from the song : “ Real men play hockey, (therefore) the Coward does not play hockey .”

We formalize it:

$X$ ${\ displaystyle X}$ - plays hockey

$M$ ${\ displaystyle M}$ - a real man

$\lnot X$ ${\ displaystyle \ lnot X}$ - does not play hockey

$\lnot M$ ${\ displaystyle \ lnot M}$ - not a real man (coward)

We get the formula:

$(X\rightarrow M)\rightarrow (\lnot M\rightarrow \lnot X)$ ${\ displaystyle (X \ rightarrow M) \ rightarrow (\ lnot M \ rightarrow \ lnot X)}$

which is a logical tautology.

Notes

Literature

Igoshin V. I. "Mathematical logic and theory of algorithms." - Academia, 2008.
Karpov Yu. G. "Theory of automata." - P., 2003 .-- S. 49, 60.
Mendelssohn E. "Introduction to Mathematical Logic". - M. Science, 1971.
Igoshin V. I. “The Problem Book is a Practice on Mathematical Logic”. - Enlightenment, 1986.