# Simple Logic Question

I've very little understanding in logic, how can I simply show that this is true:

$$((X \wedge \neg Y)\Rightarrow \neg Z) \Leftrightarrow ((X\wedge Z)\Rightarrow Y)$$

Thanks a lot.

-
One way would be a truth table with eight rows. –  Michael Hardy Apr 1 '12 at 17:29
you can simpely use the The truth table. –  Abdelmajid Khadari Apr 1 '12 at 17:30

One way would be a truth table with eight rows. $$\begin{array}{|c|c|c|c|} \hline X & Y & Z & ((X \wedge \neg Y)\Rightarrow \neg Z) \Leftrightarrow ((X\wedge Z)\Rightarrow Y) \\ \hline T & T & T & \\ T & T & f & \\ T & f & T & \\ f & T & T & \\ T & f & f & \\ f & T & f & \\ f & f & T & \\ f & f & f & \\ \hline \end{array}$$ Fill in the eight blanks in the last column.

-
great, thanks :) –  Anonymous Apr 1 '12 at 17:42

You could use "natural reasoning": suppose the implication on the right of the $\Leftrightarrow$ holds, and we want to show the left implication. So assume $X$ and $\neg Y$ holds. Then $Z$ cannot hold because $X \wedge Z$ implies $Y$ and we have $\neg Y$, so $\neg Z$ holds and we have shown the left implication from the right hand one. The other half is similar. All this can be formalized in a deduction proof in some more formal scheme, but this kind of reasoning helps me to understand what's going on.

Of course, making a truth table will also work.

-

hint: $X \Rightarrow Y \Leftrightarrow \neg X \lor Y$ is enough.

(well if you know that $\neg (X \wedge Y)= \neg X \lor \neg Y$ and the $\neg$ operations of course...)

-

proof:

by the defintion $p\Rightarrow q \Leftrightarrow \neg p \lor q$
then we have

$((X \wedge \neg Y)\Rightarrow \neg Z) \Leftrightarrow \neg (X \wedge \neg Y)\lor \neg Z$

we have by Morgan's: $\neg (X \wedge \neg Y)\lor \neg Z \Leftrightarrow \neg X \lor Y\lor \neg Z$

then we have $((X \wedge \neg Y)\Rightarrow \neg Z)\Leftrightarrow \neg X\lor\neg Z\lor Y$

and finely we have also by Morgan's: $((X \wedge \neg Y)\Rightarrow \neg Z)\Leftrightarrow \neg (X \wedge Z)\lor Y$

we know that $\neg (X \wedge Z)\lor Y \Leftrightarrow (X \wedge Z)\Rightarrow Y$

then we have:

$((X \wedge \neg Y)\Rightarrow \neg Z) \Leftrightarrow ((X\wedge Z)\Rightarrow Y)$

-

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

$\Leftrightarrow(x \land z) \Rightarrow y$

-
I'd have writte a comment that by $\Rightarrow$ you mean "if...then..." but by $\rightarrow$ you mean that from one thing you deduce another (if that's what you mean). –  Michael Hardy Apr 1 '12 at 21:38

You want to show that $$((X \wedge \neg Y)\Rightarrow \neg Z) \Leftrightarrow ((X\wedge Z)\Rightarrow Y).$$ It is hard to know without context what "show" might mean. For example, we could be working with a specific set of axioms. Since an axiom system was not specified, I will assume we are looking for a precise but not axiom-based argument.

Truth tables are nicely mechanical, so they are a very good way to verify the assertion. Below we give a "rhetorical" version of the truth table argument. It probably shows that truth tables would have been a better choice! However, it is important to be able to scan a sentence and understand under what conditions that sentence is true.

We want to show that (a) if $(X \wedge \neg Y)\Rightarrow \neg Z$ is true then $(X\wedge Z)\Rightarrow Y$ is true and (b) if $(X\wedge Z)\Rightarrow Y$ is true then $(X \wedge \neg Y)\Rightarrow \neg Z$ is true.

We deal with (a). There are two ways for $(X \wedge \neg Y)\Rightarrow \neg Z$ to be true: (i) if $\neg Z$ is true or (ii) if $X \wedge \neg Y$ is false. In case (i), $Z$ is false, which implies that $X\wedge Z$ is false, which implies that $(X\wedge Z)\Rightarrow Y$ is true. In case (ii), $X$ is false or $Y$ is true. If $X$ is false, then $X\land Z$ is false, and as in case (i), $(X\wedge Z)\Rightarrow Y$ is true. If $Y$ is true, then automatically $(X\wedge Z)\Rightarrow Y$ is true. We now have completed proving (a).

The proof for the direction (b) is very similar.

Another way: We can also use (Boolean) algebraic manipulation to show that each side is logically equivalent to $(\neg X \lor \neg Z)\lor Y$.

Note that $(X \wedge \neg Y)\Rightarrow \neg Z$ is equivalent to $\neg(X\wedge \neg Y)\lor \neg Z$, which is equivalent to $(\neg X \lor Y)\lor \neg Z$, which is equivalent to $(\neg X \lor \neg Z)\lor Y$.

Note also that $(X\wedge Z)\Rightarrow Y$ is equivalent to $\neg(X\wedge Z)\lor Y$, which is equivalent to $(\neg X\lor \neg Z)\lor Y$. This completes the argument.

-

A simple way to work with exercises like these (unless trying to formally prove them in some formal system), lies in seeing what happens if one variable is true, and then seeing what happens if that same variable is false. Then you can use logical equations (which you can derive and check quickly from truth tables for the basic connectives) like

(0 $\land$ y)=0

(0 $\implies$ y)=1

(1 $\land$ y)=y

(x $\implies$ 0)=$\lnot$x

(1$\implies$y)=y

(x$\implies$1)=1.

These ones should suffice for this exercise.

-