The binary operation [] is defined as follows. P=T,Q=T gives P[]Q=T; P=T,Q=F gives P[]Q=T; P=F,Q=T gives P[]Q=F; P=F,Q=F gives P[]Q=T. Which one of the following is equivalent to P v Q? A. (not Q) [] (not P) B. P [] (not Q) C. (not P) [] Q D. (not P) [] (not Q)

GATE 2009 · Discrete Mathematics · Propositional Logic · easy

Answer: P [] (not Q) = P or Q, so option B is equivalent to P v Q.

1. Decode the operation from the table: P[]Q is FALSE in exactly one row, P=F and Q=T, i.e. when (not P) and Q are both true. So P[]Q = not((not P) and Q). By De Morgan's law this is (not(not P)) or (not Q) = P or (not Q). Hence the operation is X[]Y = X or (not Y).
2. Test option B: Substitute X=P and Y=(not Q) into X[]Y = X or (not Y): P[](not Q) = P or not(not Q) = P or Q. This is exactly P v Q, so option B is equivalent. (Checking the rest: A gives not Q or P = P or not Q; C gives not P or not Q; D gives not P or Q. None of these equals P v Q.)