数理逻辑

什么是逻辑？ 逻辑示例 有2个红色帽子，3个黑色帽子。 三个人站成一纵队，各戴一顶帽子，每人仅能看到前面人帽子颜色。 问？ 第三个人帽子颜色？ 回答：不知道！ 第二个人帽子颜色？ 第一个人帽子颜色？ 回答：知道！ 问题：第一个人帽子颜色是什么？为什么？ 知道 不知道 不知道 第一个人推理： （1）如果第一人和第二人都是红色帽子，则第三人知道自己帽子颜色为黑色。 （2）因为第三人不知道自己帽子颜色为黑色，所以，第一人和第二人不都是红色帽子。 （3）如果第一是红色帽子，则第二人知道自己帽子颜色为黑色。 （4）因为第二人不知道自己帽子颜色为黑色，所以，第一不是红色帽子。 （5）第一是黑色帽子。 1 2 3

推理： 如果第一人和第二人都是红色帽子，则第三人知道自己帽子颜色为黑色。 因为第三人不知道自己帽子颜色为黑色，所以，第一人和第二人不都是红色帽子。 如果第一是红色帽子，则第二人知道自己帽子颜色为黑色。 因为第二人不知道自己帽子颜色，所以，第一不是红色帽子。 第一人是黑色帽子。 第一个人推理： （1）如果第一人和第二人都是红色帽子，则第三人知道自己帽子颜色为黑色。 （2）因为第三人不知道自己帽子颜色为黑色，所以，第一人和第二人不都是红色帽子。 （3）如果第一是红色帽子，则第二人知道自己帽子颜色为黑色。 （4）因为第二人不知道自己帽子颜色为黑色，所以，第一不是红色帽子。 （5）第一是黑色帽子。

聪明的囚徒 古希腊有个国王，处死囚徒总是用两种方式：砍头或绞刑。 这个国王自恃聪明地做出了这样一种规定，让囚徒自己选择 死的方式：囚徒可以说一句话，并且这句话是马上可以验证 其真假的。 如果囚徒说的是真话，那么处以绞刑；如果囚徒说的是假话， 那么处以砍头。 许多囚徒或者是因为说了假话而被砍头或者因为说了真话而 被处以绞刑。

在日常语言中，凡是可以决定真假的陈述句叫做命题。但是有一类陈述句却就无法判定其真假。 有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出了一句巧妙的话，结果使这个国王不管按照哪种方法处死他，都违背自己的决定，最后只得将他放了。试问：这囚徒说的是句什么话？ 在日常语言中，凡是可以决定真假的陈述句叫做命题。但是有一类陈述句却就无法判定其真假。 这就是悖论：一个语句Q，如果从Q为真，可以推出Q为假；而从Q为假，可以推出Q为真。 聪明的囚徒所说的话，就应该是这样的悖论，使得国王无论怎么处置他都会带来矛盾。

这句话就是“国王决定砍我的头”。 如果国王决定砍他的头，则他说的是真话，因此按国王规定的处死方法（讲真话应处以绞刑），他应该受绞刑。这样就造成了国王的规定同国王决定的处死方法相矛盾。 同样如果国王决定让受绞刑，则他说的是假话，因此按国王规定的处死方法（讲假话应砍头），他应该砍头。这样也造成了国王的规定同国王决定的处死方法相矛盾。 无论如何，国王都将处于进退维谷的处境，因此只好免这个囚徒一死，将他放掉。

逻辑的分类 1、辩证逻辑： 2、形式逻辑： 表现形式 数理逻辑研究对象 即：演绎性的形式逻辑 研究思维的内涵即研究思维内在语义规律，属于哲学范畴。 2、形式逻辑： 研究思维的外延即研究思维外部表现的规律。 可分为演绎性推理与归纳性推理。 表现形式 数理逻辑研究对象 即：演绎性的形式逻辑

什么是数理逻辑 数理逻辑的研究对象 用数学方法研究形式逻辑中推理规律的一种理论。 宏观：证明论，模型论，递归论，集合论 狭义：形式逻辑推理规则

数理逻辑的研究方法 采用数学的方法研究演绎性推理形式逻辑的规律。 方法 引进一套符号体系的方法 引入形式语言，形成形式系统 因此数理逻辑又称为符号逻辑 优点 表达简介 概括程度高 推理方便 便于分析研究

命题逻辑 一、命题与命题联结词 命题的定义：凡是能分辨其真假的语句称为命题。 一个语句如果能再进一步分解成更为简单的语句，且又 是一个命题，则称此命题称为原子命题。 原子命题是命题演绎的最基本单位； 命题是逻辑的最基本的概念。

说明： 1）命题是表示判断的语句，判断是对事物具有或不具有某性质的客观描述，因此命题必须是陈述句，不能是祈使句，感叹句，疑问句等； 例：

2）命题必须能分辨真假，符合事实就是真，否则就是假， 二者必居其一，下面不是命题： 3）经典逻辑中，命题是真还是假是命题本事固有的性质， 与人们是否能够判断命题的真假无关。因此下面是命题， 虽然现在还不能判定其真假。

