Is this possible: ( neg X AND Y) OR neg Z <=> (neg X OR neg Z) AND (neg Y OR Z)

I think the following formula is not possible, right? How can I come from the left side to the right? Is there a rule for this transformation I am not aware of or is there an error in my solution?

$$(\neg X \land Y) \lor \neg Z \Leftrightarrow (\neg X \lor \neg Z) \land (\neg Y \lor Z)$$

To apply the distributive rule it should result in: $$(\neg X \land Y) \lor \neg Z \Leftrightarrow (\neg X \lor \neg Z) \land ( Y \lor \neg Z)$$

Thanks in advance.

• Counterexample to first: X is false, Y is true, Z is false. – Daniel Schepler May 31 '18 at 23:07
• Would it change if the left formula is without parenthesis  $$\neg X \land Y \lor \neg Z \Leftrightarrow (\neg X \lor \neg Z) \land (\neg Y \lor Z)$$ Would this be possible? I think also not, right? – user3352632 May 31 '18 at 23:16

2 Answers

The second formula is indeed correct. The first one was mixing up the negations in developing the second clause.

To analyze it: For the second clause in your solution to evaluate to true, no matter what truth-value $Z$ takes, at least one of $\{X,Y\}$ has to be assigned false. Knowing this, let true be assigned to $X$, $Y$ and $Z$. Then the right-hand side cannot evaluate to true, but the left-hand side does. So they certainly cannot be truth-value-equivalent.

Furthermore, knowing this, there can be no deduction from the left- to the right-hand side, by whatever logical means, since deductions preserve the truth value of a statement, i.e. true statements remain true under reformulation by logical rules. By the above mentioned analysis, if there was such a deduction of the LHS of your solution to the RHS, this rule would be violated in your case.

• Thanks for your explanation. It the LHS is without parenthesis, would the equivalent to the RHS then possible? – user3352632 May 31 '18 at 23:18
• The first formula would not be well defined in the first place, if there were no parentheses. Putting the parentheses around "Y or not Z" in the first clause of your solution would also not work, since that can be checked for example for the assignment X false, Y true, Z false. – Peter-Max Jun 2 '18 at 10:45

Remember the distributive laws $$p\vee (q\wedge r)\equiv (p\vee q)\wedge(p\vee r)$$

$$p\wedge (q\vee r)\equiv (p\wedge q)\vee(p\wedge r)$$

The first formula which you have is not possible as per the laws of distribution.

The second formula which you have is correct. For the second law we can compare it to the distributive law. When we compare we get, $$p=\neg Z, q=\neg X, r=Y$$ $$\neg Z\vee(\neg X\wedge Y)\equiv(\neg Z \vee\neg X)\wedge(\neg Z \vee Y)$$

• Thanks for your explanation. It the LHS is without parenthesis, would the equivalent to the RHS then possible? – user3352632 May 31 '18 at 23:18
• I did not understand your question. can you tell briefly – tien lee May 31 '18 at 23:22
• Would it change if the left formula is without parenthesis as this one: ¬X∧Y∨¬Z⇔(¬X∨¬Z)∧(¬Y∨Z) Would this be possible? I think also not, right? – user3352632 May 31 '18 at 23:31
• yes, you are right. without parentheses on the left side it is not possible and would not be equal to RHS – tien lee May 31 '18 at 23:39
• Okay, thanks for your confirmation. So the first formula / statement in my post is completly incorrect. – user3352632 May 31 '18 at 23:41