3

DeMorgan の法則のブール代数(集合論ではない) の証明をGoogle で探しましたが、見つかりませんでした。Stack Overflow には、DeMorgan の法則の問題もありませんでした。

私の 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)

だから私はそれが間違っていたことを知っています. しかし、私の友人と私は約 1 時間試行し、すべての仮定 (DeMorgan の法則を除く) を調べましたが、私たちの人生でそれを単純化することはできませんでした。

どこが間違っていたのか、何を見逃していたのか、誰か教えてもらえますか? 最初のものは間違っていて、2番目のものは非常に似ていることがわかっていたので、2番目のものは気にしませんでした.

PS - これは真理値表を使用して証明できることを知っています - そして、現実の世界に適用できる明白な理由があります。ただし、簡略化された式を使用できるようにする導出を理解したいと思います。

4

5 に答える 5

3

これを行う最善の方法がわかりません。これは私がやったことです：

(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: 私自身、この証明に完全には満足していません。一撃必殺じゃない！

于 2013-12-06T13:05:08.490 に答える
0

今何をしようとしていますか？数えずに 2 + 2 = 4 であることを証明しますか?

「真実であり、真実ではない、真実ではない、または、真実ではない.」

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

「偽であり、偽ではない、偽ではない、または偽ではない」

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

「真と偽は違う、真ではない、または偽ではない」

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

「真実は次のとおりです。真と真はそうではない、真ではない、または真ではない、偽と偽はそうではない、偽ではない、または偽ではない、真と偽はそうではない、真ではない、または偽ではない.」私の句読点はおそらく少し厄介ですが、以下の式で確認できます。

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

于 2013-10-23T01:22:57.390 に答える
0 
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
于 2015-02-22T14:40:23.840 に答える