Chapter 1: Propositional logic

Proposition (Assertion)
A proposition is an assembly of words in a natural language that verifies the following three
properties:
1. It is recognized as syntactically correct;
2. It is semantically correct;
3. It can be unambiguously assigned a truth value (true or false).

otherwise: It is an informative sentence that can be judged true or false.

Examples :
1. An isosceles triangle has two equal sides.
2. The earth revolves around the moon
3. 2+3=6
4. Put your things away (order)
5. What time is it?
6. How much did you pay for this book?

Sentences 1, 2 and 3 are propositions

but sentences 4, 5 and 6 aren't, because they don't satisfy the previous conditions

- A proposition can be affirmative or negative

The sentence: the earth is spherical is affirmative.
Its negative form is: the earth is not spherical.

- A proposition can be composed. In this case, its truth value depends on the truth values of the
propositions that make it up:
“The earth is spherical and turnes around the sun”.
This proposition is true because it is the conjunction of two true propositions

The paradox
An informative sentence that is neither true nor false.
Example: “I'm lying”.

Propositional logic
The part of logic that deals with propositions is called propositional logic.
One of the aims of propositional logic is to develop a calculus, which we'll call propositional calculus.
This involves treating propositions as variables, designated by letters (p, q, r, ...) and introducing
operations to combine the values of these variables.

The benefits of propositional logic

Propositional logic allows:
- formal representation of propositions using the language of propositional calculus
- Deduction of new propositions from other propositions (deductive system)
- Check the validity of propositions in a formal way (truth tables)

Language A formal language is :

- A set of words or symbols. This set is called an alphabet.
- And rules for combining these words. These rules indicate how to construct complex propositions
called formulas.
1. The alphabet
composed of :
Propositions P, Q, R, ...
Logical connectors: ¬ , ˄ , ˅ , ⟹ , ⟺
Parentheses “(” , “)”
Symbol Designation Pronounciation
¬ Negation Not P
˄ Conjunction P and Q
˅ Disjunction P or Q
⟹ Implication P implies Q
⟺ Equivalence P is equivalent to Q
P if and only if Q

2. The syntax

A formula is a composition of propositions using logical connectors, noted α,β....

The following rules apply to composition:

1. Every proposition is a formula

2. If α is a formula, then ¬α is also a formula.
3. If α and β are two formulas then α o β is also a formula,such that o ϵ { ˄ , ˅ , ⟹ , ⟺}
4. If α is a formula then (α) is also a formula

Example
 P , Q , ¬P , ¬¬ Q , ¬P ˅ ¬Q , ¬Q⟹P˅¬R : well-formed formulas
 )PQ˅) , (P1⟹)P2¬P3)) : badly formed formulas

Connectors priority

Knowing the priorities helps you read the formula correctly and avoid extra parentheses.
- Connector priority from highest to lowest: ¬ , ˄ , ˅ , ⟹ , ⟺
- When the same connector is repeated in the same formula, priority is given to the one furthest to the
left.
- When a connector is enclosed in brackets, it takes precedence.

Examples:
1. P ˄ ¬ Q 1. Negation, [Link]
2. ¬ P ⟹ Q ˄ R 1. Negation, [Link], 3. implication
3. (P ˅ Q) ˄ R 1. Disjunction, 2. conjunction
4. P ⟹ Q ⟹ R 1. First implication 2. Second implication

Formalization:

Example: if the train arrives late and there are no cabs at the station, then the guest arrives late.
Consider the following propositional variables:
R: the train is late
T: there are cabs at the station
A: guest arrives late
We obtain: ( R ˄ ¬ T ) ⟹ A

Formula structure
A formula can be represented as a tree. This makes it easier to read the formula.
Example: R ˄ ¬ P ˅ (Q ⟹ S)
3- Semantics

The semantics of propositional language is concerned with giving a truth value to each formula in the
language.
We can define a function
f : pv → { T , F } ;
Where pv is the set of propositional variables, T means true and F means false.)
The truth values of the basic formulas are shown in the following tables, which are called truth tables:

P Q P˄ Q P˅Q P⟹Q P⟺ Q
T T T T T T
T F F T F F
F T F T T F
F F F F T T

P ¬P
T F
F T

Suppose α is a formula that contains n propositions, the corresponding truth table will contain 2n rows.

