equivalent to $A \to (C \leftrightarrow D)$

Question

I am somewhat confused while reading a paper. Are these two statements equivalent?

• $ A \wedge B \to (C \leftrightarrow D)$

• $ [(A \wedge B \wedge C) \to D] \land [(A \wedge B \wedge D) \to C]$

I think you need both statements to be equivalent to the first one. I have not worked it out on paper. I took a confusing theorem from the chapter on integration in an analysis textbook. The parts of the theorem were substituted for letters.

This could be simplified. Are these two statement equivalent?

• $A \to (C \leftrightarrow D)$

• $[(A \wedge C) \to D] \wedge [(A \wedge D) \to C]$

Are there common exm

Answer 1

First note that $p\implies q \equiv \neg p \lor q$. The first expression is thus $$ \begin{align} A\land B \implies (C\iff D) &\equiv \neg (A\land B) \lor (C\iff D) \\ &\equiv \neg (A\land B) \lor ((C\implies D) \land (D\implies C)) \\ &\equiv ( \neg (A\land B) \lor (C\implies D) ) \land ( \neg (A\land B) \lor (D\implies C) ) \\ &\equiv ( \neg (A\land B) \lor (\neg C \lor D) ) \land ( \neg (A\land B) \lor (\neg D\lor C) ) \\ &\equiv ( \neg A\lor \neg B) \lor (\neg C \lor D) ) \land ( ( \neg A\lor \neg B) \lor (\neg D\lor C) ) \\ &\equiv ( \neg A\lor \neg B \lor \neg C ) \lor D ) \land ( ( \neg A\lor \neg B \lor \neg D)\lor C ) \\ &\equiv (\neg (A\land B \land C ) \lor D ) \land (\neg (A\land B \land D ) \lor C ) \\ &\equiv ((A\land B \land C ) \implies D ) \land ((A\land B \land D ) \implies C ) \end{align} $$ where we made heavy use of the De Morgan Law, i.e. $\neg (A\land B) \equiv \neg A \lor \neg B$.

Answer 2

Verbally (if it helps):

• suppose the first statement (third bullet) is true. If $A$ and $C$ are true then $C$ and $C\leftrightarrow D$ are true, so $D$ is true. Similarly, if $A$ and $D$ are true then $C$ is true. So the second statement is true.

• conversely, suppose the second statement is true. Suppose $A$ is true. Then if $C$ is true, $A\wedge C$ is true so $D$ is true, that is, $C\to D$ is true; likewise, if $D$ is true then $C$ is true. This shows that if $A$ is true then $C\leftrightarrow D$ is true, so the first statement is true.

Answer 3

$\newcommand{\tofrom}{\leftrightarrow}$ Yes, there is an equivalence between the statements.   We argue by natural deduction that:

• $A\to (C\tofrom D)$

  If A, then C is equivalent to D.

  Case 1: Assuming A and C, then we conclude D.
  Case 2: Assuming A and D, then we conclude C.

  So if A and C, then D; and if A and D, then C.

• $\big((A\wedge C)\to D\big)\wedge\big(A\wedge D)\to C\big)$

  If A and C, then D; and if A and D, then C

  Assuming A we conclude: If C, then D; and if D, then C.

  Hence: If A, then C is equivalent to D.

Answer 4

In algebra, we know that in a Unique Factorization Domain (in general, this holds for GCD domains), an element being prime is equivalent to one being irreducible (in integral domains, every prime is irreducible, but the converse requires GCD domains). Working in a ring $R$ and fixing an element $x$ in $R$, let $A$ be the statement that $R$ is a UFD, $C$ be the statement that $x$ is prime, and $D$ be the statement that $x$ is irreducible. The first propositional form is what I already stated. Similarly, if $R$ is a UFD and $x\in R$ is prime, then $x$ is irreducible, and if $R$ is a UFD and $x\in R$ is irreducible, then $x$ is prime.

You can prove the first implies the second by assuming the first, then proving each part of the conjunction: you first assume $A$ and $C$ and prove $D$, then assume $A$ and $D$ and prove $C$. To prove the second implies the first, you assume the second statement, then assume $A$ and $C$ and prove $D$, then assume $A$ and $\neg C$ and prove $\neg D$ (which is equivalent to assuming $A$ and $D$ and proving $C$).