离散数学中的PDNF和PCNF

要理解PDNF，我们必须先学习DNF（析取范式）和最小项。要理解PCNF，我们必须学习CNF（合取范式）和最大项。

DNF

DNF 代表析取范式 (Disjunction normal form)。当一个逻辑公式是析取合取式，并且每个变量都出现一次时，该公式被称为DNF。在DNF中，每个变量或其否定必须在每个合取式中出现一次。换句话说，一个复合语句，如果它是通过对由AND连接的变量进行OR运算得到的，并且在这种情况下也包括变量的否定，则称该复合语句为DNF。

例如

CNF

CNF 代表合取范式 (Conjunction normal form)。当一个逻辑公式是合取析取式，并且每个变量都出现一次时，该公式被称为CNF。在CNF中，每个变量或其否定必须在每个析取式中出现一次。换句话说，一个复合语句，如果它是通过对由OR连接的变量进行AND运算得到的，并且在这种情况下也包括变量的否定，则称该复合语句为CNF。

例如

1. (X ∨ Y) ∧ (Z ∨ U)
2. (¬X ∨ Y ∨ Z) ∧ (U ∨ Z)

三变量的最小项

对于给定的变量数量，计算最小项的公式描述如下：

如果有两个变量X和Y，则最小项将包含4个可能的公式，这些公式是X和Y或其否定的合取式：

2² = 4

X ∧ Y, ¬X ∧ Y, X ∧ ¬Y, ¬X ∧ ¬Y

如果有三个变量，则这些变量的可用最小项将是：

2³ = 8

(X ∧ Y ∧ Z), (¬X ∧ Y ∧ Z), (X ∧ ¬Y ∧ Z), (X ∧ Y ∧ ¬Z), (¬X ∧ ¬Y ∧ Z), (X ∧ ¬Y ∧ ¬Z), (¬X ∧ Y ∧ ¬Z), and (¬X ∧ ¬Y ∧ ¬Z)。现在我们将展示X和Y的最小项真值表，如下所示：

通过这张表，我们阐明了以下细节：

1. 两个最小项之间没有等价关系。
2. 每个最小项对于变量X和Y的真值组合只有一个T真值。

三变量的最大项

最大项可以描述为最小项的对偶。计算最大项的公式描述如下：

如果有两个变量X和Y，则最大项将包含4个可能的公式，这些公式是X和Y或其否定的析取式：

2² = 4

X ∨ Y, ¬X ∨ Y, X ∨ ¬Y, ¬X ∨ ¬Y

如果有三个变量，则这些变量的可用最大项将是：

(X ∨ Y ∨ Z), (¬X ∨ Y ∨ Z), (X ∨ ¬Y ∨ Z), (X ∨ Y ∨ ¬Z), (¬X ∨ ¬Y ∨ Z), (X ∨ ¬Y ∨ ¬Z), (¬X ∨ Y ∨ ¬Z), and (¬X ∨ ¬Y ∨ ¬Z)。

每个最大项对于变量的真值组合只有一个F假值。

PDNF

PDNF 也被称为主析取范式 (Principal Disjunction normal form)。PDNF用于执行和积 (sum of products, SOP)。换句话说，一个公式 ? 被称为PDNF，如果 ? 是最小项的和。PDNF 的表达式将如下所示：