4）一个命题的值称为真值，真值包括“真”和“假”两个值； 一般用T(True)或者“1”表示真， 用F(False)或者“0”表示假 5）命题一般用大写英文字母表示（当然不可用T或F表 示） 6）一个抽象的真命题可用T（或true或者1）表示，一个 抽象的假命题可用F（false或者0）表示。

前面就说明过：有些命题可以进一步分解成原子命题。 2、命题联结词 一些简单的命题，可通过特定的联结词构成命题。 说明：原子命题和复合命题都是命题 常用的5个命题联结词 并且（合取） 或者（析取） 否定 蕴含 等价 前面就说明过：有些命题可以进一步分解成原子命题。

（1）并且（合取） Q T F P 运算表

或者（析取） Q T F P

（3）否定 P T F

（4）蕴含 → Q T F P 只考虑“形式”

（5）等价 Q T F P

组合命题 由原子命题经命题联结词可构成各种形式的复合命题，复合命题可看作是经以上提到的5种运算而得出。

排斥或 小李去并且小王不去 小李不去并且小王去

2、命题变元与命题公式 定义1：以“真”、“假”为其变域的变元称为命题变元，用P,Q,R……表示，它也可以简称为命题。 由命题经命题联结词可构成命题演算公式，亦可叫命题公式或公式，它可定义如下： 定义2： 归纳定义

遍历： 1、前序遍历 2、中序遍历 3、后序遍历

T、F分别看作0和1 例： T F 子公式

10.3 重言式 P,Q在任意指派下，真值表都相等

10.4命题逻辑的基本等式 交换律 结合律 注意： →不满足交换律、结合律

否定深入 变元等同

常值与变元的联结 联结词归化

命题运算规则

基本规则：

例1：

例2： 例3：

10.5 对偶定理 ↔和→可变换为∧,∨,¬ ¬不变

顺序也相同

10.6命题逻辑的基本蕴含式及推理规则

推理规则 ⊢

则由蕴含重言式可得到许多推理规则： 𝑃,𝑄⊢𝑃 𝑃,𝑄⊢𝑃∧𝑄 𝑃,𝑄⊢𝑄 ¬𝑃,𝑃⋁𝑄⊢𝑄 𝑃⊢𝑃⋁𝑄 𝑃,𝑃→𝑄⊢𝑄 𝑄⊢𝑃⋁𝑄 𝑃→𝑄,𝑄→𝑅⊢𝑃→𝑅 𝑃→𝑄,𝑅→𝑆⊢𝑃∧𝑅→Q ∧ S 𝑃⋁𝑄,𝑃→𝑅,𝑄→𝑅⊢𝑅 𝑃,𝑄⊢𝑃∧𝑄 ¬𝑃,𝑃⋁𝑄⊢𝑄 𝑃,𝑃→𝑄⊢𝑄 ¬𝑄,𝑃→𝑄⊢¬𝑃

例：已知有如下常识： 解：设 ⊢ （1）吸烟者必吸入大量尼古丁 （2）吸入大量尼古丁必引发很多疾病 请问如下结论正确吗？ 吸烟者必会得很多病。 解：设 ⊢

否定符号只出现一次，范围只是其后面的变元 10.7范式 研究如何把一个命题公式划归为一个标准形式 1、析取范式 否定符号只出现一次，范围只是其后面的变元

2 合取范式

也称主析取范式 可理解为条件最严格、条件的范围最小 可用二进制数来表示

由构造方法可以看出：特异析取范式不一定是最简化的形式（经常不是）

缺少P或其否定

例：设公式A的真值表如下： P Q R A T F

真值表中对应的值都是T，则相应的最小项都在公式中 公式的特异析取范式唯一（不考虑顺序）

4、特异合取范式

这里一共有三个变量P,Q,R

因为要求出每个人的情况，即P,Q,R都必须出现在析取项中，因此需要求出公式的特异析取范式

例：设有A,B,C,D四个人进行跑步比赛，有三个观众甲，乙，丙分别对名次做预测： 甲：C第一，B第二 乙：C第一，D第三 丙：A第二，D第四 比赛结束，发现甲，乙，丙的预测都只对了一半， 问实际名次如何（不考虑并列名次的情形）。

有两项是F，其余两项的析取一定是T

A、C、D顺序确定了，则B也确定

10.8 命题联结词的扩充与归约 1、扩充 P Q T F

P Q T F P Q T F

𝑃↛ Q P Q T F 𝑃↛ Q 𝑃↛ Q

P Q 命题联结词 T u1 F u2 u3 u4

下面我们将16种运算结果列出来 永真 永假 P Q 否定 否定 并且 与非 P Q 1 2 3 4 5 6 7 8 T F 或者 或非 蕴含 蕴含否定 等价 异或 蕴含 蕴含否定 P Q 9 10 11 12 13 14 15 16 T F

