3
$\begingroup$

I have proven using theorems that implication is left distributive over conjunction:

$ x \rightarrow (y \land z) \equiv ( x \rightarrow y ) \land ( x \rightarrow z ) $

Proof:

$ x \rightarrow (y \land z) \\ \equiv \\ \neg x \lor ( y \land z ) \\ \equiv \\ ( \neg x \lor y ) \land ( \neg x \lor z ) \\ \equiv \\ ( x \rightarrow y ) \land ( x \rightarrow z ) $

I have also proved that implication is left distributive over disjunction in a similar way. However, I am now struggling to prove:

  • whether or not conjunction and disjunction are left distributive over implication

    $ x \land ( y \rightarrow z ) \equiv ( x \land y ) \rightarrow ( x \land z ) $

    $ x \lor ( y \rightarrow z ) \equiv ( x \lor y ) \rightarrow ( x \lor z ) $

  • whether or not implication is right distributive over conjunction and disjunction

    $ ( y \land z ) \rightarrow x \equiv ( y \rightarrow x ) \land ( z \rightarrow x ) $ (EDIT: I think I have proven this one)

    $ ( y \lor z ) \rightarrow x \equiv ( y \rightarrow x ) \lor ( z \rightarrow x ) $

I would appreciate any help as to where to get started on these proofs, or what theorems I should be looking at to prove them, as well as any advice on how to prove if one of them is NOT​ distributive (i.e. how do I know that one of the above theorems is false without attempting, and failing, to prove it many, many different ways).

Thank you for any help in advance.

$\endgroup$

2 Answers 2

3
$\begingroup$

How do I know that one of the above statements is false without attempting, and failing, to prove it many, many different ways?

You may simply make a truth table for each of these statements, although that's not the most economic way, it's still one of the most straightforward techniques. Let's take for instance the first one, namely,

$$x \land ( y \to z ) \equiv ( x \land y ) \to ( x \land z ),$$

which we'll call $\small\tt P_1$. We have:

$$ \begin{array}{|c|c|c|c|c|c|c|c|}\hline {} \small \color{green}{x} &\small \color{green}{y} &\small \color{green}{z} &\small y\to z &\small x\land(y\to z) &\small x\land y &\small x\land z &\small (x\land y)\to(x\land z) &\small \tt P_\color{black}{1} \\ \hline {} \small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} \\ \hline \small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} \\ \hline \small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} \\ \hline \small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{royalblue}{1} \\ \hline \small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} \\ \hline \small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} \\ \hline \small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} \\ \hline \small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{#C00}{0} &\small \color{royalblue}{1} &\small \color{#C00}{0} \\ \hline \end{array} $$

Hence $\small\tt P_1$ is certainly not a tautology. The use of a truth table is unnecessary if we observe from the beginning that we do not have an equivalence when $x$ is false. You can do the same for the remaining ones, $$\begin{align} x \lor ( y \to z ) &\equiv ( x \lor y ) \to ( x \lor z ), \\ ( y \lor z ) \to x &\equiv ( y \to x ) \lor ( z \to x ), \end{align}$$ which we will respectively denote as $\small\tt P_2$ and $\small\tt P_3$. You'll see that $\small\tt P_2$ is the only tautology.

Now, to show that this is indeed the case $-$ without relying on a truth table $-$ we'll start with the RHS,

$$\begin{align} (y\to x)\lor(z\to x) & \equiv (\lnot y\lor x)\lor(\lnot z\lor x) \\ & \equiv (\lnot y\lor\lnot z)\lor x \\ & \equiv \lnot(y\land z)\lor x \\ & \equiv (y\land z)\to x. \tag*{$\small\square$} \end{align} $$

$\endgroup$
0
$\begingroup$

Prove of the above equation p -> (q ^ r) <-> (p -> q) ^ (p -> r)

https://i.stack.imgur.com/D7im1.jpg

$\endgroup$

You must log in to answer this question.

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