学習目標：
この授業の終了時には、学生は以下のことができるようになります：

1. 適用する：具体的な命題論理式に対してFND/FNCアルゴリズムを適用し、連言標準形および選言標準形を導出する。
2. 理解する：命題論理における単純スイッチおよび複合スイッチの使用法を理解する。
3. 識別する：複合スイッチおよびブラックボックスの構造を識別する。
4. 活用する：真理値表を使用して、装置に関する情報を要約する。
5. 導出する：装置の真理値表からFNDおよびFNCを導出する。
6. 設計する：与えられた装置と同じ機能を持つ複合スイッチを設計する。

目次
FND/FNC アルゴリズム
真理値表から正規形を導出するためのアルゴリズム：ブラックボックスと複合スイッチ
例題

命題論理のすべての表現が正規形と同値であることはすでに証明しましたが、そのような正規形をどのように見つけるかについてはまだ述べていません。これを達成するために、正規形の表現を生成することを目的としたアルゴリズムを確認し、最終的にこのテーマから派生する応用について考察します。

FND/FNC アルゴリズム

FND/FNC アルゴリズムは一連のステップです。これにより、任意の命題論理式から、その論理的に同値な連言標準形（FNC）または選言標準形（FND）を導出することができます。手順は次のように行います：

• ステップ 1: すべての部分式 (F\rightarrow G) を (\neg F\vee G) に、(F\leftrightarrow G) を同様に書き換えます。このステップを、すべての含意と双含意が除去されるまで繰り返します。
• ステップ 2: 二重否定を除去し、可能な場合にはド・モルガンの法則を適用します。以下の書き換えを行ってください：
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

  式中に \neg\neg G、\neg(G \wedge H)、\neg(G \vee H) のいずれの形も残っていない場合、次のステップへ進みます。

• ステップ 3: このステップは、FND または FNC のいずれを目指すかによって、2つの部分に分かれます。
  • FNC を得たい場合：

    可能な場合には \vee の分配法則を適用します。以下の書き換えを実行してください：

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    式中に G\vee(H\wedge K) または (H\wedge K)\vee G の形が残っていない場合、FNC に到達したことになります。

  • FND を得たい場合：

    可能な場合には \wedge の分配法則を適用します。以下の書き換えを実行してください：

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    式中に G\wedge(H\vee K) または (H\vee K)\wedge G の形が残っていない場合、FND に到達したことになります。

例

次の命題論理式に対して、FND/FNC アルゴリズムを用いて連言標準形および選言標準形を求めてください。

1. (A\rightarrow (B\rightarrow A)) [解答]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [解答]

真理値表から正規形を導出するためのアルゴリズム：ブラックボックスと複合スイッチ

FND/FNC アルゴリズムによって、命題論理の任意の表現に対して、その同値な正規形を求めることができます。しかしながら、初期の論理式が存在しない場合もあります。例えば、ある命題式 F の真理値表の結果だけがあり、その構造が不明であるときです。このような場合に言葉だけで説明するのは長くなりますが、実際の進め方を例で示すことで、より直感的に理解できます。以下にビデオで扱う例を示す前に、次の概念を確認しておきましょう：

• ケーブル：信号が流れる媒体。
• ノード：3本以上のケーブルが交差する点。
• 単純スイッチ：オン（1）またはオフ（0）の状態をとる装置で、常にそのいずれか一方の状態にある。オンの状態では信号が通過し、オフの状態では信号の通過を阻止する。
• 複合スイッチ：単純スイッチとケーブルで構成された装置。
• ブラックボックス：内部構造を観察できない任意の装置。

単純スイッチは命題変数を通じてモデル化され、複合スイッチは命題論理式によってモデル化されます。最も基本的な例は、以下に示す選言および連言の接続子によって得られるものです。

連言（AND）のスキーマ

選言（OR）のスキーマ

例題

1. ブラックボックスと4つのスイッチで構成される装置がある。この装置は以下の条件で起動する：
   • 条件1：2つの連続したスイッチがオンになっているときに作動する。ただし、3つの連続したスイッチがオンになっているとこの条件は無効になる。
   • 条件2：すべてのスイッチがオフの場合に作動する。
   • 例外：上記の条件が満たされない場合、装置はオフになる。

   a) 上記の情報を真理値表に要約せよ。[解答]

   b) 真理値表から、装置の動作を再現するFNDおよびFNCを導出せよ。[解答]

   c) 前のステップで得たFNDまたはFNC（より簡潔な方）を用いて、装置と同じ動作をする複合スイッチを設計せよ。[解答]

2. 前問と同様。ただし、装置には5つのスイッチがある。[読者への挑戦]