除常量T和F，以及命题变元本身外，一共只有9个命题联结词。 根据上表，可以得到： 联结词1、2表示永真T和永假F； 联结词3、4表示命题变元P和Q； 联结词5、6表示“否定”联结词； 联结词7表示“并且”联结词； 联结词8表示“谢佛（与非）”联结词； 联结词9表示“或者”联结词； 联结词10表示“魏泊（或非）”联结词； 联结词11、15表示“蕴含”联结词； 联结词12、16表示“蕴含否定”联结词； 联结词13表示“等价”联结词； 联结词14表示“异或”联结词； 除常量T和F，以及命题变元本身外，一共只有9个命题联结词。

命题联结词的归约

例 问题背景：一次警方接到报警，在某地发生严重的刑事案件，当警方赶到犯罪现场时有5人死亡，仅剩甲、乙二人仍在殊死搏斗。审讯时甲乙双方都指责对方是罪犯，自己是受害者，搏斗是出于自卫。警方根据证据最终判断有以下事实： A：甲乙二人必有一人是罪犯，一人是受害者； B：如果甲是出于自卫，则必定有伤； C：甲没有受伤。 问题：谁是罪犯？

设： 前提： p：甲是自卫； q：甲是罪犯； r：甲受伤。 p→r，如果甲是出于自卫，则必定有伤； ┐q→p，甲不是罪犯，则甲是自卫

解析： （1）┐r； 前提引入 （2）p→r； 前提引入 （3）┐r→┐p； （2）拒取式 （4）┐p； （5）┐q→p； 前提引入

谓词逻辑 1.命题逻辑的局限性 命题逻辑中，命题（原子命题）是基本的单位，不考虑命题之间内在联系和数量关系； 在命题逻辑中，一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。这样有一些逻辑问题无法解决。 例1. P：小张是大学生，Q：小李是大学生。 从符号P、Q中不能归纳出他们都是大学生的共性； 我们希望从所使用的符号那里带给我们更多的信息，比如可以看出他们的共性； 这种想法在命题逻辑中是无法实现的。

因为都是原子命题，但之间应有的逻辑联系消失了 例2：苏格拉底三段论 ① 所有的人总是要死的； ② 苏格拉底是人； ③ 所以苏格拉底总是要死的。 这是逻辑学中最基本的原理，但命题逻辑无法判断其正确性。 因为都是原子命题，但之间应有的逻辑联系消失了 命题逻辑不能判断出一些简单而常见的推理 由于命题逻辑的局限性，故应该对原子命题再细分

2. 谓词与个体 谓词逻辑中，将原子命题进一步细分为两个部分：谓词与个体。 即：个体是原子命题所能判断的对象或实体； 可具体，也可抽象 一般为名词，代词，…… 谓词是原子命题中所判定的性质或关系等。 如：前面提到的苏格拉底三段论： 个体：苏格拉底 苏格拉底是人 谓词：……是人

说明 ①一个谓词可以和多个个体相连 如：张三和李四是朋友 个体：张三，李四 谓词：……和……是朋友，刻画个体之间的关系； ②一个单独的谓词是没有意义的 如：“……是大学生” 谓词后必须跟随一定数量的个体后才有明确的含义。

谓词的表示方式 ① 谓词：大写字母P,Q,R,…… 也可以用一些特定的符号 ② 个体：常量一般用a,b,c,……表示 变量一般用x,y,z,……表示 例： ① 张三是人 用a表示张三，P表示“……是人” 则“张三是人”可以表示为P(a) ② 张三和李四是朋友 a表示张三， b表示李四， Q表示“……和……是朋友” 则“张三和李四是朋友”可表示为Q(a,b)

说明： ① 一般来说，谓词的多个个体词之间是有顺序之分的； 比如：张三比李四高 a：张三，b：李四 R：……比……高 则R(a,b) 就不能表示为R(b,a) ② 如果个体词是变量，则称为谓词命名式，或命题函数； 即变量确定后，就是一个命题 ③ 谓词和个体组合成命题，然后可进行一些命题之间的运算； 例：张三是大学生，李四也是大学生 F(x)表示：x是大学生 a为张三，b为李四 张三是大学生，李四也是大学生可表示为：F(a) ∧ F(b)

量词 为了精确化某些命题，比如： “所有的人总是要死的” “有些人能活过100岁” 在谓词逻辑中引入量词的概念。 量词：指明谓词所判定的个体的范围； ①全称量词 对于个体域中的所有个体的描述，记作∀A 在全称量词后，紧跟的括号内的式子称为全称量词的辖域；

例：所有的人总是要死的 用P(x)表示“x总是要死的” 则上述命题可表示为∀x P(x) ②存在量词 指在个体域内存在某些个体； 例：所有的人总是要死的 用P(x)表示“x总是要死的” 则上述命题可表示为∀x P(x) ②存在量词 指在个体域内存在某些个体； * 不一定是全部个体 * 但至少要有一个个体 记作：∃x 例：有些人能活过100岁 用Q(x)表示“x能活过100岁” 则上述命题可表示为∃x Q(x)

