Name:Akbar Muhammad Prakoso NIM: 1301213225 Class: IF4509

Assignment CLO 2: Predicate Logic

Mathematical Logic (CII1B3)
First Term 2021-2022

Instructions:

1. This assignment is due Wednesday, November 10, 2021 at 5:00 p.m.. Please submit
your work to the corresponding submission slot in LMS CeLOE. You need to submit a
readable .pdf file of this assignment to the provided submission slot in CeLOE . You
can contact your class instructor for more detailed information. Please make sure
that your file size do not exceed the maximum file size allowed.

2. Please upload your assignment to the LMS CeLOE under the file name: A2 -cstudent
ID>.pdf, for example: A2-1301218888.pdf.

3. You may submit this assignment in one the following form:

a.You print this assignment and write your answer using HB/2B pencil or pen with
blue/black ink (handwritten answer). You may add additional A4-sized papers.
Afterwards you submit the scan/photograph of this assignment.
b.You use a .pdf editing tools and write your answer directly using blue/black colored writing.
c.You copy the problem from this assignment to a text/word processing program and
type your answer neatly.
d.You rewrite the problem from this assignment in an A4-sized paper and submit the
scan/photograph of your work.

4. All problems in this assignment are adapted from the textbooks. The problems are
written in English. If you are a student in a regular class, you may answer the
problems in Bahasa Indonesia. However, if you are a student in international class,
your answers must be written in English—otherwise your assignment will not be
graded. You may ask your class instructor or teaching assistant for helping you
understanding the problem, but you should not ask them to give the solution of any
problem.

5. Be neat and write legibly. You will be graded not only on the correctness of your
answers, but also on the clarity with which you express them.

6. This assignment consists of 8 problems, each but Problems 6 and 7 are worth 10
points. Problems 6 and 7 are worth 20 points each.

7. Please retain yourself from copying answers from elsewhere without understanding
the steps. Such an attitude will not enhance your knowledge. This assignment is an
individual evaluation.

8. Important: late submission without reasonable explanation will not be graded.

page 1 of 9
Problem 1 (10 points) Let P (x) be the statement “x 2 — 3 ≤ 3x” and suppose the
domain for x is the set of all integers. Complete the following table concerning the truth
value of these formulas. Provide a relevant reason for each answer.

Truth Value
Part Formula (circle either T or F) Reason [1 point]
[0.25 points]
a. P (0) T/F P(0)=02 − 3 ≤ 3.0 = −3 ≤ 0 = 𝑇

b. P (1) T/F P(1)=12 − 3 ≤ 3.1 = −2 ≤ 3 = 𝑇

c. ∃𝑥𝑃(𝑥) T/F ∃𝑥𝑃(𝑥) = 𝑇, karena P(1) = T

d. ∀𝑥𝑃(𝑥) T/F ∀𝑥𝑃(𝑥) = 𝐹, karena ada P(4)= 4 2 — 3 ≤ 3.4= F

4 adalah counterexample dari ∀x (x 2 — 3 ≤ 3x)

e. ∃𝑥¬𝑃(𝑥) T/F Kita punya ¬P (4) = ¬F = T sebab P(4)= 4 2 — 3 ≤ 3.4=

F
∃𝑥¬𝑃(𝑥) = 𝑇 karena ¬P (4) = T

f. ∀𝑥¬𝑃(𝑥) T/F Kita punya ¬P (0) = ¬T = F sebab P(0)=02 − 3 ≤ 3.0 =

𝑇
∀𝑥¬𝑃(𝑥) = 𝐹 karena ¬P (0) = F
0 adalah counterexample dari ∀𝑥¬(x 2 — 3 ≤ 3x)
g. ∀𝑥𝑃(𝑥) → ∀𝑥¬𝑃(𝑥) T/F ∀𝑥𝑃(𝑥) → ∀𝑥¬𝑃(𝑥)
𝐹→𝐹
T

h. ∀𝑥(𝑃(𝑥) → ¬𝑃(𝑥)) T/F ∀𝑥(𝑃(𝑥) → ¬𝑃(𝑥)), P(4)=F dan ¬𝑃(4) = 𝑇

∀𝑥(𝐹 → 𝑇)
F
1 adalah counterexample dari ∀𝑥(𝑃(𝑥) → ¬𝑃(𝑥))

page 2 of 9
Name:Akbar Muhammad Prakoso NIM: 1301213225 Class: IF4509

Problem 2 (10 points) Let 𝑄(𝑥) ≝ (𝑥 2 + 3 > 4𝑥). If the domain consists of all
integers, what are the truth value of these formulas? Explain your reasoning.

(a ). [1 point] Q (0)

