Logic Course in 2019 Spring

第一讲：命题逻辑

命题逻辑的语法

定义1.1(字母表)

  1. 命题符：$P_0,P_1,P_2,\cdots,P_n,\cdots,n\in \mathbb{N}$, 记$PS=\{P_n|n\in\mathbb{N}\}$
  2. 联结词：$\neg$, $\wedge$, $\vee$, $\rightarrow$
  3. 辅助符：$($, $)$

定义1.2(命题)

  1. 命题符为命题
  2. 若$A$, $B$为命题, 则$(\neg A)$, $(A\wedge B)$, $(A\vee B)$, $(A\rightarrow B)$为命题
  3. 命题仅限于此
  4. BNF范式表达：$\varphi\Coloneqq P|(\neg\varphi)|(\varphi_1\wedge\varphi_2)|(\varphi_1\vee\varphi_2)|(\varphi_1\rightarrow\varphi_2),P\in PS$
  5. 闭包法也可定义命题
    令$C_\neg$, $C_\wedge$, $C_\vee$, $C_\rightarrow$为所有字母表符号串之集上的函数：
    $$C_\neg(A)=(\neg A)$$
    $$C_*(A,B)=(A*B)$$
    这里$*\in \{\wedge, \vee, \rightarrow\}$

定义1.3(命题集)
所有命题的集合$PROP$是满足以下条件的最小集合：

  1. $PS\subseteq PROP$
  2. 若$A\in PROP$, 则$C_\neg(A)\in PROP$
  3. 若$A,B\in PROP$, 则$C_\wedge(A,B)$, $C_\vee(A,B)$, $C_\rightarrow(A,B)\in PROP$
  4. 即$PROC$为函数$C_\neg$, $C_\wedge$, $C_\vee$, $C_\rightarrow$下$PS$的归纳闭包

引理1.4(括号引理)
若$A$为命题, 则$A$中所有左括号的个数等于右括号的个数

引理1.5
$A\in PROP$等价于存在有穷序列$A_0,A_1,\cdots,A_n$使$A$为$A_n$且对任何$i\leq n$,

  • 或(a) $A_i\in PS$
  • 或(b) 存在$k<i$使$A_i$为$\neg A_k$
  • 或(c) 存在$k,l<i$使$A_i$为$(A_k*A_l)$, 这里$*$为$\wedge$, $\vee$, $\rightarrow$之一
    以上序列$A_0,A_1,\cdots,A_n$被称为$A$的构造序列

结构归纳

  • 每个命题皆有构造过程, 但构造过程不一定唯一
  • 若$A_0,A_1,\cdots,A_n$为$A$的最短构造过程, 则称$n$为$A$的构造长度
  • 对$A$的结构作归纳证明一些性质, 事实上是对$A$的构造长度作归纳, 而这是自然数上的归纳

命题的语义

什么是命题的语义
对于任意的赋值, $v:PS\rightarrow\{T,F\}$, 定义一个解释
$$\hat{v}:PROP\rightarrow\{T,F\}$$

定义1.6
令真值集$B=\{T,F\}$

  • 联结词$\neg$被解释为一元函数$H_\neg:B\rightarrow B$
  • 联结词$*$被解释为二元函数$H_*:B^2\rightarrow B$
    这里$*\in \{\wedge, \vee, \rightarrow\}$
  • 定义为真值表, 此处略

