- 153

- 1

**1. Homework Statement**

**There should be lines of some values to imply the "Not" form of them, however to make it easier, i'll just use the ¬ Symbol**

(a) Let x, y be elements of a Boolean algebra. Prove from the axioms that (x · y) + x = x.

(b) Prove from the axioms of Boolean algebra that x · ¬( y · ¬x + ¬y ) = (x + x) · (y + 0). You can use DeMorgan’s and other identities we already derived in class.

(c) In the proof of completeness of Boolean algebra, we showed how to convert every formula to its “canonical DNF”: a normal form corresponding to the DNF obtained from the truth table without any simplifications.

Describe the normal form for the formula ¬( y · ¬x + ¬y )

**2. Homework Equations**

x + y = y + x

x · y = y · x

(x + y) + z = x + (y + z)

(x · y) · z = x · (y · z)

x · (y + z) = x · y + x · z

x + y · z = (x + y) · (x + z)

x + 0 = x

x · 1 = x

x + ¬x = 1

x · ¬x = 0

0 ≠ 1

**3. The Attempt at a Solution**

Part a, i don't even know how to start it. There doesn't seem to be anything i can do to it.

Part b, i have an attempt for

x * ¬(y * ¬x + ¬y) = (x + x) * (y + 0)

x * (¬y + x * y) = (x + x) * (y + 0)

x * (¬y + y * y + x) = (x + x) * (y + 0)

x * (1 * y + x) = (x + x) * (y + 0)

x * (x + 1) * (y + 1) = (x + x) * (y + 0)

x * x + x * 1 * (y + 1) = (x + x) * (y + 0)

0 + x * (y + 1) = (x + x) * (y + 0)

0 + (x * y) + (x * 1) = (x + x) * (y + 0)

0 + (x * y) + (x) = (x + x) * (y + 0)

but i get here and get stuck.

and part c, much like part a, i don't even know how to start it.