Ways to write CNF for an implication with disjunction?

2.3k Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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.