1

Given a proof, I tried to analyze it and identify the properties of boolean algebra used at each step. However, I am stumped with the first line: $(a+b) + \sim(a) \cdot \sim(b) = (a + b + \sim(a))(a+b+\sim(b))$. Which property makes those two things equal?

To show $\sim(a+b) = \sim(a) \cdot \sim(b)$

Proof

Show $(a+b) + \sim(a) \cdot \sim(b) = 1$ $$ \begin{align} (a+b) + \sim(a) \cdot \sim(b) &= (a + b + \sim(a))(a+b+\sim(b)) \\ &= (a+\sim(a) + b)(a + b+ \sim(b)) \\ &=(1+b)(a+1) \\ &=1\cdot 1 = 1 \\ \end{align} $$

Next, show $(a+b) \cdot \sim(a) \cdot \sim(b) = 0$

$$\begin{align} (a+b) \cdot \sim(a) \cdot \sim(b) &= a \cdot \sim(a) \cdot \sim(b) + \sim(a) \cdot \sim(b) \\ &= a \cdot \sim(a) \cdot \sim(b) + \sim(a) \cdot b \cdot \sim(b) \\ &=0 \cdot \sim(b) + \sim(a) \cdot 0 \\ &= 0 + 0 = 0 \end{align} $$

We conclude that $\sim(a) \cdot \sim(b)$ is the complement of $a+b$ (because those equations would not have worked otherwise).

To show $\sim(a\cdot b) = \sim(a) + \sim(b)$

... (to be completed once I understand the properties used above)

Jonathan Komar
  • 251
  • 2
    In usual arithmetic, the equation $a(b+c) = ab + ac$ is seen with multiplication and addition. While this is true in Boolean algebra, the formula $a + bc = (a+b)(a+c)$ is also true (not true in normal arithmetic) and is used in the first line. This is the distributivity of multiplication over addition. – Sarvesh Ravichandran Iyer Jan 28 '19 at 08:37
  • Boolean rules can easily be checked by a truth-table. – Peter Jan 28 '19 at 08:38
  • 1
    @Peter Thanks, but a proof table only verifies semantics. I want to understand the application of rules according to formal properties of all boolean algebras. The first comment explaining the distributive property is what I was looking for (among other things)! – Jonathan Komar Jan 28 '19 at 08:40
  • Note that the second de Morgan law can be decuced from the first: $\sim (a \cdot b) = \sim(\sim(\sim a) \cdot \sim (\sim b))$ and use the first from right to left. This uses $\sim (\sim a) =a$ of course. – Henno Brandsma Jan 28 '19 at 09:59

1 Answers1

0

Properties Used in DeMorgan's Law:

Property of 0- X+0=X ; X⋅0=0

Property of 1- X+1=1 ; X⋅1=X

Idempotence Law- X+X=X ; X⋅X=X

Involution Law- (X')'=X

Complementarity Law - X+X'=1 ; X⋅X'=0

Commutative Law-X+Y=Y+X ; X⋅Y=Y⋅X

Associative Law- (X+Y)+Z=X+(Y+Z); (X⋅Y)⋅Z=X⋅(Y⋅Z)

Distributive Law-X(Y+Z)=XY+XZ ; X+YZ=(X+Y)(X+Z)

Here in these two links you will find the proper boolean algebra proof of DeMorgan's Law along with the property used in each statement:

http://mines.humanoriented.com/410/books/boolean_algebra.pdf

http://www2.nau.edu/~sh295/EE110/deMorganproof.html

Hope This Helped✌

user639018
  • 13
  • 3
  • I had hoped my question content would imply rules in context, not just spelling them out ;) The link you provided does provide useful insights, however. Answers should be self-sufficient (your www2.nau link is external), which is why I will hold off accepting your answer. – Jonathan Komar Jan 28 '19 at 17:28