応用情報技術者 2009年 秋期 午前2 問02
問題文
論理和(∨)、論理積(∧)、排他的論理和 (⊕)の結合法則の成立に関する記述として、適切な組合せはどれか。
選択肢
ア：
イ：
ウ：
エ：（正解）
結合法則が成立する論理演算の組合せ【午前2 解説】
要点まとめ
- 結論 → 論理和(∨)、論理積(∧)、排他的論理和(⊕)はすべて結合法則を満たすので、3 列すべて「成立する」のエが正解
- 根拠 → ブール代数の公理より、これら 3 演算は が恒真。特に ⊕ は「偶数個の真が偽になる」性質から可換でかつ結合的
- 差がつくポイント → ⊕ の結合性を知らず「成立しない」と思い込む受験者が多い。真理値表 8 通りで検算できるが、性質で覚えると時短
正解の理由
排他的論理和 ⊕ は「真が奇数個なら真、偶数個なら偽」。
三つの変数に拡張しても真になるのは真が 1 個か 3 個のときで一定。
したがって と は常に同じ結果になり結合的。
∨ と ∧ はド・モルガンや分配・結合法則が基本公理として証明済み。
よって全列「成立する」の エ が唯一の組合せ。
三つの変数に拡張しても真になるのは真が 1 個か 3 個のときで一定。
したがって と は常に同じ結果になり結合的。
∨ と ∧ はド・モルガンや分配・結合法則が基本公理として証明済み。
よって全列「成立する」の エ が唯一の組合せ。
よくある誤解
- XOR は「排他的」だから 3 変数になると性質が崩れると思い込む
- 論理演算の結合法則は算術演算のように当たり前ではないと考え、不要に疑う
解法ステップ
- 結合性を問われたら「基本論理演算はすべて成立」とまず思い出す
- わからなければ ⊕ について真理値表を 8 行書き、左右を計算して検算
- 各行の結果が一致 → 成立、異なれば不成立。試験時間が厳しければ性質暗記で即断
- 三演算とも成立を確認したら、全セル「成立する」の行を選択
選択肢別の誤答解説
- ア: ∨ の結合法則が「必ずしも成立しない」とする誤り。基本公理に反する
- イ: ∧ のみ「必ずしも成立しない」とする誤り。AND もブール代数で結合的
- ウ: ⊕ が「必ずしも成立しない」とする典型ミス。偶数個真で偽になる性質を見落とし
- エ: 三列すべて成立。唯一の正解
補足コラム
排他的論理和 ⊕ は加算の「繰り上がりなし和」と同型。
ビット演算では a XOR b XOR c は (a⊕b)⊕c = a⊕(b⊕c) が成立し、CPU の XOR 命令でも順序変更して最適化可能。
多変数 XOR は「真が奇数個」で真となるため、括弧の位置は一切影響しない。
ビット演算では a XOR b XOR c は (a⊕b)⊕c = a⊕(b⊕c) が成立し、CPU の XOR 命令でも順序変更して最適化可能。
多変数 XOR は「真が奇数個」で真となるため、括弧の位置は一切影響しない。
FAQ
Q: 排他的論理和 ⊕ は可換性もありますか？
A: あります。a⊕b = b⊕a が恒真なので可換性と結合性の両方を満たします。
A: あります。a⊕b = b⊕a が恒真なので可換性と結合性の両方を満たします。
Q: 真理値表を書く時間がもったいないのですが？
A: XOR の本質「偶数個真で偽」を覚えれば 3 変数でも即判断でき、真理値表を省略できます。
A: XOR の本質「偶数個真で偽」を覚えれば 3 変数でも即判断でき、真理値表を省略できます。
Q: 他に結合性を満たさない代表例は？
A: 例えば含意演算 (→) や NAND、NOR の一部組合せは結合性を持ちませんので注意してください。
A: 例えば含意演算 (→) や NAND、NOR の一部組合せは結合性を持ちませんので注意してください。
関連キーワード: 結合法則、排他的論理和、ブール代数
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！