UMBB / FS / Computer Science Department

Subject: Mathematical logic Groups: 1st year computer-science Engineers

Date: February 10, 2024 Established by: S.Djeddai

EXERSISES SERIES: N°1

Syntax and semantics

Exercise 1 (*)
Translate the following sentences into formulas of the propositional logic:

 Today, it’s rainy.

r: it's rainy
r

 Today, it’s not rainy.

¬r

 He is clever and kind.

c : he is clever
k : he is kind
c∧k
 She didn’t write the letter or she lost it.
w: she wrote the letter
l : she lost the letter
¬w ∨ l
 If we work hard, we won’t fail.
h : working hard
f : fail
h → ¬f
 The year will be validated if and only if all the units are acquired.
v: validate the year
u: all the units are acquired.
v↔ u

Exercise 2
Give the truth tables of the statements p∨p, p∧p, p∨0 and p∨1.

p p∨p
0 0
1 1

p p∧p
0 0
1 1

p 0 p∨0
0 0 0
1 0 1
So, p∨0 ↔ p

p 1 p∨1
0 1 1
1 1 1
So, p∨0 ↔ 1

• Give the truth table of the “exclusive or”

p q P xor q
0 0 0
0 1 1
1 0 1
1 1 0

Exercise 3 (*)
Determine whether the following statements are well-formed formulas of propositional calculus.
1) ¬¬¬p
F1 is a well-formed formula of the propositional calculus; its sub-formulas are: p,¬p,¬¬p.

The syntaxic tree :

2) (p ∧ (q ∧ r)
F2 isn’t a well formed formula. It misses a right parenthesis.

3) ((p3 → p3) → p3)

F3 is a well-formed formula of the propositional calculus; its sub-formulas are p3, p3 → p3.

→ p3

p3 p3

4) ¬(p)
It is best to use parentheses only on compound statements.
¬p is a well-formed formula of the propositional calculus; its sub-formula is: p.

p
 5) ((p → q) ∨ (p ← q))
F5 isn’t a well formed formula, because the symbol ← doesn’t belong to the alphabet of
propositional calculus.

6) ¬ (p ↔ (q ∧ r))
F6 is a well-formed formula of the propositional calculus; its sub-formulas are: p, q, r, q ∧ r,
p ↔ (q ∧ r).

↔
p ∧

q r

7) (p ¬→ r)
F7 isn’t a well formed formula, because ¬ has to be applied on a propositional formula and
here it’s not.

8) r ∨(p¬(∧(q) ) →¬r)) ;
F8 isn’t a well formed formula, because ∧ is a binary connector and it’s applied here to only
one variable.

Exercise 2
Let F1 and F2 be two propositional formulas such as:
 F1 = p ∧ (r ∧ (¬q→ ¬p)) ;(*)
 F2 = ((q ∨¬p) → (¬¬q ∨¬p)) ∧ ((q ∨¬p) → (¬p ∨ q)).
List the subformulas of F1 and F2.

The subformulas of F1 are: p, q, r; ¬q ,¬p, (¬q→ ¬p), (r ∧ (¬q→ ¬p))

p ∧

r →

¬ ¬

q p

The subformulas of F2 are: p, q, ¬q ,¬p, ¬¬q, (q ∨¬p) , (¬¬q ∨¬p) , (¬p ∨ q)., ((q ∨¬p) → (¬¬q
∨¬p)), ((q ∨¬p) → (¬p ∨ q)).
 ∧

→ →

∨ ∨ ∨ ∨

q ¬ ¬ ¬ ¬ ¬ ¬ q

p ¬ p ¬ p p

q q

Exercise 3(*)

Example
I take my umbrella if and only if it’s rainy.

p:I take my umbrella

q: it’s rainy.

The sentence can be re-written as follows:

I take my umbrella if it’s rainy and I take my umbrella only if it’s rainy.

q→p∧p→q=q↔p

Give the propositional form of the following sentences:

1. If this student works hard, he will probably be admitted to the next grade.
w : this student works hard
a : he is admitted to the next grade
w→a

2. A relation is an equivalence relation if and only if it is reflexive, symmetrical and

transitive.
q: an equivalence relation , r :a reflexive relation, s : a symetrical relation ; t : a transitive
relation
q↔r∧s∧ t

3. If the humidity is high enough, it will rain in the afternoon or in the evening.
h: the humidity is high
ra: it will rain in the afternoon or in the evening.
re: it will rain in the evening.
h →ra ∨ re

4. We need courage and skills to climb a mountain

c: got courage
s: got skills
m: climb a mountain
c∧s→m
 5. The cake will be successful only if the recipe is followed correctly and the oven is at the
right temperature.
C:the cake is successful
r: the recipe is followed correctly
o: the oven is at the right temperature.
c → r ∧o

Exercise 4(*)
Consider the following proposition symbols:
P = “He needs a doctor”
Q = “He needs a lawyer”
R = “he had an accident”
S = “he is sick”
U = “he is injured”
1. (s →p)∧(r→q)
If he’s sick, he needs a doctor and if he had an accident, he needs a lawyer

2. (p ∧ q) → r
He needs a doctor and a lawyer only if he had an accident.
If he needs a doctor and a lawyer, then he had an accident.

3. p → (s ∨ u)
he needs a doctor only if he had an accident or he’s injured

4. (p ∧ q)↔ (s ∨ u)
He needs a doctor and a lawyer if and only if he is sick or injured

5. ¬(s ∨ u)→¬p
If he’s neither sick nor injured, he doesn’t need a doctor.
If he isn’t sick or injured, he doesn’t need a doctor

Exercise 6(*)
1. What are the interpretations that give the same value to (p∧ q) and (p → q)?
the interpretations that give the same value to (p∧ q) and (p → q) are :
I1 ={p →1, q→0 }
I2 ={ p →1, q→1}

2. List the models of the formula F= (p∧ q) ↔ (p → q)

I1 and I2 are the models of F
3. Study the validity of formula F?
F is not valid because there is at least an interpretation which is not a model of F

Exercise 7(* for F1)

We consider the formulas F1= p ∧ (¬q → (q → p)) and F2 = (p ∨ q) ↔ (¬p ∨¬q).

1. Let I be an interpretation. Determine, if possible, I(F1) and I(F2) in each of the following four
cases:
(a) we know that I(p) = 0 and I(q) = 1;
I(F1)= 0
(b) we know that I(p) = 0;
I(F1)= 0

(c) we know that I(q) = 1;

I(F1)= I(p)

(d) we don’t have any information about the truth values of I(p) and I(q).
I(F1)= I(p)
2. Are formulas F1 and F2 satisfiable? valid?
F1 is satisfiable it accepts at least a model.

3. Is the set {F1, F2} consistent?

In other words, is there an interpretation such that I(F1)= I(F2) = 1?