1
$\begingroup$

I show that $x \Rightarrow z$ and $y \Rightarrow t$ are true.

Is $x \vee y \Rightarrow z \vee t$ then true?

  • 1
    I see that the answers here use truth tables or otherwise implicitly use the law of the e$x$cluded middle. This is more general than that though, and still holds in constructive logic.2011-10-03

3 Answers 3

0

Since $A \Rightarrow B \Leftrightarrow \lnot A \lor B $ we may write :

$\lnot(x \lor y) \lor (z \lor t)$

$(\lnot(x \lor y) \lor z)\lor t$

$((\lnot x \land \lnot y)\lor z)\lor t$

$((\lnot x \lor z)\land(\lnot y \lor z))\lor t$

$((x \Rightarrow z)\land(\lnot y\lor z))\lor t$

$(\top \land (\lnot y\lor z))\lor t$

$(\lnot y\lor z)\lor t$

$(\lnot y \lor t) \lor z$

$(y \Rightarrow t)\lor z$

$\top \lor z$

$\top$

2

Instead of a brute force approach, one can prove the claim.

Assume $(x\Rightarrow z)\land (y\Rightarrow t)$. Since $(x\lor y)\Rightarrow(z\lor t)$ true if and only if whenever $(x\lor y)$ is valuated as true, then also $(z\lor t)$ does.

$x\lor y$ is true if and only if $x$ is true or $y$ is true.

  • If $x$ is true, then $z$ is true, therefore $t\lor z$ is true.
  • If $y$ is true, then $t$ is true, and thus $t\lor z$ is true.

Either way, if $x\lor y$ is true then $z\lor t$ is true as needed.

(Of course this can formalized completely using the $\operatorname{val}$ function and assignment of truth values for $x,y,z,t$.)

0

Yes, here is the truth table:

enter image description here

(Built by the java applet here)