定义1.7(命题的语义)

  • $v$为一个赋值, 指它为函数$v:PS\rightarrow B$
    从而对任何命题符$P-i$, $v(P_i)$为$T$或$F$

  • 对于任何赋值$v$, 定义$\hat{v}：PROP\rightarrow B$如下：

    • $\hat{v}(P_n)=v(P_n)$, $n\in\mathbb{N}$
    • $\hat{v}(\neg A)=H_\neg(\hat{v}(A))$
    • $\hat{v}(A * B)=H_*(\hat{v}(A), \hat{v}(B))$, 这里$*\in \{\wedge, \vee, \rightarrow\}$

      确实应该是$H_*(\hat{v}(A),\hat{v}(B))$

  • 引理1.8
    设$A$为命题, $v_1$, $v_2$为赋值, 若$v_1\upharpoonright FV(A)=v_2\upharpoonright FV(A)$, 即对于$P\in FV(A)$, $v_1(P)=v_2(P)$, 则$\hat{v_1}(A)=\hat{v_2}(A)$

  • 定义1.9
    设$A$为命题, $v$为赋值

    1. $v$满足$A$, 记为$v\vDash A$, 指$\hat{v}(A)=T$
    2. $A$为永真式(tautology), 记为$\vDash A$, 指对任何$v$有$\hat{v}(A)=T$
    3. $A$可满足, 指有$v$使$v\vDash A$
    4. 设$\Gamma$为命题集, $A$为$\Gamma$的语义结论, 记为$\Gamma\vDash A$, 指对所有$v$, 若对任何$B\in \Gamma$有$\hat{v}(B)=T$, 则$\hat{v}(A)=T$

  • 定义1.10
    设$A$为命题, $FV(A)=\{Q_1, \cdots, Q_n\}$. $n$元函数$H_A:B^n\to B$定义如下: 对于任何$(a_1,\cdots,a_n)\in B^n$, $H_A(a_1,\cdots, a_n)=\hat{v}(A)$, 这里赋值$v$满足$v(Q_i)=a_i(1\leq i\leq n)$. 下面称$f:B^n\to B$为$n$元真值函数, 称$H_A$为$A$定义的真值函数

  • 定义1.11

    1. 命题$A$为析合范式($\vee\wedge$-nf)指$A$呈形$\bigvee_{i=1}^m(\bigwedge_{k=1}^nP_{i,k})$, 这里$P_{i,k}$为命题符或命题符的否定(即呈形$\neg P_i$)
    2. 命题$A$为合析范式($\wedge\vee$-nf)指$A$呈形$\bigwedge_{i=1}^l(\bigvee_{k=1}^nQ_{i,k})$, 这里$Q_{i,k}$为命题符或命题符的否定(即呈形$\neg Q_i$)
      其中$\bigwedge_{k=1}^n$为$(\cdots(((B_1\wedge B_2)\wedge B_3)\cdots\wedge B_n)\cdots)$的简写; $\bigvee_{k=1}^n$为$(\cdots(((B_1\vee B_2)\vee B_3)\cdots\vee B_n)\cdots)$的简写

  • 定理1.12

    1. 存在命题$A$, 其为$\vee\wedge$-nf使$f=H_A$
    2. 存在命题$A’$, 其为$\wedge\vee$-nf使$f=H_{A’}$

  • 定义1.13

    1. 设$A, B$为命题, $A$与$B$逻辑等价, 记为$A\simeq B$, 指对任何赋值$v$,
      $$v\vDash A\textrm{ iff }v\vDash B$$

  • 命题1.14

    1. $A\simeq A$
    2. 若$A\simeq B$, 则$B\simeq A$
    3. 若$A\simeq B$且$B\simeq C$, 则$A\simeq C$
    4. 若$A\simeq B$, 则$(\neg A)\simeq (\neg B)$
    5. 若$A_1\simeq B_1$且$A_2\simeq B_2$, 则$(A_1* A_2)\simeq(B_1*B_2)$, 这里$*\in\{\wedge,\vee,\rightarrow\}$

  • 命题1.15
    设$FV(A\wedge B)=\{Q_1, \cdots, Q_n\}$且$H_A:B^n\rightarrow B$, $H_B:B^n\rightarrow B$. 我们有$A\simeq B\textrm{ iff }H_A=H_B$

  • 命题1.16
    若$A$为命题，则存在$\wedge\vee$-nf$B$和$\vee\wedge$-nf$B’$使$A\simeq B$且$A\simeq B’$, 这时称$B$和$B’$分别为$A$的$\wedge\vee$-nf和$\vee\wedge$-nf

