Negation in implies

134 Views Asked by At

$$(B(x) \lor B(y)) \implies \neg B(z)$$

Translated into English, it means these equivalent English sentences:

  1. If either $B(x)$ or $B(y)$ is true, then $B(z)$ is false
  2. If $B(z)$ is true, then neither $B(x)$ nor $B(y)$ are true.

What is the explanation for the 2nd statement?

1

There are 1 best solutions below

0
On BEST ANSWER

The only circumstance in which the formula $p\implies q$ is false is when $p$ is true but $q$ is false. I.e., it is equivalent to the formulas $\lnot p\lor q$ and $\lnot(p\land\lnot q)$. Using these equivalences, it’s not hard to see that it’s also equivalent to the contrapositive $\lnot q\implies\lnot p$. So, if $q$ is false, that is, if $\lnot q$ is true, then $p$ must also be false.

Your formula is thus equivalent to $B(z)\implies\lnot(B(x)\lor B(y))$. The right-hand side of this is equivalent to $\lnot B(x)\land\lnot B(y)$ (de Morgan’s law), from which the second statement follows.