离散数学: 数理逻辑

Posted on Edited on In , Word count in article: 1.9k Reading time ≈ 7 mins.

数理逻辑

命题逻辑

基本概念

  • 命题：只有真、假两种状态的陈述语句，在命题逻辑里，原子命题不提供任何除真假以外的信息，这也导致命题逻辑的局限性
  • 逻辑等价(p ≡ q)：表示p等价于q，即有相同的真值表
  • 否定(¬p)：表示p的否定
  • 析取(p ∨ q)：表示p或者q
  • 合取(p ∧ q)：表示p并且q
  • 异或(p ⊕ q)：表示p异或q
  • 条件(p → q)：表示若p，则q
    • 从定义上看，只有当p = T ∧ q = F时违反了语句，故其它情况均人为定义为T
  • 双条件(p ↔︎ q)：表示p当且仅当q，与p ⊙ q等价
    • 若p ↔︎ q为永真式，称p ≡ q或p ⇔ q
  • 对条件语句p → q：
    • 反命题：¬p → ¬q，即对输入取反，真值表上下颠倒
    • 逆命题：q → p，真值表上下颠倒
    • 逆否命题：¬q → ¬p，和原命题等价
  • 优先级：¬ >  ∧  >  ∨  >  →  > ↔︎

与其它逻辑系统的对应

命题逻辑 逻辑代数 位运算符 集合论 自然语言描述
¬p p̄ $\rm NOT$ 否定/取反
∨ + $\rm OR$ ∪ 析取/或/逻辑和/并
∧ · $\rm AND$ ∩ 合取/与/逻辑积/交
p → q p蕴涵q
p ⇒ q p永真蕴涵q/p是q的充分条件
p ↔︎ q ⊙ $\rm XNOR$ p当且仅当q/p同或q
p ⇔ q p是q的充要条件
| $\rm NAND$ 与非
↓ $\rm NOR$ 或非

基本等价公式

  • 满足交换律、结合律、分配律
  • 德⋅摩根律：
    • ¬(p∧q) ≡ ¬p ∨ ¬q
    • ¬(p∨q) ≡ ¬p ∧ ¬q
  • 支配律：p ∨ T ≡ T、p ∧ F ≡ F
  • 自等律：p ∨ p ≡ p、p ∧ p ≡ p
  • 恒等律：p ∨ F ≡ p、p ∧ T ≡ p
  • 否定律：p ∨ ¬p ≡ T、p ∧ ¬p ≡ F
  • 吸收律：
    • p ∨ (p∧q) ≡ p
    • 由分配律，p ∧ (p∨q) ≡ p，也即上式的对偶
  • 消解律：
    • (p∧q) ∨ (¬p∧r) ≡ q ∧ r
    • 取对偶，(p∨q) ∧ (p∨r) ≡ q ∨ r

条件命题的等价

  • p → q ≡ ¬q → ¬p ≡ ¬p ∨ q
  • (p→q) ∧ (p→r) ≡ p → (q∧r)
  • (p→r) ∧ (q→r) ≡ (p∨q) → r
  • (p→q) ∨ (p→r) ≡ p → (q∨r)
  • (p→r) ∨ (q→r) ≡ (p∧q) → r

逻辑函数

对偶规则

  • 恒等式通常成对出现，称其为对偶，以Fd表示F的对偶函数，对一个恒等式两边取对偶不影响恒等性
  • Fd ≢ F(一般)、(Fd)d ≡ F
  • 对偶函数由原函数交换逻辑与、逻辑或，交换0和1得到

反演规则

  • 一个函数的反函数可以由原函数交换逻辑与、逻辑或，交换0和1，同时原变量变反变量、反变量变原变量而得，其中反变量特指单个变量上的非号，跨两个及以上变量的非号不能动
  • 同样可借F̄来求F

谓词逻辑

命题逻辑的局限

命题逻辑的最小单元是命题，所以命题逻辑无法表示那些不真不假的语句，因为它们没有指定变量的值

因此也无法从若干简单命题中得到新命题，例如亚里士多德三段论：

  • 三个原子命题：p:所有人都要死、q:苏格拉底是人、r:所以苏格拉底要死
  • 根据逻辑推理，由p且q一定可以得到r，即要证明(p∧q) ⇒ r
  • 尽管p ∧ q = T，在命题逻辑的系统里，仍然可以把F指派给r
  • 换句话说就是，给命题赋予真值的同时，也掩盖掉了具体的信息，你只知道p是对的，q是对的，然后无法得知任何其它信息，也就无法得知r的真值
  • 如果能变成假言三段论的形式，是可以通过命题逻辑表示的，但原子命题已经是最小的命题了

