論理演算・論理回路と集合

結論：各演算は「どんなときに1になるか」の一言で覚える

真理値表は、入力の全組合せと出力を並べた表です。各演算の「1になる条件」を一言で覚えておけば、真理値表はその場で毎回作れます。なお、試験では否定を文字の上の横線（上線）で書きますが、このレッスンでは ¬ と書きます。

頭に N が付くと、出力が全部ひっくり返ります。 だから覚えるのは AND・OR・XOR の3つだけで済みます。NOR の穴埋め問題も、OR の 0111 を反転した 1000 と即答できます。

XOR は「違えば1」、XNOR（一致回路）は「同じなら1」

XOR と XNOR は互いに否定の関係です。 一方の結果が常にもう一方の否定になる関係を相補演算といいます。出題が多いのは一致回路（XNOR）で、真逆の XOR と取り違えさせるのが最大のひっかけです。

たとえるなら、階段の上と下にある照明スイッチです。どちらを切り替えても灯りが反転するのは、点灯が「2つのスイッチの状態が同じか違うか」だけで決まる XOR（または XNOR）の配線だからです。

回路図の問題は、ゲートを左から1つずつ式にして、最後に展開するだけで解けます。

• ¬A と ¬B を OR に入れる → ¬A+¬B（¬(A・B) と同じ＝NAND）
• それを A との AND、B との AND に分け、2つを OR → A・(¬A+¬B) + B・(¬A+¬B)
• 展開すると A・¬A と B・¬B は常に0なので消える → A・¬B + ¬A・B ＝ XOR

ビット操作の問題も考え方は同じです。(L1 OR L2) AND NOT(L1 AND L2) は「どちらかが1」から「両方1」を除いた形なので、XOR になります。

XOR で「条件付き反転」

XOR は「もう一方の入力が1のときだけ反転するスイッチ」として使えます。 A XOR 0 = A、A XOR 1 = ¬A となるからです。

AND(A,G) は、G=0 のとき常に0、G=1 のとき A のままで反転しません。OR(A,G) は G=1 のとき常に1 です。どちらも G の値で A を反転させる動きにならないので、「G=0 ならそのまま、G=1 なら反転」を作れるのは XOR だけです。

ド・モルガンの法則：否定をくぐらせると・と+が入れ替わる

ド・モルガンの法則とは、全体にかかる否定を括弧の中へ配るときの規則です。否定を配ると、・と+が入れ替わり、各変数の否定も付け替わります。

• ¬(A・B) = ¬A + ¬B
• ¬(A+B) = ¬A・¬B

手順は次の3つをセットで覚えます。

1. ・と+を入れ替える
2. 各変数の否定を付け替える（¬¬A は A に戻る）
3. 全体の否定を外す

試験の選択肢には、このうちどれか1つを忘れた式がそのまま並びます。

プログラムの条件にも同じ規則が使えます。たとえば「P でない又は Q」の否定は「P かつ Q でない」です。流れ図の分岐を書き換える問題は、これで「処理を通る条件」と「迂回する条件」を整理すれば解けます。

真理値表から式を選ぶ：作るより代入

真理値表から式を選ぶ問題は、式を一から作るより、選択肢に値を代入して表と照合するほうが速くて確実です。

• 式を作る場合：F=1 の行ごとに、その行だけで1になる積を作り、+でつなぎます。これを積和形といいます。例：X=0、Y=0、Z=1 の行なら ¬X・¬Y・Z。
• 選択肢から選ぶ場合：F=0 の行と F=1 の行を1〜2個ずつ選んで代入し、表と合わない選択肢を消します。

2つの演算結果から未知の演算 X□Y を逆算させる問題（令和6年度の公開問題）もあります。1行ずつ「この行で □ が0なら、1なら」を試すと、答えは1つに決まります。

含意：(not P) or Q は「P ならば Q」

「(not P) or Q」は「P ならば Q」（含意）の書き換えです。P が真なのにこの式が真なら、Q は必ず真です。 論理和が真になるには、片方が真であれば十分です。しかし P が真だと not P は偽になるので、残る Q が真でなければなりません。

たとえるなら「雨なら傘を持つ」という約束です。約束が守られていて（式が真）、実際に雨が降った（P が真）なら、傘を持っている（Q が真）以外にありえません。この連鎖を2回たどると、Q も R も真と決まります。

eq の入れ子は「一致の一致」

eq(eq(A,B), eq(B,C)) が1になるのは、内側の2つの eq が同じ値のときです。つまり「両方1」か「両方0」のどちらかです。 両方1は「A=B かつ B=C」、両方0は「A≠B かつ B≠C」にあたります。外側の eq は一致回路（XNOR）と同じ働きをしている、と見ると速く解けます。

集合とベン図：論理演算の言い換え

集合の演算は論理演算の言い換えです。 積集合（∩）が AND、和集合（∪）が OR、補集合（全体集合のうちその集合に属さない部分）が NOT に対応します。ド・モルガンの法則も集合でそのまま成り立ちます。

• ド・モルガン：¬A∩¬B = ¬(A∪B) で、両円の外側にあたります。¬A−B（¬A から B を除いたもの）も同じ領域です。一方、¬A∪¬B は ¬(A∩B)（重なり以外の全部）で、別の領域です。
• 3円のベン図：∩でつながった条件を、A の中か外か、B の中か外か、C の中か外か、と1つずつ確かめて領域を決めます。たとえば ¬A∩B∩C は「B と C だけが重なる部分」です。
• 分配法則：(A∪B)∩C = (A∩C)∪(B∩C)、(A∩B)∪C = (A∪C)∩(B∪C)。1つ目は掛け算の a(b+c)=ab+ac と同じ形です。集合では∩と∪を逆にした2つ目も成り立ちます。
• 包含（⊆：部分集合である）：A∩B ⊆ A ⊆ A∪¬B のように「狭い→広い」の鎖をつなげられれば常に成り立ちます。迷ったら、具体的な要素を1つ置いて反例を探します。