A.1
\(X\implies Y\) (Y is true if X is true) is equivalent to \(\lnot X\lor Y\) or \(\lnot(X\land\lnot Y)\).
The truth table of logical implication
| \(X\) | \(Y\) | \(X\implies Y\) | \(\lnot X\) | \(\lnot X\lor Y\) |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Exercise
-
A.1.1. What is the negation of the statement "either x is true, or y is true, but not both"?
- Our Answer A.1.1
A.1.2
What is the negation of the statement "X is true if and only if Y is true"? (There may be multiple ways to phrase this negation).
$$ X\implies Y=\lnot(X\land\lnot Y) $$
$$ X \iff Y = (X\implies Y)\land(Y\implies X)=\lnot(X\land\lnot Y)\land\lnot(Y\land\lnot X) $$
$$ \lnot(\lnot(X\land\lnot Y)\land\lnot(Y\land\lnot X))=(X\land\lnot Y)\lor(Y\land\lnot X) $$
Either X is true and Y is false, or X is false and Y is true.
| $X$ | $Y$ | $¬ X$ | $¬ Y$ | $¬ X∨ Y$ | $¬ Y∨ X$ | $(¬ X∨ Y)∧(¬ Y∨ X)$ | $X∧¬ Y$ | $Y∧¬ X$ | $(X∧¬ Y)∨(Y∧¬ X)$ |
| T | T | F | F | T | T | T | F | F | F |
| T | F | F | T | F | T | F | T | F | T |
| F | T | T | F | T | F | F | F | T | T |
| F | F | T | T | T | T | T | F | F | F |
A.1.3
Suppose that you have shown that whenever X is true, the 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\iff Y = (X\implies Y)\land(Y\implies X) $$
\(\lnot X\implies\lnot Y\) is contraposition of \(Y\implies X\). Hence,
$$ (X\implies Y)\land((\lnot X\implies\lnot Y)=(X\implies Y)\land(Y\implies X)=X\iff Y $$
It demonstrates that X is true if and only if Y is true.
| $X$ | $Y$ | $X⟹ Y$ | $Y⟹ X$ | $¬ X$ | $¬ Y$ | $¬ X⟹¬ Y$ | $(X⟹ Y)∧(Y⟹ X)$ | $(X⟹ Y)∧(¬ X⟹¬ Y)$ |
| T | T | T | T | F | F | T | T | T |
| T | F | F | T | F | T | T | F | F |
| F | T | T | F | T | F | F | F | F |
| F | F | T | T | T | T | T | T | T |
A.1.4
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\iff Y = (X\implies Y)\land(Y\implies X) $$
\(\lnot Y\implies\lnot X\) is contraposition of \(X\implies Y\). Hence,
$$ (X\implies Y)\land((\lnot Y\implies\lnot X)=(X\implies Y)\land(X\implies Y)=X\implies Y $$
It does not demonstrate that X is true if and only if Y is true.
| $X$ | $Y$ | $X⟹ Y$ | $Y⟹ X$ | $¬ X$ | $¬ Y$ | $¬ Y⟹¬ X$ | $(X⟹ Y)∧(Y⟹ X)$ | $(X⟹ Y)∧(¬ Y⟹¬ X)$ |
| T | T | T | T | F | F | T | T | T |
| T | F | F | T | F | T | F | F | F |
| F | T | T | F | T | F | T | F | T |
| F | F | T | T | T | T | T | T | T |
A.1.5
Suppose you know that X is true if and only if Y 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 quivalent? Explain.
| $A$ | $B$ | $A⇔ B$ |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
X iff Y states that X and Y are logically equivalent, and Y iff Z states that Y and Z are logically equivalent. Therefore, X iff Y and Y iff Z state that X, Y, Z are logically equivalent.
A.1.6
Soppose 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\implies Y)\land(Y\implies Z)\land(Z\implies X) $$
| $X$ | $Y$ | $Z$ | $X⟹ Y$ | $Y⟹ Z$ | $Z⟹ X$ | $(X⟹ Y)∧(Y⟹ Z)∧(Z⟹ X)$ |
| T | T | T | T | T | T | T |
| T | T | F | T | F | T | F |
| T | F | T | F | T | T | F |
| T | F | F | F | T | T | F |
| F | T | T | T | T | F | F |
| F | T | F | T | F | T | F |
| F | F | T | T | T | F | F |
| F | F | F | T | T | T | T |
\((X\implies Y)\land(Y\implies Z)\land(Z\implies X)\) states that X, Y, Z are logically equivalent.