3
$\begingroup$

I just started reading the book Probability Theory the Logic of Science by Jaynes and on pg. 13 he includes this exercise, which I'm having trouble proving:

$C\equiv(A+\bar B)(\bar A+A \bar B)+\bar AB(A +B)$

"... it is left for the reader to verify that $C$ is logically the same statement as the implication $C=(B\implies \bar A)$"

I'm getting $C=(\bar B + \bar AB)$ when I think $(B\implies \bar A)$ means I should be getting $C=(\bar B + \bar A)$.

Would someone please show me how to prove this?

I think I'm stuck on the specific part, $\bar B + \bar AB == \bar B + \bar A$?

$\endgroup$
2
  • 1
    $\begingroup$ Probably the easiest way to see the result from where you are is to note that you'd get $B\implies\neg A\land B$, to use more logical notation. This is only true if $B\implies\neg A$ and $B\implies B$, but the latter holds trivially, so the statement is equivalent to $B\implies\neg A$ as desired. $\endgroup$
    – Derek Elkins left SE
    Apr 25, 2018 at 19:14
  • 1
    $\begingroup$ Or you could use truth tables or even just consider what happens when you assign $B$ to be $1$ and $0$ respectively for $B\implies\overline A$ and $B\implies\overline AB$. $\endgroup$
    – Derek Elkins left SE
    Apr 25, 2018 at 19:21

2 Answers 2

Reset to default
1
$\begingroup$

$$\begin{align} C &\equiv (A+\bar B)(\bar A+A \bar B)+\bar AB(A +B)\tag 1\\ \\ &\equiv \underbrace{A(\bar A)}_{\large \text F}+ A(A\bar B) + \bar B(\bar A) +\bar B A\bar B + \underbrace{\bar AB A}_{\large\text{F}}+ \bar ABB \tag {(2) distribution} \\ \\ &\equiv A\bar B + \bar A \bar B+ \bar AB\tag {(3) complement.}\\ \\ &\equiv (\underbrace{A+\bar A}_{\large\text{T}})\bar B + \bar AB \tag {(4) distribution}\\ \\ &\equiv \bar B + \bar AB \tag {(5) idempotence}\\ \\ &\equiv (\bar B + \bar A)(\underbrace{\bar B +B}_{\large T})\tag{(6) distribution} \\ \\ &\equiv \bar B + \bar A \tag{(7) idempotence} \end{align}$$

$\endgroup$
6
  • $\begingroup$ Thanks. I'm still not understanding going from the 3rd to 4th step, maybe I'm forgetting an identity. I know that A+\not A=1, but why drop the B on the second term? edit: It seems my difficulty is in understanding why \not B + \not AB == \not B + \not A? $\endgroup$
    – Austin
    Apr 25, 2018 at 19:33
  • 1
    $\begingroup$ given $\bar B + \bar A$: If $\bar B$ is not true, (then $B$ automatically holds), so if $\bar A$ holds, (i.e., so $\bar AB$ holds). $\endgroup$
    – amWhy
    Apr 25, 2018 at 19:39
  • $\begingroup$ Oh thanks I think I get it now. Is there any specific name for this identity or relation? $\endgroup$
    – Austin
    Apr 25, 2018 at 19:41
  • 1
    $\begingroup$ Note that from $\bar B + \bar A B$, we have $(\bar B + \bar A)(\bar B+ B) \equiv (\bar B + \bar A )(T) = \bar B + \bar A$, by the distributive rule of addition over multiplication. $\endgroup$
    – amWhy
    Apr 25, 2018 at 19:53
  • 1
    $\begingroup$ Yes, it sometimes feels like "playing a game" when working with boolean logic! You were very much on the right track, though, Jake! $\endgroup$
    – amWhy
    Apr 25, 2018 at 20:03
1
$\begingroup$

By complementation and idempotence: $\bar B+\bar AB ~{= (A+\bar A)\bar B+\bar AB \\= (A+\bar A+\bar A)\bar B+\bar AB \\= (A+\bar A)\bar B+ \bar A(\bar B+\bar B)\\=\bar B+\bar A}$

By distribution: $\bar B+(\bar A)(B) ~{= (\bar B+\bar A)(\bar B+B) \\= \bar A+ \bar B}$

Note also: $(\bar A +B)\bar B ~{= \bar A\bar B+B\bar B \\= \bar A \bar B}$

$\endgroup$
1
  • $\begingroup$ Thanks definitely writing this down in my book! $\endgroup$
    – Austin
    Apr 26, 2018 at 0:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .