Let p, q, r, s represent the following propositions. p : x in {8, 9, 10, 11, 12} ; q : x is a composite number ; r : x is a perfect square ; s : x is a prime number. The integer x >= 2 which satisfies not((p => q) and (not r or not s)) is ____________.

GATE 2016 · Discrete Mathematics · Propositional Logic · medium

Answer: The unique integer is x = 11.

1. Negate the conjunction: The formula not((p => q) and (not r or not s)) is true exactly when (p => q) and (not r or not s) is false, i.e. when (p => q) is false OR when (not r or not s) is false (so r and s are both true).
2. Make the implication false: We need p true (so x in {8,9,10,11,12}) and q false (x not composite). Among 8,9,10,11,12 only 11 is not composite (it is prime). So x = 11 makes p true and q false, hence p => q false.
3. Confirm x = 11 satisfies the formula: For x = 11: p => q = T => F = false, so (p => q) and (not r or not s) is false, and its negation is true. No other integer x >= 2 works (numbers outside the set make p false, hence p => q true, and then the conjunction can only be broken via the impossible r-and-s case). Thus x = 11.