初等逻辑入门科普介绍简介

# 命题逻辑

# 命题

• 具有真假意义的句子称作命题，命题是一个陈述句，用 P,Q,R 等字母表示。

• 一个命题如果不能再分解为更简单的命题，则称之为简单命题，或原子命题。

  否则，如果它可以分解成更简单的命题以及一些 “逻辑联结词”，则称之为复合命题。显然，复合命题的真值由组成其的简单命题和逻辑联结词决定。

# 逻辑联结词

• 否定$\neg$，析取$\vee$，合取$\wedge$，蕴含$\rightarrow$，等价$\leftrightarrow$，

# 合式公式 (well formed formula, wff)（简称公式）

• wff 的归纳定义：

  • 命题变元以及命题常元 0，1 是合成公式。
  • 如果 A，B 是合成公式，则$\neg A,(A\vee B),(A\wedge B),(A\rightarrow B),(A\leftrightarrow B)$ 是合成公式。
  • 任何合成公式通过有限次以上两种方式得到。

• 逻辑联结词优先级的确定：$\neg,\vee,\wedge,\rightarrow,\leftrightarrow$（从左到右优先级降低）

• 对公式 G 中出现的每个命题变元指定一个真值 1 或 0，则得到该公式中命题变元的一个真值组合，称之为对公式 G 的一个真值指派（或解释）。公式 A 在指派 I 下的真值可记为$A^I$

  • 指派可以用

    $$\tilde{P_i}=\left\{ \begin{aligned} P_i , \delta_i=1\\ \neg P_i,\delta_i=0 \\ \end{aligned} \right.$$

    表示，例如指定 (P, Q, R)=(1, 0, 1)，即可记为$(P,\neg Q,R)$

• 如果公式 A 在任意指派下均为真，则称其为永真式（或重言式），如果均为假，则称为永假式（或矛盾式）。如果至少有一个指派使 A 为真，则称 A 为可满足的。

• 代入原则：对一个永真式，将其中的命题变元用其他 wff 替换掉，则结果仍为永真式。

# 等价式

• 若公式 A 和 B 在任意指派 I 下真值总相同，则称 A,B 等价，记为$A=B$。注意 A 和 B 中出现的变量不完全一样也可能是等价的，譬如$P\vee \neg P=1$, 做指派时需要指派所有在 A,B 中出现的命题变元。

• 等价是一个等价关系。

• $A=B$ 当且仅当$A\leftrightarrow B$ 永真。

• 一些重要等价式

  • $P\rightarrow Q=\neg P\vee Q=\neg Q\rightarrow \neg P$
  • $P\rightarrow(Q\rightarrow R)=P\wedge Q\rightarrow R=Q\rightarrow(P\rightarrow R)$
  • $(P\rightarrow R)\wedge(Q\rightarrow R)=(P\vee Q)\rightarrow R$
  • $P\leftrightarrow Q=(P\rightarrow Q)\wedge(Q\rightarrow P)=(P\wedge Q)\vee(\neg P\wedge \neg Q)$

• 代入原则：若 A=B，则用任意公式代换掉 A，B 中命题变元得到的公式 A’=B’。

• 设$A_1$ 是公式$A$ 的一部分，且$A_1$ 构成公式，则称其为 A 的子公式。用一个等价于$A_1$ 的公式$B_1=A_1$ 去替换$A_1$，得到的新公式等价于 A。

# 对偶式

• 把公式 A 中的$\vee,\wedge,0,1$ 分别对应替换为$\wedge,\vee,1,0$，得到的公式$A^*$ 称为 A 的对偶式。将 A 中的命题变元替换（$P换为\neg P$），得到的公式记为$A^-$。

• $\neg(A^*)=(\neg A)^*,\neg(A^-)=(\neg A)^-$，对任何公式都有\neg A=A^

• 若$A=B$，则$A^*=B^*$。

# 范式

• 命题变元及其否定统称为文字。一些文字的合取称为基本合取式（或短语），一些文字的析取称为基本析取式（或子句）。特别地，一个单独的文字既是短语又是子句。

• 有限个短语的析取（$A_1\vee A_2\vee...\vee A_n$）称为析取范式，有限个子句的合取$B_1\wedge B_2\wedge...\wedge B_n$ 称为合取范式。特别地，一个单独的短语或子句既是析取范式又是合取范式。

• 对于任意命题公式，都存在等价于它的析取范式和合取范式，获得范式步骤如下：

  • 利用基本等价式去掉$\rightarrow,\leftrightarrow$
  • 使用德摩根率和双重否定率，将所有否定词$\neg$ 都放在命题变元前形成文字
  • 使用分配律得到范式

• 范式很容易判断公式是否永真或永假。

• 设$P_1,P_2,...P_n$ 为 n 个命题变元，则$\tilde{P_1}\wedge \tilde{P_2}\wedge...\wedge \tilde{P_n}$ 称之为由$P_1,...,P_n$ 生成的极小项，其中$\tilde{P_i}=P_i或\neg P_i$。可以通过一个二进制数描述这个极小项，例如$P_1\wedge\neg P_2\wedge P_3=m_{101}$，就是 1 表示对应位置不取非，0 表示对应位置取非。显然地，当且仅当真值指派等于这个二进制数时 ($P_1=1,P_2=0,P_3=1$)，该极小项取真。

• n 个变元生成的极小项有$2^n$ 个，每个极小项只有一个真值指派可使其为真。

• 如果公式 A 中所有命题变元是$P_1,...P_n$，且它的析取范式中，每个短语都是$P_1,...,P_n$ 生成的极小项，则称该析取范式为 A 的主析取范式。

• 对任意公式 A，都存在唯一一个与其等价的主析取范式。

  • 例：$P\vee (R\wedge Q)=[P\wedge (Q\vee \neg Q)\wedge (Q\vee \neg Q)]\vee[R\wedge Q\wedge(P\wedge \neg P)]$, 就是把不足的项补齐。

• 完全对称定义有最大项，主析取合式，和最小项和主析取范式性质一样。

# 推理理论

• 当前提的真蕴含结论的真时，称前提和结论之间有可推导性关系，这种推理称为演绎推理。

• 对公式 A，B 如果对于任意指派 I，当 A 为 1 时的指派 B 也为 1，则称 A 蕴涵 B，或称 B 是 A 的逻辑结果，记为$A\Rightarrow B$。A 称为蕴涵式前件，B 称为蕴涵式后件。显然，$A\Rightarrow B$ 当且仅当$A\rightarrow B$ 永真。

• 蕴涵是一个反对称关系。

• 设$\Gamma(A_1,A_2,...,A_n)$ 是一个公式集合，B 是公式，且$A_1\wedge A_2\wedge ...\wedge A_n\Rightarrow B$，则称 B 是$\Gamma(A_1,A_2,...,A_n)$ 的逻辑结果，记为$\Gamma\Rightarrow B,或A_1,A_2,...,A_n\Rightarrow B$

• 基本蕴涵式

  • $P\wedge Q\Rightarrow P\quad P\Rightarrow P\vee Q$

  • $\neg P\Rightarrow P\rightarrow Q\quad Q\Rightarrow P\rightarrow Q$

  • $\neg(P\rightarrow Q)\Rightarrow P\quad \neg(P\rightarrow Q)\Rightarrow\neg Q$

• 代入原则：若$A\Rightarrow B$，则用任意公式带换掉 A，B 中的命题变元，仍有$A'\Rightarrow B'$。实际上就是$A\rightarrow B$ 永真式的代入原则$A'\rightarrow B'$ 仍永真。

• 设$\Gamma$ 是一个公式集合，从$\Gamma$ 推出公式 A 的一个演绎推理是一个有序公式序列:$A_1,A_2,...,A_k,A$，其中，$A_i$ 满足以下条件之一：

  • $A_i\in\Gamma$（前提引入规则，记为 P）
  • $A_i是一些A_j,j<i$ 的逻辑结果（结论引用规则，记为$C(j_1)(j_2)...(j_n)$），特别地，由$A,A\rightarrow B$ 可引入公式 B 是一种特殊的结论引用，称为分离规则，因为其重要，记作 MP。
  • $A_i$ 是永真式（永真式引入规则，记为 T）

• 当存在一个从公式集合$\Gamma$ 推出公式 A 的演绎推理时，称$\Gamma$ 可演绎出 A，记为$\Gamma\models A$ 其中$\Gamma$ 中的公式称为前提，A 称为演绎结果或推论。

  $\Gamma\models A$ 当且仅当$\Gamma\Rightarrow A$

• 若$\Gamma\cup\{B\}\Rightarrow C$ 则$\Gamma\Rightarrow B\rightarrow C$（附加条件规则，记为 CP）

• 演绎推理三段式：序号 + 公式 + 依据（P, C (1)(2), T, MP, CP），其中每个公式都是真的。（前提为真的条件下）

• 设$A_1,A_2,...,A_n$ 是一串公式，若$A_1\wedge A_2\wedge ...\wedge A_n$ 是可满足的，则称这些公式是相容的，否则称其为不相容的或不一致的。

  反证法：$\Gamma\Rightarrow A当且仅当\Gamma\cup\{\neg A\}不相容$

• $A_1,A_2,...,A_n$ 是不相容的当且仅当存在公式 R 使得$A_1\wedge A_2\wedge ...\wedge A_n\Rightarrow R\wedge \neg R$

# 谓词逻辑

# 谓词与量词

• 一个命题的主语部分通常由我们所讨论的对象担任，称为个体，用小写字母表示。个体所在的范围称为论域或个体域，用 D 表示。最大的论域（相当于全集）称为全总论域。

  命题的谓语部分一般称作谓词，用大写字母表示。譬如 P (a) 表示 “a 是学生”，a 是主语，P 是谓语。

• 主语的位置也可由个体变元 x，y，z 填补。使得命题中去除主语个体只保留重要的谓语。个体变元可以由论域中任一具体个体替换，此时得到一个普通命题。

• 定义：$D^n(指有n个个体的论域)到\{0,1\}$ 的函数称为 n 元谓词或 n 元命题函数。谓词可以是多元的。

• 量词：对于任意$\forall$，存在$\exists$。使用量词前必须确定论域。

  全称量词后的特性谓词一般作为蕴涵联结词的前件，而存在量词后的特性谓词则一般为合取式中的一项。

  例如：M (x):x 是人，P (x):x 会死。

  所有人都会死:$\forall x(M(x)\rightarrow P(x))$，有人会死:$\exists x(M(x)\wedge P(x))$

• 当论域是有限集时，谓词可以被基本联结词代替。$\forall xP(x)=P(a_1)\wedge...\wedge P(a_n)$，存在时变为析取。

# 合式公式

• 四种符号：

  • 常量符号（个体符号）：a, b, c, …
  • 变量符号：x, y, z,…
  • 函数符号：f, g, h,…（函数不同于谓词在于值域不同，函数的值域是论域，谓词的值域是 {0, 1})
  • 谓词符号：P, Q,R,…

