离散结构及应用-all.ppt

离散结构与应用,湖北经济学院 软件工程系,第1部分 数理逻辑,第1章 命题逻辑 第2章 一阶逻辑,第1章 命题逻辑,这章是以“命题”为中心，主要讨论： 1、命题的表示、命题的演算 2、命题演算中的公式，及其应用 3、命题逻辑推理,1.1 命题与联结词,命题是一个能确定是真的或是假的判断判断都是用陈述句表示） 判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一 例：判定下面这些句子哪些是命题 ⑴ 2是个素数 ⑵ 雪是黑色的 ⑶ 2017年人类将到达火星 ⑷ 如果 ab且bc，则ac ⑸ x+y5 ⑹ 请打开书！ ⑺ 您去吗？ ⑴ ⑵ ⑶ ⑷ 是命题,1.1 命题与联结词,一个命题所作的判断有两种可能：是正确的判断或者是错误的判断所以一个命题的真值有两个：“真”或“假” 真值为真: 一个命题所作的判断与客观一致,则称该命题的真值为真,记作T (True) 真值为假: 一个命题所作的判断与客观不一致,则称该命题的真值为假,记作F (False) 上例中(1)(4)的真值为真, (2)的真值为假, (3)暂时不能定，等到2017年确定1.1 命题与联结词,简单命题 (原子命题)：由最简单的陈述句构成的命题 (该句再不能分解成更简单的句子了)。

通常用大写英字母表示 上例中的(1)、(2)、(3)是原子命题 复合命题 (分子命题)：由若干个原子命题构成的命题 上例中的(4)是由三个原子命题(ab、bc、ac)构成的复合命题1.1 命题与联结词,复合命题：是用“联结词”将原子命题联结起来构成的定义了六个逻辑联结词： (1) 否定： (2) 合取：∧ 并且 (3) 析取：∨ 可兼取的或者 (4) 异或： 不可兼取的或 （教程未提） (5) 蕴涵： 如果 (6) 等价：,1.1 命题与联结词,1.1 命题与联结词（课题练习）,已知P∧Q为T，则P为( )，Q为( ) 已知P∨Q为F，则P为( )，Q为( ) 已知P为F，则P∧Q为( ) 已知P为T，则P∨Q为( ) 已知P∨Q为T，且P为F ，则Q为( ) 已知PQ为F，则P为( )，Q为( ) 已知P为F，则PQ为( ) 已知Q为T，则PQ为( )1.1 命题与联结词（课题练习）,已知 PQ为F，则P为( )， Q为( ) 已知P为T，PQ为T，则Q为( ) 已知Q为T, PQ为T，则P为( ) 已知PQ为T，P为T , 则Q为( ). 已知PQ为F，P为T , 则Q为( ). PP 的真值为( ). PP 的真值为( )。

1.2 命题公式及符号化,常值命题：即是我们前面所说的命题它有具体含义 (真值) 例如：“3是素数就是常值命题 命题变元：用大写的英文字母如P、Q等表示任何命题称这些字母为命题变元 对命题变元作指派(给命题变元一个解释)：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值“T”或“F”的过程 注意：命题变元本身不是命题，只有给它一个解释，才变成命题1.2 命题公式及符号化,合式公式 ( wff ) (well formed formulas)：对计算机而言，最方便的定义方式就是构造性的（或递归性的），即用简单的原子命题变元和联结词，通过有限步构造出新的复合命题来因此，我们给出下面的定义： 见教程 P6/定义1.10 注意：这个定义是递归的1)是递归的基础，由(1)开始，使用(2)、(3)规则，可以得到任意的合式公式1.2 命题公式及符号化,对每个命题变元可以有两个真值(T,F)被指派，所以有n个命题变元的命题公式 A(P1,P2,…,Pn) 的真值表有2n行 为有序地列出A(P1,P2,…,Pn)的真值表，可将F看成0、T看成1，按二进制数次序列表如A(P,Q)的真值表可按照如下次序指派：00(FF)，01(FT)，10(TF)，11(TT) A(P,Q,R)的真值表可按照如下次序指派：,1.2 命题公式及符号化,命题符号化定义： 用命题公式的符号串来表示给定的命题。