Exemple α : Q ˅ R ⟹ P
P Q R Q ˅ R Α
T T T T T
T T F T T
T F T T T
T F F F T
F T T T F
F T F T F
F F T T F
F F F F T

Satisfiability
A formula α is satisfiable, if, its truth table contains at least one line whose truth value of α is T
Examples:
R⟹ Q ˅ P is satisfiable
P ˄ Q ˄ ¬ (P ⟺ Q) is not satisfiable

Generalization: Generalizing, we say that a set of formulas Γ ={α1 , α2 , ... ,αn} is satisfiable if,
its truth table contains at least one row such that all formula values are true.
Examples:
 {(P˄Q),(P˅Q), (P⟹Q),(P⟺Q)} is a satisfiable set (see the truth table of connectors),
on the other hand, the set {(P˄Q),(P˅Q), ¬P} is unsatisfiable.

Tautology
A formula β is said to be a tautology, if it is true in all lines of its truth table. We note ⊨ β
Example: β : P ˄ Q ⟹ Q

P Q P˄Q Β
T T T T
T F F T
F T F T
F F F T
So we have ⊨β (β is a tautology).

An antilogy is a formula that is false in every line of its truth table.

Logical consequence

We say that The formula β is a logical consequence of the formula α (we note α⊨ β) if the
truth value of β is T in all lines where the truth value of α is T.
Generalizing, we say that Formula β is a logical consequence of the set of formulas Γ ={α1 ,
α2 , ... ,αn} (we note Γ⊨ β) if the truth value of β is T in all lines where the truth values of the
formulas in Γ are all true.

Examples :
(P ˄ Q) ⊨ (P ⟹ Q)
{(P ⟹ Q) , ¬ Q} ⊨ ¬ P
P Q P⟹Q ¬Q ¬P
T T T F F
T F F T F
F T T F T
F F T T T

Logical equivalence

We say that α and β are logically equivalent if they have the same truth table (we note: α ≡ β).
Example : P ⟹ Q ≡ ¬ P ˅ Q

Substitution theorem

Let β be a formula containing the proposition P and β' the formula that results from β by
substituting all occurrences of P by α (α is any formula ) , so we have :
If ⊨ β then ⊨β'
Example : β : P ⟹ ( Q ⟹ R ⟹ P ) ,
We substitute all occurrences of the proposition P with the formula (A ˄ B) and obtain:
β' : A ˄ B ⟹ ( Q ⟹ R ⟹ A ˄ B)
We can easily verify that β and β' are tautologies
Replacement theorem

Let α be a formula containing several occurrences of a subformula β, and α' be the resulting
formula of α by replacing β by β' in one or more occurrences of β. So we have:
If β ≡ β' then α ≡ α'

Example:
α : P ˅ (Q ⟹ R) ⟺ S ˅ (Q ⟹ R)
α' : P ˅ (¬ Q ˅ R) ⟺ S ˅ (Q ⟹ R)
According to the theorem: α ≡ α' because (Q⟹ R) ≡ (¬ Q ˅ R)

Usual equivalents

 ˄ , ˅: commutative and associative

α˅β≡β˅α
α˄β≡β˄α
α˅(β˅α)≡(α˅β)˅α
α˄(β˄α)≡(α˄β)˄α

 ˅ is distributive over ˄ and ˄ is distributive over ˅

α˅(β˄γ)≡(α˅β)˄(α˅γ)
α˄(β˅γ)≡(α˄β)˅(α˄γ)

 Morgan's Law

¬(α˄β)≡¬α˅¬β
¬(α˅β)≡¬α˄¬β

 Idempotence

α˄α≡α
α˅α≡α
Remarks:
1. we can replace the logical connector “˄” by “.” and the logical connector “˅” by “+”.
2. we note a tautology “1” and a contradiction “0”.

Other equivalents:
α ≡ ¬¬α
α ⟹ β ≡ (¬ α ˅ β)
α ⟹ β ≡ ¬ (α ˄ ¬ β)
α ⟺ β ≡ ( α ⟹ β) ˄ ( β ⟹ α)
α ⊕ β ≡ ¬ (α ⟺ β)
α+0=α
α+1=1
α.1=α
α.0=0
α.α=α
α+α=α
α .( α + β) = α
α + (¬α . β) = α + β
 (α. β) + ¬ β = α
α.( ¬ α+ β) = α . β
α + (β . γ) = (α + β) . (α + γ)

