I need help with conjunctive normal form. Can you give me some tips?
I have following formula. I did the first few steps.
$$ [(p \implies q) \land (r \implies q)] \implies [( \neg q \vee \neg q) \implies ( \neg p \vee \neg r)] $$
- Step one - Deleting arrows by swap $\ p \implies q $ to $\ \neg (p \vee q) $
$$ [ \neg(\neg(p \vee q) \land \neg(r \vee q)) ] \vee [ \neg(\neg q \vee \neg q)) \vee (\neg p \vee \neg r)] $$
Step two - Deleting double negations: $$ [\neg((\neg p \land \neg q) \land (\neg r \land \neg q))] \vee [\neg ((q \land q) \vee \neg (p \land r))] $$
Step three - Using De Morgan's Laws, so now I have following formula: $$ [(p \vee q) \land (\neg r \land \neg q)] \vee [(q∨¬q)∨(¬p∨¬r)] $$
At this moment I don't know what to do next. Can You help me?
First, I would use $\rightarrow$ instead of $\implies$; $p \rightarrow q$ is a logic statement that may or may not be true, depending on the truth-values of $p$ and $q$, but $p \implies q$ is typically understood as a meta-logical statement that says that $p$ logically implies $q$ ... which it does not ... and hence that statement is definitely false.
OK, so let's start with:
$$ [(p \rightarrow q) \land (r \rightarrow q)] \rightarrow [( \neg q \vee \neg q) \rightarrow ( \neg p \vee \neg r)] $$
As you said, we can rewrite any conditional $p \rightarrow q$, but note that the correct equivalence is that $p \rightarrow q \Leftrightarrow \neg p \vee q$, rather than $p \rightarrow q \Leftrightarrow \neg (p \vee q)$, which is what you had: the latter is not true!
OK, so let's use the correct equivalence, so we get:
$$ \neg [(\neg p \vee q) \land (\neg r \vee q)] \vee [\neg ( \neg q \vee \neg q) \vee ( \neg p \vee \neg r)] $$
Now we can do some DeMorgan's:
$$ \neg (\neg p \vee q) \vee \neg (\neg r \vee q) \vee (\neg \neg q \land \neg \neg q) \vee \neg p \vee \neg r $$
(note we can drop the square brackets, since everything is disjuncted together, and by associativity of disjunction, the order in which you disjunct things together doesn't matter. Likewise, we can drop the parentheses from the $( \neg p \vee \neg r)$ at the end)
Some more Demorgan's:
$$ (\neg \neg p \land \neg q) \vee (\neg \neg r \land \neg q) \vee (\neg \neg q \land \neg \neg q) \vee \neg p \vee \neg r $$
And some Double Negations:
$$ (p \land \neg q) \vee (r \land \neg q) \vee (q \land q) \vee \neg p \vee \neg r $$
Idempotence says that $p \land p \Leftrightarrow p$, so:
$$ (p \land \neg q) \vee (r \land \neg q) \vee q \vee \neg p \vee \neg r $$
Reduction says that $p \vee (\neg p \land q) \Leftrightarrow p \vee q$, so:
$$ p \vee r \vee q \vee \neg p \vee \neg r $$
$p \vee \neg p \Leftrightarrow \top$, so:
$$ q \vee \top \vee \top $$
And finally, $p \vee \top \Leftrightarrow \top$, so we get:
$$ \top $$