例如：假设有三个变量X、Y和Z。使用这些变量的PDNF表达式将是(X.Y'.Z) + (X'.Y.Z) + (X.Y.Z')。

其中

+ 用于表示和是主要运算符。

在学习PDNF（主析取范式）和DNF（析取范式）时，我们总是感到困惑，但这两个术语之间存在巨大差异。DNF（析取范式）的表达式不一定包含所有变量的相同长度。

例如

1. 表达式(X.Y'.Z) + (X'.Y.Z) + (X.Y) 可以被认为是DNF的一个例子，但这个表达式不能是PDNF。
2. 表达式(X.Y'.Z) + (X'.Y.Z) + (X.Y.Z') 可以被认为是DNF和PDNF的例子。

构造PDNF的方法

有两种方法可以获得给定公式的PDNF。我们将逐一讨论它们。

方法 1：使用真值表

1. 在此步骤中，我们将首先为给定公式构建真值表。
2. 现在，我们将查看真值表，对于每个真值T，我们将选择与X和Y的T值组合相同的最小项。
3. 在最后一步中，我们将看到这些最小项的析取，它将等价于给定的公式。

示例 1：在此示例中，我们有一个表达式 X → Y，并且我们需要通过真值表确定PDNF。

解决方案：X → Y 的真值表如下所示：

在此表中，X → Y 只有一个假值。所以 X → Y 的 PDNF 将是：

(X ∧ Q) ∨ (¬X ∧ Q) ∨ (¬X ∧ ¬Q)

因此

∴ X → Y ⇔ (X ∧ Q) ∨ (¬X ∧ Q) ∨ (¬X ∧ ¬Q)

示例 2：在此示例中，我们有一个表达式 (X ∧ Y) ∨ (¬X ∧ Z) ∨ (Y ∧ Z)，并且我们需要通过真值表确定PDNF。

解决方案：(X ∧ Y) ∨ (¬X ∧ Z) ∨ (Y ∧ Z) 的真值表如下所示：

在此表中，表达式 (X ∧ Y) ∨ (¬X ∧ Z) ∨ (Y ∧ Z) 中有多个假值。对于PDNF，我们将只选择真值。所以 (X ∧ Y) ∨ (¬X ∧ Z) ∨ (Y ∧ Z) 的 PDNF 将是：

(X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)

方法 2：不构造真值表

我们可以通过以下方式获得给定公式的PDNF。

1. 在此步骤中，我们将把 → 替换为它们等价的公式，这些公式用于包含 ¬, ∧, 和 ∨。
2. 现在，我们将使用德摩根定律和分配律对变量应用否定。
3. 现在我们将删除那些矛盾的初等乘积。在此之后，通过引入缺失的因子，我们可以得到析取的最小项。如果析取中存在一些相同的最小项，我们将删除它们。

示例 1：在此示例中，我们有一个表达式 ¬X ∨ Y，并且我们需要确定PDNF。

解决方案

¬X ∨ Y

⇔ (¬X ∧ T) ∨ (Y ∧ T) [∵ A ∧ T ⇔ A]

⇔ (¬X ∧ (Y ∨ ¬Y)) ∨ (Y ∧ (X ∨ ¬X)) [∵ X ∨ ¬X ⇔ T]

⇔ (¬X ∧ Y) ∨ (¬X ∧ ¬Y) ∨ (Y ∧ X) ∨ (Y ∧ ¬X) [∵ X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)]

⇔ (¬X ∧ Y) ∨ (¬X ∧ ¬Y) ∨ (X ∧ Y) [∵ X ∨ X ⇔ X]

因此，所需的PDNF如下所示：

(X ∧ Y) ∨ (¬X ∧ Y) ∨ (¬X ∧ ¬Y)

示例 2：在此示例中，我们有一个表达式 (X ∧ Y) ∨ (¬X ∧ Z) ∨ (Y ∧ Z)，并且我们需要确定PDNF。

解决方案：(X ∧ Y) ∨ (¬X ∧ Z) ∨ (Y ∧ Z)

⇔ (X ∧ Y ∧ T) ∨ (¬X ∧ Z ∧ T) ∨ (Y ∧ Z ∧ T)

⇔ (X ∧ Y ∧ (Z ∨ ¬Z)) ∨ (¬X ∧ Z ∧ (Y ∨ ¬Y)) ∨ (Y ∧ Z ∧ (X ∨ ¬X))

⇔ (X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Z ∧ Y) ∨ (¬X ∧ Z ∧ ¬Y) ∨ (Y ∧ Z ∧ X) ∨ (Y ∧ Z ∧ ¬X)

⇔ (X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)

因此，所需的PDNF如下所示：

(X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)

示例 3：在此示例中，我们有一个表达式 X → ((X → Y) ∧ ¬(¬Y ∨ ¬X))，并且我们需要在不构造真值表的情况下确定PDNF。

解决方案：这里，我们将使用 X → Y ⇔ ¬X ∨ Y 和德摩根定律，然后我们将得到以下结果：

→ ((X → Y) ∧ ¬(¬Y ∨ ¬X))

⇔ ¬X ∨ ((¬X ∨ Y) ∧ (Y ∧ X))

⇔ ¬X ∨ ((¬X ∧ Y ∧ X) ∨ (Y ∧ Y ∧ X))

⇔ ¬X ∨ F ∨ (X ∧ Y)

⇔ ¬X ∨ (X ∧ Y)

⇔ (¬X ∧ T) ∨ (X ∧ Y)

⇔ (¬X ∧ (Y ∨ ¬Y)) ∨ (X ∧ Y)

⇔ (¬X ∧ Y) ∨ (¬X ∧ ¬Y) ∨ (X ∧ Y)

因此，所需的PDNF如下所示：

(X ∧ Y) ∨ (¬X ∧ Y) ∨ (¬X ∧ ¬Y)

PCNF

PCNF 也被称为主合取范式 (Principal Conjunction normal form)。PCNF 用于执行积之和 (product of sums, POS)。换句话说，一个公式 ? 被称为PCNF，如果 ? 是最大项的积。PCNF 的表达式将如下所示：

例如：假设有三个变量 X、Y 和 Z。使用这些变量的 PCNF 表达式将是(X + Y' + Z) . (X' + Y + Z) . (X + Y + Z')。

其中

'.' 用于表示积是主要运算符。

在学习PCNF（主合取范式）和CNF（合取范式）时，我们总是感到困惑，但这两个术语之间存在差异。CNF（合取范式）的表达式不一定包含所有变量的相同长度。

例如

1. 表达式(X + Y' + Z) . (X' + Y + Z) . (X + Y) 可以被认为是CNF的一个例子，但这个表达式不能是PCNF。
2. 表达式(X + Y' + Z) . (X' + Y + Z) . (X + Y + Z') 可以被认为是CNF和PCNF的例子。

获取给定公式PCNF的方法与我们之前描述的方法相同。

示例：在此示例中，我们有一个表达式 (¬X → Z) ∧ (Y ↔ X)，并且我们需要确定PCNF。

解决方案：(¬X → Z) ∧ (Y ↔ X)

⇔ [¬(¬X ) ∨ Z] ∧ [(Y → X) ∧ (X → Y)]

⇔ (X ∨ Z) ∧ [(¬Y ∨ X) ∧ (¬X ∨ Y)]

⇔ (X ∨ Z ∨ F) ∧ [(¬Y ∨ X ∨ F) ∧ (¬X ∨ Y ∨ F)]

⇔ [(X ∨ Z) ∨ (Y ∧ ¬Y)] ∧ [¬Y ∨ X) ∨ (Z ∧ ¬Z)] ∧ [(¬X ∨ Y) ∨ (Z ∧ ¬Z)]

⇔ (X ∨ Z ∨ Y) ∧ (X ∨ Z ∨ ¬Y) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)

⇔ (X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)

因此，所需的PCNF如下所示：

(X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)

PDNF 和 PCNF 的示例

PCNF 和 PDNF 有各种示例，其中一些如下所示：

示例 1：在此示例中，我们有一个表达式 (X ∧ Y) ∨ (¬X ∧ Z)。 现在我们需要获得 PDNF（主析取范式）和 PCNF（主合取范式）。

解决方案

假设

S ⇔ (X ∧ Y) ∨ (¬X ∧ Z)

⇔ (X ∧ Y ∧ T) ∨ (¬X ∧ Z ∧ T)

⇔ (X ∧ Y ∧ (Z ∨ ¬Z)) ∨ (¬X ∧ Z ∧ (Y ∨ ¬Y))

⇔ (X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Z ∧ Y) ∨ (¬X ∧ Z ∧ ¬Y)

⇔ (X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)

该方程是最小项的和。

因此，我们可以说它表示 PDNF。

现在我们将通过收集 S 中剩余的最小项来确定 PCNF，如下所示：

¬S ⇔ (X ∧ ¬Y ∧ Z) ∨ (X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ ¬Z)

¬(¬S) ⇔ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ Y ∨ Z)

