## 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.