Conjunctive Normal Form Conversion

249 Views Asked by At

The question is to turn the following formula into Conjunctive Normal Form:

$\rm \neg [(p \vee q) \wedge (r \to s)] \to p \wedge \neg q \wedge \neg s$

I have come up to here:

$\rm \neg [(p \vee q) \wedge (r \to s)] \to (p \wedge \neg q \wedge \neg s) \\[2ex] \rm \neg [(p \vee q) \wedge (\neg r \vee s)] \to (p \wedge \neg q \wedge \neg s) \\[2ex] \rm \neg \neg [(p \vee q) \wedge (\neg r \vee s)] \vee [p \wedge \neg q \wedge \neg s] \\[2ex] \rm [(p \vee q) \wedge (\neg r \vee s)] \vee [p \wedge \neg q \wedge \neg s] \\[2ex] \rm [(p \vee q) \vee (p \wedge \neg q \wedge \neg s)] \wedge [(\neg r \vee s) \vee (p \wedge \neg q \wedge \neg s)] $

From here forward, I have no clue what the next step could be. Any hints or guidance would be very useful. Thanks

EDIT: I've worked further ahead, but I am not sure if this would be correct as I have a gut feeling that I made an error in some of the steps

$\rm \neg [(p \vee q) \wedge (r \to s)] \to (p \wedge \neg q \wedge \neg s) \\[2ex] \rm \neg [(p \vee q) \wedge (\neg r \vee s)] \to (p \wedge \neg q \wedge \neg s) \\[2ex] \rm \neg \neg [(p \vee q) \wedge (\neg r \vee s)] \vee [p \wedge \neg q \wedge \neg s] \\[2ex] \rm [(p \vee q) \wedge (\neg r \vee s)] \vee [p \wedge \neg q \wedge \neg s] \\[2ex] \rm [(p \vee q) \vee (p \wedge \neg q \wedge \neg s)] \wedge [(\neg r \vee s) \vee (p \wedge \neg q \wedge \neg s)] \\[2ex] \rm [[(p \wedge p) \vee (p \wedge q)] \wedge \neg q \wedge \neg s] \wedge [(\neg s \wedge s) \vee (\neg s \wedge \neg r)] \wedge p \wedge \neg q] \\[2ex] \rm [[p \vee (p \wedge q)] \wedge \neg q \wedge \neg s] \wedge [(\neg s \wedge \neg r) \wedge p \wedge \neg q] \\[2ex] \rm p \wedge \neg q \wedge \neg s \wedge \neg s \wedge \neg r \wedge p \wedge \neg q \\[2ex] \rm p \wedge \neg q \wedge \neg s \wedge \neg r \wedge p \wedge \neg q \\[2ex] \rm p \wedge \neg q \wedge \neg s \wedge \neg r$

1

There are 1 best solutions below

0
On

Let's see: $\rm \neg [(p \vee q) \wedge (r \to s)] \to (p \wedge \neg q \wedge \neg s) \\[2ex] \rm \neg [(p \vee q) \wedge (\neg r \vee s)] \to (p \wedge \neg q \wedge \neg s) \\[2ex] \rm \neg \neg [(p \vee q) \wedge (\neg r \vee s)] \vee [p \wedge \neg q \wedge \neg s] \\[2ex] \rm [(p \vee q) \wedge (\neg r \vee s)] \vee [p \wedge \neg q \wedge \neg s] \\[2ex] \rm [(p \vee q) \vee (p \wedge \neg q \wedge \neg s)] \wedge [(\neg r \vee s) \vee (p \wedge \neg q \wedge \neg s)] \\[2ex] \text{That's okay up till here, then you went horribly wrong.} \\[2ex]\require{cancel} \rm \xcancel{[[(p \wedge p) \vee (p \wedge q)] \wedge \neg q \wedge \neg s] \wedge [(\neg s \wedge s) \vee (\neg s \wedge \neg r)] \wedge p \wedge \neg q]} \\[2ex]\text{The next few steps should be:} \\[2ex] \rm [(p \vee q \vee p) \wedge (p \vee q \vee \neg q) \wedge (p \vee q \vee \neg s)] \wedge [(\neg r \vee s \vee p) \wedge (\neg r \vee s \vee \neg q) \wedge (\neg r \vee s \vee \neg s)] \\[2ex] \rm [(p \vee q) \wedge \top \wedge (p \vee q \vee \neg s)] \wedge [(\neg r \vee s \vee p) \wedge (\neg r \vee s \vee \neg q) \wedge \top] \\[2ex] \rm (p \vee q) \wedge [(\neg r \vee s) \vee (p \wedge \neg q)] $

Can you finish from here?