析取范式和合取范式

发布时间：2023-05-19

析取范式和合取范式

在逻辑学中，析取范式和合取范式分别是命题逻辑中某些命题的标准化形式，它们是由命题变量和逻辑运算符组成的组合式。

一、析取范式

1、什么是析取范式？

在命题逻辑中，析取范式是由若干个含有变量的析取式进行“与”运算而得到的命题。

2、析取范式的含义

如果一个命题是由多个命题“或”起来的，则我们可以将其表示为一个含有变量的析取式。 例如：

((p1 ∨ p2) ∧ (p1 ∨ ¬p2) ∧ (¬p1 ∨ p2))

这个式子可以表示为：如果 p1 与 p2 中至少有一个成立，那么命题就成立。

3、如何将一个命题转化为它的析取范式？

我们可以使用以下步骤将一个命题转化为它的析取范式：

  1. 将命题中的“与”运算符转化为“或”运算符；
  2. 根据“或”运算符的结合律，将多个变量的“或”运算符进行合并；
  3. 根据德摩根定律，对含有“非”运算符的变量进行变形，得到不含有“非”运算符的项。 例如，对于命题 (p → q) ∧ (¬p ∨ r)，我们可以按以下步骤转化为析取范式：
  4. 将命题中的“与”运算符转化为“或”运算符：
(p → q) ∧ (¬p ∨ r) = (¬p ∨ q) ∧ (p ∨ r)
  1. 根据“或”运算符的结合律，将多个变量的“或”运算符进行合并：
(¬p ∨ q) ∧ (p ∨ r) = (¬p ∧ p) ∨ (¬p ∧ r) ∨ (q ∧ p) ∨ (q ∧ r)
  1. 根据德摩根定律，对含有“非”运算符的变量进行变形，得到不含有“非”运算符的项：
(¬p ∧ p) ∨ (¬p ∧ r) ∨ (q ∧ p) ∨ (q ∧ r) = (q ∧ p) ∨ (¬p ∧ r)

4、示例代码

function toDNF(expr) {
    // 将“与”运算符转化为“或”运算符
    expr = expr.replace(/∧/g, '∨');
    // 对含有“非”运算符的变量进行变形
    let matches = null;
    let re = /¬?\w+/g;
    while ((matches = re.exec(expr)) !== null) {
        let variable = matches[0];
        if (variable.charAt(0) === '¬') {
            let pos = expr.indexOf(variable);
            let start = pos - 1;
            let length = variable.length + 1;
            if (pos === 0) {
                expr = expr.substring(length);
            } else if (expr.charAt(start) === '∨') {
                expr = expr.substring(0, start) + expr.substring(start + length);
            } else if (expr.charAt(start) === '∧') {
                let left = expr.substring(0, start);
                let right = expr.substring(pos + length);
                expr = left + '¬' + variable.substring(1) + '∨' + '¬(' + variable.substring(1) + ')' + right;
            }
        }
    }
    // 将多个变量的“或”运算符进行合并
    expr = expr.split('∨').filter(function (item, pos, self) {
        return self.indexOf(item) === pos;
    }).join('∨');
    return expr;
}
console.log(toDNF('(p → q) ∧ (¬p ∨ r)'));

二、合取范式

1、什么是合取范式？

在命题逻辑中，合取范式是由若干个含有变量的合取式进行“或”运算而得到的命题。

2、合取范式的含义

如果一个命题是由多个命题“与”起来的，则我们可以将其表示为一个含有变量的合取式。 例如：

((p1 ∧ ¬p2) ∨ (¬p1 ∧ p2))

这个式子可以表示为：如果 p1 与 ¬p2 同时成立，或者 ¬p1 与 p2 同时成立，那么命题就成立。

3、如何将一个命题转化为它的合取范式？

我们可以使用以下步骤将一个命题转化为它的合取范式：

  1. 将命题中的“或”运算符转化为“与”运算符；
  2. 根据“与”运算符的结合律，将多个变量的“与”运算符进行合并；
  3. 根据德摩根定律，对含有“非”运算符的变量进行变形，得到不含有“非”运算符的项。 例如，对于命题 (p → q) ∧ (¬p ∨ r)，我们可以按以下步骤转化为合取范式：
  4. 将命题中的“或”运算符转化为“与”运算符：
(p → q) ∧ (¬p ∨ r) = (¬p ∨ q) ∧ (p ∨ r)
  1. 根据“与”运算符的结合律，将多个变量的“与”运算符进行合并：
(¬p ∨ q) ∧ (p ∨ r) = (¬p ∨ q ∨ r) ∧ (p ∨ q ∨ r)
  1. 根据德摩根定律，对含有“非”运算符的变量进行变形，得到不含有“非”运算符的项：
(¬p ∨ q ∨ r) ∧ (p ∨ q ∨ r) = ((¬p ∨ q ∨ r) ∧ p) ∨ ((¬p ∨ q ∨ r) ∧ (¬p))

4、示例代码

function toCNF(expr) {
    // 将“或”运算符转化为“与”运算符
    expr = expr.replace(/∨/g, '∧');
    // 对含有“非”运算符的变量进行变形
    let matches = null;
    let re = /¬?\w+/g;
    while ((matches = re.exec(expr)) !== null) {
        let variable = matches[0];
        if (variable.charAt(0) === '¬') {
            let pos = expr.indexOf(variable);
            let start = pos - 1;
            let length = variable.length + 1;
            if (pos === 0) {
                expr = expr.substring(length);
            } else if (expr.charAt(start) === '∨') {
                let left = expr.substring(0, start);
                let right = expr.substring(pos + length);
                expr = left + '¬' + variable.substring(1) + '∧' + '¬(' + variable.substring(1) + ')' + right;
            } else if (expr.charAt(start) === '∧') {
                expr = expr.substring(0, start) + expr.substring(start + length);
            }
        }
    }
    // 将多个变量的“与”运算符进行合并
    expr = expr.split('∧').filter(function (item, pos, self) {
        return self.indexOf(item) === pos;
    }).join('∧');
    return expr;
}
console.log(toCNF('(p → q) ∧ (¬p ∨ r)'));

三、小结

在命题逻辑中，析取范式和合取范式是两种标准化的命题表达方式。通过将一个命题转化为它的析取范式或合取范式，我们可以快速简化命题，从而更方便地进行推理和计算。在实际编程中，我们可以编写相关函数，帮助我们将命题转化为它的标准化表达形式。

推荐文章