离散数学导论(第5版)-第五篇

19
§11.6 谓词逻辑永真公式
（9）谓词逻辑永真公式定义 谓词公式的解释与赋值
（10）谓词逻辑永真公式定义——公式在所有解 释下对所有赋值均为真
（11）谓词逻辑永真公式等式： （xP（x））＝x（P（x）） （x P（x））＝x（P（x）） xP（x）∨Q＝x（P（x）∨Q） xP（x）∧Q＝x（P（x）∧Q）
21
（12）谓词逻辑的蕴含永真公式 xyP（x , y） yx（P（x , y）） xP（x） P（x） P（x）x P（x） xP（x）∨x Q（x）x（P（x）∨Q（x）） xP（x）∧x Q（x）x（P（x）∧Q（x）） x（P（x）x（P（x）） x（P（x）Q（x））x（P（x）x Q（x） x（P（x）Q（x））xP（x）x Q（x）
18
§11.5 自由变元与约束变元
（8）谓词公式中的自由变元与约束变元 • 谓词公式中的自由变元与约束变元 • 约束变元的改名规则——改名在量词变元及其辖 域中该变元的约束出现处进行且该变元不在量词辖域内 出现过。 • 自由变元的代入规则——代入在公式的自由变元 出现的每一处进行且该代入变元不允许在式中以任何约 束形式出现。
29
谓词逻辑公式： ① 原子公式是公式； ② A，B是公式则：（A），（A∨B），（A∧B）， （AB）,（AB）是公式； ③ A是公式则（xA），（xB）是公式； ④公式由且仅由有限次使用①、②、③而得。
30
２ 推理部分 1）公理 如P，Q，R为公式，则有下述的公理： ① PP； ② （P（QR））（Q（PR））； ③ （PQ）（（QR）（PR））； ④ （P（PQ））（PQ）； ⑤ （PQ）（PQ）； ⑥ （PQ）（QP）；
7
联结词化归 P∧Q＝（P∨Q）； P∨Q＝（P∧Q）； PQ＝P∨Q； PQ＝（PQ）∧（QP） 其它 PQ＝QP (PQ)∧（PR）＝PQ∧R P∨（P∧Q）＝P P（QR）＝P∧QR P∧（P∨Q）＝P
8
（8）推理规则： • 代入规则 • 替换规则
(9)推理过程 由P到Q的推理过程是一个等式序列： P=P1 P1= P2 …… Pn-1= Pn Pn=P
——ＵＳ规则 ——ＵＧ规则 ——ＥＳ规则 ——ＥＧ规则
•证明规则： ——Ｐ规则 ——Ｔ规则 ——ＣＰ规则
24
§11.９ 谓词逻辑范式
（1６）前束范式——公式的所有量词均非否定 的出现在公式最前面，它的辖域一直延伸至公式末尾， 且公式中不出现与。
（1７）斯科林范式——前束范式的首标处仅出 现 全 称 量 词 且 公 式 中 不 出 现 自 由 变 元 x1x2…xnM （x1 , x2,…, x n）
（15）范式——命题公式的一种标准形式 （16）主析取范式：该范式是一个析取式， 每个析取项是所有命题变元式其否定的合取式。 （17）主异合取范式：该范式是一个合取式， 每个析取项是所有命题变元式其否定的析取式。
14
§10.8 命题联结词的扩充与归约
（18）命题联结词的扩充——异或：、谢佛：、 魏泊：、
5
否定深入 P＝P； （P∧Q）＝P∨Q； （P∨Q）＝P∧Q； （PQ）＝P∧Q； (14)（PQ）＝PQ＝PQ； 变元等同 P∧P＝P； P∨P＝P； P∧P＝F； P∨P＝T； PP＝T； PP＝P； PP＝P； PP＝T； PP＝PP＝F；
6
常值与变元的联结 T∧P＝P； F∧P＝F； T∨P＝T； F∨P＝F； TP＝P； FP＝T； PT＝T； PF＝P； TP＝P； FP＝P；
22
§11.7 谓词逻辑等式推理
(13) 有三部分组成： • 基本等式 • 推理规则——代入规则与替换规则 • 推理过程——等式序列
§11.８谓词逻辑蕴含推理
(1４)谓词逻辑蕴含推理是单向推理，有三部分组成： •前提 •证明——推理规则与证明过程 •定理
23
（１５）谓词逻辑蕴含推理组成： •推理规则：
25
第12章 数理逻辑公理化理论
§12.1 公理化理论的基本思想
（1８）公理系统的两个部分 • 公理系统的组成与推理 • 公理系统的讨论： • • 不矛盾性 • • 完整性 • • 独立性
26
§12.2 命题逻辑与谓词逻辑的公理化理论
（1９）命题逻辑永真公理系统的组成 １、组成部分 命题：P1，P2，…，Pn； 命题联结词：，∨，∧，，； 个体常量：a，b，c，x，y，z； 个体变量：P，Q，R…； 函 数：f，g，h； 谓 词：，； 括 号：（，）
16
§11. 2量词
（3）存在量词：x P (x)——“有一些”之语义 （4）全称量词：x P (x)——“所有”之语义 （5）量词的辖域——量词所作用的范围
§11.3 函数
（6）函数——个体间的特定关系称函数，它是个体间的映射。 f (x)中X是个体而f为函数符号，f (x)为函数。
17
§11.4 谓词逻辑公式
38
⑨ P∧QP． ⑩ P（QP∧Q）． 11 PP∨Q． 12 QP∨Q． 13 （QP）（（RP）（Q∨RP））． 14 （PQ）（QP）． 15 PP． 16 xP（x）P（x）． 17 P（x）xP（x）。
39
2）推理规则 ① 分离规则：PQ，P├Q. ② 全称规规：QP（x）├QxP（x）． ③ 存在规则：P（x）Q├x P（x）Q． 上面17个公理与3个规则中有15个公理与1个 规则是命题逻辑公理系统的，真正属谓词逻辑的 仅有2个公理与2个规则。
12
（13）11个推理规则 P∧Q├P； P∧Q├Q； P├P∨Q； Q├P∨Q； P，Q P├Q； P，P∨Q├Q； P，PQ├Q； Q，PQ├P； PQ，QR├P R； PQ，RS├P∧R Q∧S； P∨Q，PR，QR├R；
13
(14) 证明过程
是一个公式序列并运用三个规则： • P规则 • T规则 • CP规则 §10.6 范式
36
（23）谓词逻辑永真公理系统 1．系统组成部分 2．推理部分 1）公理 设P，Q，R为公式，则有公理如下：
37
① pp． ② （P（QR））（Q（PR））． ③ （PQ）（（QR）（PR））． ④ （P（PQ））（PQ）． ⑤ （PQ）（PQ）． ⑥ （PQ）（QP）． ⑦ （PQ）（（QP）（PQ））． ⑧ P∧QQ．
20
xP（x）∨Q＝x（P（x）∨Q） xP（x）∧Q＝x（P（x）∧Q） xyP（x , y）＝yx（P（x , y） xyP（x , y）＝yx（P（x , y） x P（x）Q＝x（P（x）Q） x P（x）Q＝x（P（x）Q） Qx P（x）＝x（Q P（x）） Qx P（x）＝x（Q P（x）） x（P（x）∧Q（x））＝x（P（x）∧x Q（x） x（P（x）∨Q（x））＝x（P（x）∨x Q（x）
11
P∧（P∨Q）Q； Q∧（P∨Q）P； P∧（PQ）Q； Q∧（PQ）P； (PQ)∧(QR) PR； (PQ)∧(RS) P∧RQ∧S； (P∨Q)∧(PR)∧(QR)R； P(QP∧Q)； (PQ)((QR)(PR))； (P(QR))(Q(PR))； (PQ)((RQ)(P∨RQ))．
31
⑦ （PQ）（QP）（PQ））； ⑧ P∧QQ； ⑨ P∧QP； ⑩ P（QP∧Q）； 11 PP∨Q； 12 QP∨Q； 13 （QP）（（RP）（Q∨RP））； 14 （PQ）（QP）； 15 PP；
32
2）推理规则 分离规则：PQ，P├Q。 3）证明（过程）与定理 证明（过程）给出了公理系统中定理生成的 过程，它是一个公式序列：P1，P2，…，Pn，其中 每个Pi（i＝1，2，…，n）必须满足下条件之一。
27
项： ① 个体常量是项； ② 个体变量是项； ③ f是n元函数，t1，t2，…,tn是项，则 f(t1，t2，…,tn)是项； ④ 项由且仅由有限次使用①、②、③而得。
28
原子公式：P是n元谓词，t1，t2，…，tn是项， 则P（t1，t2，…，tn)是原子公式。
命题逻辑公式： ① 命题是公式； ② P是公式则（P）是公式； ③ P，Q是公式则（P∨Q），（P∧Q），（PQ）， （PQ）是公式； ④ 公式由且仅由有限次使用① ， ② ， ③ 而得。
4
§10.4 命题逻辑基本等式及等式推理
（6）等式推理：由三部分组成：它们是基本等 式、推理规则及推理过程。
（7）命题逻辑42个基本等式。 交换律 P∨Q＝Q∨P； P∧Q＝Q∧P； PQ＝QP． 结合律
（P∨Q）∨R＝P∨（Q∨R）； （P∧Q）∧R＝P∧（Q∧R）； （PQ）R＝P（QR）．
分配律 P∧（Q∨R）＝（P∧Q）∨（P∧R）； P∨（Q∧R）＝（P∨Q）∧（P∨R）；
（19）命题联结词的归约 命题联结词可归约为如下形式之一：
• {, } • {, } • {} • {}
15
第11章 谓词逻辑
谓词逻辑基本概念
§11.1 谓词与个体
（1）个体 • 个体常量与个体变量 • 个体域与全总个体域 （2）谓词 • 一元谓词——刻划个体性质 • 二元谓词——刻划两个个体间关系 • n元谓词——刻划n个个体间关系
40
3）证明（过程）与定理。 证明（过程）是一个公式序列：P1，P2，…，Pn， 其中每个Pi（i＝1，2，…，n）必须满足下条件之一： ① Pi是公理； ② Pi是由Pk，Pr，（k，r<i）施行分离规则而 得； ③ Pi是由Pk（k<i）施行全称规则而得； ④ Pi是由Pk（k<i）施行存在规则而得。 最后，Pn＝Q 即为定理。
9
§10.5 命题逻辑基本蕴含式及蕴含推理
（10）蕴含推理是单向推理，它有三部分组成： • 前提－已知条件 • 证明－是一种过程 • 定理－结论 (11) 蕴含推理组成： • 基本蕴含式 • 推理规则 • 证明过程
10
（9）19个基本蕴含重言式 P∧QP； P∧QQ； P P∨Q； QP∨Q； PPQ； QPQ； （PQ） P； （PQ） Q；
（7）谓词逻辑公式 • 项：个体是项，函数是项 • 原子公式：P（t1 , t2 ,…tn）是原子公式（其中ti为项） • 公式： • • 原子公式是公式； • • A，B是公式，则（A）,（A∨B）,（A∧B）,（AB），
（AB）是公式； • • A是公式，x为个体变量，则（xA），（xA）为公式； • • 公式由且仅由有限次使用前面三步而得。
34
３ 假设推理的证明过程必须满足： ① Ｐi是假设前提； ② Ｐi是公理； ③ Ｐi是由Ｐk，Pr用分离规则而得 最后。Pn=B，而Ａ１→（Ａ２→（…（Ａn →B）） …）为定 理。
35
（２２）额外假设推理——反证法 １ 以结论为假设作前提 ２ 反证推理定理： 设有A1，A来自百度文库，…，An，B├P∧P，则必有： ├A1→(A2→(…(An→B））…） 3 反证推理证明过程必须满足 1)Pi是公理； 2)Pi是假设； 3)Pi是待证定理B的否定，即为P； 4)Pi是由Pk，Pr用分离规则而得。 最后Pn=P∧P，而此时：A1→(A2→(…(An→B））…）为定理。
33
① Pi是公理； ② Pi是由Pk，Pr，（k，r<i）施行分离规则而得。 最后，Pn＝Q 即为定理。
（２０）导出规则——如有AB为定理则必有A├B。 （２１）假设推理 １ 具有特定环境下的假设作前提 ２ 推理定理——设有A1，A2，…，An├B，则 必有：A 1, A2, …An-1├An B。
3
第10章 命题逻辑
命题逻辑以命题为对象，研究命题的符号体系及推理规则。
§10.1 命题与命题联结词
（1）命题——能判别真假的语句。 （2）基本命题联结词——否定、并且、或者、蕴含、等价。
§10.2 命题公式
（3）命题公式——由命题及命题联结词构成命题公式。
§10.3 重言式
（4）指派——命题公式中变元的一组确定的值。 （5）重言式——所有指派均取值为真的公式。
离散数学导论（第5版）
电子教案
1
第五篇 数理逻辑
数理逻辑是用数学方法研究形式逻辑演绎推理规则 的科学，它是一门数学，是一门研究演绎推理规则的数 学，在学习此部分时，主要要掌握如下几个要点：
① 思维的形式化 ② 指派法 ③ 公式推理 ④ 公理系统 ⑤ 范式 ⑥ 自动定理证明
2
本篇由命题逻辑、谓词逻辑、公理化理论部 分组成，其中命题逻辑以命题为研究对象而谓词 逻辑则以谓词为研究对象，而公理化理论则是数 理逻辑中演绎推理的形式化思想的介绍，它们的 有机结合构成完整的整体。