TIFR CSE 2016 | Part B | Question: 1

Question

A Boolean formula is said to be a $tautology$ if it evaluates to TRUE for all assignments to its variables. Which one of the following is NOT a tautology?

• A. $(( p \vee q) \wedge (r \vee s)) \Rightarrow (( p \wedge r) \vee q \vee s)$
• B. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow (q \vee s)$
• C. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( r \vee q \vee s)$
• D. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q \vee s)$
• E. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q)$

Comments

Why not E . suppose p=q=1 and r=s=0 then p or q =1 and r or s =0 . 1 and 0 =0 but p or q =1 LHS = 0 and RHS = 1.

Answer 1

in B) option if we try with value as p=1, r=1 , q=s=0;

then LHS evaluates to 1 and RHS evaluates to 0
There ans is B.