Negation, contrapositive and reciprocal of an implication P ⟹ Q:

Negation : ¬ (P ⟹ Q ) ≡ ¬ (¬ P ˅ Q) = P ˄ ¬ Q
Contrapositive : (P ⟹ Q ) ≡ (¬ Q ⟹ ¬ P)
Reciprocal: Q ⟹ P

Complete connectors system

Let S be a subset of logical connectors. We say that S is a complete system if for any formula
α, we can find a formula α' containing only the elements of S, such that α≡ α'.

Example

The set { ¬ , ˄ } is a complete system

Proof
Α α'
P˅Q ¬(¬P ˄ ¬ Q)
P⟹ Q ¬ (P ˄ ¬Q)
P⟺Q ¬(P ˄¬Q) ˄ ¬(Q ˄ ¬P)

The Sheffer connector

Henry M. Sheffer considered a connector which, by itself, forms a complete system:

- the value of the function representing the first connector must not be T when the values of P
and Q are both T
- the value of the function representing the second connector must not be F when the values of
P and Q are both F.

P Q P˄Q P˅Q ¬( P ˄ Q) ¬( P ˄ Q)
T T T T F F
T F F T T F
F T F T T F
F F F F T T

Comparing the definition with the table, we find that the two connectors correspond to the
negation of the two logical connectors ˄ , ˅.

 Nand : P ↑ Q = ¬ (P ˄ Q)
 Nor : P ↓ Q = ¬ (P ˅ Q)

To show that these two symbols do indeed represent Sheffer connectors, it's enough to be able
to write all the other connectors just with these connectors (↑,↓)
1. The NAND

Α α'
¬P P↑P
P˄Q P↑Q↑ P↑Q
P˅Q P↑P↑Q↑Q
P⟹Q ..........................
P⟺Q ...........................

2. The NOR :

Α α'
¬P P↓P
P˄Q P↓Q↓ P↓Q
P˅Q P↓P↓Q↓Q
P⟹Q .........................
P⟺Q ..........................

The Normal forms

1. Conjunctive Normal Form (CNF)

A formula α is in conjunctive normal form, if it is of the form: C1 ˄ ... ˄ C n , such that each Ci
is a clause of the form L1 ˅ ... ˅ Lm where each Li is a literal of the form P or ¬ P.

Examples
(P ˅¬Q) ˄ (R ˅ ¬P ˅ Q)
P ˄ (¬ Q ˅ P)

2- Disjunctive Normal Form (DNF)

A formula α is in disjunctive normal form, if it is of the form: M1 ˅ ... ˅ Mn , such that each
Mi is a monomial of the form L1 ˄ ... ˄ Lm where each Li is a literal of the form P or ¬ P.

Examples
(¬P ˄¬Q) ˅ (P ˄ R)
P ˅ (¬ P ˄ Q) ˅ R

How to construct an CNF or DNF of a formula α ?

1. Draw up the truth table for the formula α

P Q R α
T T T F
T T F F
T F T T
T F F F
F T T T
F T F F
F F T F
F F F T
2. The DNF: we take the rows of the table where the value of α is true (T) and construct the
conjunctions :
Line 3 : P ˄ ¬ Q ˄ R
Line 5 : ¬ P ˄ Q ˄ R
Line 8 : ¬P˄ ¬Q ˄ ¬R

Where we take P if the value of the proposition is T and ¬P if the value of the proposition is F
(and so for propositions Q and R).
The DNF is: (P ˄ ¬ Q ˄ R) ˅ (¬ P ˄ Q ˄ R) ˅ (¬P˄ ¬Q ˄ ¬R)

3. The CNF : we take the rows of the table where the value of α is false (F) and build the
disjunctions:

Line 1: ¬P ˅ ¬Q ˅ ¬R
Line 2: ¬P ˅ ¬Q ˅ R
Line 4: ¬P ˅ Q ˅ R
Line 6: P ˅ ¬Q ˅ R
Line 7: P ˅ Q ˅ ¬R

Where we take P if the value of the proposition is F and ¬P if the value of the proposition is T
(and so for propositions Q and R).

The CNF is : (¬P ˅ ¬Q ˅ ¬R) ˄ (¬P ˅ ¬Q ˅ R) ˄ (¬P ˅ Q ˅ R) ˄ (P ˅ ¬Q ˅ R) ˄ (P ˅ Q ˅¬R)