Chapter 1

The language of propositional calculus

1.1. Introduction
Propositional calculus is a logical theory that studies the logical relationships between
"propositions" and defines the formal laws according to which, by means of logical
connectors, propositions coordinate and link together to produce valid reasoning.

Also called 0-order logic, it is one of the privileged formal languages of mathematical logic
for the formulation of its concepts in formal systems, because of its applicability to the
foundations of mathematics and the richness of its properties related to the theory of
demonstration.

The notion of proposition has been the subject of much debate in the history of logic; the
common idea is that a proposition is a syntactic construction supposed to have a truth value.

In mathematical logic, the calculus of propositions is the first step in defining logic and
reasoning. It defines the rules of deduction that link propositions together, without examining
their content; it is thus a first step in the construction of the calculus of predicates, which is
concerned with the content of propositions and is a completed formalisation of mathematical
reasoning. The calculus of propositions is sometimes called the logic of propositions,
propositional logic, or the calculus of statements, and sometimes the theory of truth functions.

1.2. Definition
A proposition is a collection of words in a natural language that has the following three
properties:

1- It is recognized as syntactically correct;

2- It is semantically correct;
3- It can be clearly assigned a truth value (true or false).

Example

Louis 14 is a prime number.

1/11
A literary person will attribute to this sentence property (1) but probably not property (2). It is
therefore not a proposition.

Example

In a right-angled triangle, the square of the hypotenuse is equal to the sum of the squares of
the sides of the right angle.

Properties (1, 2 and 3) are verified: it is a (true) proposition.

Example

Has the postman arrived?

properties (1) and (2) are verified, but not (3). It is therefore not a proposition.

1.3. Propositional language

The propositional language is composed of formulas representing propositions. Like other
languages, the language of propositional calculus is characterised by its syntax and semantics.

1.3.1. The syntax of propositional language

The syntax of a language defines the alphabet and the rules for writing (grammar) the
expressions of the language. It is not concerned with their meaning.

The alphabet

The alphabet is composed of the symbols of language. It includes:

- A countable set of propositional variables. The letters of the Latin alphabet (a, b, c ...)
should be used, possibly indexed.
- Logical connectors (¬, ⋀, ⋁, →, ⟷). This list is not complete, it may change from one
teacher to another or from one university to another.
- Auxiliary symbols.

Writing rules

The writing rules specify how the symbols of the alphabet are assembled to form well-formed
expressions (or formulas) of the propositional language:

1- Any propositional variable is a formula;

2- If 𝛼 is a formula, ¬𝛼 or 𝑎 is a formula;

2/11
 3- If 𝛼 and 𝛽 are formulas, (𝛼 ∧ 𝛽), (𝛼 ⋁ 𝛽), (𝛼 ⟶ 𝛽) and (𝛼 ↔ 𝛽) are also formulas.
4- An expression is only a formula if it is written according to rules 1, 2 and 3.

Example

1- p, q, r are propositional variables, therefore formulas.

2- (𝑝 ∧ 𝑞) is a formula.
3- 𝑝 → (𝑞𝑟) isn’t a formula.

1.3.2. Connector priority

The connectors are applied in the following order:

(¬, ⋀, ⋁, →, ⟷)

Example

1. 𝑝 ⋀ 𝑞 is read as ( 𝑝 ) ⋀ 𝑞
2. 𝑝 ⋀ 𝑞 ⟶ 𝑟 is read as (𝑝 ⋀ 𝑞) ⟶ 𝑟
3. 𝑝 ⋁ 𝑞 ⋀ 𝑟 is read as 𝑝 ⋁(𝑞 ⋀ 𝑟)
4. 𝑝 ⋁ 𝑞 ∨ 𝑟 is read as (𝑝 ⋁ 𝑞) ∨ 𝑟

1.4. Semantics of a propositional language

The semantic study of a language for the calculation of propositions aims to give a truth value
to the formulas of the language. It is also called model theory.
The semantics associates a valuation function.

V : vp → {1,0}

(Where vp is the set of propositional variables, 1 means true and 0 means false) unique to
each of the logical connectors.

This function is described by a graph called truth table. Each formula α with n propositional
variables has a unique truth function. The graph of this function is defined by a truth table
with 2n lines representing the truth value of a corresponding to each combination of truth
values of the n variables (also called distribution of truth values of the variables).

3/11
1- The negation
The negation of a proposition a noted ¬𝑎 or 𝑎 is defined as follows:
If the proposition a is true, then 𝑎 is false.
If the proposition a is false, then 𝑎 is true.

The truth table of negation:

a 𝒂
1 0
0 1
2- The conjunction
The conjunction of two propositions a and b noted symbolically by 𝑎 ∧ 𝑏 and read (a
and b) is true if and only if both propositions a and b are true simultaneously.
The truth table of the conjunction:
a b 𝒂∧𝒃
1 1 1
1 0 0
0 1 0
0 0 0