S ⇔ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ Y ∨ Z)

该方程是最大项的积。

因此，我们可以说它表示 PCNF。

示例 2：在此示例中，我们有一个表达式 (X ∨ Z) ∧ (X ∨ ¬Y)。现在我们需要获得 PDNF（主析取范式）和 PCNF（主合取范式）。

解决方案

假设

S ⇔ (X ∨ Z) ∧ (X ∨ ¬Y)

⇔ ((X ∨ Z) ∨ F) ∧ ((X ∨ ¬Y) ∨ F)

⇔ ((X ∨ Z) ∨ (Y ∨ ¬Y)) ∧ ((X ∨ ¬Y) ∧ (Z ∨ ¬Z))

⇔ ((X ∨ Z ∨ Y) ∧ (X ∨ Z ∨ ¬Y) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z)

⇔ ((X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z)

该方程是最大项的积。

因此，我们可以说它表示 PCNF。

现在我们将通过收集 S 中剩余的最大项来确定 PDNF，如下所示：

¬S ⇔ (¬X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ ¬Z)

¬(¬S) ⇔ (X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ Z)

S ⇔ (X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ Z)

该方程是最小项的和。

因此，我们可以说它表示 PDNF。

示例 3：在此示例中，我们有一个表达式 X → (Y ∧ X) ∧ (¬X → (¬Y ∧ ¬Z))。现在我们需要获得 PDNF（主析取范式）和 PCNF（主合取范式）。

解决方案

假设

S: X → (Y ∧ X) ∧ (¬X → (¬Y ∧ ¬Z))

⇔ ¬X ∨ (Y ∧ X) ∧ (X ∨ (¬Y ∧ ¬Z))

⇔ (¬X ∨ Y) ∧ (¬X ∨ X) ∧ (X ∨ ¬Y) ∧ (X ∨ ¬Z)

⇔ (¬X ∨ Y) ∧ T ∧ (X ∨ ¬Y) ∧ (X ∨ ¬Z)

⇔ (¬X ∨ Y) ∧ (X ∨ ¬Y) ∧ (X ∨ ¬Z)

⇔ (¬X ∨ Y ∨ F) ∧ (X ∨ ¬Y ∨ F) ∧ (X ∨ ¬Z ∨ F)

⇔ (¬X ∨ Y ∨ (Z ∧ ¬Z)) ∧ (X ∨ ¬Y ∨ (Z ∧ ¬Z)) ∧ (X ∨ ¬Z ∨ (Y ∧ ¬Y))

⇔ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (X ∨ ¬Z ∨ Y) ∧ (X ∨ ¬Z ∨ ¬Y)

⇔ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (X ∨ Y ∨ ¬Z)

该方程是最大项的积。

因此，我们可以说它表示 PCNF。

现在我们将通过收集 S 中剩余的最大项来确定 PDNF，如下所示：

¬S: (X ∨ Y ∨ Z) ∧ (¬X ∨ ¬Y ∨ Z) ∧ (¬X ∨ ¬Y ∨ ¬Z)

现在我们将对这个方程的两边取否定，然后我们将得到以下结果：

¬(¬S): (¬X ∧ ¬Y ∧ ¬Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (X ∧ Y ∧ Z)

S ⇔ (¬X ∧ ¬Y ∧ ¬Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (X ∧ Y ∧ Z)

该方程是最小项的和。

因此，我们可以说它表示 PDNF。

示例 4：在此示例中，我们有一个表达式 (Y ∨ (X ∧ Z)) ∧ ¬((X ∨ Z) ∧ Y))。现在我们需要获得 PDNF（主析取范式）和 PCNF（主合取范式）。

解决方案

假设

S: (Y ∨ (X ∧ Z)) ∧ ¬((X ∨ Z) ∧ Y))

⇔ (Y ∨ (X ∧ Z)) ∧ (¬(X ∨ Z) ∨ ¬Y)

⇔ (Y ∨ (X ∧ Z)) ∧ ((¬X ∧ ¬Z) ∨ ¬Y)

⇔ (Y ∨ X) ∧ (Y ∨ Z) ∧ (¬X ∨ ¬Y) ∧ (¬Z ∨ ¬Y)

⇔ (X ∨ Y) ∧ (Y ∨ Z) ∧ (¬X ∨ ¬Y) ∧ (¬Y ∨ ¬Z)

⇔ (X ∨ Y ∨ F) ∧ (Y ∨ Z ∨ F) ∧ (¬X ∨ ¬Y ∨ F) ∧ (¬Z ∨ ¬Y ∨ F)

⇔ (X ∨ Y ∨ (Z ∧ ¬Z)) ∧ (Y ∨ Z ∨ (X ∧ ¬X)) ∧ (¬X ∨ ¬Y ∨ (Z ∧ ¬Z)) ∧ (¬Z ∨ ¬Y ∨ (X ∧ ¬X))

⇔ (X ∨ Y ∨ Z) ∧ (Y ∨ Y ∨ ¬Z) ∧ (Y ∨ Z ∨ X) ∧ (Y ∨ Z ∨ ¬X) ∧ (¬X ∨ ¬Y ∨ Z) ∧ (¬X ∨ ¬Y ∨ ¬Z) ∧ (¬Y ∨ ¬Z ∨ X) ∧ (¬Y ∨ ¬Z ∨ ¬X)

⇔ (X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ ¬Z)

该方程是最大项的积。

因此，我们可以说它表示 PCNF。

现在我们将通过收集 S 中剩余的最大项来确定 PDNF，如下所示：

¬S: (X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)

现在我们将对这个方程的两边取否定，然后我们将得到以下结果：

¬(¬S): (¬X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z)

S: (¬X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z)

该方程是最小项的和。

因此，我们可以说它表示 PDNF。

示例 5：在此示例中，我们有一个表达式 X ∨ (¬X → (Y ∨ (¬Y → Z)))。现在我们需要获得 PDNF（主析取范式）和 PCNF（主合取范式）。

解决方案

假设

S: X ∨ (¬X → (Y ∨ (¬Y → Z)))

⇔ X ∨ (¬X → (Y ∨ (Y ∨ Z)))

⇔ X ∨ (X ∨ (Y ∨ (Y ∨ Z)))

⇔ X ∨ (X ∨ (Y ∨ Y) ∨ Z))

