COS2661 Assignment 3 memo 2024

COS2661 Assignment 3 memo 2024: QUESTION 1 [15] In this question you have to translate sentences of English sentences into First-Order Logic, using the predicates and names given in Table 1. English FOLComment TabisoTabisoThe name of a boy. StudentstudentTafaratafaraPetpet Names The name of a girl. Predicates x is smallSmall (x) x is largeLarge (x) x LeftOf yLeftOf (x, y) x Smaller ySmaller (x, y) x Larger yLarger (x, y) x Owned yOwned (x, y) x BackOf yBackOf (x, y) x Gave yGave (x, y) x Fed yFed (x, y) x Own yOwn (x, y) x is smartSmart Smart referring to intelligent Table 1 1.1Nothing to the left of Tabiso is larger than everything to the left of Tafara. (3) 1.2Anything to the left of Tabiso is smaller than something that is in back of every pet to the right of Tafara.(3) 1.3Every student gave a pet to some other student sometime or other.(3) 1.4No student fed every pet.(3) 1.5If Tabiso ever gave Tafara a pet, she owned it then and he didn’t.(3) 2COS2661/105/0/2024 QUESTION 2 [15] In this question you have to translate sentences of First-Order Logic into English sentences, using the predicates and names given in Table 1. 2.1∀x (¬∃y FrontOf(y, x) → Large (x)) (3) 2.2∀x ((Student(x) ∧ ∃y (Pet(y) ∧ LeftOf(x; y))) → Own(x, y)) (3) 2.3∀x∀y ((Between (tafara, x, y) ∧ x ≠ y) → (Small(x) ∧ Small(y))) (3) 2.4∀x ((Pet(x) ∧ ∀y ¬BackOf (y, z)) → ¬∃z (Pet(z) ∧ x ≠ z ∧ Smaller (x, z)) (3) 2.5∃x∃y [Student (x) ∧ Student (y) ∧ x ≠ y ∧ ∀z(Student(z) → (z = x ˅ z = y)) ∧ Smart (x) ∧ Smart (y)] (3) QUESTION 3 [10] Below a Tarski World is given followed by ten sentences. Which of the sentences are true and which sentences are false in the given world? back a: C, M f: D, S left right d: T, M e: C, S b: D, L c: T, L front Tarski World: Question 5Sentences: 1.∃x ∀y ¬SameSize(y, x) 2.∀x (Tet(x) → ∀y ∃z (Cube(y) ∧ Tet(z) ∧ RightOf(y, x) ∧ LeftOf(x, z))) 3.∀x ∀y (Adjoins (x, y) → ¬SameSize(x, y)) 4.∀x∀y [¬ (Tet(x) ∧ Smaller(x, y))  Medium(x)] 5.∀x∀y [(Dodec(x) ∧ Dodec(y)) → (LeftOf(x, y)  RightOf(x, y))] 6.∃y ∀x (Medium(y) → (Tet(y) ∧ (Cube(x) → Smaller(y, x)))) 7.∀x∀y[(Tet(x) ∧ Cube(y)) → Larger(x, y)] 8.∃x ∃y (Cube(x) ∧ Tet(y) ∧ ¬SameSize(x, y)) 9.∃x ∃y [x ≠y ∧ Tet(x) ∧ Tet(y) ∧ Medium(x) ∧ Medium(y)] 10.Cube(d) → ∀x ∀y SameShape(x, y) QUESTION 4[15] 4.1(5) Transform the following formula into the prenex normal form: x ((C(x)  y (T(y)  L(x, y))) → y (D(y)  B(x, y))) 4.2Find the prenex normal form of ∀x (∃y R(x, y) ∧ ∀y ¬S(x, y) → ¬(∃y R(x, y) ∧ P))(5) 4.3Transform the following formula into prenex normal form:(5) x (P(x) → ((y)(P(y) → P(f(x,y)))  (y)(Q(x,y) →P(y)))) QUESTION 5 [45] In this question, you have to construct formal proofs using the natural deduction rules. The Fitch system makes use of these rules. A summary of the rules of natural deduction is given on pages 573 to 578 of your textbook. Consult this when you do this question. Remember that De Morgan’s laws and other tautologies are not permissible natural deduction rules. You are also not allowed to use Taut Con, Ana Con or FO Con. It is important to number your statements, to indicate subproofs and at each step to give the rule that you are using. Hint: If you have access to a computer, take advantage of the fact and use Fitch. 5.1 (Formally) prove that the following two premises are contradictory: 4 1.x Clever(x) 2.x  Clever(x) (6)COS2661/105/0/2024 5.2 Using the natural deduction rules, give a formal proof of: ∀x∀y(Ixy→ Iyx) ∴ ∀x∀y(Ixy ↔ Iyx ) 5.3 (12) Construct a proof for the argument: ∀x∀y∀z[(Sxy ∧ Syz) → Sxz], ∀x¬Sxx ∴ ∀x∀y(Sxy → ¬Syx) 5.4 (13) Construct a proof for the argument: ∀x∃yRxy ∀x∀y(Rxy→∃zRzx), ∀x∀y(Ryx→∀zRxz) ∴∀x∀yRxy