GATE CSE 2002 | Question: 5b

Question

Determine whether each of the following is a tautology, a contradiction, or neither ("$\lor$" is disjunction, "$\land$" is conjunction, "$\rightarrow$" is implication, "$\neg$" is negation, and "$\leftrightarrow$" is biconditional (if and only if).

1. $A \leftrightarrow (A \lor A)$
2. $(A \lor B) \rightarrow B$
3. $A \land (\neg (A \lor B))$

Comments

Option A is Always tautology

Answer 1

This can be solved by Truth table. But there is something else which can be done quickly. See what each formula means:

1.  A↔(A∨A) It says if A then (A or A) and if (A or A) then A. Always a tautology

2.  (A∨B)→B If A or B then B. No guarantee that if only A is true, B need to be true. Hence neither tautology nor contradiction

3.  A∧(¬(A∨B)) When A is true ¬(A∨B) will be false. So, this formula is a contradiction

Comments

Okay. Probably browser in symbian doesnt support latex.

---

 Deepak Poonia, please verify this, and provide the relation between tautology, contradiction contingency, and satisfiable 

1. it is  a tautology, not a contradiction, not a contingency
2. Not a tautology, not a contradiction, it is contingency.
3. Not a tautology, it is contradiction, not contingency.

.

 

---

contingency can be true (satisfiable)

Answer 2

We can also solve it by the properties.

1.) A <--> ( A v A)

A <--> A (Since A + A is A.)

AA + A'A' ( Since A <--> B is AB +A'B')

Therefore A + A' is 1. Which is a Tautology.

2.) (A v B) --> B

A'B' + B ( Since A-->B is A' + B)

A' + B ( By law of Absorption.)

Hence it is neither Tautology nor Contradiction and Hence Contingency.

3.) A ∧ ( ¬ ( A v B))

Which can be written as

A.(A + B)'

A.(A'B') ( By de-morgan's Law)

A.A'B' = 0.

Hence it is a Contradiction.

• A.