谓词逻辑解决这样的事情：提取出命题中的信息，并提供一套符号用于产生新的、适用更广的命题

谓词与量词

通过谓词可以从这些语句中生成命题，谓词逻辑允许对命题进行更细的划分

  • 个体：命题所描述的对象，约定用小写字母表示
  • 谓词：命题赋予主体的属性或动作，约定用大写字母P、Q、R表示
  • 命题的谓词形式：由谓词和若干个体常元组合成P(a1,a2,⋯,an)的形式
    • 称P(x1,x2,⋯,xn)为一个n元谓词，其中x为个体变元，称它能够表示的所有个体的集合为它的个体域
  • 量词：通过量词来限定个体域在谓词中的不确定性，例如所有、至少等
    • 全称量词(∀x)：表达所有
    • 存在量词$(\exist x)$：表达存在
    • 存在唯一量词$(\exist\ !\ x)$：表达存在唯一
    • 后接谓词P(x)表示该量词的辖域

谓词逻辑公式

  • 德·摩根律：
    • $\neg(\exist x)P(x)\equiv (\forall x)\neg P(x)$
    • $\neg (\forall x)P(x)\equiv(\exist x)\neg P(x)$
  • 量词的辖域扩张：
    • (∀x)P(x) ∨ Q ≡ (∀x)(P(x)∨Q)，其中Q不含变元
    • 同理，将析取换为合取、将全称量词换位存在量词也成立
    • $(\forall x)(P(x)\rightarrow Q)\equiv(\exist x)P(x)\rightarrow Q$，将∀和$\exist$互换同理
      • 证明：左式$=(\forall x)(\neg P(x)\vee Q)=(\forall x)\neg P(x)\vee Q=\neg(\exist x)P(x)\vee Q=$右式
    • (∀x)(Q→P(x)) ≡ Q → (∀x)P(x)，将∀换成$\exist$同理
  • 量词的分配律：
    • ∀x对∧、$\exist x$对∨满足分配律
    • ∀x对∨、$\exist x$对∧不满足分配律，只满足$(\forall x)P(x)\vee (\forall x)Q(x)\Rightarrow(\forall x)(P(x)\vee Q(x))\\(\exist x)(P(x)\wedge Q(x))\Rightarrow(\exist x)P(x)\wedge (\exist x)Q(x)$
  • 永真蕴涵式：$(\exist x)P(x)\rightarrow(\forall x)Q(x)\Rightarrow(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\forall x)P(x)\rightarrow(\forall x)Q(x)$

嵌套量词

  • 嵌套量词的顺序：
    • $(\forall x)(\forall y)\equiv (\forall y)(\forall x)\\(\exist x)(\exist y)\equiv (\exist y)(\exist x)$
    • $(\forall x)(\forall y)\Rightarrow(\exist x)(\forall y)\Rightarrow(\forall y)(\exist x)\Rightarrow(\exist x)(\exist y)\\(\forall x)(\forall y)\Rightarrow(\exist y)(\forall x)\Rightarrow(\forall x)(\exist y)\Rightarrow(\exist x)(\exist y)$
  • 嵌套量词的否定：
    • 层层套用德·摩根律，结果为∀和$\exist$互换，非号在最里层，例如：
    • $\neg(\forall x)(\exist y)P(x,y)\equiv(\exist x)(\forall y)\neg P(x,y)$

推理规则

命题逻辑规则

  • P：引入一个前件
  • T：引用公式S
  • CP：P ∧ Q → R ≡ P → (Q→R)
  • 假言推理：表示为永真式(p∧(p→q)) → q
  • 假言三段论：由一个大条件和一个小条件可得出，表示为永真式((p→q)∧(q→r)) → (p→r)
  • 利用永真式化简命题，其实就是在使用规则T

谓词逻辑规则

  • 谓词逻辑是命题逻辑的推广，同样可使用命题逻辑的推理规则
  • 全称特指$(\rm US)$：(∀x)P(x) ⇒ P(y)
  • 存在特指$(\rm ES)$：$(\exist x)P(x)\Rightarrow P(a)$
  • 存在推广$(\rm EG)$：$P(y)\Rightarrow(\exist x)P(x)$，y属于x的个体域
  • 全称推广$(\rm UG)$：P(y) ⇒ (∀x)P(x)，x属于y的个体域