boolean-logic - bool 代数 - 证明德摩根定律

Question

我在 Google 上到处寻找德摩根定律的 bool 代数(不是集合论)证明，但找不到。 Stack Overflow 也缺少 DeMorgan 定律问题。

作为我的 CIS 251 类(class)家庭作业的一部分，我们被要求证明德摩根定律的一部分，给出以下表达式:

[z + z' = 1 和 zz' = 0]

通过证明(简化)来证明 (xy)' = x' + y'

(x y) + (x' + y') = 1 和 (x y)(x' + y') = 0

我(和一个 friend )在第一个表达式中的尝试是(步骤编号以供引用):

1. (x y) + (x' + y')                =  1
2. (xy  + x’)(xy + y’)              =  (Distributive Prop)
3. (x + x’)(y + x’)(x + y’)(y + y’) =  (Distributive Prop) // This is probably not correct
4. (1)(y + x’)(x + y’)(1)           =  (Compliment Prop)
5. (y + x’)(x + y’)                 =  (0 & 1 Identity Prop)
6. (x + x’)(y + y’)                 =  (Commutative Prop) // I know for a fact this is not how the commutative property works
7. (1)(1)                           =  (Compliment Prop)
8. 1                                =  (0 & 1 Identity Prop)

所以我知道我错了 - 我在某个地方作弊并夸大了其中一些假设的实际运作方式。但是我和我的 friend 尝试了大约一个小时，并且遍历了每个假设(不包括德摩根定律)，但我们终究还是无法将其简化。

谁能告诉我哪里出了问题，或者我们错过了什么？我们没有理会第二个，因为我们知道第一个错了，第二个会非常相似。

PS - 我知道这可以使用真值表来证明 - 并且出于显而易见的原因，它适用于现实世界。但是，我想了解允许我们使用简化表达式的推导。

Answer 1

我不知道这样做的最佳方法。这就是我所做的:

(x.y)' = x' + y' 

↔

(x.y)' + x.y = x' + y' + x.y ............ (assuming x.y != 1)

↔

1 = x' + y' + x.y

↔

1 = x' + (y' + x).(y' + y)............... (Distributive property)

↔

1 = x' + (y' + x)

↔

1 = 1

现在，在第一步中我们假设 x.y != 1。如果是这样，那么该陈述显然是正确的。

P.S.:我自己对这个证明并不完全满意，因为我们仍然在案件中处理它。这不是一劳永逸!