ANSWER: 𝑄 (0) ≡ ( 02 + 3 > 4.0) ≡ 3 > 0 ≡ 𝑇

True

(b ). [1 point] Q (1)

ANSWER: 𝑄 (1) ≡ ( 12 + 3 > 4.1) ≡ 4 > 4 ≡ 𝐹

False

(c ). [2 points] ∃𝑥𝑄 (𝑥)

ANSWER: ∃𝑥𝑄 (𝑥 ) = 𝑇, 𝑘𝑎𝑟𝑒𝑛𝑎 𝑄(0 ) ≡ 𝑇

True

(d ). [2 points] ∀ 𝑥𝑄(𝑥)

ANSWER: ∀ 𝑥𝑄 (𝑥) = 𝐹, 𝑘𝑎𝑟𝑒𝑛𝑎 𝑄 (1) ≡ 𝐹

1 adalah counterexample dari ∀𝑥𝑄(𝑥)
False

(e ). [2 points] ∃𝑥 ¬𝑄(𝑥)

ANSWER: ∃𝑥¬ 𝑄(𝑥 ) = 𝑇, 𝑘𝑎𝑟𝑒𝑛𝑎 ¬𝑄 (1) ≡ ¬𝐹 ≡ 𝑇

True

(f ). [2 points] ∀ 𝑥¬𝑄(𝑥)

ANSWER: ∀ 𝑥 𝑄(𝑥 ) = 𝐹, 𝑘𝑎𝑟𝑒𝑛𝑎 𝑄 (0) ≡ 𝑇 ≡ 𝐹

0 adalah counterexample dari ∀ 𝑥¬𝑄(𝑥)
False

page 3 of 9
 Problem 3 (10 points) Suppose R (x, y) is the predicate x ‡ 2y > 2x — y. Determine
the truth of the following predicate formulas.

(a ). [2.5 points] R (3, fi)

ANSWER: R (3, 1) ≡ 3 + 2(1) > 2(3) − 1

≡ 5 > 5, Jadi bernilai False (F)

(b ). [2.5 points] R (fi, 3)

ANSWER: R (1,3) ≡ 1 + 2(3) > 2(1) − 3

≡ 7 > −1, maka bernilai True (T)

(c ). [2.5 points] ∃ x∃ y R (x,y)

ANSWER: : Karena R(1, 3) bernilai True

Jadi ∃𝑥∃𝑦 R(x, y) adalah True (T)

(d ). [2.5 points] ∀ x∀ y R (x,y)

ANSWER: Karena R(3, 1) bernilai False

Jadi ∀𝑥∀𝑦 R(x, y) adalah False (F)

page 4 of 9
 Name:Akbar Muhammad Prakoso NIM: 1301213225 Class: IF4509

Problem 4 (10 points) Suppose we have the following statements

G (x) : x is participated in the game,
S (x) : x (can) stop playing,
E (x) : x will be eliminated, and
C (x) : x cheats in the game.
Suppose the domain of x is all players. Express each of these statements using quantifiers,
logical connectives, and the previously defined predicates:

(a ). [2.5 points] No one participated in the game can stop playing.

ANSWER: ¬∃x ( G( x ) Λ S( x ))

(b ). [2.5 points] Everyone who cheats in the game will be eliminated.

ANSWER: ∀𝑥 ( 𝐶(𝑥) → 𝐸(𝑥 ))

(c ). [2.5 points] Someone who is participated in the game does not cheat.

ANSWER: ∃x ( G( x ) Λ -C( x ))

(d ). [2.5 points] All players who stop playing will be eliminated.

ANSWER: ∀𝑥 ( 𝑆(𝑥) → 𝐸 (𝑥))

page 5 of 9
 Problem 5 (10 points) Translate each of these statements into logical expression using
only the specified domain and predicates.

(a ). [2 points] “Someone in your school has not visited Jakarta”.

The domain is D := (x | x is a human being} and the predicates are S (x) := “x is

a person in your school” and J (x) := “x has visited Jakarta”.
ANSWER: ∃𝑥 ( S (x) ⋀ J (x))

(b ). [2 points] “Everyone in your class has studied mathematical logic and programming”.

The domain is D := (x | x is a human being} and the predicates are C (x) := “x is in

your class”,
M (x) := “x has studied mathematical logic”, and P (x) := “x has studied
programming”.

