離散数学 11：基本法則と試験問題の解き方
最後に、集合と論理をつなぐ基本法則を整理します。情報処理技術者試験では、式変形そのものだけでなく、条件判定、検索条件、アクセス制御、回路の動作などとして出題されることがあります。
ド・モルガンの法則
ド・モルガンの法則は、否定が AND と OR を入れ替えるという法則です。
- NOT (P AND Q) は、(NOT P) OR (NOT Q)
- NOT (P OR Q) は、(NOT P) AND (NOT Q)
集合でも同じ考え方です。A∩B の補集合は A の補集合と B の補集合の和集合、A∪B の補集合は A の補集合と B の補集合の積集合になります。
分配則
AND と OR には分配則があります。
- P AND (Q OR R) は、(P AND Q) OR (P AND R)
- P OR (Q AND R) は、(P OR Q) AND (P OR R)
見慣れない形でも、真理値表を作ると同じ結果になることを確認できます。
吸収則
P OR (P AND Q) は P と同じです。P が真なら全体は真、P が偽なら P AND Q も偽だからです。同様に、P AND (P OR Q) も P と同じです。
問題を解く順序
- 命題を P, Q, R に分ける
- NOT, AND, OR, XOR などの演算を確認する
- 迷ったら真理値表を作る
- 否定がかかった複合条件はド・モルガンでほどく
- 集合問題ならベン図に戻す
ミニ演習
NOT (P OR Q) と同じ式はどれでしょうか。
答えは (NOT P) AND (NOT Q) です。「どちらかが真ではない」は、「P も偽で、Q も偽」と同じです。
連載のまとめ
離散数学は、コンピュータの数値表現と条件判断の基礎です。基数、補数、誤差、集合、命題、論理演算を別々に覚えるのではなく、ビット列と真偽の扱いとしてつなげて理解すると、試験問題だけでなくプログラムの条件分岐やデータ表現にも強くなります。