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

Question

我在谷歌上到处寻找德摩根定律的布尔代数（不是集合论）证明，但找不到。Stack Overflow 也缺乏德摩根定律的问题。

作为我的 CIS 251 课程的家庭作业的一部分，我们被要求证明德摩根定律的一部分，给出以下表达式：

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

证明(xy)' = x' + y'（简化）

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

我（和朋友）在第一个表达式中的尝试是（步骤编号以供参考）：

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)

所以我知道我弄错了——我在某个地方作弊，夸大了其中一些假设实际上如何运作的现实。但是我和我的朋友尝试了大约一个小时，并且遍历了所有假设（不包括德摩根定律），但我们终其一生都无法将其简化。

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

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

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

PS：我自己对这个证明并不完全满意，因为我们仍然在处理它。这不是一击必杀！

Answer 2

1. (XY) + (X' + Y') = 1;
2. (X + X' + Y) (Y + X' + Y') = 1; 分布 AB+C = (A+C)(B+C);
3. (1 + Y) (1 + X') = 1; 因为 Z + Z' = 1;
4. (1) (1) = 1; 因为 1 + Z = 1；
5. 1 = 1; 身份; 量子点

Answer 3

现在想做什么？证明 2 + 2 = 4 不计算？

“真真假假，不真不真，不真不真。”

⊤ ∧ ⊤ ↔ ¬(¬⊤ ∨ ¬⊤)

“假不假，不假不假，不假不假。”

⊥ ∧ ⊥ ↔ ¬(¬⊥ ∨ ¬⊥)

“真假不，不真或，不假”。

⊤ ∧ ⊥ ↔ ¬(¬⊤ ∨ ¬⊥)

“真理是：真与真非，非真或，非真与；假与非非，非假或，非与；真与假非，非真或，非假。” 我的标点符号可能有点古怪，但下面的公式检查了。

⊤ ↔ (⊤ ∧ ⊤ ↔ ¬(¬⊤ ∨ ¬⊤)) ∧ (⊥ ∧ ⊥ ↔ ¬(¬⊥ ∨ ¬⊥)) ∧ (⊤ ∧ ⊥ ↔ ¬(¬⊤ ∨ ¬⊥))

Answer 4

i bet this is a good method
we got to prove,
xy + x' + y' =1
take LHS
x'+xy+y'
add xx' and x'y to it (notice that it does not change anything prove using simple boolean laws)

so now
LHS becomes,
x'+xx'+xy+x'y+y'
=> x'(1+x)+y(x+x')+y'
=> x'+y+y'
=> x'+1
=> 1

hence xy+x'+y'=1
similarly do it for the other one  

Answer 5

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

让x.y=A

然后看下面的语句

A+A'=1