0
$\begingroup$

I have the following statement before it's converted to CNF: p → (s ∨ q). When I initially convert this to a CNF, I get the following: ¬p ∨ (s ∨ q).

I'm wondering if I could use laws of associativity and commutativity to rearrange this statement a bit more while keeping it in the CNF.

Using the associativity law, we can say that ㄱp ∨ s ∨ q is equivalent to s ∨ ㄱp ∨ q.

Using the commutativity law, ㄱp ∨ s ∨ q is equivalent to s ∨ ㄱp ∨ q.

Alternatively, could another way to express this statement above be ㄱs ∨ p ∨ q? If not, what is the correct way to express it? I am trying to conduct a proof by resolution, and my goal right now is to keep the CNF while getting some sort of negation of s. I want to know if this is a valid way of rewriting the original statement.

$\endgroup$

1 Answer 1

0
$\begingroup$

Using the associativity law, we can say that ㄱp ∨ s ∨ q is equivalent to s ∨ ㄱp ∨ q.

I think you meant to say: by the associative law we can drop parentheses from $\neg p \lor (s \lor q)$ and simply get $\neg p \lor s \lor q$

Alternatively, could another way to express this statement above be ㄱs ∨ p ∨ q?

No, that is not equivalent. Consider: $p$ is True and $q$ and $s$ are False. Then $\neg p \lor (s \lor q)$ is False, but $\neg s \lor p \lor q$ is True

Both $\neg p \lor s \lor q$ and $s \lor \neg p \lor q$ (and indeed any rearranegment of these three literals) are CNF's of the original statement. But you're not going to get anything with a $\neg s$ in there.

$\endgroup$
2
  • $\begingroup$ This makes sense. I do have a follow-up question: If I have a statement like "¬a ∨ b", would it be equivalent to "¬b ∨ a"? This would be two valid CNFs for an original implication statement of "a → b"? $\endgroup$ Commented Oct 5, 2020 at 15:55
  • $\begingroup$ @skancharla No. Again, not equivalent. Consider $a$ being true and $b$ being false. Then $a \to b$ is false, $\neg a \lor b$ is also false, but $\neg b \lor a$ is true. $\neg a \lor b$ is equivalent to $a \to b$, and $\neg b \lor a$ is not equivalent to them. $\endgroup$
    – Bram28
    Commented Oct 5, 2020 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .