Indian Institute of Information Technology

Design and Manufacturing, Kancheepuram

Chennai 600 127, India Instructor
An Autonomous Institute under MHRD, Govt of India N.Sadagopan
http://www.iiitdm.ac.in
COM205T Discrete Structures for Computing

Problem Session - Logic

1. Translate each of the following sentences into FOL.

(a) Not all cars have carburetors

¬∀x [car(x) → carburetors(x)]
∃x [car(x) ∧ ¬carburetors(x)]

(b) Some people are either religious or pious

∃x (R(x) ⊕ P (x)) ≡ ∃x ¬(R(x) ↔ P (x))
¬∀x [R(x) ↔ P (x)]
∃x((R(x) ∧ ¬P (x)) ∨ (¬R(x) ∧ P (x))

(c) No dogs are intelligent

∀x (dog(x) → ¬Intelligent(x))
¬∃x (dog(x) ∧ Intelligent(x))

(d) All babies are illogical

∀x (baby(x) → illogical(x))
¬∃x (baby(x) ∧ ¬illogical(x))

(e) Every number is either negative or has a square root

∀x ¬(number(x) ↔ sqroot(x))
¬∃x (number(x) ↔ sqroot(x))
∀x((number(x) ∧ ¬sqroot(x)) ∨ (¬number(x) ∧ sqroot(x))

(f) Some numbers are not real

∃x¬Real(x) or ¬∀x Real(x)

(g) Every connected and circuit-free graph is a tree

∀x [(conn(x) ∧ ¬cir(x)) → tree(x)]
¬∃x [(conn(x) ∧ ¬cir(x)) ∧ ¬tree(x)]

(h) Not every graph is connected

¬∀x connected(x) or ∃x ¬connected(x)

(i) All that glitters is not gold

∀x [glitter(x) → ¬gold(x)]
¬∃x [glitter(x) ∧ gold(x)]

(j) There is a barber who shaves all men in the town who do not shave themselves
∃x [Barber(x) ∧ ∀y [man(y) ∧ ¬shaves(y, y)] → shaves(x, y)]
 (k) There is no business like show business
∀x [(business(x) ∧ (x 6= show business)) → ¬like(x, show business)]

2. Rewrite each proposition symbolically, when universe of discourse is a set of real numbers

(a) For each integer x, there exist an integer y such that x + y = 0

∀x [int(x) → ∃y (int(y) ∧ (x + y = 0))]

(b) There exist an integer x such that x + y = y for every integer y

∃x [int(x) ∧ ∀y (int(y) → (x + y = y))]

(c) For all integers x and y, x.y = y.x

∀x ∀y [[int(x) ∧ int(y)] → x.y = y.x]

(d) There are integers x and y such that x+y=5

∃x ∃y [(int(x) ∧ int(y)) ∧ (x + y = 5)]

3. Using FOL, express the following

(a) Every student in this class has taken exactly two mathematics course at this
school
∀x [stud(x) → ∃y1 ∃y2 (y1 6= y2 ∧ math(y1 ) ∧ math(y2 ) ∧ taken(x, y1 ) ∧ taken(x, y2 )∧
∀y3 (y3 6= y1 ∧ y3 6= y2 ∧ math(y3 ) → ¬taken(x, y3 )) )]

∀x (stud(x) → mathcount(x) = 2)

(b) Someone has visited every country in the world except Libya
∃x ∀y [notvisited(x, y) ↔ (y = Libya)]
∃x ∃!y [notvisited(x, y) ↔ (y = Libya)]
∃x [person(x) ∧ ∀y (country(y) → (visited(x, y) ↔ (y 6= Libya)))]

(c) No one has climbed every mountain in the Himalayas

∀x (person(x) → ¬ ∀ y(M ountain(y) → Climb(x, y))
¬ ∃x (person(x) ∧ ∀ y(M ountain(y) → Climb(x, y))
∀x∃y¬climb(x, y), where climb(x, y) is “x climbs y, ”the domain x consists of all human
beings and the domain y consists of all mountains in the world.

4. Check the validity: Every computer science student takes discrete mathematics. Neetha is
taking discrete mathematics. Therefore, Neetha is a computer science student.
The given conclusion is false. The following Venn diagram is a counter example for the given
conclusion.
DM

Comp.
Sci Neetha

5. Check the validity: If it does not rain or it is not foggy then the sailing race will be held
and life saving demonstrations will go on. If the sailing race is held, then the trophy will be

2
 awarded. The trophy was not awarded. Therefore, it rained.
The conclusion is TRUE by the following argument.
premise ¬R ∨ ¬F → S ∧ D . . . (1)
premise S → T . . . (2)
premise ¬T . . . (3)
1 ¬R ∨ ¬F → S . . . (4)
4, 2 ¬R ∨ ¬F → T . . . (5)
5 ¬T → ¬(¬R ∨ ¬F ) . . . (6)
6, 3 ¬(¬R ∧ ¬F ) . . . (7)
7 R∧F . . . (8)
8 R
6. Prove or Disprove: All doctors are college graduates. Some doctors are not golfers. Hence,
some golfers are not college graduates.

premise : ∀x(Doctor(x) → Grad(x))

premise : ∃x(Doctor(x) ∧ ¬Golf (x))
conclusion : ∃x(Golf (x) ∧ ¬Grad(x))

The given conclusion is false. The following Venn diagram is a counter example for the given
conclusion.
Graduates

Doctor Golfers

7. Using FOL: express the following

(a) All boys in the class are at least as tall as Mr.Sharma whereas Mr.Sharma is taller than
some girls in the class.

∀x (Boys(x) → Atleast-tall(x, Sharma)) ∧∃y (Girls(y)∧ taller(Sharma, y))

(b) In the array A with 100 integer elements, the first fifty numbers are in increasing order
and the last fifty are in decreasing order.

(∀i(1 ≤ i ≤ 49)[A[i] ≤ A[i + 1]]) ∧ (∀i(51 ≤ i ≤ 99)[A[i] ≥ A[i + 1]])

(c) It is not the case that all blueline buses are bad. Some persons who drive blueline buses
are not certified drivers.

¬∀x (Bluelinebus(x)).
∃x (Person(x)∧ Drives(x, bluelinebus) ∧¬ Certified(x))

8. The attack will succeed only if the enemy is taken by surprise or the position is weakly de-
fended. The enemy will not be taken by surprise unless he is overconfident. The enemy will
not be overconfident if the position is weakly defended. Therefore, the attack will not succeed.

Let, A represents attack will succeed.

3
 E represents enemy is taken by surprise.
W represents the position is weakly defeded.
O represents he is overconfident.
The given statement can be written as follows:

premise : A→E∨W
premise : ¬O → ¬E
premise : W → ¬O
Conclusion : ¬A
Using Truth Table, we can check whether the given conclusion follows from the premises.
a b c
A E W ¬A E ∨ W W ∧ E ¬(W ∧ E) A → (E ∨ W ) a ∧ b c → ¬A
T T T F T T F T F T
T T F F T F T T T F
T F T F T F T T T F
T F F F F F T F F T
F T T T T T F T F T
F T F T T F T T T T
F F T T T F T T T T
F F F T F F T T T T

The last column says that the given argument is contigency. i.e., the given argument is
invalid. Thus, the conclusion does not follows from the premises.

9. Check the validity of the following implications

(a) P → (Q → R) equivalent to (P → Q) → (P → R)

P Q R Q → R (P → Q) (P → R) (P → Q) → (P → R) P → (Q → R)
T T T T T T T T
T T F F T F F F
T F T T F T T T
T F F T F F T T
F T T T T T T T
F T F F T T T T
F F T T T T T T
F F F T T T T T

Hence, P → (Q → R) is equivalent to (P → Q) → (P → R).

(b) [(P → Q) ∧ (R → S)] → [(P ∨ R) → (Q ∨ S)]

From the table, it is clear that [(P → Q) ∧ (R → S)] → [(P ∨ R) → (Q ∨ S)] is a

contigency. Refer the table given below.

4
 (P → Q) (P ∨ R) [(P → Q) ∨ (R → S)]
P Q R S P → Q R → S (P ∨ R) (Q ∨ S) ∨ → →
(R → S) (Q ∨ S) [(P ∨ R) → (Q ∨ S)]
T T T T T T T T T T T
T T T F T F T T T T T
T T F T T T T T T T T
T F T T F T T T T T T
T T F F T T T T T T T
T F T F F F T F F F T
T F F T F T T T T T T
T F F F F T T F T F F
F T T T T T T T T T T
F T T F T F T T T T T
F T F T T T F T T T T
F F T T T T T T T T T
F T F F T T F T T T T
F F T F T F T F T F F
F F F T T T F T T T T
F F F F T T F F T T T
10. Show that the following propositions are valid
(a) [∀xP (x) → Q] equivalent to [∃xP (x) → Q]

∀xP (x) and ∃xP (x) are atomic predicates. Therefore, we can check the validity of the
given proposition using truth table.
From the last two columns we can conclude that given propositions are not equivalent.
∀xP (x) Q ∃xP (x) ∀xP (x) → Q ∃xP (x) → Q
0 0 0 1 1
0 0 1 1 0
0 1 0 1 1
0 1 1 1 1
1 0 0(NA) NA NA
1 0 1 0 0
1 1 0(NA) NA NA
1 1 1 1 1

(b) ∀x[P → Q(x)] equivalent to [P → ∀xQ(x)]

∀x[P → Q(x)]
↔ ∀x[¬P ∨ Q(x)]
↔ [¬P ∨ Q(0)] ∧ [¬P ∨ Q(1)] ∧ [¬P ∨ Q(0)] ∧ . . .
↔ [¬P ∨ (Q(0) ∧ Q(1) ∧ Q(2) ∧ . . .)]
↔ [¬P ∨ (∀xQ(x))]
Hence, the given propositions are equivalent.

11. Everyone who gets admitted into an IIT gets a job. Therefore, if there are no jobs, then
nobody gets admitted into any IIT.

Premise: ∀x((∃y(IIT (y) ∧ admit(x, y))) → (∃z(job(z) ∧ getjob(x, z))))

Conclusion: ∀z(¬(job(z)) → ∀x∃y(IIT (y) ∧ ¬admit(x, y)). (or)
∀z(¬(job(z)) → ¬∃x∀y(IIT (y) → admit(x, y)).

5
12. All horses are animals. Therefore, heads (leader) of horses are heads of animals.

Premise: ∀x(H(x) → A(x))

Conclusion: ∀x(∃y(H(y) ∧ Head(x, y)) → ∃y(A(y) ∧ Head(x, y))).