Predicate Logic Tutorial 3 PDF

Tutorial 3 PREDICATE LOGIC Made by: -Ahmad Ahmad Muhammad Predicates and Quantifiers Predicates P and the Open statement P(x) A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables....

Tutorial 3 PREDICATE LOGIC Made by: -Ahmad Ahmad Muhammad Predicates and Quantifiers Predicates P and the Open statement P(x) A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable. A statement P(x) is called open, if its truth could be known whenever the variable assigned a value. The set { x : P(x) is true } is called the solution set or truth set 1- Find the solution set for P(x), P(x)={ x : x is a garden in Giza} Ans. The solution set is {Zoo} 2- Find the solution set for P(x)= (x+3=1) Ù (x2 = 4) x ϵ Z (Z integer numbers) Ans. The solution set for x+3 =1 is {-2} The solution set for x2 = 4 is {-2, 2} The solution set for (x+3=1) Ù (x2 = 4) is {-2}. The Universal and Existential quantifiers: The universal quantifier ": " is read as “for each” or “for every” and it means "x : P(x) is true (Same as conjunction) 1- "x: P(x) = x2 ³ 0 (read; for all x, x2 is greater than or equal to zero) The existential quantifier $ : $ is read “there exists” or “for some” and it means $x : P(x) is true (Same as disjunction ) 2- $x, x2 < 0 (there exists an x such that x2 is less than zero) Negation of quantifiers: ¬ ("x : P(x)) = $x : ¬ P(x) ¬ ($ x : P(x)) = "x : ¬ P(x) The Universal and Existential quantifiers: De Morgan’s Law: Practice on Universal & Existential Quantifiers: Check every given Predicate that give True/False Quantifier according to given domain: a) Q (x) : “ x < 2 “, Domain is all Real Numbers (R) , Check “ " x Q (x) “ is True or False. b) P (x ) : “x2 > 0 “, Domain is all Integers , Check “ " x P (x) “ is True or False. c) P (x ) : “x2 > 0 “, Domain is all Positive Integers, Check “ " x P (x) “ is True or False. d) P (x ) : “ x > 3 “, Domain is all Real Numbers (R) , Check “ $ x P (x) “ is True or False. e) Q (x ) : “ x = x + 1 “, Domain is all Real Numbers (R) , Check “ $ x Q (x) “ is True or False. f) R (x ) : “x2 > 10 “, Domain is Positive integers not exceeding Four , Check “ $ x R (x) “ is True or False. Question 01 Rewrite each of the following statements in the form “∀ x,.” or “∃ x such that.” a) All dinosaurs are extinct. b) Every real number is positive, negative, or zero. c) No logicians are lazy. d) Some exercises have answers. e) There is a student in Math 211 Question 02 Rewrite each of the following statements in the form ∀ , if then. a. If a real number is an integer, then it is a rational number. b. All bytes have eight bits. c. No fire trucks are green. Question 03 Let P (x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English. a) ∃xP (x) b) ∀xP (x) c) ∃x ¬P (x) d) ∀x ¬P (x)  Question 05 Let P(x), Q(x), R(x), and S(x) be the statements “x is a baby,” “x is logical,” “x is able to manage a crocodile,” and “x is despised,” respectively. Suppose that the domain consists of all people. Express each of these statements using quantifiers; logical connectives; and P(x), Q(x), R(x), and S(x). a) Babies are illogical. b) Nobody is despised who can manage a crocodile. c) Illogical persons are despised. d) Babies cannot manage crocodiles.  Question 04 Express each of these statements using quantifiers. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”) a) Some old dogs can learn new tricks. b) No rabbit knows calculus. c) Every bird can fly. d) There is no dog that can talk. e) There is no one in this class who knows French and Russian. Precedence of Quantifiers and Logical Operators: e.g.: ∀x P(x) ∨ Q(x) equivalent to ( ∀x P(x) ) ∨ Q(x) not equivalent to ∀x (P(x) ∨ Q(x)) Binding Variables (Free and Bound Variables): E.g.: ∃ x (x + y = 1) x : is bound variable by the quantifier ∃. y: is free variable (not bounded by any quantifier) (x+y = 1) : is the scope of the quantifier ∃. Notes: - An expression with zero free variables is an actual proposition. - An expression with one or more free variables is still only a predicate: ∀x P(x,y). Nested Quantifiers Question 06 Let Q(x, y) be the statement “x has sent an e-mail message to y,” where the domain for both x and y consists of all students in your class. Express each of these quantifications in English. a) ∃x ∃y Q(x, y) b) ∃x ∀y Q(x, y) c) ∀x ∃y Q(x, y) d) ∃y ∀x Q(x, y) e) ∀y ∃x Q(x, y) f) ∀x ∀y Q(x, y) Question 07 Let D = E = {−2,−1, 0, 1, 2}. Determine whether each of the following statements is true or false. justify the false. a) ∀x in D, ∃y in E such that x + y = 0. b) ∃x in D such that ∀y in E, x + y = y. c) ∃x in D such that ∀y in E, x ≤ y. d) ∀x in D, ∃y in E such that xy ≥ y. Question 08 Use quantifiers and predicates with more than one variable to express these statements. a) Every computer science student needs a course in discrete mathematics b) There is a student in this class who owns a personal computer. c) Every student in this class has taken at least one computer science course. d) There is a student in this class who has taken at least one course in computer science. e) Every student in this class has been in every building on campus. f) There is a student in this class who has been in every room of at least one building on campus.  Bonus Express each of these statements using mathematical and logical operators, predicates, and quantifiers, where the domain consists of all integers. a) The sum of two negative integers is negative. b) The difference of two positive integers is not necessarily positive c) The sum of the squares of two integers is greater than or equal to the square of their sum. d) The absolute value of the product of two integers is the product of their absolute value Thank You J