• 谓词逻辑中的项可递归定义为：

  • 常量符号，变量符号是项
  • 若$t_1,...,t_n$ 是项，则$f(t_1,...,t_n)$ 是项
  • 通过有限次以上两个操作得到的是项

• 若$t_1,...,t_n$ 是项，则$P(t_1,...,t_n)$ 是原子公式。

• 谓词逻辑中的合式公式（wff）定义为：

  • 原子公式是合式公式
  • 如果 A，B 是合成公式，则$\neg A,(A\vee B),(A\wedge B),(A\rightarrow B),(A\leftrightarrow B)$ 是合成公式。
  • 若 A 是合式公式，则$\forall xA,\exists xA$ 是合式公式
  • 用以上三种方式进行有限次生成的是合式公式

• 若 A 是公式，且$\forall xA_1或\exists xA_1$ 是 A 的子公式，则 A 中相应于$A_1$ 的一段称为$\forall x或\exists x$ 的辖域。

• 对于公式 A 中的个体变元 x，若它出现在某个量词$\forall x或\exists x$ 的辖域之内，则称这次出现为约束的，否则是自由的。一个个体变元，如果至少有一次是约束出现的则称其为约束变元，如果至少有一次是自由出现的，则称其为自由变元。可以同时是约束变元和自由变元。

