Topper Copies

Obtain: pdf and cnf: $f = p \to [(p \to q) \wedge \sim(\sim q \vee \sim p)]$

Kush Motwani, AIR 11, 2023

[ wkt : $p \to q \Rightarrow \sim p \vee q$ ] $\to$ (1)

$\Rightarrow f = p \to [(p \to q) \wedge \sim(\sim q \vee \sim p)]$

$= p \oslash \sim p \vee [(\sim p \vee q) \wedge (p \wedge q)]$

( using (1), and De Morgan's law : $\sim(\sim q \vee \sim p) = p \wedge q$ )

$= \sim p \vee [(\sim p \wedge p \wedge q) \vee (q \wedge p \wedge q)]$

$\Rightarrow$ [ $f = \sim p \vee (p \wedge q)$ ] [ ( $\because \sim p \wedge p = 0$, $q \wedge q = q$ ) ] $\to$ (2)

now: to reduce (2) to pdf : (sum of products form)

$f = [\sim p \wedge (q \vee \sim q)] \vee (p \wedge q)$

$f = (\sim p \wedge q) \vee (\sim p \wedge \sim q) \vee (p \wedge q) \to (3)$

$\hookrightarrow$ SOP form, i.e pdnf

to reduce (3) to cnf (product of sum form)

$f = \sim p \vee (p \wedge q)$

$f = (\sim p \vee q) \to (4)$.

($\because x \vee (\sim x \wedge y) = x \vee y\ \ \forall x,y$).

$\downarrow$

Pos form, i.e cnf

Thus, (3) and (4) give, the required solution