学习目标：
完成本节课后，学生将能够：

1. 应用 FND/FNC 算法到具体的表达式，以找到它们的合取和析取标准形。
2. 理解 命题逻辑中简单和复合开关的使用。
3. 识别 复合开关和黑盒的结构。
4. 使用 真值表来总结设备的信息。
5. 提取 设备的真值表中的 FND 和 FNC。
6. 设计 与给定设备具有相同功能的复合开关。

目录
FND/FNC 算法
从真值表中获得标准形的算法：黑盒和复合开关
示例练习

虽然我们已经证明了所有命题逻辑表达式都等价于一种标准形，但我们还没有说明如何找到这些标准形。为此，我们将回顾一个算法，其目标是生成标准形表达式，并最终回顾由这些主题引发的应用。

FND/FNC 算法

FND/FNC 算法是一系列步骤 可以帮助您从任何命题逻辑表达式中找到其在 FND 或 FNC 中的等价表达式（视情况而定）。执行方式如下：

• 步骤 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。

• 步骤 3： 此步骤分为两部分，取决于您希望获得 FND 还是 FNC
  • 如果想要获得 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 的真值表结果，但不知道其命题结构时。用语言解释这个过程很长；然而，技术通过展示如何开发的例子更容易理解，所以我会留下我将在视频中开发的一些例子，但首先你需要查看以下概念：

• 电缆： 信号传播的介质
• 节点： 三条或更多电缆相交的点。
• 简单开关： 一种只接收开（1）和关（0）两种状态的装置，始终处于其中之一状态。开启状态允许信号通过，关闭状态阻止信号通过。
• 复合开关： 是由简单开关和电缆组成的装置。
• 黑盒： 是任何内部结构无法观察到的装置。

简单开关是通过命题变量进行建模的，而复合开关是通过命题逻辑表达式来建模的。最简单的情况是从下面显示的析取和合取连接器中获得的。

合取结构

析取结构

示例练习

1. 一个装置由一个黑盒和 4 个有序开关组成。该装置在以下条件下激活
   • 条件 1： 如果有两个连续的开关打开，则激活。如果有三个连续的开关打开，该条件失效。
   • 条件 2： 如果所有开关都关闭，则激活。
   • 例外： 如果上述条件都不满足，则设备关闭。

   a) 在真值表中总结这些信息 [解答]

   b) 从真值表中提取再现机器操作的 FND 和 FNC。 [解答]

   c) 使用前一步获得的 FNC 或 FND（较简单的一个）来设计一个具有相同功能的复合开关。 [解答]

2. 与前一练习相同，但现在该设备有 5 个开关。[读者挑战]