Logical connectives

1.6. Logical connectives

We defined earlier the concept of logical connective. Let us now list the main useful ones, beyond both nullary ones (Boolean constants) 1 and 0. (To this will be added the conditional connective in 2.4).

Tautologies

Their properties will be expressed by tautologies, which are formulas only involving connectives and Boolean variables (here written A, B, C), and true for all possible combinations of values of these variables. So, they also give necessarily true formulas when replacing these variables by any defining formulas using any language and interpreted in any systems. Such definitions of Boolean variables by formulas of a theory may restrict their ranges of possible values depending on each other.

Tautologies form the rules of Boolean algebra, an algebraic theory describing operations on the Boolean type, itself 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».

Negation

The only useful unary connective is the negation ¬, that exchanges Booleans (¬A is read «not A»):

¬1
¬0
¬(¬A)

⇔ 0
⇔ 1
⇔ A

It is often denoted by barring the root of its argument, forming with it another symbol with the same format:

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)

Conjunctions, disjunctions

The conjunction ∧ means «and», being true only when both arguments are true;
The disjunction ∨ means «or», being true except when both arguments are false.
Each of them is :

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))

This similarity (symmetry) of their properties comes from the fact they are exchanged by negation:

(A ∨ B) ⇎ (¬A ∧ ¬B)
(A ∧ B) ⇎ (¬A ∨ ¬B)

The inequivalence is also called exclusive or because (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.

Implication

The binary connective of implication ⇒ is defined as (A ⇒ B) ⇔ ((¬A) ∨ B). It can be read «A implies B», «A is a sufficient condition for B», or «B is a necessary condition for A». Being true except when A is true and B is false, it expresses the truth of B when A is true, but no more gives information on B when A is false (as it is then true).
Moreover,

(A ⇒ B) ⇎
(A ⇒ B) ⇔

(A ∧ ¬B)
(¬B ⇒ ¬A)

The formula ¬B ⇒ ¬A is called the contrapositive of A ⇒ B.
The equivalence can also be redefined as (A ⇔ B) ⇔ ((A ⇒ B) ∧ (B ⇒ A)). Thus in a given theory, a proof of A ⇔ B can be formed of a proof of the first implication (A ⇒ B), then a proof of the second one (B ⇒ A), called the converse of (A ⇒ B).

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:

(A ⇒ (B ⇒ C)) ⇔ ((A ∧ B) ⇒ C)
(A ⇒ (B ∨ C)) ⇔ ((A ⇒ B) ∨ C)

(A ⇒ (B ∧ C)) ⇔ ((A ⇒ B) ∧ (A ⇒ C))
((A ∨ B) ⇒ C) ⇔ ((A ⇒ C) ∧ (B ⇒ C))
((A ⇒ B) ⇒ C) ⇔ ((A ∨ C) ∧ (B ⇒ C))
(A ∧ (B ⇒ C)) ⇔ ((A ⇒ B) ⇒ (A ∧ C))

Finally,

(A ⇒ B) ⇒ ((A∧C) ⇒ (B∧C))
(A ⇒ B) ⇒ ((A∨C) ⇒ (B∨C)).

Chains of implications and equivalences

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.1. Introduction to the foundations of mathematics 1.2. Variables, sets, functions and operations 1.3. Form of theories: notions, objects, meta-objects 1.4. Structures of mathematical systems 1.5. Expressions and definable structures ⇦ 1.6. Logical connectives ⇨ 1.7. Classes in set theory	1.8. Binders in set theory 1.9. Axioms and proofs 1.10. Quantifiers 1.11. Second-order quantifiers Time in model theory Truth undefinability Introduction to incompleteness Set theory as unified framework
2. Set theory - 3. Algebra - 4. Arithmetic - 5. Second-order foundations

Other languages:
FR : 1.6. Connecteurs