命题符号化的方法： 1.首先要明确给定命题的含义 2.对于复合命题，找联结词，用联结词断句，分解出各个原子命题 3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式1.2 命题公式及符号化,例 如果小张与小王都不去，则小李去 P：小张去 Q：小王去 R：小李去 该命题可写成： (P∧Q)R 如果小张与小王不都去，则小李去 该命题可写成： (P∧Q)R 也可以写成： (P∨Q)R,1.2 命题公式及符号化,重言式(矛盾式)定义：A(P1,P2,…,Pn) 是含有命题变元P1,P2,…, Pn的命题公式，如不论对P1, P2 , …, Pn作任何指派，都使得A(P1,P2,…, Pn) 为真(假)，则称之为重言式(矛盾式), 也称之为永真式 (永假式) 重言式的证明方法： 方法1：列真值表 方法2：公式的等价变换，化简成“T” 方法3：用公式的主析取范式1.2 命题公式及符号化,例如，证明 (P∧(PQ))Q 为重言式 P Q PQ P∧(PQ) (P∧(PQ))Q F F T F T F T T F T T F F F T T T T T T,1.3 等值演算（定义）,定义：A、B 是含有命题变元 P1,P2,…, Pn 的命题公式，如不论对 P1, P2 , …, Pn 作任何指派，都使得 A 和 B 真值相同，则称之为 A与B 等值，记作AB。

例如：PQ  ¬ P ∨ Q  ¬ Q ¬ P 定义：根据已知等值式，推演出另一些等值式的过程称为 等值演算1.3 等值演算（重要的等值公式1）,⑴ 双重否定律，对合律 ¬ ¬ P  P ⑵ 幂等律 P∨P  P P∧P  P ⑶ 结合律 P∨(Q∨R)  (P∨Q)∨R P∧(Q∧R)  (P∧Q)∧R ⑷交换律 P∨QQ∨P P∧QQ∧P ⑸分配律 P∨(Q∧R)(P∨Q)∧(P∨R) P∧(Q∨R)(P∧Q)∨(P∧R) ⑹ 吸收律 P∨(P∧Q)P P∧(P∨Q)P,1.3 等值演算（重要的等值公式2）,⑺德-摩根定律 ¬(P∨Q) ¬P∧¬Q ¬(P∧Q) ¬P∨¬Q ⑻ 同一律 P∨0  P P∧1  P ⑼ 零律 P∨1  1 P∧0  0 ⑽ 互补律 P∨¬P  1 P∧¬P  0 ⑾ PQ  ¬P∨Q ⑿PQ¬Q¬P ⒀ PQ  (PQ)∧(QP) 等价等值式 ⒁ PQ  (¬P∨Q)∧(P∨¬Q) ⒂ PQ  (P∧Q) ∨ (¬P∧¬Q ),1.3 等值演算（和集合公式关系）,⑴ 对合律 ~~AA ~A表示A的绝对补集 ⑵ 幂等律 A∪AA A∩AA ⑶ 结合律 A∪(B∪C)(A∪B)∪C A∩(B∩C)(A∩B)∩C ⑷交换律 A∪BB∪A A∩BB∩A ⑸分配律 A∪(B∩C)(A∪B)∩(A∪C) A∩(B∪C)(A∩B)∪(A∩C),1.3 等值演算（和集合公式关系）,⑹ 吸收律 A∪(A∩B)A A∩(A∪B)A ⑺ 德-摩根定律 ~(A∪B)~A∩~B ~(A∩B)~A∪~B ⑻ 同一律 A∪ΦA A∩EA E表示全集 ⑼ 零律 A∪EE A∩ΦΦ ⑽ 否定律 A∪~AE A∩~AΦ,1.3 等值演算（判断等值方法）,方法1：用列真值表。