⇔ X ∨ (X ∨ Y ∨ Z)

⇔ (X ∨ X) ∨ Y ∨ Z

⇔ X ∨ Y ∨ Z

该方程是最大项的积。

因此，我们可以说它表示 PCNF。

现在我们将通过收集 S 中剩余的最大项来确定 PDNF，如下所示：

¬S: (¬X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ ¬Z)

现在我们将对这个方程的两边取否定，然后我们将得到以下结果：

¬(¬S): (X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ Z)

S: (X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ Z)

该方程是最小项的和。

因此，我们可以说它表示 PDNF。

示例 6：在此示例中，我们有一个表达式 (¬X → Z) ∧ (Y ↔ X)。现在我们需要通过等价来获得 PDNF（主析取范式）和 PCNF（主合取范式）。

解决方案

假设

S: (¬X → Z) ∧ (Y ↔ X)

⇔ (X ∨ Z) ∧ ((Y → X) ∧ (X → Y))

⇔ (X ∨ Z) ∧ (¬Y ∨ X) ∧ (¬X ∨ Y)

⇔ (X ∨ Z) ∧ (X ∨ ¬Y) ∧ (¬X ∨ Y)

⇔ (X ∨ Z ∨ F) ∧ (X ∨ ¬Y ∨ F) ∧ (¬X ∨ Y ∨ F)

