Nested quantifiers

Nested quantifiers

1. وہ آے گھر میں ہمارے خدا کی قدرت ہے کبھی ہم انکو کبھی اپنے گھر کو دیکھتے ہیں Slides-4

2. It means at any time either I see my home or my friend. It also concludes that I do not see somewhere else and I do not see both at a time. Suppose I have many homes and many friends but at least one friend is special one. Set of homes and friends are denoted by H and F, respectively. Look(x) = Having a look at x  

3. Exercise How to modify the formula in previous slide if I say we are talking about the home in which friend is there? Write a logical expression for “All the time if door is closed then I am not inside my cabin”. Where the propositions p and q are “Door is closed” and “I am inside my cabin”. “All the time if door is closed then I am not inside my cabin otherwise I am inside”.

4. Excecise Translate these statements into English, where C(x) is “ x is a comedian” and F(x) is “ x is funny” and the domain consists of all people. a) ∀ x(C(x) → F(x)) b) ∀ x(C(x) ∧ F(x)) c) ∃ x(C(x) → F(x)) d) ∃ x(C(x) ∧ F(x))

5. Exercise P(x): “x is a professor” I(x): “x is ignorant” V(x): “x is vain” Express the following statements using quantifiers, logical connectives and P(x), I(x), and V(x ), where the universe is the set of all people. a) No professors are ignorant. b) All ignorant people are vain. c) No professors are vain

6. Nested Quantifiers  xy P(x, y) “For all x, there exists a y such that P( x,y )”. Example:  xy ( x+y == 0 ) where x and y are integers  xy P( x,y ) There exists an x such that for all y P( x,y ) is true”  xy (x*y == 0)

7. Meanings of multiple quantifiers  x  y P( x,y )  x  y P( x,y )  x  y P( x,y )  x  y P( x,y ) P( x,y ) true for all x, y pairs. For every value of x we can find a (possibly different) y so that P( x,y ) is true. P( x,y ) true for at least one x, y pair. There is at least one x for which P(x,y) is always true. quantification order is not commutative. Suppose P(x,y) = “x’s favorite class is y.”

8. Example Let S be the set of students, i.e., {s1, s2, s3, …} and P be the set of sports {hockey, cricket, badminton, tennis, chess} Let Q ( x,y ):= “x plays y” be a predicate which is true if x plays y otherwise false . Then  x  y Q( x,y ) means every student plays each game

9.  x  y Q( x,y ) There is at least one student from S who plays at least one game from the set P.  x  y Q( x,y ) All students play at least one game.  x  y Q( x,y ) There is at least one student who plays all games.

10. Exercise Let M(x), F(x), E(x) and S( x,y ) be the statements for “x is a male”, “x is a female”, “x is employee of COMSATS” and “x and y are spouse”, respectively. Write a logical formula for “There is at least one couple in employees of COMSATS and one of them is male and other is female”.

11. Bound and free variables A variable is bound if it is known or quantified. Otherwise, it is free. Examples: P( x ) x is free P(5) x is bound to 5  x P( x ) x is bound by quantifier Reminder: in a proposition, all variables must be bound.