更多例子： ①凡是实数不是大于零就是等于零或小于零 >(x,0) 表示 x大于0 =(x,0) 表示 x等于0 <(x,0) 表示 x小于0 R(x) 表示 x是实数 则：∀𝑥(𝑅 𝑥 → > 𝑥,0 ∨ = 𝑥,0 ∨ < 𝑥,0 )

②用逻辑表达式刻画高等数学中的极限的定义： lim 𝑥→𝑐 𝑓(𝑥)=𝑘 极限定义： 任给ε>0，必存在一个δ>0，对所有x， 如果|𝑥−𝑐|< δ，则必有|𝑓(𝑥)−k|<ε 用R(x)表示：x是实数

如果 𝑥−𝑐 < δ，则必有 𝑓(𝑥)−𝑐 < ε 则极限的定义为： ∀ε(𝑅(ε)∧ <(0,ε)→∃δ(𝑅(δ))∧< 0,𝛿 ∧ ∀𝑥(𝑅(𝑥)→(<(|𝑥−𝑐|,δ)→<(|𝑓(𝑥)−𝑘|,ε))))) 存在一个实数δ >0 对于任意的实数ε>0 对所有的x 如果 𝑥−𝑐 < δ，则必有 𝑓(𝑥)−𝑐 < ε

函数 函数的值也是个体 谓词逻辑中，个体与个体之间有一定关系，这种关系称为函数。函数根据其个体变量的个数n定义为n元函数。 说明： ① 个体经过函数符作用后，得到的函数值仍然是个体 因此函数是个体到个体的映射； 个体 个体 ②由于函数的运算结果仍然是个体， 则函数中的自变量也可以是函数； ③个体和函数都可以用到谓词中。 𝑓

例：小明和张三的儿子、李四的儿子是同学 用f(x)表示x的儿子 a表示小明 b表示张三 c表示李四 P(x,y,z)表示x,y,z是同学 则P(a,f(b),f(c))

谓词逻辑公式 在引入了个体，函数，谓词及量词后，结合命题逻辑中的联结词可构成谓词逻辑中的公式。 谓词逻辑公式中使用的符号共有7种： ①个体常量：a,b,c,…… ② 个体变量：x,y,z,…… ③ 函数：f,g,h,…… ④谓词：F,G,H…… ⑤联结词：¬，∧，∨，→，← ⑥量词：∀，∃ ⑦括号 一个谓词逻辑公式是由上述符号按一定规则组成的符号串。

定义：项 ① 个体常量是项； ② 个体变量是项； ③ 设f为n元函数符，𝑡, 𝑡 2 ,⋯， 𝑡 𝑛 为项，则 f(𝑡, 𝑡 2 ,⋯， 𝑡 𝑛 )是项； ④项由且仅由有限次使用① ② ③而得。

