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