**未完成**【离散数学】离散数学中的数理逻辑
摘 要 （本文章尚未完成）
1 命题逻辑
1.1 联结词
以下“运算结果”一栏分别表示公式在 $(p,q)=\{(\top,\top),\ (\top,\bot),\ (\bot,\top),\ (\bot,\bot)\}$ 的值.
| 联结词 | 联结词 | 联结词 | 联结词 |
|---|---|---|---|
| $\top=\top\top\top\top$ | $\bot=\bot\bot\bot\bot$ | $p\leftrightarrow q=\top\bot\bot\top$ | $p\mathop{\triangledown} q=\bot\top\top\bot$ |
| $p=\top\top\bot\bot$ | $\lnot p=\bot\bot\top\top$ | $q=\top\bot\top\bot$ | $\lnot q=\bot\top\bot\top$ |
| $p\land q=\top\bot\bot\bot$ | $p\uparrow q=\bot\top\top\top$ | $p\lor q=\top\top\top\bot$ | $p\downarrow q=\bot\bot\bot\top$ |
| $p\to q=\top\bot\top\top$ | $p\nrightarrow q=\bot\top\bot\bot$ | $p\gets q=\top\top\bot\top$ | $p\nleftarrow q=\bot\bot\top\bot$ |
其它二元联结词可转换为仅用 $\mathcal A=\{\lnot, \land\}$ 或仅用 $\mathcal B=\{\lnot, \lor\}$ 表示的逻辑公式. $\mathcal A$ 与 $\mathcal B$ 间也可以互相转换. 称 $\mathcal A$ 或 $\mathcal B$ 为完备联结词集, 因为它们都可以用来表示所有联结词. 其他联结词的表示方法如下:
| 联结词 | 等价表示方法 | 联结词 | 等价表示方法 |
|---|---|---|---|
| 蕴含 | $p\to q=\lnot p\lor q$ | 非蕴含 | $p\nrightarrow q=\lnot(p\to q)$ |
| 双条件 | $(p\land q)\lor (\lnot p\land \lnot q)$ | 异或 | $p\mathop{\triangledown} q=\lnot(p\mathop{\triangledown} q)$ |
| 与非 | $p\uparrow q=\lnot(p\land q)$ | 或非 | $p\downarrow q=\lnot(p\lor q)$ |
1.2 运算律及对偶式
联结词集 $\mathcal A\cup \mathcal B=\{\lnot,\land,\lor\}$ 具有以下运算律:
| 运算律 | 表达式 | 运算律 | 表达式 |
|---|---|---|---|
| 对合律 | $\lnot \lnot p=p$ | 吸收律 | $p\land(p\lor q)=p$ $p\lor(p\land q)=p$ |
| 幂等律 | $p\land p=p$ $p\lor p=p$ | de Morgan 律 | $\lnot(p\land q)=\lnot p\lor \lnot q$ $\lnot(p\lor q)=\lnot p\land \lor q$ |
| 结合律 | $(p\land q)\land r=p\land(q\land r)$ $(p\lor q)\lor r=p\lor(q\lor r)$ | 同一律 | $p\land \top=p$$p\lor \bot=p$ |
| 交换律 | $p\land q=q\land p$ $p\lor q=q\lor p$ | 零律 | $p\land \bot=\bot$ $p\lor \top=\top$ |
| 分配律 | $p\land(q\lor r)=p\land q\lor p\land r$ $p\lor(q\land r)=p\lor q\land p\lor r$ | 否定律 | $p\land \lnot p=\bot$ $p\lor \lnot p=\top$ |
对于仅包含联结词 $\{\lnot,\land,\lor\}$ 的逻辑式 $f(p_1,p_2,\cdots,p_n)$, 定义其对偶式 $f^*$ 为将 $f$ 中的 $\land$ 与 $\lor$ 互换, $\top$ 与 $bot$ 互换后的式子. 例如
$$f=p\land \lnot q\lor \top,\quad f^*=p\lor \lnot q\land \bot$$
原式与对偶式有关系
$$\lnot f(p_1,p_2,\cdots,p_n)=f(\lnot p_1,\lnot p_2,\cdots,\lnot p_n)$$
1.3 合取范式与析取范式
合取范式 合取范式有格式 $A_1\land A_2\land \cdots \land A_n$, 其中 $A_i$ 为命题或其否定的析取式.
析取范式 析取范式有格式 $B_1\lor B_2\lor \cdots \land B_n$, 其中 $B_i$ 为命题或其否定的合取式.
对于一个一般的逻辑公式, 先将其化为仅含 $\{\lnot,\land,\lor\}$ 的逻辑式, 然后使用 de Morgan 律将所有 $\lnot$ 移到命题前, 最后重复使用分配律与交换律即可将其转换为范式.
小 项 对于命题集 $\{p_1,p_2,\cdots,p_n\}$, 称这些命题或其否定 (但是对于每一个命题 $p_i$, 原命题与其否定必须存在一个) 的合取称为一个小项, 记为 $m$. 如对于命题集 $\{p_1,p_2,p_3\}$,
$$m_{110_{(2)}}=m_{6_{(10)}}=p_1\land p_2\land \lnot p_3$$
大 项 与上述定义相似, 称命题或其否定 (必出现其一) 的析取称为一个大项, 记为 $M$. 如
$$M_{110_{(2)}}=M_{6_{(10)}}=p_1\lor p_2\lor \lnot p_3$$
小项和大项具有以下性质:
- 任二不同小项的合取为假, 任二不同大项的析取为真, 即
$$m_i\land m_j=\bot,\ M_i\lor M_j=\top,\ i\neq j$$ - 全体小项的析取为真, 全体大项的合取为假, 即
$$\bigwedge_{i=0}^{2^n-1} m_i=\top,\ \bigvee_{i=0}^{2^n-1} M_i=\bot$$ - 对于给定指派的命题集 $\{p_1,p_2,\cdots,p_n\}$, 有且仅有与其逻辑值相同下标的那一个小项 $m^*$ 为 $\top$ 和那一个大项 $M^*$ 为 $\bot$. 其它的小项均为 $\bot$, 大项均为 $\top$.
主析取范式 任一公式均可以化为小项的析取, 称为主析取范式. 一般的析取范式的合取项可能不含某一命题, 只需将其与缺失的那一个命题的零律 $(p\lor \lnot p)$ 作合取, 然后使用分配律展开即可. 主析取范式可以简记为
$$m_{i_1}\lor m_{i_2}\lor \cdots \lor m_{i_n}=\bigvee (i_1,i_2,\cdots ,i_n)$$
主合取范式 将任一公式化为大项的合取的形式. 若一般合取范式的析取项不含某一命题, 只需与 $(p\land \lnot p)$ 作析取, 然后展开即可. 主合取范式可写作
$$M_{i_1}\land M_{i_2}\land \cdots \land M_{i_n}=\bigwedge (i_1,i_2,\cdots ,i_n)$$
化主范式除使用等价变换外, 也可使用真值表法. 即只需枚举所有 $2^n$ 种情况下公式的运算结果, 然后化为主范式即可. 例如某公式 $f(p,q)$ 当且仅当 $(p,q)\in\{(\top,\top),(\bot,\bot)\}$ 时为 $\top$, 此时它的主范式为
$$(p\land q)\lor (\lnot p\land \lnot q)=\bigvee(0,3),\quad (p\lor \lnot q)\land (\lnot p\lor q)=\bigwedge(1,2)$$
2 谓词逻辑
2.1 约束变元和自由变元
量词所指导的变元(约束变元)如 $\forall xP(x),\ \exists xP(x)$ 其后的逻辑公式 $P(x)$ 称为变元 $x$ 的作用域. 如果谓词公式 $\alpha$ 中出现了 $n$ 个未被任何量词指导的变元(自由变元), 则称 $\alpha$ 为 $n$ 元谓词公式.
换 名 即是将谓词公式 $\alpha$ 中的某个约束变元更换符号表示.
代 入 即是将谓词公式 $\alpha$ 中的某个自由变元更换符号表示. 该操作可以相当于给自由变元赋予一个具体的值.
2.2 谓词逻辑的演算
穷 举 如果约束变元的取值是有限个, 则可以将谓词写作穷举形式
$$\forall xP(x)=\bigwedge_xP(x),\quad \exists xP(x)=\bigvee_xP(x)$$
量词与逻辑非 $\lnot\forall xP(x)=\exists x\lnot P(x),\ \lnot\exists xP(x)=\forall x\lnot P(x)$
作用域的扩张与收缩 若作用域为谓词公式与逻辑公式的合取或析取, 则量词作用域可以收缩, 反之亦可. 即
$$\forall x\Big(P(x)\land q\Big)=\forall xP(x)\land q$$
上式 $\forall$ 可换为 $\exists$, $\land$ 可换为 $\lor$. 于是有以下推论:
$$\forall x\Big(P(x)\to q\Big)=\exists xP(x)\to q,\quad \forall x\Big(p\to Q(x)\Big)=p\to \forall xQ(x)$$
上式 $\forall$ 与 $\exists$ 互换后结论仍成立.
作用域的拆分
参考文献
[1] 左孝凌, 李为, 刘永才. 离散数学[M]. 上海: 上海科学技术文献出版社, 1982.
[2] 朱保平, 陆建峰, 金忠, 张琨. 离散数学[M]. 北京: 清华大学出版社, 2019.