3
$\begingroup$

Questions from section A.1. (reading this book on my own / self-studying, not a student, this is not homework):

Edit: Apparently I had misinterpreted some or/and stuff so I am redoing my questions now:

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $X$ is false, $Y$ is false. Have you now demonstrated that $X$ and $Y$ are logically equivalent? Explain.

I believe this is saying, $(X \rightarrow Y) \land (\lnot X \rightarrow \lnot Y)$ which reduces to $(X \land Y) \lor (\lnot X \land \lnot Y)$, and this is the definition of "if and only if", so yes, they are logically equivalent.

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $Y$ is false, then $X$ is false. Have you now demonstrated that $X$ is true if and only if $Y$ is true? Explain.

$(X \rightarrow Y) \land (\lnot Y \rightarrow \lnot X)$, which reduces to $\lnot X \lor Y$, or just $X \rightarrow Y$ which is not the same as if-and-only-if.

Suppose that you know that $X$ is true if and only if $Y$ is true, and you know that $Y$ is true if and only if $Z$ is true. Is this enough to show that $X, Y, Z$ are all logically equivalent? Explain.

I think so? We know $X$ is logically equivalent to $Y$, and $Y$ is logically equivalent to $Z$, and by transitive property, $X$ is logically equivalent to $Z$, so they're all logically equivalent. I'm not sure if I am "allowed" to just invoke transitive property like that or if I have to show that it even applies here.

Suppose you know that whenever $X$ is true, then $Y$ is true; that whenever $Y$ is true, then $Z$ is true; and whenever $Z$ is true, then $X$ is true. Is this enough to show that $X, Y, Z$ are all logically equivalent? Explain.

$(X \rightarrow Y) \land (Y \rightarrow Z) \land (Z \rightarrow X)$, right? So by transitive property again, we have $(X \rightarrow Z) \land (Z \rightarrow X)$ so $X$ and $Z$ are logically equivalent, and similar for the other two combinations.

$\endgroup$
1
  • $\begingroup$ it says '$X\rightarrow Y$ and $\neg X\rightarrow\neg Y$' not or. $\endgroup$ – Alvin Lepik Aug 26 '18 at 15:49
1
$\begingroup$
  1. Yes, you have shown equivalence since you have $$X\rightarrow Y\ \&\ Y\rightarrow X \equiv X\leftrightarrow Y. $$
  2. No. You have shown $$X\rightarrow Y\ \&\ \neg Y\rightarrow\neg X \equiv X\rightarrow Y\ \&\ X\rightarrow Y\equiv X\rightarrow Y. $$
  3. Yes, since the implication operation is transitive.
  4. Yes. Again, transitivity of implication. We have $$X\rightarrow Y\ \&\ Y\rightarrow Z\ \&\ Z\rightarrow X. $$ The statements $X,Y,Z$ are pairwise equivalent using the identity given at 1. since $$X\rightarrow Y\ \&\ (Y\rightarrow Z\ \&\ Z\rightarrow X) \equiv X\rightarrow Y\ \&\ Y\rightarrow X\equiv X\leftrightarrow Y\\ (X\rightarrow Y\ \&\ Y\rightarrow Z)\ \&\ Z\rightarrow X \equiv X\rightarrow Z\ \&\ Z\rightarrow X\equiv X\leftrightarrow Z\\ Y\rightarrow Z\ \&\ (Z\rightarrow X\ \&\ X\rightarrow Y) \equiv Y\rightarrow Z\ \&\ Z\rightarrow Y\equiv Y\leftrightarrow Z $$
$\endgroup$
0
0
$\begingroup$

Yes you have. The contrapositive of $p\implies q$ is $\lnot q\implies \lnot p$. They are equivalent.

So you have proved both directions: $X\implies Y$ and $Y\implies X$.

Secondly, no. As just pointed out, contrapositives are equivalent.

Thirdly, equivalence is transitive. So yes.

Finally, yes. This is a good way of proving several statements are equivalent...

$\endgroup$
0
$\begingroup$

So... it sounds to me that you have defined $X$ and $Y$ are "equivalent" to mean $X$ is true if and only if $Y$ is true. ANd to show that you must show two things:

i) $X\implies Y$ and ii) $Y \implies X$.

So for question 1) you are told $X \implies Y$ (so that's i); all you need to show is ii)) and the $\lnot X \implies \lnot Y$.

So you have to show that $(\lnot X \implies \lnot Y)$ implies that $Y \implies X$. This is the basic contrapositive and you can cite it as a proposition that should have be proven early on. But basically, if we assume $Y$ we can either have $X$ or $\lnot X$. If $\lnot X$ we'd have $\lnot Y$ which would make $Y$ impossible. So if $\lnot X \implies \lnot Y$ we can conclude ii) $Y \implies X$.

(So from now on. If ever you need to prove $a \implies b$ you can always choose to show $\lnot b \implies \lnot a$ instead. You have proven those statements are logically equivalent.)

For question 2) you are told $X\implies Y$ (so that is i); have to show whether ii) must be true or if it is possible for ii) to be false). ANd you are told $\lnot Y \implies \lnot X$. We need to show whether this does or does not imply ii) $Y \implies X$.

It does not. It is perfectly possible to have $Y$ true but $X$ not true. This satisfies i) $X \implies Y$ because a) $\lnot X$ means we don't ever get started on the hypothesis and b) $Y$ is not a contradictory conclusion. And this satisfies $\lnot Y \implies \lnot X$ because as $Y$, we never even get started on the hypothesis.

But this clearly violates ii) $Y \implies X$. So know those are not equvivalent.

For question 3) we know $X \iff Y$ and $Y \iff Z$ and we want to show $X \iff Z$.

So we have to prove two things i) $X \implies Z$ and ii) $Z \implies X$.

So... let's show them... on after the other.

i) Does $X \implies Z$?

Well Assume $X$. Then we know $X \iff Y$ so we know $Y$. And we know $Y \iff Z$ therefore we know $Z$. So $X \implies Z$.

So yes.

ii)Does $Z \implies X$?

Well Assume $Z$. Then we know $Y \iff Z$ so we know $Y$. And we know $X \iff Y$ therefore we know $X$. So $Z \implies X$.

So yes.

And that's it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.