3- The disjunction
The disjunction of two propositions a and b noted symbolically by 𝑎 ∨ 𝑏 and reads (a
or b) is false if and only if both propositions a and b are false simultaneously.
The truth table of the disjunction:
a b 𝒂∨𝒃
1 1 1
1 0 1
0 1 1
0 0 0
4- Conditional
The proposition 𝑎 ⟶ 𝑏 is false in the case where a is true and b is false. It is defined
by the following table:

4/11
 a b 𝒂⟶𝒃
1 1 1
1 0 0
0 1 1
0 0 1

Let a and b be two propositions, in the formula 𝑎 ⟶ 𝑏, a is called the antecedent and
b the consequence.
With conditional situations, we also have the following:
The original conditional is “if a, then b” a → b
• The converse is “if b, then p” b → a
• The inverse is “if not a, then not b” 𝑎 → 𝑏
• The contrapositive is “if not b, then not a” 𝑏 → 𝑎

5- Biconditional
The proposition 𝑎 ↔ 𝑏 is true in the case where a and b have the same truth value. It
is defined by the following table:
a b 𝒂↔𝒃
1 1 1
1 0 0
0 1 0
0 0 1
Example:

Let α be the formula:

𝑝⋁𝑞 → 𝑟

The truth table of this formula:

5/11
 p q r 𝒑⋁𝒒 α
1 1 1 1 1
1 1 0 1 0
1 0 1 1 1
1 0 0 1 0
0 1 1 1 1
0 1 0 1 0
0 0 1 0 1
0 0 0 0 1

1.4.1. Satisfiability
A formula α is said to be satisfiable if and only if its truth table contains at least one row
where the truth value of α is true (or V(α) = 1).

α is said to be unsatisfiable if it is false on all rows of its truth table.

Example: The formula α of the previous example is satisfiable.

Example: Let 𝛽 be the formula (𝑝⋀𝑞)⋀(𝑝 ↔ 𝑞),

p q 𝒑⋀𝒒 (𝒑 ↔ 𝒒) 𝜷
1 1 1 0 0
1 0 0 1 0
0 1 0 1 0
0 0 0 0 0

Hence 𝛽 is unsatisfiable.

1.4.2. Satisfiability of a set of formulas

The notion of satisfiability is generalized to a set of formulas:

6/11
Let L = {α1,α2, … , αn} be a set of formulas. L is said to be satisfiable if and only if given the
truth table of all the formulas α1,α2, … , αn there exists at least one row where all these
formulas are simultaneously true.

Example:

1- The set {𝑝 ⋀ 𝑞, 𝑝 ⋁ 𝑞 , 𝑝 → 𝑞} is satisfiable.

2- The set {𝑝 ⋀ 𝑞, 𝑝 ⋁ 𝑞 , 𝑝} is unsatisfiable.

1.4.3. Tautology
A formula α is a tautology (note ⊨ α), if and only if α is true on all lines of its truth table.

Example A formula a ⋀ b → b is a tautology.

a b a⋀b a⋀b→b
1 1 1 1
1 0 0 1
0 1 0 1
0 0 0 1

Remark

- If ⊨ α → β, we say that α logically implies β.

- If ⊨ α ↔ β, we say that α logically equivalent to β and we note α ≡ β.

Lemma A formula 𝛼 is a tautology if and only if 𝛼 is unsatisfiable.

Demonstration.

1. Suppose that ⊨ α but 𝛼 is satisfiable. Therefore, there is at least one row in the truth
table where α is true. For this line, α is false but ⊨ α. Then α is unsatisfiable.
2. Now suppose that 𝛼 is unsatisfiable, but α is not a tautology. Therefore, there is at
least one line in the truth table where α is false. For this line, 𝛼 must be true which
contradicts the fact that 𝛼 is unsatisfiable.

Theorem - If ⊨ α and ⊨ α → β, then ⊨ β.

Demonstration. Let's proceed by absurdity.

7/11
 - Suppose ⊨ α and ⊨ α → β, but ⊭ β. Therefore, there is at least one line where β is
false. For this line, α → β is false because ⊨ α. Contradiction with the fact that
⊨α→β.

1.4.4. Logical consequence

In propositional language, a formula 𝛽 is a logical consequence of a formula 𝛼 (and we note
𝛼 ⊨ 𝛽 ), if and only if given the truth table of 𝛼 and 𝛽, the truth value of 𝛽 is true on all lines
where the truth value of 𝛼 is true.

In general, a formula 𝛽 is a logical consequence of a set of formulas Γ = {𝛼1, 𝛼2, … , 𝛼n }

(and we note Γ ⊨ 𝛽 or 𝛼1, 𝛼2, … , 𝛼n ⊨ 𝛽) if and only if, given the truth table of the formulas
𝛼1, 𝛼2, … , 𝛼n, 𝛽, the truth value of 𝛽 is true on all the lines in which the formulas 𝛼1, 𝛼2, … ,
𝛼n, are true simultaneously.

Example p → q, 𝑞 ⊨ 𝑝

