Tautologies form the rules of Boolean algebra, an algebraic theory describing operations on the Boolean type, naturally interpreted as the pair of elements 0 and 1 but also admitting more sophisticated interpretations beyond the scope of this chapter.
The binary connective of equality between Booleans is written ⇔ and called equivalence: A ⇔ B is read «A is equivalent to B».¬1 ¬0 ¬(¬A) |
⇔ 0 ⇔ 1 ⇔ A |
x ≠ y x ∉ E (A ⇎ B) |
⇔ ¬(x = y) ⇔ ¬(x ∈ E) ⇔ (A ⇔ ¬B) |
(x is not equal to y) (x is not an element of E) (inequivalence) |
Idempotent (A ∧ A) ⇔ A (A ∨ A) ⇔ A |
Commutative (B∧A) ⇔ (A∧B)
(B∨A) ⇔ (A∨B) |
Associative ((A∧B)∧C) ⇔ (A∧(B∧C))
((A∨B)∨C) ⇔ (A∨(B∨C)) |
Distributive over the other (A ∧ (B∨C)) ⇔ ((A∧B)
∨ (A∧C))
(A ∨ (B∧C)) ⇔ ((A∨B) ∧ (A∨C)) |
(A ∨ B)
⇎ (¬A ∧ ¬B)
(A ∧ B) ⇎ (¬A ∨ ¬B)
Chains of conjunctions such as (A ∧ B ∧ C), abbreviate any formula with more parenthesis such as ((A ∧ B) ∧ C), all equivalent by associativity ; similarly for chains of disjunctions such as (A ∨ B ∨ C).
Asserting (declaring as true) a conjunction of formulas amounts to successively asserting all these formulas.(A ⇒ B) ⇎ (A ⇒ B) ⇔ |
(A ∧ ¬B) (¬B ⇒ ¬A) |
The formula A ∧ (A ⇒ B) is equivalent to A ∧ B but will be written A ∴ B, which reads «A therefore B», to indicate that it is deduced from the truths of A and A ⇒ B.
Negations turn the associativity and distributivity of ∧ and ∨, into various tautologies involving implications:
In a different kind of abbreviation, any chain of formulas linked by ⇔ and/or ⇒ will mean the chain of conjunctions of these implications or equivalences between adjacent formulas:
(A ⇒ B
⇒ C) ⇔ ((A ⇒ B) ∧ (B ⇒ C)) ⇒
(A ⇒ C)
(A ⇔ B ⇔ C) ⇔ ((A ⇔ B) ∧ (B
⇔ C)) ⇒ (A ⇔ C)
0 ⇒ A ⇒ A ⇒ 1
(¬A) ⇔ (A ⇒ 0) ⇔ (A ⇔ 0)
(A ∧ 1) ⇔ A ⇔ (A ∨ 0) ⇔ (1 ⇒ A) ⇔ (A
⇔ 1)
(A ∧ B) ⇒ A ⇒ (A ∨ B)
Set theory and Foundations of Mathematics | |
1. First
foundations of mathematics |
1.6. Logical connectives
⇨ 1.7. Classes
in set theory |
2. Set theory (continued) - 3. Algebra - 4. Arithmetic | 5. Second-order foundations |