定义：原子公式 设P是n元谓词符， 𝑡 1 , 𝑡 2 ,⋯， 𝑡 𝑛 为项，则P( 𝑡 1 , 𝑡 2 ,⋯， 𝑡 𝑛 )是原子公式。 定义：谓词逻辑公式（简称公式） ① 原子公式是公式； ② 如果A,B是公式，则： ¬𝐴),(𝐴∨𝐵),(𝐴∧𝐵),(𝐴→𝐵),(𝐴↔𝐵 是公式； ③ 如果A是公式，x为个体变量，则 ∀𝑥𝐴),(∀𝑥𝐵 是公式； ④ 公式由且仅由有限次使用① ② ③而得。

自由变元与约束变元 一个公式中如果其中有部分公式形如∀𝑥𝐴或∃𝑥𝐴，则： 在这部分中变元x的一切出现都叫做x在此公式中的约束出现，变元x称为约束变元； 即：一个变元x的出现是在关于该变量的量词的辖域之内； 否则称为自由出现，变元x称为自由变元。 说明： ① ∀𝑥(𝑃 𝑥 →𝐹 𝑥 ) ∀x的辖域为𝑃(𝑥)→𝐹(𝑥)，则变元x为约束变元； ∀𝑥(𝑃 𝑥,𝑦 →𝐹 𝑥 ) ，y是自由变元。

② 如果一个公式中所有的变元都是约束变元，则公式是确定的， 并能判断其真假； ③ ∀𝑥𝑃(𝑥)∧Q(𝑥) 这里的变元x既有约束出现，又有自由出现； 但为了避免概念上的混乱，一般会通过改名规则，使一个变 量在一个公式中只有一种出现形式。 改名规则：（改变公式中约束变元的符号） ① 改名时需要改的变元符号的范围是变量词中的变元及该量词辖域中此变元的所有约束出现处，而在公式的其余部分不变； ② 改名时所用的符号，一定没有在量词的辖域内出现。

例∀𝑥(𝑃 𝑥 →R 𝑥,𝑦 ) ① 不可将x改成y，可以改成z 因为y在∀𝑥的辖域内出现 ② 如果要将x改成z，则辖域内的x都要改名成 ∀𝑧(𝑃(𝑧)→R(𝑥,𝑦))是不正确的 对自由变元的改名规则，称为代入。 自由变元的代入规则： ① 代入时，需在公式中出现该自由变元的每一处进行； ② 用以代入的变元不允许在原公式中以任何约束的形式出现。

例：公式 ∃𝑥(𝑃(𝑦)∧𝑅(𝑥,𝑦) 对自由变元y可应用代入规则 用z代入y 则 ∃𝑥(𝑃(z)∧𝑅(𝑥,z) 下面的代入是错误的： ∃𝑥(𝑃(x)∧𝑅(𝑥,𝑥) 将y代入为x ∃𝑥(𝑃(z)∧𝑅(𝑥,𝑦) 只将第一个y代入为z，第二个没有变

谓词逻辑的永真公式 在谓词逻辑中，公式是一个符号串，必须给定具体的解释后才可能分辨其真假，（也就是明确命题的内容或范围） 解释： * 给公式中的个体变量指定一个具体的个体域D * 给个体变量指定个体域中一个具体的个体 * 对n元函数f指定一个具体的从 𝐷 𝑛 到D的映射 * 对n元谓词P指定一个n元的具体关系，即指定一个具体的从 𝐷 𝑛 到{F,T}的映射 说明：一个公式经解释后才有具体的意义。 即成为一个命题的函数

例：用如下的公式定义一个半群 ∀𝑥∀𝑦∀𝑧((𝑥∘𝑦)∘𝑧)=𝑥∘(𝑦∘𝑧) 给出“解释”为： ① 个体域D：整数 ② 二元函数“∘”：整数的加运算 ③ 二元谓词“=”：整数的相等关系 说明：公式经解释后，若公式中无自由变元，则公式的真假可确定；若有自由变元出现，则公式的真假无法确定，需要对公式“赋值”才能使公式成为确定的。 赋值：在个体域D中选择一组个体，分别代入到公式的自由变元之处，经赋值后的公式是一个能确定真假的命题。

当公式在解释的基础上并赋值后，则已经有了真假之分。 定义： 公式A如至少在一种解释下有一个赋值使其为真，则称A是可满足的； 公式A在所有解释下的所有赋值均使其为真，则称A永真； 公式A在所有解释下的所有赋值均使其为假，则称A永假； 定义：设A、B为公式，如果有𝐴↔𝐵为永真公式，则称其为等价永真公式，可写为𝐴⇔𝐵，或称A与B相等，记作A=B；如果有𝐴→𝐵为永真公式，则称其为蕴含永真公式，可写成𝐴⇒𝐵

常用等价式和蕴含永真式 ①全称量词和存在量词间的转化 ⑴ ¬(∀𝑥𝑃 𝑥 )=∃𝑥(¬𝑃(𝑥) ⑵ ¬(∃𝑥𝑃 𝑥 )=∀𝑥(¬𝑃(𝑥) (1) 设x的个体域是 𝑥 1 ,⋯, 𝑥 𝑛 则¬(∀𝑥𝑃(𝑥)) = ¬(𝑃( 𝑥 1 )∧𝑃( 𝑥 2 )∧⋯∧𝑃( 𝑥 𝑛 ) = ¬𝑃( 𝑥 1 ) ∨¬𝑃( 𝑥 2 )∨⋯∨¬𝑃( 𝑥 𝑛 = ∃𝑥(¬𝑃(𝑥) 意义：不是任意的x都满足P(x)，也就是存在有的x不满足P(x) (2) 意义：不是存在x满足P(x)，也就是对所有的x，都没有P(x) 类似于德·摩根律

②对量词辖域的扩充与收缩有如下等式 ∀𝑥𝑃(𝑥)∨𝑄=∀𝑥(𝑃(𝑥)∨𝑄 ∀𝑥𝑃(𝑥)∧𝑄=∀𝑥(𝑃(𝑥)∧𝑄 ∃𝑥𝑃(𝑥)∨𝑄=∃𝑥(𝑃(𝑥)∨𝑄 ∃𝑥𝑃(𝑥)∧𝑄=∃𝑥(𝑃(𝑥)∧𝑄 其中Q中不出现变元x 同后面的⑤，即不包含的变元的公式可以放在该约束变元的辖域内。

③多个量词间的次序排列 ∀𝑥∀𝑦𝑃(𝑥,𝑦)=∀𝑦∀𝑥(𝑃(𝑥,𝑦) ∀和∀可以交换 ∃𝑥∃𝑦𝑃(𝑥,𝑦)=∃𝑦∃𝑥(𝑃(𝑥,𝑦) ∃和∃可以交换 ∃𝑥∀𝑦𝑃(𝑥,𝑦)⇒∀𝑦∃𝑥(𝑃(𝑥,𝑦) ∃和∀不可交换 ④对公式中量词的添加和除去 ∀𝑥𝑃(𝑥)⇒𝑃(𝑥 𝑃(𝑥)⇒∃𝑥𝑃(𝑥 不等价

⑤ 对量词辖域的扩充与收缩还有如下等式（和② 类似） ∀𝑥𝑃(𝑥)→𝑄=∃𝑥(𝑃(𝑥)→𝑄 ∃𝑥𝑃(𝑥)→𝑄=∀𝑥(𝑃(𝑥)→𝑄 𝑄→∀𝑥𝑃(𝑥)=∀𝑥(𝑄→𝑃(𝑥) 𝑄→∃𝑥𝑃(𝑥)=∃𝑥(𝑄→𝑃(𝑥) 设x的个体域是 𝑥 1 ,⋯, 𝑥 𝑛 则∀𝑥𝑃(𝑥) →𝑄 = (𝑃 𝑥 1 →𝑄)∧(𝑃 𝑥 2 →𝑄)∧⋯∧(𝑃 𝑥 𝑛 →𝑄 = (¬𝑃( 𝑥 1 )∨𝑄)∧(¬𝑃( 𝑥 2 )∨𝑄)∧⋯∧(¬𝑃( 𝑥 𝑛 )∨𝑄) = ¬(𝑃( 𝑥 1 ) ∨𝑃( 𝑥 2 )∨⋯∨𝑃( 𝑥 𝑛 ) ∨𝑄 = ∃𝑥(𝑃(𝑥)→𝑄

⑥对量词与命题联结词间关系的等式 ∀𝑥(𝑃(𝑥)∧𝑄(𝑥))=∀𝑥(𝑃(𝑥)∧∀𝑥𝑄(𝑥) ∃𝑥(𝑃(𝑥)∨𝑄(𝑥))=∃𝑥(𝑃(𝑥)∨∃𝑥𝑄(𝑥) ∀ 𝑥𝑃(𝑥)∨∀𝑥𝑄(𝑥)⇒∀𝑥(𝑃(𝑥)∨𝑄(𝑥) ∃𝑥𝑃(𝑥)∧∃𝑥𝑄(𝑥)⇐∃𝑥(𝑃(𝑥)∧𝑄(𝑥) （有问题，课本上写反了） ∀𝑥(𝑃(𝑥))⇒∃𝑥(𝑃(𝑥) ∀𝑥(𝑃(𝑥)→𝑄(𝑥))⇒∀𝑥(𝑃(𝑥)→∀𝑥𝑄(𝑥) ∀𝑥(𝑃(𝑥)→𝑄(𝑥))⇒∃𝑥(𝑃(𝑥)→∃𝑥𝑄(𝑥)

对偶定理： 设有等式A=B，并且A,B中不出现联结词→及↔，则此时必有 𝐴 ∗ = 𝐵 ∗

范式 谓词逻辑公式的一种标准形式，作用和命题逻辑中的范式类似。 两种范式 前束范式 斯科林范式 前束范式： *所有量词均非否定地出现在公式的最前面； *且它们的辖域一直延伸到公式的末尾； （所有的量词的辖域都相同，都是整个公式） *且公式中不出现联结词→及↔。 例： ∀𝑥∃𝑦∀𝑧(𝑃(𝑥)∧𝐹(𝑦,𝑧)∧𝑄(𝑦,𝑧)

求取前束范式的过程： ①将公式中的联结词→,↔消去； ②利用 ¬(∀𝑥𝑃(𝑥))=∃𝑥(¬𝑃(𝑥) ¬(∃𝑥𝑃(𝑥))=∀𝑥(¬𝑃(𝑥) 将公式内的否定符号深入到谓词变元之前； ③利用改名、代入规则使所有约束变元均不同，并且自由变元及约束变元也不相同； ④利用： ∀𝑥𝑃(𝑥)∨𝑄=∀𝑥(𝑃(𝑥)∨𝑄 ∀𝑥𝑃(𝑥)∧𝑄=∀𝑥(𝑃(𝑥)∧𝑄 ∃𝑥𝑃(𝑥)∨𝑄=∃𝑥(𝑃(𝑥)∨𝑄 ∃𝑥𝑃(𝑥)∧𝑄=∃𝑥(𝑃(𝑥)∧𝑄 将量词的辖域扩大到整个公式。

例： ∀𝑥(𝑃(𝑥)∨∃𝑦𝑅(𝑦))→∀𝑥𝐹(𝑥 ①除去→和↔ ∀𝑥(𝑃(𝑥)∨∃𝑦𝑅(𝑦))→∀𝑥𝐹(𝑥 = ¬(∀𝑥𝑃(𝑥)∨∃𝑦𝑅(𝑦))∨∀xF x ② 将否定符号深入到谓词前 = ∃𝑥(¬𝑃(𝑥)∧∀𝑦(¬𝑅(𝑦)))∨∀𝑥𝐹(𝑥 ③改变变元符号 = ∃𝑥(¬𝑃(𝑥)∧∀𝑦(¬𝑅(𝑦)))∨∀𝑧𝐹(𝑧 ④将量词辖域扩大至整个公式 = ∃𝑥∀𝑦∀𝑧(¬𝑃(𝑥)∧¬𝑅(𝑦)∨𝐹(𝑧)

前束范式： 特点：量词全部集中在公式的前面，理解、使用方便； 称为首标，公式其余部分称为尾部 缺点：量词有全称量词及存在量词，排列无规律。 斯科林范式（对前束范式改进） ① 只出现全称量词 ② 不出现自由变元 设公式A的前束范式为： 𝑄 1 𝑥 1 𝑄 2 𝑥 2 ⋯ 𝑄 𝑛 𝑥 𝑛 M， 其中 𝑄 1 𝑥 1 𝑄 2 𝑥 2 ⋯ 𝑄 𝑛 𝑥 𝑛 为首标， 𝑄 𝑖 𝑥 𝑖 为量词，M为尾部。 可以是全称量词，也可以是存在量词

求取斯科林范式的方法： ①将公式中出现的自由变元用全称量词进行约束； 设公式A中有m个自由变元 𝑥 ′ 1 𝑥 ′ 2 ⋯ 𝑥 ′ 𝑚 则A可写为∀ 𝑥 ′ 1 ∀ 𝑥 ′ 2 ⋯∀ 𝑥 ′ 𝑚 𝑄 1 𝑥 1 𝑄 2 𝑥 2 ⋯ 𝑄 𝑛 𝑥 𝑛 𝑀 ②对每个 𝑄 𝑖 𝑥 𝑖 从左到右作代换 * 若 𝑄 𝑖 𝑥 𝑖 为全称量词，则不作改动； * 若 𝑄 𝑖 𝑥 𝑖 为存在量词且左边无全称量词，则取一个常量符号c（此符号在公式中其他处并不出现），并且用c替代M中出现的 𝑥 𝑖 ，同时将 𝑄 𝑖 𝑥 𝑖 删除； * 若 𝑄 𝑖 𝑥 𝑖 为存在量词且其左边有全称量词，则取一个函数 𝑓( 𝑥 𝑠1 , 𝑥 𝑠2 ,⋯, 𝑥 𝑠𝑟 ，其中 𝑄 𝑖 𝑥 𝑖 左边出现的全称量词个数为r，

其约束变量分别为 𝑥 𝑠1 , 𝑥 𝑠2 ,⋯, 𝑥 𝑠𝑟 ，而f是一个r元函数符号，它在公式其它处并不出现； 其约束变量分别为 𝑥 𝑠1 , 𝑥 𝑠2 ,⋯, 𝑥 𝑠𝑟 ，而f是一个r元函数符号，它在公式其它处并不出现； * 然后利用 𝑓( 𝑥 𝑠1 , 𝑥 𝑠2 ,⋯, 𝑥 𝑠𝑟 替代M中所出现的 𝑥 𝑖 ，同时将 𝑄 𝑖 𝑥 𝑖 删除。 定理： 公式A是可满足的充分必要条件是其斯科林范式为可满足的； 公式A是永假的充分必要条件是其斯科林范式为永假的； 公式A是用真的充分必要条件是其斯科林范式为永真的。 说明： ①公式A和它的斯科林范式有相同的可满足性，永真和永假性； ②但一般来说并不等价。

推理理论 1.命题逻辑中的推理理论 推理：从一些称为前提的命题，如按照公认的推理规则，合乎逻辑地得到一个称为结论的命题的过程； 结论：通过对前提进行“演算”而得到，演算就是按公认的推理规则进行。 定义：设 𝐺 1 ,⋯, 𝐺 𝑚 ，𝐻是一些命题，如果 ( 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 𝑚 )⇒𝐻 则称H是前提集合{ 𝐺 1 ,⋯, 𝐺 𝑚 }的有效结论； 也可记作 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 𝑚 ⇒𝐻 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 𝑚 𝐻 说明：可按真值表进行，但一般来说过于复杂。 蕴含永真

推理过程形式化描述： 设G是命题公式集合（前提集合）， 从G推出公式H的演绎是一个公式序列 𝑆 1 , 𝑆 2 ,⋯, 𝑆 𝑘 其中 𝑆 𝑖 或者属于G，或者是 𝑆 𝑗 （j<i）的有效结论，并且 𝑆 𝑘 =H 例：G= 𝑃∧𝑅,𝑃→𝑄 ，H=Q 则序列 𝑃∧𝑅, 𝑃, 𝑃→𝑄, 𝑄 是G推理出H的一个演绎： 𝑃∧𝑅,𝑃→𝑄是前提集合中元素 P是𝑃∧𝑅的有效结论 Q是P和𝑃→𝑄的有效结论

判断一个前提集合能否得到有效结论的方法 真值表方法 推理方法 直接证法 间接证法 直接证法： 由一组前提，利用公认的一些规则，并且利用已知的等价蕴含式，演绎得到有效结论。 规则P：（前提引入规则） 在演绎过程中，随时使用前提集合中任一公式； 规则T：（结论引入规则） 在演绎过程中，随时可使用前面演绎中已得到的有效结论。

例：证明{P→Q,Q→R,P}⇒R 证明： 规则 𝑆 1 ① P→Q P 𝑆 2 ② P P 𝑆 3 ③ Q T ① ② 𝑆 4 ④ Q→R P 𝑆 5 ⑤R T ③ ④ 说明：列出使用的规则，如果是规则T，还应指出是由哪几个公式推出的有效结论。

定理：设 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ，𝐴,𝐵都是公式 则 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ⇒𝐴→𝐵 当且仅当 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ，𝐴⇒𝐵 证明： （ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ）→（𝐴→𝐵） =¬（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ）∨ ¬𝐴∨𝐵 蕴含等价式 =（¬（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ∨¬𝐴）∨𝐵 结合律 =¬（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ∧𝐴）∨𝐵 德.摩根律 = 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ∧𝐴→𝐵 蕴含等价式

当 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ⇒𝐴→𝐵 即为（ 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ）→（𝐴→𝐵）=1 因此（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ∧𝐴）→𝐵=1 即 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ，𝐴=𝐵 同理，若 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ，𝐴⇒𝐵 则可得 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ⇒𝐴→𝐵

定义：设 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m 是公式，若存在某解释（指派） 使 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m =1 则称公式集合 {𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m }是相容的； 若对任意解释（指派），都有 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m =0 则称公式集合 {𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m }是不相容的。

定理：设 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m 是公式 若{ 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m }是相容的， 而{ 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ，¬𝐻}是不相容的， 则 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ⇒𝐻 证明：由于{ 𝐺 1 ， 𝐺 2 ，⋯， 𝐺 m ，¬𝐻}不相容 因此对任意指派Ⅰ都有 0=（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ∧¬𝐻） 双重否定 =¬¬（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ∧¬𝐻） 结合律 =¬（¬（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ）∨𝐻）德.摩根律 =¬（（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ）→𝐻） 蕴含等价式 即（ 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ）→𝐻=1 即 𝐺 1 ∧ 𝐺 2 ∧⋯∧ 𝐺 m ⇒𝐻

规则CP：附加前提引入规则 如果需要演绎出的公式形如A→B，则可将A作为附加前提使用，而力图演绎出有效结论B即可； 规则F ： 归谬法，反证法 如果需要演绎出有效结论H，可将¬H作为附加前提使用，而力图演绎出恒假式。

例：证明{P→(Q→S),Q,¬R∨P}⇒R→S 证明： S 1 R CP(附加前提) S 2 ¬R∨P P S 3 R→P T ② 蕴含等价式 S 4 P T ① ③ S 5 P→(Q→S) TP S 6 Q→S T ④ ⑤ S 7 Q P S 8 S T ⑥ ⑦ S 9 R→S CP ① ⑧

例：证明 ¬𝑃∧¬𝑄⇒¬(𝑃∧𝑄 证明： S 1 ¬ ¬(𝑃∧𝑄) F（附加前提） S 2 𝑃∧Q T S 1 结合律 S 3 P T S 2 S 4 ¬𝑃∧¬𝑄 P S 5 ¬𝑃 T S 4 S 6 𝑃∧¬P T S 3 S 5 S 7 ¬(𝑃∧𝑄) F S 1 S 6

2.谓词演算的推理 ①全称量词消去规则（US规则） ∀𝑥𝐴(𝑥)⇒𝐴(𝑦 ② 全称量词引入规则（UG规则） 𝐴(𝑦)⇒∀𝑥𝐴(𝑥 ③ 存在量词消去规则（ES规则） ∃𝑥𝐴(𝑥)⇒𝐴(𝑐 ④存在量词引入规则（EG规则） 𝐴(𝑐)⇒∃𝑥𝐴(𝑥 说明：前面介绍的命题运算中的推理规则也可用。

课程总结 四大部分：集合论、代数结构、图论、数理逻辑 集合论 集合：集合的基本概念、有限集与无限集、包含排斥原理； 关系：关系的基本概念、关系的运算、关系的性质及其判定 方法、等价关系、相容关系、偏序关系； 函数：映射和函数、单射与满射、鸽洞原理； 应用：概率论、关系数据库、特殊函数；

代数结构 代数系统：基本概念、性质、同构与同态、代数运算； 群论：基本概念、半群、群、循环群、凯莱表示定理、陪集及拉格朗日定理； 其它代数系统：环与域、格与布尔代数； 应用：加密、伪随机数、编码、组合逻辑线路；

图论 数理逻辑 图论的基本概念、图的邻接矩阵和关联矩阵、树、欧拉图、 哈密顿图、二分图、平面图，权图中的最短路径，有向图； 补充：网络流理论、图着色、超图； 应用：网络编码、复杂网络； 数理逻辑 命题逻辑：命题与联结词、命题公式、真值表、命题公式的 运算、析取范式与合取范式、演绎推理 谓词逻辑：谓词公式及其运算、范式、谓词推理。

考试说明 考试形式：开卷 时间：2016年？月？日下午15:55-18:00 地点：3122 作业占30% 考试范围： 试题形式： 课本上占多数，可能会有一些补充内容 试题形式： 计算、问答、证明题； 没有选择、填空等题目；