Predicate Logic Problems and Solutions
Explore various scenarios and challenges in predicate logic, from converting statements to normal form to reasoning using predicate logic. Dive into encoding sentences in first-order logic, understanding FOL formulas, and formalizing sentences with FOL formulas.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Tutorial First Order (Predicate) Logic Foundations of Computing Science Pallab Dasgupta Professor, Dept. of Computer Sc & Engg 1 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Convert to Normal Form Express the statements below in FOL and convert each to Normal Form using the predicates: Phil(x) : x is a Philosopher Book(x): x is a Book Write(x,y): x writes book y StudentOf(y,x): y is a student of x. Read(x,y): x reads y Every philosopher writes at least one book All students of a philosopher read one of their teacher s books. There exists a philosopher with students 2 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Reasoning using Predicate Logic Consider the following statements: A topper is a student with highest CGPA. For each topper, either everyone likes the topper or the topper dislikes everyone. Raj dislikes everyone. Express these statements in first-order logic. Use meaningful predicate names, such as, Topper(x), Likes(x, y) (for x likes y). Convert the statements into normal form. For each of the following statements, determine whether it is entailed from the above statements. For the ones that are entailed, provide a resolution-refutation proof. For the ones that are not entailed (if any), provide a justification. G1: Raj is the topper G2: Every topper dislikes everyone 3 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Encode the following sentences in FOL: Jack owns a dog Every dog owner is an animal lover No animal lover kills an animal Either Jack or Curiosity killed the cat, who is named Tuna Did Curiosity kill the cat? 4 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Questions 1. What is the meaning of the following FOL formulas? i. bought(Frank, dvd) ii. x.bought(Frank, x) iii. x(bought(Frank, x) bought(Susan, x)) iv. x.bought(Frank, x) x.bought(Susan, x) v. x y.bought(x, y) vi. x y.bought(x, y) 5 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Questions 2. Define an appropriate language and formalize the following sentences using FOL formulas. i. Bill has at least one sister. ii. Bill has no sister. iii. Bill has at most one sister. iv. Bill has (exactly) one sister. v. Bill has at least two sisters. vi. Every student takes at least one course. vii. Only one student failed Geometry. viii. No student failed Geometry but at least one student failed Analysis. ix. Every student who takes Analysis also takes Geometry. 6 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Questions 3. Which of the following formulas is a formalization of the sentence: "There is a computer which is not used by any student x.(Computer(x) y.( Student(y) Uses(y, x))) x.(Computer(x) y.(Student(y) Uses(y, x))) x.(Computer(x) y.(Student(y) Uses(y, x))) 7 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