ANSWER: ∀𝑥 ( C (x) → M (x) ∧ P (x)

(c ). [2 points] No one in your school speaks French and German.

The domain is D := (x | x is a human being} and the predicates are S (x) := “x is

a person in your school”, F (x) := “x speaks French”, and M (x) := “x speaks
German”.
ANSWER: ¬∃𝑥 ( S(x) ∧ ( F (x) ∧ M (x)))

(d ). [2 points] There is a person in your school who is not happy.

The domain is D := (x | x is a human being} and the predicates are S (x) := “x is

a person in your school” and H (x) := “x is happy”.
ANSWER: ∃𝑥 ( S (x) ∧ ¬ H (x))

(e ). [2 points] Everyone in your school was born in Indonesia or Malaysia.

The domain is D := (x | x is a human being} and the predicate are S (x) := “x is

a person in your school”, I (x) := “x was born in Indonesia”, and M (x) := “x
was born in Malaysia”.
ANSWER: ∀𝑥 (S(x) → I (x) ∨ M (x))

page 6 of 9
 Name:Akbar Muhammad Prakoso NIM: 1301213225 Class: IF4509

Problem 6 (20 points) Verify whether each of these arguments is valid or not. Explain
which rules of inference are used for each step.

(a ). [5 points] “Linda, a student in this class, owns a red car. Everyone who owns a red
car has gotten at least one speeding ticket. Therefore, someone in this class has
gotten a speeding ticket.” Use the following predicates: C (x) := x is a student in
this class, R (x) := x owns red car, T (x) := x has gotten a speeding ticket. Suppose
the domain for x is the set of all persons.
ANSWER:
1. C (Linda) ∧ R (Linda) (premis)
2. ∀x (R (x) → T (x)) (premis)
3. R (Linda) → T (Linda) (universal instantiation dari (2))
4. R (Linda) (simplifikasi dari (1))
5. T (Linda) (modus ponens dari (3) dan (4))
6. C (Linda) (simplikasi dari (1))
7. C (Linda) ∧ T (Linda) (konjungsi (5) dan (6))
8. ∃x (C (x) ∧ T (x)) (existential generalization dari (7))

Jadi kesimpulan yang dapat ditarik dari pernyataan ∃x (C (x) ∧ T (x)), atau “seseorang di
kelas punya tiket tilang” adalah Terbukti kesimpulan bernilai Benar/ True(T).

(b ). [5 points] “All good players are expensive. Jack Grealish is not a good player.
Therefore, Jack Grealish is not expensive”. Use the following predicates: G (x) :=
x is a a good player and E (x) := x is expensive. Suppose the domain of x is the set
of all players.
ANSWER:

1. ∀x (G(x) → E(x)) (premis)

2. ¬G(Jack Grealish) (premis)
3. G(Jack Grealish)→ E(Jack Grealish) (instaniasi universal dari 1)

Jadi kesimpulan yang dapat ditarik adalah ¬𝐸 tidak dapat dtitentukan, sehingga dapat
dikatakan Kesimpulan bernilai Salah/ False(F).

page 7 of 9
 (c ). [5 points] “All movies produced by Steven Spielberg are exciting. Steven
Spielberg produced a movie about dinosaurs. Therefore, there is an exciting
movie about dinosaurs.” Use the following predicates: S (x) := x is a movie
produced by Steven Spielberg, E (x) := x is an exciting movie, D (x) := x is a
movie about dinosaurs. Suppose the domain of x be the set of all movies.
ANSWER:

a. ∀x (S (x) → E (x)) (premis)

b. ∃x (S (x) ∧ D (x)) (premis)
c. S (c) ∧ D (c) (instansiasi eksistansial dari (2) untuk suatu c)
d. S (c) → E (c) (instansiasi universal dari (1) untuk c di (3))
e. S (c) (simplifikasi dari (3))
f. E (c) (modus ponens dari (4) dan (5))
g. D (c) (simplifikasi dari (3))
h. E (c) ∧ D (c) (konjungsi (6) dan (7))
i. ∀x (E (x) ∧ D (x)) (generalisasi eksistensi dari (8))

Jadi kesimpulan yang dapat ditarik dari pernyataan “ ada film menarik tentang
dinosaurus” atau ∀x (E (x) ∧ D (x)) adalah Terbukti kesimpulan bernilai Benar/
True(T).

(d ). [5 points] “There is someone in this class who has been to France. Everyone who
goes to France visit the Louvre. Therefore, someone in this class has visited the
Louvre.” Use the following predicates: C (x) := x is in this class, F (x) := x has
been to France, G (x) := x has visited Louvre. Suppose the domain of x be the set
of all persons.
ANSWER:

a. ∃x (C (x) ∧ F (x)) (premis)

b. ∀x (F (x) → L(x)) (premis)
c. C (c) ∧ F (c) (instansiasi eksitenasi (1) untuk sebuah c)
d. F (c) → L(c) (un from (2) for c in (3))
e. F (c) (simplification from (3))
f. L(c) (modus ponens from (4) and (5))
g. C (c) (simplification from (3))
h. C (c) ∧ L(c) (conjunction from (6) and (7))
i. ∃x (C (x) ∧ L(x)) (existential generalization from (8))

Jadi kesimpulan yang dapat ditarik dari pernyataan “ada seseorang yang pernah ke
Louvre” atau ∃x (C (x) ∧ L(x)) adalah Terbukti kesimpulan bernilai Benar/
True(T).

page 8 of 9
 Name:Akbar Muhammad Prakoso NIM: 1301213225 Class: IF4509
Problem 7 (20 points) Mowgli lives in an Indian rainforest and recently he learned following facts:

All tigers are carnivorous animal.

Sherkan is a tiger and it eats plants regularly.
Every animal that eats plants regularly has a long life span.

(a ). [10 points] Suppose we have D = (x | x is an animal} and following predicates:

T (x) : “x is a tiger” P (x) : “x eats plants regularly”

C (x) : “x is a carnivorous animal” L (x) : “x has a long life span”.

Help Mowgli to translate each of his facts into predicate

formulas. ANSWER:
a. ∀x (T(x) → C (x))
b. T(Sherkan) ∧ P (Sherkan)
c. ∀x (P (x) → L (x))

(b ). [10 points] Mowgli thinks only one of the following conclusion is correct:

There is a carnivorous animal who has a long life span.

There is no carnivorous animal who has a long life span.

What is the correct conclusion? Explain your reasoning using rule of inference in
predicate logic. ANSWER:
1. ∀x (T(x) → C (x)) (premis)
2. T(Sherkan) ^ P (Sherkan) (premis)
3. ∀x (P (x) → L (x)) (premis)
4. T(Sherkan) → C (Sherkan) (instaniasi universal dari 1)
5. T(Sherkan) (simplifikasi dari 2)
6. C (Sherkan) (modus ponens dari 4 dan 5)
7. P (Sherkan) (simplifikasi dari 2)
8. P (Sherkan) → L (Sherkan) (instansiasi universal dari 3)
9. L (Sherkan) (modus ponens dari 7 dan 8)
10. C (Sherkan) ∧ L (Sherkan) (konjungsi dari 8 dan 9)
11. ∃x (C (x) ∧ L (x)) (generalisasi eksistensi dari 10)

Jadi kesimpulan yang benar dari pernyataan diatas adalah ada hewan karnivora yang memiliki usia
yang panjang (There is no carnivorous animal who has a long life span.)

page 9 of 9
 Problem 8 (10 points) Suppose we have the following Prolog knowledge base.

plant(herbs). eats(deer,shrub).
plant(grass). eats(grasshopper,grass).
plant(shrub). eats(rabbit,herbs).

animal(caterpillar). eats(crow,caterpillar).
animal(deer). eats(crow,herbs).
animal(grasshopper). eats(crow,grasshopper).
animal(rabbit). eats(fox,rabbit).
animal(crow). eats(frog,caterpillar).
animal(fox). eats(frog,grasshopper).
animal(frog).
eats(snake,frog).
animal(snake).
eats(snake,rabbit).
animal(hawk).
animal(lion). eats(hawk,crow).
eats(hawk,snake).
eats(caterpillar,grass).
eats(lion,deer). eats(lion,fox).
eats(caterpillar,herbs).
eats(deer,herbs).

Suppose the above knowledge base is supplemented with the following rules:

● herbivore(X):- eats(X,Y), plant(Y).

● carnivore(X):- eats(X,Y), animal(Y).

● omnivore(X):- herbivore(X), carnivore(X).

● prey(X):- eats(Y,X), animal(X), animal(Y).

page 10 of
9
 Akbar Muhammad Prakoso 1301213225 IF4509
Name: NIM: Class:
Determine the output of the following queries if the program is run using SWI-Prolog:

(a ). [1 point] eats(hawk,X). (e ). [2 points] omnivore(X).

(b ). [1 point] eats(X,caterpillar).
(f ). [2 points] prey(hawk).
(c ). [1 point] herbivore(frog).
(g). [2 points] prey(X), not(carnivore(X)).
(d ). [1 point] carnivore(crow).

ANSWER:
(a). eats(hawk,X)
X = crow ;
X = snake.

(b). eats(X,caterpillar)
X = crow;
X = frog.

(c). herbivore(frog). returns

False.

(e). omnivore(X). returns

X = crow.

(f). prey(hawk). returns

False.

(g). prey(X), not(carnivore(X)). returns

X = caterpillar;
X = deer;
X = grasshopper;
X = rabbit.

page 11 of
9