跳到主要内容

离散数学中的数理逻辑

摘 要 （本文章尚未完成）

1 命题逻辑​

1.1 联结词​

  以下“运算结果”一栏分别表示公式在 (p,q)={(⊤,⊤), (⊤,⊥), (⊥,⊤), (⊥,⊥)}(p,q)=\{(\top,\top),\ (\top,\bot),\ (\bot,\top),\ (\bot,\bot)\} 的值.

联结词联结词联结词联结词
⊤=⊤⊤⊤⊤\top=\top\top\top\top⊥=⊥⊥⊥⊥\bot=\bot\bot\bot\botp↔q=⊤⊥⊥⊤p\leftrightarrow q=\top\bot\bot\topp▽q=⊥⊤⊤⊥p\mathop{\triangledown} q=\bot\top\top\bot
p=⊤⊤⊥⊥p=\top\top\bot\bot¬p=⊥⊥⊤⊤\lnot p=\bot\bot\top\topq=⊤⊥⊤⊥q=\top\bot\top\bot¬q=⊥⊤⊥⊤\lnot q=\bot\top\bot\top
p∧q=⊤⊥⊥⊥p\land q=\top\bot\bot\botp↑q=⊥⊤⊤⊤p\uparrow q=\bot\top\top\topp∨q=⊤⊤⊤⊥p\lor q=\top\top\top\botp↓q=⊥⊥⊥⊤p\downarrow q=\bot\bot\bot\top
p→q=⊤⊥⊤⊤p\to q=\top\bot\top\topp↛q=⊥⊤⊥⊥p\nrightarrow q=\bot\top\bot\botp←q=⊤⊤⊥⊤p\gets q=\top\top\bot\topp↚q=⊥⊥⊤⊥p\nleftarrow q=\bot\bot\top\bot

  其它二元联结词可转换为仅用 A={¬,∧}\mathcal A=\{\lnot, \land\} 或仅用 B={¬,∨}\mathcal B=\{\lnot, \lor\} 表示的逻辑公式. A\mathcal A 与 B\mathcal B 间也可以互相转换. 称 A\mathcal A 或 B\mathcal B 为完备联结词集, 因为它们都可以用来表示所有联结词. 其他联结词的表示方法如下:

联结词等价表示方法联结词等价表示方法
蕴含p→q=¬p∨qp\to q=\lnot p\lor q非蕴含p↛q=¬(p→q)p\nrightarrow q=\lnot(p\to q)
双条件(p∧q)∨(¬p∧¬q)(p\land q)\lor (\lnot p\land \lnot q)异或p▽q=¬(p▽q)p\mathop{\triangledown} q=\lnot(p\mathop{\triangledown} q)
与非p↑q=¬(p∧q)p\uparrow q=\lnot(p\land q)或非p↓q=¬(p∨q)p\downarrow q=\lnot(p\lor q)

1.2 运算律及对偶式​

  联结词集 A∪B={¬,∧,∨}\mathcal A\cup \mathcal B=\{\lnot,\land,\lor\} 具有以下运算律:

运算律表达式运算律表达式
对合律¬¬p=p\lnot \lnot p=p吸收律p∧(p∨q)=pp\land(p\lor q)=p
p∨(p∧q)=pp\lor(p\land q)=p
幂等律p∧p=pp\land p=p
p∨p=pp\lor p=p		de Morgan 律¬(p∧q)=¬p∨¬q\lnot(p\land q)=\lnot p\lor \lnot q
¬(p∨q)=¬p∧∨q\lnot(p\lor q)=\lnot p\land \lor q
结合律(p∧q)∧r=p∧(q∧r)(p\land q)\land r=p\land(q\land r)
(p∨q)∨r=p∨(q∨r)(p\lor q)\lor r=p\lor(q\lor r)		同一律p∧⊤=pp\land \top=p
p∨⊥=pp\lor \bot=p
交换律p∧q=q∧pp\land q=q\land p
p∨q=q∨pp\lor q=q\lor p		零律p∧⊥=⊥p\land \bot=\bot
p∨⊤=⊤p\lor \top=\top
分配律p∧(q∨r)=p∧q∨p∧rp\land(q\lor r)=p\land q\lor p\land r
p∨(q∧r)=p∨q∧p∨rp\lor(q\land r)=p\lor q\land p\lor r		否定律p∧¬p=⊥p\land \lnot p=\bot
p∨¬p=⊤p\lor \lnot p=\top

  对于仅包含联结词 {¬,∧,∨}\{\lnot,\land,\lor\} 的逻辑式 f(p1,p2,⋯ ,pn)f(p_1,p_2,\cdots,p_n), 定义其对偶式 f∗f^* 为将 ff 中的 ∧\land 与 ∨\lor 互换, ⊤\top 与 botbot 互换后的式子. 例如

f=p∧¬q∨⊤,f∗=p∨¬q∧⊥f=p\land \lnot q\lor \top,\quad f^*=p\lor \lnot q\land \bot

原式与对偶式有关系

¬f(p1,p2,⋯ ,pn)=f(¬p1,¬p2,⋯ ,¬pn)\lnot f(p_1,p_2,\cdots,p_n)=f(\lnot p_1,\lnot p_2,\cdots,\lnot p_n)

1.3 合取范式与析取范式​

合取范式 合取范式有格式 A1∧A2∧⋯∧AnA_1\land A_2\land \cdots \land A_n, 其中 AiA_i 为命题或其否定的析取式.