方法2：用公式的等价变换即置换定律) 置换定律: A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB 应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换1.3 等值演算（等值判断例）,例. 求证 (¬P∨Q)→(P∧Q) P 证明： (¬P∨Q)→(P∧Q) ¬(¬P∨Q)∨(P∧Q) (蕴涵等值式)  (¬¬P∧¬Q)∨(P∧Q) (摩根定律)  (P∧¬Q)∨(P∧Q) (对合律)  P∧(¬Q∨Q) (分配律)  P∧T (互补律)  P (同一律),1.3 等值演算（等值化简例）,例.化简 ¬(P∧Q)→(¬P∨(¬P∨Q)) 解 原公式  ¬¬(P∧Q)∨((¬P∨¬P)∨Q) (蕴涵等值 结合)  (P∧Q)∨(¬P∨Q) (对合律 幂等律)  (P∧Q)∨(Q∨¬P) (交换律)  ((P∧Q)∨Q)∨¬P (结合律)  Q∨¬P (吸收律),1.3 等值演算（性质）,1). 自反性：任何命题公式A，有AA。

2). 对称性：若 AB，则BA 3). 传递性：若 AB 且 BC，则 AC 4). 如果A(P1,P2,…,Pn)  B(P1,P2,…,Pn)，则 A(¬P1, ¬P2,…, ¬Pn)  B(¬P1, ¬P2,…, ¬Pn),1.4 范式（定义，合取式，析取式）,范式就是命题公式形式的规范形式这里约定在范式中只含有联结词 ¬ 、∨ 和 ∧ 合取式：是用“∧”联结命题变元 或 变元的否定 构成的式子 析取式：是用“∨”联结 命题变元 或 变元的否定 构成的式子1.4 范式（定义，合取范式，析取范式）,合取范式：公式 A 如果写成如下形式： A1 ∧ A2 ∧ . ∧ An (n≥1) ，每个Ai (i=1,2,…,n)都是是析取式 ，称之为 A 的合取范式 析取范式：公式 A 如果写成如下形式： A1 ∨ A2 ∨ . ∨ An (n≥1) ，每个Ai (i=1,2,…,n)都是是合取式 ，称之为 A 的析取范式1.4 范式（求 合取范式，析取范式）,1、先用相应的公式去掉  和  2、用 对偶式性质 或 摩根定律 将 ¬ 后移到命题变元前 3、用分配律、幂等律 等公式进行整理。

1.5 推理演算,推理就是根据一个或几个已知的判断得出一个新的判断的思维过程 称这些已知的判断为前提得到的新的判断为前提的有效结论 实际上，推理的过程就是证明重言蕴含式 的过程，即令 H1，H2，…，Hn 是已知的命题公式(前提)，若有 H1 ∧ H2 ∧ ∧ Hn  C 则称C是H1，H2，…Hn的有效结论，简称结论1.X 小结,命 题,原子命题,复合命题,联结词,命题公式,永真式,永真蕴涵式,等价公式,范式,命题逻辑推理,直接推理,间接推理,条件论证,反证法,,,,,,,,,,,,,,,,析取,合取,主析取,主合取,,,,,第2章 一阶逻辑,这章是以“谓词”为中心，主要讨论： 1、命题中的谓词、量词 2、谓词公式及翻译、等价式 3、谓词推理演算,2.1 谓词概念（个体）,定义：能够独立存在的事物，称之为个体，也称之为客体它可以是具体的，也可以是抽象的事物通常用小写英文字母a、b、c、.表示例如，小张、小李、8、a、沈阳、社会主义等等都是个体 定义：用小写英文字母x、y、z.表示任何个体，则称这些字母为个体变项（客体变元） 注意：个体变项本身不是个体2.1 谓词概念（谓词）,定义：一个大写英文字母后边有括号，括号内是若干个个体变项，用以表示客体的属性或者客体之间的关系，称之为 谓词。

如果括号内有n个个体变项，称该谓词为 n元谓词 例如： S(x):表示x是大学生 一元谓词 G(。