⇔ (X ∨ Z ∨ (Y ∧ ¬Y)) ∧ (X ∨ ¬Y ∨ (Z ∧ ¬Z)) ∧ (¬X ∨ Y ∨ (Z ∧ ¬Z))

⇔ (X ∨ Z ∨ Y) ∧ (X ∨ Z ∨ ¬Y) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z)

⇔ (X ∨ Y ∨ Z) ∧ (¬X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z) ∧ (X ∨ ¬Y ∨ ¬Z) ∧ (¬X ∨ Y ∨ ¬Z)

该方程是最大项的积。

因此，我们可以说它表示 PCNF。

现在我们将通过收集 S 中剩余的最大项来确定 PDNF，如下所示：

¬S: (X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z) ∧ (¬X∨ ¬Y ∨ ¬Z)

现在我们将对这个方程的两边取否定，然后我们将得到以下结果：

¬(¬S): (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (X ∧ Y ∧ Z)

S: (¬X ∧ ¬Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (X ∧ Y ∧ Z)

该方程是最小项的和。

因此，我们可以说它表示 PDNF。

示例 7：在此示例中，我们有一个表达式 Y ∨ (X ∧ Z) ∧ ¬((X ∨ Z) ∧ Y)。现在我们需要获得 PDNF（主析取范式）。

解决方案

Y ∨ (X ∧ Z) ∧ ¬((X ∨ Z) ∧ Y)

现在我们将在此表达式中使用德摩根定律，如下所示：

⇔ (Y ∨ (X ∧ Z)) ∧ (¬((X ∨ Z) <∧ Y))

现在我们将再次使用德摩根定律，如下所示：

⇔ (Y ∨ (X ∧ Z)) ∧ ((¬X ∧ ¬Z) ∨ ¬Y))

现在我们将使用扩展分配律，如下所示：

⇔ (Y ∧ (¬X ∧ ¬Z)) ∨ (Y ∧ ¬Y) ∨ ((X ∧ Z) ∧ ¬X ∧ ¬Z) ((X ∧ Z) ∧ ¬Y)

现在我们将使用否定律，如下所示：

⇔ (¬X ∧ Y ∧ ¬Z) ∨ F ∨ (F ∧ Z ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z)

现在我们将再次使用否定律，如下所示：

⇔ (¬X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z)>

因此，所需的PDNF如下所示：

(¬X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z)

示例 8：在此示例中，我们有一个表达式 (¬X ∨ ¬Y) → (X ↔ ¬Y)。现在我们需要获得 PDNF（主析取范式）。

解决方案：(¬X ∨ ¬Y) → (X ↔ ¬Y) 的真值表如下所示：

因此，PCNF 如下所示：

X ∨ Y，以及

PDNF 如下所示：

(X ∧ Y) ∨ (X ∧ ¬Y) ∨ (¬X ∧ Y)