1

Problem: Prove that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$.

What I have done so far:

  1. $(A \land B)'$ premise
  2. $(C' \land A)'$ premise
  3. $(C \land B')'$ premise
  4. $A' \lor B'$ 1, De Morgan
  5. $C \lor A'$ 2, De Morgan
  6. $C' \lor B$ 3, De Morgan

4 Answers4

3

$R \equiv(A'\lor B')\land(C\lor A')\land(C'\lor B) $
$\equiv(A'\lor(B'\land C))\land(B\lor C') $
$\equiv((A'\lor(B'\land C))\land B)\lor ((A'\lor(B'\land C))\land C')$
$\equiv((B\land A')\lor (B\land (B'\land C)) \lor((C'\land A')\lor (C'\land (B'\land C))$
Since $(B\land (B'\land C)) \equiv 0$ and $(C'\land (B'\land C)) \equiv 0$, We have that :
$R \equiv (B\land A')\lor (C'\land A') \equiv A' \land(B\lor C')$
So you can say that if $R\equiv 1$, then $A'\equiv 1$.

2

Consider the following: Let $$ \Omega\equiv\neg(A\land B)\land\neg(\neg C\land A)\land\neg(C\land\neg B)\to\neg A. $$ Your job, then, is to show that $\Omega$ is a tautology: \begin{align} \Omega&\equiv\neg(A\land B)\land\neg(\neg C\land A)\land\neg(C\land\neg B)\to\neg A\tag{by definition}\\[1em] &\equiv (\neg A\lor\neg B)\land(C\lor\neg A)\land(\neg C\lor B)\to\neg A\tag{DeMorgan}\\[1em] &\equiv[A\land(B\lor\neg C)]\lor(C\land\neg B)\lor\neg A\tag{mat. imp., distrib.}\\[1em] &\equiv [(A\lor\neg A)\land(B\lor\neg C\lor\neg A)]\lor(C\land\neg B)\tag{distrib.}\\[1em] &\equiv (B\lor\neg C\lor\neg A\lor C)\land(B\lor\neg C\lor\neg A\lor\neg B)\tag{distrib.}\\[1em] &\equiv \mathbf{T}\land\mathbf{T}\\[1em] &\equiv \mathbf{T}. \end{align} The biggest "jump" is from the second to the third step. If you can see that, then you should be well on your way.

1

Good so far.

You have shown that $(A \land B)' \land (C' \land A)' \land (C \land B')' \equiv (A' \lor B') \land (C \lor A') \land (C' \lor B)$

You can then write $(A' \lor B') \land (C \lor A') \land (C' \lor B) \equiv (A' \lor B') \land \left [(C \lor A') \land C' \lor (C \lor A') \land B) \right]$ (distributive law)

Then consider smaller parts like $(C \lor A') \land C' \equiv [C \land C'] \lor [A' \land C'] \equiv 0 \lor [A' \land C'] \equiv A' \land C'$

tomi
  • 9,594
1
  1. (A∧B)′ premise
  2. (C′∧A)′ premise
  3. (C∧B′)′ premise
  4. A′∨B′ 1, De Morgan
  5. C∨A′ 2, De Morgan
  6. C′∨B 3, De Morgan
  7. 'A v B 5, 6 resolution
  8. 'A 4, 7 resolution