Chapter - 2, Quantificational Logic

Section - 2.2 - Equivalences Involving Quantifiers


Summary

  • Equivalances:
    • .
    • .
  • means P(x) is true for exactly one value of x. It is equivalent to
    .
  • Bounded Quantifiers:
    • .
    • .
  • Similar to negation equivalances( in first point), Equivalences for Bounded Quantifiers:
    • .
    • .
  • If then:
    • is always false irrespective of P(x).
    • is true irrespective of P(x).
  • Universal Quantifiers distributes over conjunction i.e. . But Universal Quantifiers does not distributes over disjunction.
  • Existential Quantifier distributes over disjunction but does not distributes over conjunction.

Soln1

(a)
where means is maths major,
and means is a friend of ,
and means needs help in homework.

Negation of the above statement:







There exists a maths major and all of his friends don’t need help in their homework.

(b)
where means is the roommate of ,
and means likes .

Negation of the above statement:







There exists someone whose all roommates likes atleast one person.

(c) Required statement is:




(d) Required statement is:






Soln2

(a) .

Negation of above statement:





.

where means is a freshman.
and means and are roommates.

(b)

Negation of above statement:




Either there exists someone who does not like anyone or there exists someone who likes everyone.

(c) .

This is equivalent to:

.

Negation of the above statement:






There exists an a in A such that for all values of b in B, either a is in C and b is not in C, or a is not in C and b is in C.

(d) Required statement is:





Soln3

(a) All possible values of x are 0,1,2,3,4,5,6. It can be easily verified that there exists a,b and c such that for all possible values of x. Thus statement is True.

(b) False. x has two possible values 1 and 7.

(c) True. x has two values -1 and 9. But as x is Natural number. Thus only x has one posssible value 9.

(d) True. x = 9 and y = 9.


Soln4

Given: .

To Prove: .

Putting in the given equivalence:

Taking negation on both sides:


Hence Proved.


Soln5

To Prove: is equivalent to .

LHS:




Hence Proved.


Soln6

To Prove is equivalent to .

Taking LHS:






Hence Proved.


Soln7

To Prove is equivalent to .

Starting from LHS



Hence Proved.


Soln8

To Prove: is equivalent to

Starting from LHS:





Applying reverse distributive law:




Hence Proved.


Soln9

Statement is not equivalent to .

Assigning , if x is even.
and , if x is odd.

Lets have Universe as all Natural Numbers.

Clearly is true as Every number is either even or odd.
But is not true. A neither all numbers are even not all numbers are odd.


Soln10

(a)


Using Law of distribution in reverse:


Hence Proved.

(b)

is not equivalent to .

If A and B are disjoint set, then clearly RHS will be false as . But even in this case for some values of x LHS can be true.


Soln11

is equivalent to

Also,
No elements exist in the set. Thus it is equivalent to:




Thus both are same.


Soln12

(a) There is exactly one student who is taught by x.

(b) There exists atleast one teacher having exactly one student.

(c) There is exactly one teacher having at-least one student.

(d) There atleast exist one student having exactly one teacher.

(e) There is only one teacher having only one student.

(f) There is exactly one teacher having only one student.

Clearly (e) and (f) are same.