Here we list some of the more famous, historically important, or otherwise useful equivalences and tautologies. They can be added to the ones listed in Interdefinability of connectives . We can go on at quite some length here, but will try to keep the list somewhat restrained. Remember that for every equivalence of
φ
{\displaystyle \varphi \,\!}
ψ
{\displaystyle \psi \,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
Bivalence
edit
Every formula has exactly one of two truth values.
⊨
P
∨
¬
P
{\displaystyle \vDash \ \mathrm {P} \lor \lnot \mathrm {P} \,\!}
Law of Excluded Middle
⊨
¬
(
P
∧
¬
P
)
{\displaystyle \vDash \ \lnot (\mathrm {P} \land \lnot \mathrm {P} )\,\!}
Law of Non-Contradiction Analogues to arithmetic laws
edit
Some familiar laws from arithmetic have analogues in sentential logic.
Reflexivity
edit
Conditional and biconditional (but not conjunction and disjunction) are reflexive.
⊨
P
→
P
{\displaystyle \vDash \ \mathrm {P} \rightarrow \mathrm {P} \,\!}
⊨
P
↔
P
{\displaystyle \vDash \ \mathrm {P} \leftrightarrow \mathrm {P} \,\!}
Commutativity
edit
Conjunction, disjunction, and biconditional (but not conditional) are commutative.
P
∧
Q
{\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}
Q
∧
P
{\displaystyle \mathrm {Q} \land \mathrm {P} \,\!}
P
∨
Q
{\displaystyle \mathrm {P} \lor \mathrm {Q} \,\!}
Q
∨
P
{\displaystyle \mathrm {Q} \lor \mathrm {P} \,\!}
P
↔
Q
{\displaystyle \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}
Q
↔
P
{\displaystyle \mathrm {Q} \leftrightarrow \mathrm {P} \,\!}
Associativity
edit
Conjunction, disjunction, and biconditional (but not conditional) are associative.
(
P
∧
Q
)
∧
R
{\displaystyle (\mathrm {P} \land \mathrm {Q} )\land \mathrm {R} \,\!}
P
∧
(
Q
∧
R
)
{\displaystyle \mathrm {P} \land (\mathrm {Q} \land \mathrm {R} )\,\!}
(
P
∨
Q
)
∨
R
{\displaystyle (\mathrm {P} \lor \mathrm {Q} )\lor \mathrm {R} \,\!}
P
∨
(
Q
∨
R
)
{\displaystyle \mathrm {P} \lor (\mathrm {Q} \lor \mathrm {R} )\,\!}
(
P
↔
Q
)
↔
R
{\displaystyle (\mathrm {P} \leftrightarrow \mathrm {Q} )\leftrightarrow \mathrm {R} \,\!}
P
↔
(
Q
↔
R
)
{\displaystyle \mathrm {P} \leftrightarrow (\mathrm {Q} \leftrightarrow \mathrm {R} )\,\!}
Distribution
edit
We list ten distribution laws. Of these, probably the most important are that conjunction and disjunction distribute over each other and that conditional distributes over itself.
P
∧
(
Q
∧
R
)
{\displaystyle \mathrm {P} \land (\mathrm {Q} \land \mathrm {R} )\,\!}
(
P
∧
Q
)
∧
(
P
∧
R
)
{\displaystyle (\mathrm {P} \land \mathrm {Q} )\land (\mathrm {P} \land \mathrm {R} )\,\!}
P
∧
(
Q
∨
R
)
{\displaystyle \mathrm {P} \land (\mathrm {Q} \lor \mathrm {R} )\,\!}
(
P
∧
Q
)
∨
(
P
∧
R
)
{\displaystyle (\mathrm {P} \land \mathrm {Q} )\lor (\mathrm {P} \land \mathrm {R} )\,\!}
P
∨
(
Q
∧
R
)
{\displaystyle \mathrm {P} \lor (\mathrm {Q} \land \mathrm {R} )\,\!}
(
P
∨
Q
)
∧
(
P
∨
R
)
{\displaystyle (\mathrm {P} \lor \mathrm {Q} )\land (\mathrm {P} \lor \mathrm {R} )\,\!}
P
∨
(
Q
∨
R
)
{\displaystyle \mathrm {P} \lor (\mathrm {Q} \lor \mathrm {R} )\,\!}
(
P
∨
Q
)
∨
(
P
∨
R
)
{\displaystyle (\mathrm {P} \lor \mathrm {Q} )\lor (\mathrm {P} \lor \mathrm {R} )\,\!}
P
∨
(
Q
→
R
)
{\displaystyle \mathrm {P} \lor (\mathrm {Q} \rightarrow \mathrm {R} )\,\!}
(
P
∨
Q
)
→
(
P
∨
R
)
{\displaystyle (\mathrm {P} \lor \mathrm {Q} )\rightarrow (\mathrm {P} \lor \mathrm {R} )\,\!}
P
∨
(
Q
↔
R
)
{\displaystyle \mathrm {P} \lor (\mathrm {Q} \leftrightarrow \mathrm {R} )\,\!}
(
P
∨
Q
)
↔
(
P
∨
R
)
{\displaystyle (\mathrm {P} \lor \mathrm {Q} )\leftrightarrow (\mathrm {P} \lor \mathrm {R} )\,\!}
P
→
(
Q
∧
R
)
{\displaystyle \mathrm {P} \rightarrow (\mathrm {Q} \land \mathrm {R} )\,\!}
(
P
→
Q
)
∧
(
P
→
R
)
{\displaystyle (\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {P} \rightarrow \mathrm {R} )\,\!}
P
→
(
Q
∨
R
)
{\displaystyle \mathrm {P} \rightarrow (\mathrm {Q} \lor \mathrm {R} )\,\!}
(
P
→
Q
)
∨
(
P
→
R
)
{\displaystyle (\mathrm {P} \rightarrow \mathrm {Q} )\lor (\mathrm {P} \rightarrow \mathrm {R} )\,\!}
P
→
(
Q
→
R
)
{\displaystyle \mathrm {P} \rightarrow (\mathrm {Q} \rightarrow \mathrm {R} )\,\!}
(
P
→
Q
)
→
(
P
→
R
)
{\displaystyle (\mathrm {P} \rightarrow \mathrm {Q} )\rightarrow (\mathrm {P} \rightarrow \mathrm {R} )\,\!}
P
→
(
Q
↔
R
)
{\displaystyle \mathrm {P} \rightarrow (\mathrm {Q} \leftrightarrow \mathrm {R} )\,\!}
(
P
→
Q
)
↔
(
P
→
R
)
{\displaystyle (\mathrm {P} \rightarrow \mathrm {Q} )\leftrightarrow (\mathrm {P} \rightarrow \mathrm {R} )\,\!}
Transitivity
edit
Conjunction, conditional, and biconditional (but not disjunction) are transitive.
⊨
(
P
∧
Q
)
∧
(
Q
∧
R
)
→
P
∧
R
{\displaystyle \vDash \ (\mathrm {P} \land \mathrm {Q} )\land (\mathrm {Q} \land \mathrm {R} )\rightarrow \mathrm {P} \land \mathrm {R} \,\!}
⊨
(
P
→
Q
)
∧
(
Q
→
R
)
→
(
P
→
R
)
{\displaystyle \vDash \ (\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {R} )\rightarrow (\mathrm {P} \rightarrow \mathrm {R} )\,\!}
⊨
(
P
↔
Q
)
∧
(
Q
↔
R
)
→
(
P
↔
R
)
{\displaystyle \vDash \ (\mathrm {P} \leftrightarrow \mathrm {Q} )\land (\mathrm {Q} \leftrightarrow \mathrm {R} )\rightarrow (\mathrm {P} \leftrightarrow \mathrm {R} )\,\!}
Other tautologies and equivalences
edit
Conditionals
edit
These tautologies and equivalences are mostly about conditionals.
⊨
P
∧
Q
→
P
⊨
P
∧
Q
→
Q
{\displaystyle \vDash \ \mathrm {P} \land \mathrm {Q} \rightarrow \mathrm {P} \qquad \qquad \vDash \ \mathrm {P} \land \mathrm {Q} \rightarrow \mathrm {Q} \,\!}
⊨
P
→
P
∨
Q
⊨
Q
→
P
∨
Q
{\displaystyle \vDash \ \mathrm {P} \rightarrow \mathrm {P} \lor \mathrm {Q} \qquad \qquad \vDash \ \mathrm {Q} \rightarrow \mathrm {P} \lor \mathrm {Q} \,\!}
⊨
(
P
→
Q
)
∨
(
Q
→
R
)
{\displaystyle \vDash \ (\mathrm {P} \rightarrow \mathrm {Q} )\lor (\mathrm {Q} \rightarrow \mathrm {R} )\,\!}
⊨
¬
P
→
(
P
→
Q
)
{\displaystyle \vDash \ \lnot \mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!}
Conditional addition
⊨
Q
→
(
P
→
Q
)
{\displaystyle \vDash \ \mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!}
Conditional addition
P
→
Q
{\displaystyle \mathrm {P} \rightarrow \mathrm {Q} \,\!}
¬
Q
→
¬
P
{\displaystyle \lnot \mathrm {Q} \rightarrow \lnot \mathrm {P} \,\!}
Contraposition
P
∧
Q
→
R
{\displaystyle \mathrm {P} \land \mathrm {Q} \rightarrow \mathrm {R} \,\!}
P
→
(
Q
→
R
)
{\displaystyle \mathrm {P} \rightarrow (\mathrm {Q} \rightarrow \mathrm {R} )\,\!}
Exportation Biconditionals
edit
These tautologies and equivalences are mostly about biconditionals.
⊨
P
∧
Q
→
(
P
↔
Q
)
{\displaystyle \vDash \ \mathrm {P} \land \mathrm {Q} \rightarrow (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!}
Biconditional addition
⊨
¬
P
∧
¬
Q
→
(
P
↔
Q
)
{\displaystyle \vDash \ \lnot \mathrm {P} \land \lnot \mathrm {Q} \rightarrow (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!}
Biconditional addition
⊨
(
P
↔
Q
)
∨
(
P
↔
¬
Q
)
{\displaystyle \vDash (\mathrm {P} \leftrightarrow \mathrm {Q} )\lor (\mathrm {P} \leftrightarrow \lnot \mathrm {Q} )\,\!}
¬
(
P
↔
Q
)
{\displaystyle \lnot (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!}
¬
P
↔
Q
{\displaystyle \lnot \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}
P
↔
¬
Q
{\displaystyle \mathrm {P} \leftrightarrow \lnot \mathrm {Q} \,\!}
Miscellaneous
edit
We repeat DeMorgan's Laws from the Interdefinability of connectives section of Expressibility and add two additional forms. We also list some additional tautologies and equivalences.
⊨
P
↔
P
∧
P
{\displaystyle \vDash \ \mathrm {P} \leftrightarrow \mathrm {P} \land \mathrm {P} \,\!}
Idempotence for conjunction
⊨
P
↔
P
∨
P
{\displaystyle \vDash \ \mathrm {P} \leftrightarrow \mathrm {P} \lor \mathrm {P} \,\!}
Idempotence for disjunction
⊨
P
→
P
∨
Q
{\displaystyle \vDash \ \mathrm {P} \rightarrow \mathrm {P} \lor \mathrm {Q} \,\!}
Disjunctive addition
⊨
Q
→
P
∨
Q
{\displaystyle \vDash \ \mathrm {Q} \rightarrow \mathrm {P} \lor \mathrm {Q} \,\!}
Disjunctive addition
⊨
P
∧
¬
P
→
Q
{\displaystyle \vDash \ \mathrm {P} \land \lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!}
P
∧
Q
{\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}
¬
(
¬
P
∨
¬
Q
)
{\displaystyle \lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\,\!}
Demorgan's Laws
P
∨
Q
{\displaystyle \mathrm {P} \lor \mathrm {Q} \,\!}
¬
(
¬
P
∧
¬
Q
)
{\displaystyle \lnot (\lnot \mathrm {P} \land \lnot \mathrm {Q} )\,\!}
Demorgan's Laws
¬
(
P
∧
Q
)
{\displaystyle \lnot (\mathrm {P} \land \mathrm {Q} )\,\!}
¬
P
∨
¬
Q
{\displaystyle \lnot \mathrm {P} \lor \lnot \mathrm {Q} \,\!}
Demorgan's Laws
¬
(
P
∨
Q
)
{\displaystyle \lnot (\mathrm {P} \lor \mathrm {Q} )\,\!}
¬
P
∧
¬
Q
{\displaystyle \lnot \mathrm {P} \land \lnot \mathrm {Q} \,\!}
Demorgan's Laws
P
{\displaystyle \mathrm {P} \,\!}
¬
¬
P
{\displaystyle \lnot \lnot \mathrm {P} \,\!}
Double Negation Deduction and reduction principles
edit
The following two principles will be used in constructing our derivation system on a later page. They can easily be proven, but—since they are neither tautologies nor equivalences—it takes more than a mere truth table to do so. We will not attempt the proof here.
Deduction principle
edit
Let
φ
{\displaystyle \varphi \,\!}
ψ
{\displaystyle \psi \,\!}
Γ
{\displaystyle \Gamma \,\!}
I
f
Γ
∪
{
φ
}
⊨
ψ
,
t
h
e
n
Γ
⊨
(
φ
→
ψ
)
{\displaystyle \mathrm {If} \ \ \Gamma \cup \{\varphi \}\vDash \psi \mathrm {,\ then} \ \ \Gamma \vDash (\varphi \rightarrow \psi )\,\!}
Reduction principle
edit
Let
φ
{\displaystyle \varphi \,\!}
ψ
{\displaystyle \psi \,\!}
Γ
{\displaystyle \Gamma \,\!}
I
f
Γ
∪
{
φ
}
⊨
ψ
a
n
d
Γ
∪
{
φ
}
⊨
¬
ψ
,
t
h
e
n
Γ
⊨
¬
φ
,
{\displaystyle \mathrm {If} \ \ \Gamma \cup \{\varphi \}\vDash \psi \ \ \mathrm {and} \ \ \Gamma \cup \{\varphi \}\vDash \lnot \psi \mathrm {,\ then} \ \ \Gamma \vDash \lnot \varphi ,\!}
I
f
Γ
∪
{
¬
φ
}
⊨
ψ
a
n
d
Γ
∪
{
¬
φ
}
⊨
¬
ψ
,
t
h
e
n
Γ
⊨
φ
{\displaystyle \mathrm {If} \ \ \Gamma \cup \{\lnot \varphi \}\vDash \psi \ \ \mathrm {and} \ \ \Gamma \cup \{\lnot \varphi \}\vDash \lnot \psi \mathrm {,\ then} \ \ \Gamma \vDash \varphi \,\!}
Contraposition
