次の等式を証明せよ（離散数学）

質問

離散数学の
(A^c∧B^c)∨(B^c∧C)∨(A∧C^c)=B^cV(A∧C^c)
を証明せよという問題が分かりません。
左辺だけをブール代数を用いてをどのように右辺と合わせるのか教えてください。

回答No.2

alice_44 · ベストアンサー

(A^c∧B^c)∨(B^c∧C)∨(A∧C^c)
= {(A^c∧B^c∧C)∨(A^c∧B^c∧C^c)}∨{(A∧B^c∧C)∨(A^c∧B^c∧C)}∨{(A∧B∧C^c)∨(A∧B^c∧C^c)}
= (A∧B∧C^c)∨(A∧B^c∧C)∨(A^c∧B^c∧C)∨(A∧B^c∧C^c)∨(A^c∧B^c∧C^c)

(B^c)∨(A∧C^c)
= {(A∧B^c∧C)∨(A∧B^c∧C^c)∨(A^c∧B^c∧C)∨(A^c∧B^c∧C^c)}∨{(A∧B∧C^c)∨(A∧B^c∧C^c)}
= (A∧B∧C^c)∨(A∧B^c∧C)∨(A^c∧B^c∧C)∨(A∧B^c∧C^c)∨(A^c∧B^c∧C^c)

ちゃんと同じになっている。

例えば、括弧のたくさん付いた煩雑な多項式を比較するときは、
展開して、同類項を整理して、降冪(または昇冪)の順に並べ替える。

論理式の場合にも、
(A^c∧B^c) = (A^c∧B^c)∧(C∨C^c) = (A^c∧B^c∧C)∨(A^c∧B^c∧C^c) のように
各項に全ての変数 A,B,C を補った後、括弧は展開して、重複した項は整理して、
項を何か統一的な順序で並べ替えれば、直接比較できる形になる。

上記では、項の並べ替えに辞書式順序を使った。

今回のように変数の個数が 3 以下だと、便図を書いて塗り絵で済ます手もあるが、
変数が 4 個以上になると、図は書けなくなる。
標準形へ展開する方法は、変数が何個でも変わりなく使える。

回答No.1

alice_44

両辺とも、完全積和形に展開して
比べるが吉。