I'm working with the book "Language, Proof and Logic" and they asked me to make an NNF of this sentence ¬(¬A ∨ ¬B ∨ C). They said that the resulting Sentence won't have any negation signs in it.
Did I make a mistake when translating it from
¬(¬Cube(a) ∨ ¬Larger(a, b) ∨ a ≠ b) to ¬(¬A ∨ ¬B ∨ C)?
and why is
(A ∨ B ∨ ¬C) wrong?
On
You made two, and possibly three, mistakes.
First, $a\neq b$ is short for $\neg a=b$. So, the sentence is really of the form $\neg (\neg A \lor \neg B \lor \color{red}\neg C)$
Second, when applying DeMorgan’s laws, make sure to change the $\lor$ into $\land$ (and vice versa). So, what you get is $A \color{red}\land B \color{red}\land C$
Note: there are indeed no negations in this sentence (and it is in NNF)
Finally, I am not so sure that they want $A \land B \land C$ as your answer …. Wouldn’t they want you to work with the original predicates? In which case the answer would be $Cube(a) \land Larger(a,b) \land a =b$
You can rewrite the formula $\neg (\neg A \vee \neg B \vee C)$ in Negation Normal Form as follows:
$\neg (\neg A \vee \neg B \vee C)$
$\neg \neg A \wedge \neg \neg B \wedge \neg C \:\:\:\:\:\:$ by DeMorgan's Law
$A \wedge B \wedge \neg C \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:$ by double negation elimination
NOTE: if $C$ is "$a \neq b$," then $\neg C$ is "$\neg(a \neq b)$" which is logically equivalent to "$\neg \neg (a=b)"$ and "$a=b$."