p q p→q 𝒒 𝒑
1 1 1 0 0
1 0 0 1 0
0 1 1 0 1
0 0 1 1 1

Remark

1. {𝛼1, … , 𝛼n } ⊨ 𝛼 if and only if ⊨ 𝛼1 ⋀ … ⋀ 𝛼n → 𝛼.

2. Let E be a set of formulas and A ⊆ E. Then, if E is satisfiable, A is satisfiable.
3. The empty set is satisfiable.
4. The set of all formulas is unsatisfiable.
5. Let E be a set of formulas and A ⊆ E. Then, if A is unsatisfiable so E is unsatisfiable.
6. Every tautology is a logical consequence of any set of formulas, in particular of an empty set.

1.4.5. Substitution theorem

Let β be a formula containing the propositional variable x, and let β’ be the formula obtained
from β by substituting for x, in all its occurrences, a formula α.

If ⊨ β, then ⊨ β’

8/11
Example

Let β ≡ x → ((y → z) → x). We can check that |= β. And let β 0 ≡ (a ∧ b) → ((y → z) → (a ∧

b)) obtained by substituting in β, (a ∧ b) for x. Then, |= β 0.

1.4.6. Replacement theorem

Let α be a formula in which the formula β appears in one or more occurrences and let α' be
the formula obtained from α by replacing β in one or more of its occurrences by the formula
β'.

If β ≡ β’, then α ≡ α’

Example

Let α ≡ x ∨ (x → y) ↔ (z ∨ (z → y). We can verify that z → y ≡ 𝑧 ∨ y.

Let α' be the formula obtained from α by replacing z → y by 𝑧 ∨ y.

α' ≡ x ∨ (x → y) ↔ (z ∨ (z ∨ y)) We can easily verify that α ≡ α'.

1.5. Complete system of connectors

A set Γ of connectors is said to be complete, if given any formula α of the propositional
calculus, we can find a formula α' in which only the elements of Γ intervene and such that

α ≡ α'.

Example

The set {¬, ∨} is complete.

1.6. Normal Form

Definition: (atom, literal, clause, conjunctive normal form).

- An atom or atomic formula is a formula with only one propositional variable (no
connectives).
- A literal is an atomic formula or the negation of an atomic formula.
- A conjunctive monomial is a conjunction of literals.
- A clause is a disjunction of literals.
- A formula is in conjunctive normal form if it is a conjunction of clauses.

9/11
 - A formula is in disjunctive normal form if it is a disjunction of monomials.

1.6.1. Obtaining Disjunctive Normal Form (DNF)

It is necessary to have an algorithmic means to obtain the (DNF) from the truth table.

Let α be a propositional calculus formula with n variables x1, x2, . . . , xn. Suppose A is the
truth table of α. The DNF of α is obtained as follows:

- Let p be the number of rows of A such that V (α) = 1.

- For each row i, i = 1, . . . , p where V (α) = 1, let Mi be the corresponding conjunctive
monomial.
𝑛
𝑥𝑘 , 𝑖𝑓 𝑉(𝑥𝑘 ) = 1;
𝑀𝑖 = ⋀ 𝑎𝑖𝑘 , 𝑤𝑖𝑡ℎ 𝑎𝑖𝑘 = {
𝑥𝑘 , 𝑖𝑓 𝑉(𝑥) = 0.
𝑘=1

- The DNF of α is then:

𝑝

α ≡ ⋁ 𝑀𝑖
𝑖=1

1.6.2. Conjunctive Normal Form (CNF)

In a similar way, we obtain the CNF of a formula α. Let α be a propositional calculus formula
with n variables x1, x2, . . . , xn. Suppose A is the truth table of α. The CNF of α is obtained as
follows:

- Let q be the number of rows of A, such that V (α) = 0.

- For each row i, i = 1, . . . , q where V (α) = 0, let Ci be the corresponding clause.
𝑛
𝑥𝑘 , 𝑖𝑓 𝑉(𝑥𝑘 ) = 0;
𝐶𝑖 = ⋁ 𝐼𝑖𝑘 , 𝑤ℎ𝑖𝑡ℎ 𝐼𝑖𝑘 = {
𝑥𝑘 , 𝑖𝑓 𝑉(𝑥) = 1.
𝑘=1

- The CNF of α is then:

𝑝

𝛼 ≡ ⋀ 𝑀𝑖
𝑖=1

Remark:

1. DNF(α) ≡ CNF(α)
2. By convention, if |= α, then DNF(α) ≡ 1;

10/11
 3. If α is a contradiction (antilogy or unsatisfiable formula) then, CNF(α) ≡ 0.

1.7. Conclusion
A lot of problems can be formulated in propositional logic, but when the number of variables
is large or unknown, the use of truth tables becomes difficult and sometimes impossible. In
Chapter 2, we will present a formal method (which does not use truth tables) to show that
formulas are tautologies or logical consequences of other formulas: proof theory.

11/11