• 换名规则：将每个个体变元在量词中的指导变元和该量词辖域里的出现都换成新的个体变元。（$\forall xP(x)变为\forall y P(y)$）

  ​ 所用新的个体变元不能再原式中出现过。

  任一公式在经过换名后，总可以使任意约束变元不是自由变元。

• 谓词公式 A 的一个解释 I，对论域 D 和常量符号，函数符号，谓词符号依下列规则进行指定：

  • 指定 D 是一非空集合
  • 对每个常量符号指定 D 中一个元素
  • 对每个函数符号指定函数的映射关系
  • 对每个谓词符号，指定一个同元谓词（谓词不变，指示词换名）

  若公式 A 不含自由变元，则经过解释 I 后已经成为一个命题。如果含有自由变元，则还需要对自由变元指派为论域中的元素。

• 设 A 是一个谓词公式，I 是 A 的一个解释，在 I 的基础上指定 A 中的自由变元为 D 中的元素，称为对公式 A 在解释 I 下的一个赋值。

• 设 A 是一个谓词公式，若对任意解释 I 和赋值 v，A 的真值总为 1，则称 A 是有效的。否则称 A 为非有效的。

• 代入原则：A 是一个永真命题公式，用任意谓词公式去替换 A 中的命题变元，所得还是一个永真的命题公式。

