Assignment 2: Predicate Logic: Mathematical Logic (CII1B3) [PDF]

Citation preview

Name: Ahmad Naufal Diwantara Putra



NIM: 1302204085



Class: SE-44-03



Assignment 2: Predicate Logic Mathematical Logic (CII1B3) First Term 2020-2021



Instructions: 1. This assignment is due Wednesday, November 4, 2020 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-.pdf, for example: A2-1301208888.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. Afterwardsyou 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 “1+x2 ≤ 3x”. 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) [0.25 points]



a.



P ( - 1)



T /F



P (-1) ≡ (1+(-1)2 ≤ 3(-1) ≡(2 ≤ (-3)) ≡ F



b.



P (1)



T /F



P(1) ≡ (1+(1)2 ≤ 3(1) ≡ (2 ≤ 3) ≡ T



c.



∃x P (x)



T /F



∃x P (x) ≡ T karena P (1) ≡ T



d.



∀x P(x)



T /F



∀x P(x) 𝐶 F karena P (-1) ≡ F P (-1) merupakan counterexample dari ∀x P(x)



e.



∃x¬P (x)



T /F



∃x¬P (x) ≡ T karena ¬P (-1)≡ ¬F ≡ T



f.



∀x¬P (x)



T /F



∀x¬P (x) ≡ F karena ¬P (1)≡ ¬T ≡ F ¬P (1) merupakan counterexample dari ∀x¬P (x)



g.



∃xP(x) ˄∃x¬P(x)



T /F



∃x P (x) ≡ T (dari c) dan ∃x¬P (x) ≡ T (dari e) Maka, ∃xP(x) ˄ ∃x¬P(x) ≡ T ˄ T = T



h.



∀xP(x)→ ∀x¬P(x)



T /F



Reason [1 point]



∀x P(x) ≡ F (dari d) dan ∀x¬P (x) ≡ F (dari f) Maka, ∀xP(x)→ ∀x¬P(x) ≡ F→ F ≡ T .



Problem 2 (10 points) Let Q (x) ≡ def x2 + 1 > 2x. If the domain consists of all integers, what are the truth value of these formulas? Explain your reasoning. (a) [1 point] Q(1) ANSWER: Formula ini False, karena kita dapat Q (1) ≡ (12 + 1 > 2·1) ≡ (2 > 2) adalah False (b) [1 point] Q (2) ANSWER: Formula ini True, karena kita dapat Q (2) ≡ (22 + 1 > 2·2) ≡ (5 > 4) adalah True (c) [2 points] ∃x Q(x) ANSWER: Formula ini True, Ketika, untuk x = 2 kita punya Q(2) ≡ adalah True.



(d) [2 points] ∀x Q (x) ANSWER: Formula ini False, Ketika, untuk x = 1 kita punya Q(1) ≡ adalah False. (e) [2 points] ∃x ¬Q (x) ANSWER: Formula ini True, Ketika kita punya ¬Q (1) ≡ (12 + 1 > 2·1) ≡ (2 > 2) adalah True (f) [2 points] ∀x ¬ Q (x) ANSWER: Formula ini False, Ketika kita punya ¬ Q (2) ≡ (22 + 1 > 2·2) ≡ (5 > 4) adalah False Problem 3 (10 points) Suppose Q (x, y) is the predicate x + 2y ≤ 2x - y. Determine the truth of the following predicate formulas. (a). [2.5 points] Q (3,1) ANSWER: Q (3,1) ≡ (3 + 2 · 1 ≤ 2 · 3 - 1) ≡ 5 ≤ 5 , Q (3,1) adalah True. (b). [2.5 points] Q (1,3) ANSWER: Q (1,3) ≡ (1 + 2 · 3 ≤ 2 · 1 - 3) ≡ 7 ≤ -1 , Q (1,3) adalah False (c) [2.5 points] ∃x∃y Q (x,y) ANSWER: Ketika Q (3,1) True, maka ∃x∃y Q (x,y) akan True (d) [2.5 points] ∀x∀y Q (x, y) ANSWER: Ketika Q (1,3) False, maka ∀x∀y Q (x, y) akan False



Problem 4 (10 points) Let C (x), P (x), A (x), and D (x) be the statements “x is a cat”, “x is one of my pet”, “x is an artist”, and “x is willing to dance”, respectively. Express each of these statements using quantifiers, logical connectives, and also using the previously mentioned predicates. (a). [2.5 points] No cats are willing to dance. ANSWER: ¬∃𝑥



Cx˄Dx ∀𝑥 (C x → ¬D(x))



. Setara dengan ∀𝑥 ¬ (C



x



˄ D(x)) , ∀𝑥 (¬C(x)˅¬D(x)), dan



(b). [2.5 points] No artist ever decline to dance. ANSWER: ¬∃𝑥(𝐴 𝑥 𝑥 ). Setara dengan ∀𝑥¬ (A(x) ˄ ¬D(x)), ∀𝑥 (¬A(x) ˅ D(x)), dan ∀x ˄ ¬𝐷 (A(x) → D(x)).



(c). [2.5 points] All my pets are cats. ANSWER: ∀𝑥(𝑃



𝑥



→𝐶



𝑥



)



(d). [2.5 points] My cats are not artists. ANSWER: ∀𝑥



𝐶 𝑋 → ¬𝐴 𝑥



.



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 visited Russia”. The domain is D := {x I x is a human being} and the predicates are P (x) := “x is a person in your school” and R (x) := “x has visited Russia”. ANSWER: ∃x (P (x) ˄ R(x))



(b). [2 points] “Everyone in your class has studied mathematical logic and programming”. The domain is D := { x I 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: ∀x (C (x) → M (x) ˄ P (x))



(c). [2 points] No one in your school owns both a bicycle and a motorcycle. The domain is D := {x I x is a human being} and the predicates are S (x) := “x is a person in your school”, B (x) := “x owns a bicycle”, and M (x) := “x owns amotorcycle”. ANSWER: ¬∃x (S (x) ˄ (B (x) ˄ M (x)))



(d). [2 points] There is a person in your school who is not happy. The domain is D := {x I x is a human being} and the predicates are S (x) := “x is a person in your school” and H (x) := “x ishappy”. ANSWER: ∃x (S (x) ˄ ¬H (x))



(e). [2 points] Everyone in your school was born in the twentieth or twenty-first century. The domain is D := {x I x is a human being} and the predicate are S (x) := “x is a person in your school”, T (x) := “x was born in the twentieth century”, and F (x) := “x was born in the twenty-first century”. ANSWER: ∀x (S (x) → T (x))



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) (instansiasi universal dari (2)) (4) R(Linda) (simplifikasi dari (1)) (5) T (Linda) (modus ponens dari (3) dan (4)) (6) C (Linda) (simplifikasi dari (1)) (7) C (Linda) ˄ T (Linda) (konjungsi dari (5) dan (6)) (8) ∃x (C (x) ˄ T (x)) (generalisasi eksistensial dari (7)) Dapat disimpulkan bahwa ∃x (C (x) ˄ T (x)), atau “someone in this class has gotten one speeding ticket”, Adalah kesimpulan yang benar..



(b). [5 points] “A convertible car is fun to drive. Isaac’s car is not a convertible. Therefore, Isaac’s car is not fun to drive.” Use the following predicates: C (x) := x is a convertible car, F (x) := x is fun to drive. Suppose the domain of x is the set of all cars. ANSWER:



(1) ∀x (C (x) → F (x)) (premis) (2) ¬C (Isacc’s Car) (premis) (3) C (Isacc’s Car) → F (Isacc’s Car) (instansiasi universal dari (1)) Dari pernyataan diatas, kita tidak bisa menyimpulkan :F (Isacc’s Car). Oleh karena itu, kesimpulannya :F (Isacc’s Car), atau “Isaac’s Car is not fun to drive”, bukan kesimpulan yang benar.



(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 eksistensial dari (2) untuk ∃ 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 dari (6) dan (7)) (9) ∃x (E (x) ˄ D(x)) (generalisasi eksistensial dari (8)) Dapat disimpulkan bahwa ∃x (E (x) ˄ D(x)), atau “there is an exciting movie about dinosaurs”, adalah kesimpulan yang 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 allpersons. ANSWER:



(1) ∃x (C (x) ˄ F (x)) (premis) (2) ∀x (F (x) → L(x)) (premis) (3) C (c) ˄ F (c) (instansiasi eksistensial dari (1) untuk ∃ c) (4) F (c) → L(c) (instansiasi universal dari (2) untuk c di (3)) (5) F (c) (simplifikasi dari (3)) (6) L(c) (modus ponens dari (4) dan (5)) (7) C (c) (simplifikasi dari (3)) (8) C (c) ˄ L(c) (konjungsi dari (6) dan (7)) (9) ∃x (C (x) ˄ L(x)) (generalisasi eksistensial dari (8)) Dapat disimpulkan bahwa ∃x (C (x) ˄ L(x)), atau “someone in this class has visited Louvre”, adalah kesimpulan yang benar.



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 I x is an animal} and following predicates: T (x) : “x is a tiger”



P (x) : “xeats 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) (instansiasi 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 eksistensial dari 10) Kesimpulannya “there is a carnivorous animal who has a long life span”.



Problem 8 (10 points) Suppose we have the following Prolog knowledge base. plant(herbs).



eats(deer,shrub).



plant(grass). plant(shrub).



eats(grasshopper,grass). eats(rabbit,herbs).



animal(caterpillar). animal(deer).



eats(crow,caterpillar).



animal(grasshopper). animal(rabbit).



eats(crow,grasshopper).



eats(crow,herbs).



animal(crow). animal(fox).



eats(fox,rabbit).



animal(frog). animal(snake).



eats(frog,grasshopper).



animal(hawk). animal(lion).



eats(snake,rabbit).



eats(frog,caterpillar). eats(snake,frog).



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). (c)[1 point] herbivore(frog). (d) [1 point] carnivore(crow).



ANSWER:



(a). eats(hawk,X). returns X = crow ; X = snake. (b). eats(X,caterpillar). returns X = crow; X = frog. (c). herbivore(frog). Returns false.



(f). [2 points] prey(hawk). (g). [2 points] prey(X), not(carnivore(X)).



(d). carnivore(crow). returns true. (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.