離散数学 10：論理演算と真理値表
論理演算は、真と偽、または 1 と 0 を扱う演算です。情報処理技術者試験では、否定、論理和、論理積、排他的論理和、否定論理和、否定論理積などが出ます。
基本の論理演算
- NOT P: P でない
- P AND Q: P かつ Q
- P OR Q: P または Q
- P XOR Q: P と Q の一方だけが真
- P NAND Q: P AND Q の否定
- P NOR Q: P OR Q の否定
OR は、日常語の「または」と違って、両方真でも真です。XOR は、どちらか一方だけが真のときに真です。この違いはよく問われます。
真理値表の作り方
2つの命題 P と Q なら、組合せは4通りです。
- P=真, Q=真
- P=真, Q=偽
- P=偽, Q=真
- P=偽, Q=偽
この4行を作り、式を左から順に計算します。複雑な論理式でも、途中列を増やせば機械的に解けます。
ビット演算として見る
論理演算はビット列にも適用できます。例えば 1010 AND 1100 は、各桁ごとに AND を取るので 1000 です。桁をそろえて、同じ位置どうしを計算します。
試験での見方
式を見て悩むより、真理値表を書いた方が速い場面があります。特に XOR、NAND、NOR が混ざる問題は、暗算より表が安全です。
確認問題
P=真、Q=偽 のとき、P XOR Q は真でしょうか。
一方だけが真なので、真です。