# 等价与范式

• 谓词公式的等价，即为在任意解释和赋值下，真值均相同的两个公式。

• 等价式代入原则：A 和 B 是一对等价的命题公式，用任意谓词替换其中的命题变元，得到的还是一对等价的命题公式、

• 量词否定形：$\neg\forall xA(x)=\exists x\neg A(x),\neg \exists xA(x)=\forall x\neg A(x)$

• 重要的等价式：

  • $\forall x(A(x)\vee B)=\forall xA(x)\vee B$ (存在，合取都成立)
  • $\forall x(A(x)\wedge B(x))=\forall xA(x)\wedge\forall x B(x)=\forall x\forall y(A(x)\wedge B(y))$（注意析取不成立）
  • $\exists x(A(x)\vee B(x))=\exists xA(x)\vee \exists xB(x)=\exists x\exists y(A(x)\vee B(y))$（注意合取不成立）

• 形如$Q_1x_1Q_2x_2...Q_nx_nM$ 的式子称为前束范式，其中$Q_i$ 为量词 “存在 “或 “对于任意 “，$x_i$ 为个体变元，M 中不含量词（称为母式）。若将 M 中的原子公式及其否定视为文字，则若 M 是析取范式时，该式称为前束析取范式，M 是合取范式时，该式称为前束合取范式。

• 对于任意谓词公式 A，都存在与其等价的前束范式。

  • 去除$\rightarrow,\leftrightarrow$
  • 将$\neg$ 放在原子公式之前
  • 将所有量词提到公式最前面（必要时换名）

• 只有量词一样时可以交换顺序。例如：对于任意 x，存在 y 使得 x+y=0 为永真，但存在 y，使得对于任意 x 有 x+y=0 就假了。

  $\exists x\forall y A(x,y)\Rightarrow \forall y\exists x A(x,y)$，反之推不出来。