自然推理系统及其性质

  • 定义1.17
    一个矢列是一个二元组$(\Gamma, \Delta)$, 记为$\Gamma\vdash\Delta$, 这里$\Gamma, \Delta$为命题的有穷集合(可以为空), 称$\Gamma$为前件, $\Delta$为后件. 命题逻辑的自然推理系统$G’$由以下公里和规则组成, $\Gamma, \Delta, \Lambda, \Theta$表示任何命题有穷集合, $A, B$表示任何命题, $\Lambda, A, \Delta$为集合$\Lambda\cup\{A\}\cup\Delta$的缩写

    • 公理: 左右两边有一样的
    • 规则:
      • 否定调换左右
      • 左或右且分为两个
      • 左且右或逗号隔开
      • 箭头看作有否定的或
      • $$\textrm{Cut}: \frac{\Gamma\vdash\Lambda,A\quad\Delta,A\vdash\Theta}{\Gamma,\Delta\vdash\Lambda,\Theta}$$
        规则的上矢列被称为前提, 下矢列被称为结论. $G’$系统中的规则被称为推理规则, 规则中被作用的命题被称为主命题, 而不变的命题被称为辅命题

  • 定义1.18
    设$\Lambda$为$\{A_1,A_2,\cdots, A_m\}$, $\Delta$为$\{B_1,B_2,\cdots, B_n\}$

    1. $\Lambda\vdash\Delta$有反例(falsifiable)指存在赋值$v$使$v\vDash(A_1\wedge \cdots\wedge A_m)\wedge(\neg B_1\wedge\cdots\wedge\neg B_n)$, 这时称$v$反驳$\Lambda\vdash\Delta$
    2. $\Lambda\vdash\Delta$有效(valid)指对任何赋值$v$, $v\vDash(A_1\wedge\cdots\wedge A_m)\rightarrow(B_1\vee B_2\vee\cdots\vee B_n)$, 这时称$v$满足$\Lambda\vdash\Delta$
    3. $\Lambda\vdash\Delta$有效也被记为$\Lambda\vDash\Delta$
    4. 当$m=0$时, $\vdash B_1,\cdots B_n$有反例指$(\neg B_1\wedge\cdots\wedge\neg B_n)$可满足; $\vdash B_1,\cdots B_n$有效指$(B_1\vee \cdots\vee B_n)$永真
    5. 当$n=0$时, $A_1,\cdots A_n\vdash$有反例指$(A_1\wedge \cdots\wedge A_m)$可满足; $A_1,\cdots A_n\vdash$有效指$(A_1\wedge \cdots\wedge A_m)$不可满足
    6. 约定$\{\}\vdash\{\}$非有效

  • 命题1.19
    $\Gamma\vdash\Delta$有效$\textrm{ iff }$$\Gamma\vdash\Delta$无反例

  • 引理1.20
    对于$G’$系统中的每条异于$\textrm{Cut}$的规则:

    1. 赋值$v$反驳规则的结论$\textrm{ iff }$$v$至少反驳规则的一个前提
    2. $v$满足规则的结论$\textrm{ iff }$$v$满足规则的所有前提
    3. 每个前提有效$\textrm{ iff }$结论有效

  • 定义1.21
    设$\Gamma\vdash\Lambda$为矢列, 树$T$为$\Gamma\vdash\Lambda$的证明树指: (见书本图片)

  • 定义1.22
    设$\Gamma\vdash\Lambda$为矢列, $\Gamma\vdash\Lambda$可证(provable)指存在$\Gamma\vdash\Lambda$的证明树

  • 定理1.23($G’$的soundness)
    若$\Gamma\vdash\Delta$在$G’$中可证, 则$\Gamma\vdash\Delta$有效

  • 定理1.24($G’$的completeness)
    若$\Gamma\vdash\Delta$有效, 则$\Gamma\vdash\Delta$在$G’$中可证. 这就是$G’$的完全性

  • 系1.25
    $\Gamma\vdash\Delta$可证$\textrm{ iff }$$\Gamma\vdash\Delta$有效

  • 系1.26
    若$\Gamma\vdash\Delta$在$G’$中可证, 则$\Gamma\vdash\Delta$在$G’$中由一个无$\textrm{Cut}$证明

  • 定理1.27(compactness)
    设$\Gamma$为命题的集合, 若$\Gamma$的任何有穷子集可满足, 则$\Gamma$可满足