Raihan Abdurrahman 1301210340 IF – 45 – 01

Name: NIM: Class:

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
correspondingsubmissionslotin 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-<student 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
(handwrittenanswer). YoumayaddadditionalA4-sizedpapers. Afterwardsyousubmitthescan/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 “x2 − 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)≡ 0-3≤ 0 ≡ −3 ≤ 0 (T)

b. P (1) T/F P(1) ≡ 12 – 3 ≤ 3(1) ≡ −2 ≤ 3 (𝑇)

c. ∃ x P (x) T/F ∋ 𝑥 P(x) ≡ T, karena P(1) = T

Ada satu persamaan yang benar, maka dianggap
True

d. ∀ x P (x) T/F ∀𝑥 P(x) ≡ F, karena P(6) = F

Tidak semua persamaan benar, maka dianggap False

e. ∃ x ¬P (x) T/F ∋ 𝑥 − P(x) ≡ T, karena -P(6) = -(F) = T

Ada satu persamaan yang benar, maka dianggap
True

f. ∀ x ¬P (x) T/F ∀𝑥 − P(x) ≡ F, karena -P(1) = -(T) = F

Tidak semua persamaan benar, maka dianggap False

g. ∀ xP (x) → ∀ x¬P (x) T/F ∀𝑥P(x) ≡ F, dan ∀x -P(x) ≡ F

Maka F → F ≡ 𝑇

h. ∀ x (P (x) → ¬P (x)) T/F Misal, P = 0, maka P(x)≡ 𝑇 dan ¬P(x)≡F

Maka, T→ 𝐹 ≡ F
Tidak semua persamaan benar, maka dianggap False

page 2 of 9
 Raihan Abdurrahman 1301210340 IF – 45 – 01
Name: NIM: Class:

def
Problem 2 (10 points) Let Q (x) ≡ x2 + 3 > 4x . If the domain consists of all integers, what are the truth
value of these formulas? Explain your reasoning.

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

ANSWER: Q (0) ≡ 02 + 3 > 4 (0) ≡ 3 > 0 (𝑇)
True
(b). [1 point] Q (1)
ANSWER: Q (1) ≡ 12 + 3 > 4(1) ≡ 4 > 4 (𝐹)
False
(c). [2 points] ∃ x Q (x)
ANSWER: Karena Q(0) bernilai True, maka formula tersebut bernilai True
(Satu persamaan benar sudah cukup untuk membuktikan bahwa nilainya True)

(d). [2 points] ∀ x Q (x)

ANSWER: Karena Q(1) bernilai False, maka formula tersebut bernilai False
(Semua persamaan harus bernilai True agar bisa bernilai True)

(e). [2 points] ∃ x ¬Q (x)

ANSWER: ¬Q (x)≡ - (𝑥2 + 3 ≤ 4𝑥)
¬Q (1) ≡ -(12 + 3 ≤ 4(1)) ≡ −(𝐹) ≡ 𝑇 (Formula bernilai True, karena hanya
butuh satu formula bernilai True
(f). [2 points] ∀ x ¬Q (x)
ANSWER: ¬Q (x) ≡ -(𝑥2 + 3 ≤ 4𝑥)
¬Q (0) ≡-( 02 + 3 ≤ 4(0)) ≡ −(𝑇) ≡ 𝐹 ( Formula bernilai False, karena tidak
semua persamaan bernilai True)

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, 1)

ANSWER: R (3, 1) ≡ 3 + 2(1) > 2(3) − 1
≡ 5 > 5, maka pernyataan itu False (F)
(b). [2.5 points] R (1, 3)
ANSWER: R (1,3) ≡ 1 + 2(3) > 2(1) − 3
≡ 7 > −1, maka pernyataan itu True(T)
(c). [2.5 points] ∃ x∃ y R (x,y)
ANSWER: Karena R(1, 3) bernilai True
Maka ∃𝑥∃𝑦 R(x, y) adalah True (T)

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

ANSWER : Karena R(3, 1) bernilai False
Maka ∀𝑥∀𝑦 R(x, y) adalah False (F)

page 3 of 9
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 6 of 9
Name: Raihan Abdurrahman NIM: 1301210340 Class: IF – 45 – 01

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 5 of 9
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))

Kesimpulan ∃x (C (x) ∧ T (x)), atau “seseorang di kelas punya tiket tilang” terbukti kesimpulan
yang benar.

(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)
Kesimpulan ¬𝐸 tidak dapat dtitentukan, maka merupakan kesimpulan yang salah

page 6 of 9
Name: Raihan Abdurrahman NIM: 1301210340 Class: IF – 45 – 01

(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:
(1) ∀x (S (x) → E (x)) (premis)
(2) ∃x (S (x) ∧ D (x)) (premis)
(3) S (c) ∧ D (c) (instansiasi eksistansial dari (2) untuk suatu c)
(4) S (c) → E (c) (instansiasi universal dari (1) untuk c di (3))
(5) S (c) (simplifikasi dari (3))
(6) E (c) (modus ponens dari (4) dan (5))
(7) D (c) (simplifikasi dari (3))
(8) E (c) ∧ D (c) (konjungsi (6) dan (7))
(9) ∀x (E (x) ∧ D (x)) (generalisasi eksistensi dari (8))

Kesimpulan “ ada film menarik tentang dinosaurus” atau ∀x (E (x) ∧ D (x)) terbukti
benar

(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, L (x) := x has visited Louvre. Suppose the
domain of x be the set of all persons.
ANSWER:
(1) ∃x (C (x) ∧ F (x)) (premis)
(2) ∀x (F (x) → L(x)) (premis)
(3) C (c) ∧ F (c) (instansiasi eksitenasi (1) untuk sebuah c)
(4) F (c) → L(c) (un from (2) for c in (3))
(5) F (c) (simplification from (3))
(6) L(c) (modus ponens from (4) and (5))
(7) C (c) (simplification from (3))
(8) C (c) ∧ L(c) (conjunction from (6) and (7))
(9) ∃x (C (x) ∧ L(x)) (existential generalization from (8))

Kesimpulan “ada seseorang yang pernah ke Louvre” atau ∃x (C (x) ∧ L(x)) terbukti
benar

page 7 of 9
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:

• ∀x (T(x) → C (x))

• T(Sherkan) ∧ P (Sherkan)
• ∀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)

Kesimpulan yang benar adalah ada hewan karnivora yang memiliki usia yang panjang

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

page 8 of 9
Name: Raihan Abdurrahman NIM: 1301210340 Class: IF – 45 – 01

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(caterpillar,grass). eats(hawk,snake).
eats(caterpillar,herbs). eats(lion,deer).
eats(deer,herbs). eats(lion,fox).

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).

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).

(d). [1 point] carnivore(crow). (g). [2points] prey(X), not(carnivore(X)).

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

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

(c). herbivore(frog).
false.

page 9 of 9
(d). carnivore(crow).
true.

(e). omnivore(X).
X = crow.

(f). prey(hawk).
false.

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

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