• skolem 范式：将一个前束范式进行如下操作消去所有存在量词：

  • 若该存在量词左侧没有对于任意量词，则直接删除，并且找一个新的常量符号替换该量词后面跟的个体变元
  • 若该存在量词左侧有任意量词，则用一个函数（自变量为所有左侧任意量词后面的个体变元）替换该量词后面的个体变元

  例如：$\exists x\forall y\forall z\exists u\exists v f(x,y,z,u,v)$ 的 Skolem 范式为$\forall y\forall zf(c,y,z,f(y,z),g(y,z))$

• 公式 A 永假当且仅当其 Skolem 范式在任意解释和赋值下永假。

# 推理理论

• 谓词公式中的蕴涵类似的，有$A\Rightarrow B$ 当且仅当$A\rightarrow B$ 有效。

• 蕴涵式代入原则：若命题公式 A，B 满足 A 蕴涵 B，则用任意谓词公式替换 A，B 中的命题变元仍有 A‘蕴涵 B’。

• 推理理论：

  • 全称量词消去律 ($\forall -$)：由$\forall x A(x)$ 引入$A(a),A(x),A(y)$ 条件：y 不在 A (x) 中约束出现，c 为固定个体
  • 全称量词引入律 ($\forall +$)：由$A(x)$ 引入$\forall x A(x)$ 条件：在任意解释和赋值下 A (x) 真值与 x 无关
  • 存在量词消去律 ($\exists -$)：由$\exists x A(x)$ 引入$A(A)$ 条件：$\exists xA(x)$ 中无自由变元，c 是一固定个体
  • 存在量词引入律 ($\exists +$)：由$A(x)或A(a)$ 引入$\exists x A(x)$ 条件：x 不在 A© 中出现

# 关于线性递推求解

$$a_n=c_1a_{n-1}+...+c_ka_{n-k}+F(n)$$

首先求齐次线性递推：

$$a_n=c_1a_{n-1}+...+c_ka_{n-k}$$

特征方程：

$$r^n=c_1r^{n-1}+...+c_kr^{n-k}$$

注意，每有一个 m 重特征根，结果需要多$(b_0+b_1n+...b_{m-1}n^{m-1})r^n$ 一项

$$a_n=\sum(b_0+b_1n+...b_{m-1}n^{m-1})r^n$$

• 若特征根方程有虚数，说明数列成循环数列。

然后考虑特解。若$F(n)$ 形如以下形式

$$F(n)=(s_0+s_1n+...+s_pn^p)t^n$$

则，特解为：

$$(b_0+b_1n+...+b_pn^p)t^n，若t不为特征值\\ n^m(b_0+b_1n+...+b_pn^p)t^n,若t为m重特征值$$

最后结果为

$$a_n=\sum(b_0+b_1n+...b_{m-1}n^{m-1})r^n+(b_0+b_1n+...+b_pn^p)t^n\\ 或\sum(b_0+b_1n+...b_{m-1}n^{m-1})r^n+n^m(b_0+b_1n+...+b_pn^p)t^n$$

例：

$$a_n=6a_{n-1}-9a_{n-2}+3^n\\ 齐次递推a_n=6a_{n-1}-9a_{n-2}的解为a_n=(p+qn)3^n,而F(n)=3^n对应特解为a_n=n^2C3^n\\ 将特解代入递推式:n^2C3^n=6(n-1)^2C3^{n-1}-9(n-2)^2C3^{n-2}+3^n解得C=\frac{1}{2}\\ 所以a_n=(p+qn)3^n+\frac{1}{2}n^23^n\\ 若a_1=a_2=1,有p=\frac{14}{9}，q=-\frac{31}{18}\\ 此时，a_n=(\frac{14}{9}-\frac{31}{18}n)3^n+\frac{1}{2}n^23^n$$

• 注意：解特解时，待定的系数 ($C$) 应代入递推式保证恒成立，而解齐次通解时，待定的系数$(p,q)$ 应代入初始项保证成立。