Consider the following expressions: i. false ; ii. Q ; iii. true ; iv. P or Q ; v. not Q or P. The number of expressions given above that are logically implied by P and (P => Q) is ___________.

GATE 2016 · Discrete Mathematics · Propositional Logic · medium

Answer: Exactly 4 expressions (ii, iii, iv, v) are logically implied by P and (P => Q).

1. Find when the premise holds: P must be true; with P true, P => Q forces Q true (this is just modus ponens detaching Q). So the premise P and (P => Q) is satisfiable only in the single world P = T, Q = T.
2. Evaluate each expression at P=T, Q=T: i. false = FALSE -> not implied. ii. Q = T -> implied. iii. true = T -> implied. iv. P or Q = T or T = T -> implied. v. not Q or P = F or T = T -> implied.
3. Count the implied expressions: Four expressions (ii, iii, iv, v) are true at the premise's only true-world, so four are logically implied. Expression i is the lone exception.