virtualgate's picture

Predicates and Quantifiers

Predicates and quantifiers

Quantifiers: 
∀x P(x) ≡ P(x1) ∧ P(x1) ∧ P(x1) ∧ P(x1) ∧.....P(xn)
∃x P(x) ≡ P(x1) ∨ P(x1) ∨ P(x1) ∨ P(x1) ∨.....P(xn)

Statement When True ? When False ?
∀x P(x) P(x) is true for every x There is an x for which P(x) is false 
∃x P(x) There is an x for which P(x) is true. P(x) is false for every x

Uniqueness quantifier

∃! x P(x) ≡ There exists a unique x such that P(x) is true.
De Morgan's Laws for Quantifiers:
¬∃x P(x) = ∀x ¬P(x)
¬∀x P(x) = ∃x ¬P(x)
Quantifications of two variables:

Contributor's Info

Created: Edited:
0Comment
First Order logic Part1 [Learn How to write First order logic statements]
Content covered: 

Learn How to write First order logic statements

More Less
2Comments
First Order Logic Part2 [ GATE PROBLEMS ON CONVERTING INTO FIRST ORDER]
Content covered: 

GATE PROBLEMS ON CONVERTING INTO FIRST ORDER

More Less
0Comment

  • This quiz contains 5 questions on the topic Predicates and quantifiers
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate
Example for first order logic

Example1:

For a person p, let w(p), A(p,y), L(p) and J(p) denote that p is a woman, p admires y, p is a lawyer and p is a judge respectively. Which of the following is the correct translation in first order logic of the sentence: "All woman who are lawyers admire some judge"?

A) ∀x:[(w(x)ΛL(x))⇒(∃y:(J(y)Λw(y)ΛA(x,y)))]

B) ∀x:[(w(x)⇒L(x))⇒(∃y:(J(y)ΛA(x,y)))]

C) ∀x∀y:[(w(x)ΛL(x))⇒(J(y)ΛA(x,y))]

D) ∃y∀x:[(w(x)ΛL(x))⇒(J(y)ΛA(x,y))]

E) ∀x:[(w(x)ΛL(x))⇒(∃y:(J(y)ΛA(x,y)))]

 

 

Solution:

 

Just translating to English:

 

A) Every women who is a lawyer admires some women judge.

B) If a person being women implies she is a lawyer then she admires some judge. OR If a person is not women or is a lawyer he/she admires some judge.

C) Every women who is a lawyer admires every judge.

D) There is some judge who is admired by every women lawyer.

E) Every women lawyer admire some judge. 

 

So, option (E) is the answer. 

 

Example 2:

Which of the following is NOT necessarily true? { Notation: The symbol ''¬''notes negation; P(x,y) means that for given xx and yy, the property P(x,y) is true }.

A) (∀x∀yP(x,y))⇒(∀y∀xP(x,y))

B) (∀x∃y¬P(x,y))⇒¬(∃x∀yP(x,y))

C) (∃x∃yP(x,y))⇒(∃y∃xP(x,y))

D) (∃x∀yP(x,y))⇒(∀y∃xP(x,y))

E) (∀x∃yP(x,y))⇒(∃y∀xP(x,y))

 

 

Solution:

 

Option E is not necessarily true.

 

 

Example 3:

 

Consider the first-order logic sentence F:∀x(∃yR(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by FF?

∃y(∃xR(x,y))

∃y(∀xR(x,y))

∀y(∃xR(x,y))

¬∃x(∀y¬R(x,y))

A) IV only

B) I and IV only

C) II only

D) II and III only

 

Solution:

option B is true

 

1st Method: F:∀x(∃yR(x,y))

Take option 4: ¬∃x(∀y¬R(x,y))

≡∀x(∃yR(x,y)) ((Since we know that ¬∀x≡∃x And  ¬∃x=∀x)

 

 

Example 4:

 

Which one of the following well-formed formulae in predicate calculus is NOT valid ?

A) (∀xp(x)⟹∀xq(x))⟹(∃x¬p(x)∨∀xq(x))

B) (∃xp(x)∨∃xq(x))⟹∃x(p(x)∨q(x))

C) ∃x(p(x)∧q(x))⟹(∃xp(x)∧∃xq(x))

D) ∀x(p(x)∨q(x))⟹(∀xp(x)∨∀xq(x))

 

Solution:

 

Here, (D) is not valid 

Let me prove by an example 

What (D) is saying here is: 

For all x ( x is even no or x is odd no ) ⟹ For all x( x is even no ) or For all x ( x is odd no) 

OR 

If every x is either even or odd, then every x must be even or every x must be odd. 

If our domain is the set of natural numbers LHS is true but RHS is false as not all natural numbers are even or odd. 
 

Contributor's Info

Created:
0Comment

  • This quiz contains 10 questions on the topic First order logic
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate
Souradip Guha @souradipguha 1 Sep 2017 12:21 am

Check the last few examples on Nested qualifiers 

Pages