析取范式 析取范式有格式 B1∨B2∨⋯∧BnB_1\lor B_2\lor \cdots \land B_n, 其中 BiB_i 为命题或其否定的合取式.

  对于一个一般的逻辑公式, 先将其化为仅含 {¬,∧,∨}\{\lnot,\land,\lor\} 的逻辑式, 然后使用 de Morgan 律将所有 ¬\lnot 移到命题前, 最后重复使用分配律与交换律即可将其转换为范式.

小 项 对于命题集 {p1,p2,⋯ ,pn}\{p_1,p_2,\cdots,p_n\}, 称这些命题或其否定 (但是对于每一个命题 pip_i, 原命题与其否定必须存在一个) 的合取称为一个小项, 记为 mm. 如对于命题集 {p1,p2,p3}\{p_1,p_2,p_3\},

m110(2)=m6(10)=p1∧p2∧¬p3m_{110_{(2)}}=m_{6_{(10)}}=p_1\land p_2\land \lnot p_3

大 项 与上述定义相似, 称命题或其否定 (必出现其一) 的析取称为一个大项, 记为 MM. 如

M110(2)=M6(10)=p1∨p2∨¬p3M_{110_{(2)}}=M_{6_{(10)}}=p_1\lor p_2\lor \lnot p_3

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

  1. 任二不同小项的合取为假, 任二不同大项的析取为真, 即
mi∧mj=⊥, Mi∨Mj=⊤, i≠jm_i\land m_j=\bot,\ M_i\lor M_j=\top,\ i\neq j
  1. 全体小项的析取为真, 全体大项的合取为假, 即
⋀i=02n−1mi=⊤, ⋁i=02n−1Mi=⊥\bigwedge_{i=0}^{2^n-1} m_i=\top,\ \bigvee_{i=0}^{2^n-1} M_i=\bot
  1. 对于给定指派的命题集 {p1,p2,⋯ ,pn}\{p_1,p_2,\cdots,p_n\}, 有且仅有与其逻辑值相同下标的那一个小项 m∗m^* 为 ⊤\top 和那一个大项 M∗M^* 为 ⊥\bot. 其它的小项均为 ⊥\bot, 大项均为 ⊤\top.

主析取范式 任一公式均可以化为小项的析取, 称为主析取范式. 一般的析取范式的合取项可能不含某一命题, 只需将其与缺失的那一个命题的零律 (p∨¬p)(p\lor \lnot p) 作合取, 然后使用分配律展开即可. 主析取范式可以简记为

mi1∨mi2∨⋯∨min=⋁(i1,i2,⋯ ,in)m_{i_1}\lor m_{i_2}\lor \cdots \lor m_{i_n}=\bigvee (i_1,i_2,\cdots ,i_n)

主合取范式 将任一公式化为大项的合取的形式. 若一般合取范式的析取项不含某一命题, 只需与 (p∧¬p)(p\land \lnot p) 作析取, 然后展开即可. 主合取范式可写作

Mi1∧Mi2∧⋯∧Min=⋀(i1,i2,⋯ ,in)M_{i_1}\land M_{i_2}\land \cdots \land M_{i_n}=\bigwedge (i_1,i_2,\cdots ,i_n)

  化主范式除使用等价变换外, 也可使用真值表法. 即只需枚举所有 2n2^n 种情况下公式的运算结果, 然后化为主范式即可. 例如某公式 f(p,q)f(p,q) 当且仅当 (p,q)∈{(⊤,⊤),(⊥,⊥)}(p,q)\in\{(\top,\top),(\bot,\bot)\} 时为 ⊤\top, 此时它的主范式为

(p∧q)∨(¬p∧¬q)=⋁(0,3),(p∨¬q)∧(¬p∨q)=⋀(1,2)(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 约束变元和自由变元​

  量词所指导的变元(约束变元)如 ∀xP(x), ∃xP(x)\forall xP(x),\ \exists xP(x) 其后的逻辑公式 P(x)P(x) 称为变元 xx 的作用域. 如果谓词公式 α\alpha 中出现了 nn 个未被任何量词指导的变元(自由变元), 则称 α\alpha 为 nn 元谓词公式.

换 名 即是将谓词公式 α\alpha 中的某个约束变元更换符号表示.

代 入 即是将谓词公式 α\alpha 中的某个自由变元更换符号表示. 该操作可以相当于给自由变元赋予一个具体的值.

2.2 谓词逻辑的演算​

穷 举 如果约束变元的取值是有限个, 则可以将谓词写作穷举形式

∀xP(x)=⋀xP(x),∃xP(x)=⋁xP(x)\forall xP(x)=\bigwedge_xP(x),\quad \exists xP(x)=\bigvee_xP(x)

量词与逻辑非 ¬∀xP(x)=∃x¬P(x), ¬∃xP(x)=∀x¬P(x)\lnot\forall xP(x)=\exists x\lnot P(x),\ \lnot\exists xP(x)=\forall x\lnot P(x)

作用域的扩张与收缩 若作用域为谓词公式与逻辑公式的合取或析取, 则量词作用域可以收缩, 反之亦可. 即

∀x(P(x)∧q)=∀xP(x)∧q\forall x\Big(P(x)\land q\Big)=\forall xP(x)\land q

上式 ∀\forall 可换为 ∃\exists, ∧\land 可换为 ∨\lor. 于是有以下推论:

∀x(P(x)→q)=∃xP(x)→q,∀x(p→Q(x))=p→∀xQ(x)\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.