摘 要 (本文章尚未完成)

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$$

小项和大项具有以下性质:

  1. 任二不同小项的合取为假, 任二不同大项的析取为真, 即
    $$m_i\land m_j=\bot,\ M_i\lor M_j=\top,\ i\neq j$$
  2. 全体小项的析取为真, 全体大项的合取为假, 即
    $$\bigwedge_{i=0}^{2^n-1} m_i=\top,\ \bigvee_{i=0}^{2^n-1} M_i=\bot$$
  3. 对于给定指派的命题集 $\{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.

标签: 数理逻辑, 离散数学

添加新评论