离散数学─逻辑和证明 南京大学计算机科学与技术系

Presentation on theme: "离散数学─逻辑和证明 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─逻辑和证明 南京大学计算机科学与技术系
命题逻辑（续） 离散数学─逻辑和证明 南京大学计算机科学与技术系 致谢：部分内容改编自中科大肖明军老师的《离散数学》slides。

2 前情回顾 数理逻辑（符号逻辑） 命题 逻辑运算符 命题表达式 命题的真值表 逻辑等价 问题： 我们给出的五个逻辑运算符是否够用？

3 内容提要 常用的命题公式逻辑等价 命题逻辑的推理问题 命题逻辑公式的范式 自然演绎规则及论证 命题逻辑的正确性及完备性

4 常用的逻辑等价(1) 名称 等价 双重否定律 p  ¬¬ p 幂等律 p  p  p, p  pp
名称 等价 双重否定律 p  ¬¬ p 幂等律 p  p  p, p  pp 交换律 pq  qp, pq  qp 结合律 (pq)r  p(qr) (pq)r  p(qr) 分配律 p(qr) (pq)(pr) p(qr) (pq)(pr) 德摩根律 ¬(pq)  ¬p¬q ¬(pq)  ¬p¬q 吸收律 p(pq)  p p(pq)  p

5 常用的逻辑等价(2) 名称 等价 支配律 A1≡1, A0≡0 恒等律 A0≡A, A1≡A 排中律 A¬A ≡ 1
名称 等价 支配律 A1≡1, A0≡0 恒等律 A0≡A, A1≡A 排中律 A¬A ≡ 1 矛盾律 A¬A ≡ 0 AB≡¬AB AB≡(AB)(B  A) 假言易位 AB≡¬B¬A AB≡¬B¬A 归缪论 (AB)(A¬B)≡¬A 否定律

6 逻辑等价的判定 ¬(pq)和p¬q是否逻辑等价？ ¬(pq)  ¬(¬pq)  ¬(¬p) ¬q  p  ¬q
 ¬pp ¬q q  T

7 通过逻辑等价进行推理（续） We know that Bill, Jim and Sam are from Boston, Chicago and Detroit, respectively. Each of following sentence is half right and half wrong: Bill is from Boston, and Jim is from Chicago. Sam is from Boston, and Bill is from Chicago. Jim is from Boston, and Bill is from Detroit. Tell the truth about their home town.

8 通过逻辑等价进行推理（续） We set : So, We have: P1 = Bill is from Boston
P2 = Jim is from Chicago. P3 = Sam is from Boston P4 = Bill is from Chicago. P5 = Jim is from Boston P6 = Bill is from Detroit. So, We have: ((p1~ p2) (~p1p2))  ((p3~ p4) (~p3p4)) ((p5~ p6) (~p5p6)) is true p1 p3 is False p1 p4 is False p2 p4 is False p2 p5 is False ……

9 通过逻辑等价进行推理（续） We have:
((p1~p2)(~p1p2))((p3~p4)(~p3p4))((p5~p6)(~p5p6)) Note: ((p1~ p2)(~p1p2))  ((p3~ p4) (~p3p4)) So, (~p1p2p3~ p4) [注意前述条件] And (~p1p2p3~ p4)((p5~p6)(~p5p6)) So, (~p1p2p3~ p4~p5p6) is True So, Jim is from Chicago, Sam is from Boston, and Bill is from Detroit.

10 Sudoku谜题（九宫格数独游戏） 3232的网格，32个33的子网格。 每行、每列及每宫填入数字1-9且不能重复。 2 9 4 1
4  5 4 4 4 2 6 7 5 7 3 5 1 9 6

11 设计Sudoku谜题，使得它有（唯一）解 ?
sxyz : 第x行第y列的格子里填上数字z. There are 9 × 9 × 9 = 729 such propositions ????? ????? every column contains every number every row contains every number 设计Sudoku谜题，使得它有（唯一）解 ? each of the nine 3 × 3 blocks contains every number ……

12 命题逻辑公式的范式 为何要“范式”？ 对于给定公式的判定问题，可用真值表方法加以解释，但当公式中命题变元的数目较大时，计算量较大，每增加一个命题变元，真值表的行数要翻倍，计算量加倍，此外，对于同一问题，可以从不同的角度去考虑，产生不同的但又等价的命题公式，即同一个命题可以有不同的表达形式。这样给命题演算带来了一定的困难，因此有必要使命题公式规范化。

13 命题逻辑公式的范式 一些术语： 命题变元或命题变元的否定称为文字；
有限个文字的析取式称为简单析取式(基本和)， 有限个文字的合取式称为简单合取式(基本积)； 由有限个简单合取式构成的析取式称为析取范式(DNF，Disjunctive Normal From)， 由有限个简单析取式构成的合取式称为合取范式 (CNF，Conjunctive Normal From)。

14 命题逻辑公式的范式 例如， ①：p，¬p ； ②：p∨q∨ ¬r； ③：¬p∧q∧r； ④：(p∧q)∨(¬p∧q)； ⑤：(p∨q)∧(¬p∨q)； ①：P，¬P 是文字，简单析取式，简单合取式，析取范式，合取范式； ②：P∨Q∨ ¬R是简单析取式，析取范式，合取范式； ③：¬P∧Q∧R是简单合取式，析取范式，合取范式； ④：(P∧Q)∨(¬P∧Q)是析取范式； ⑤：(P∨Q)∧(¬P∨Q)是合取范式。

15 命题逻辑公式的范式 性质： 一个文字既是一个析取范式又是一个合取范式； 一个析取范式为矛盾式，当且仅当它的每个简单合 取式是矛盾式；
一个合取范式为重言式，当且仅当它的每个简单析 取式是重言式。 ①：P，¬P 是文字，简单析取式，简单合取式，析取范式，合取范式； ②：P∨Q∨ ¬R是简单析取式，析取范式，合取范式； ③：¬P∧Q∧R是简单合取式，析取范式，合取范式； ④：(P∧Q)∨(¬P∧Q)是析取范式； ⑤：(P∨Q)∧(¬P∨Q)是合取范式。

16 命题逻辑公式的范式 定理：任一命题公式都存在着与之等值的析取范式和合取范式。
证明：对于任一公式，可用下面的方法构造出与其等值的范式： 利用等价公式：A ↔B<=>(A→B)∧(B→A)使公式中仅含联结词¬，∧，∨； 利用德•摩根定律和双重否定律¬(A∨B) <=> ¬A∧¬B，¬(A∧B) <=> ¬A∨¬B， ¬ ¬A <=>A将否定符¬移到命题变元前，并去掉多余的否定符； 利用分配律A∧(B∨C) <=>(A∧B)∨(A∧C)， A∨(B∧C) <=>(A∨B)∧(A∨C)将公式化成析取范式或合取范式，所得即与原公式等价。 证毕

17 命题逻辑公式的范式 主析取范式和主合取范式
范式不唯一。如公式(p∨q)∧(p∨r)与之等价的公式有：p∨(q∧r)，(p∧p)∨(q∧r) ，p∨(q∧¬q)∨(q∧r)，p∨(p∧r)∨(q∧r),等。 包含所有命题变元或其否定一次仅一次的简单合取式，称为极小项； 包含所有命题变元或其否定一次仅一次的简单析取式，称为极大项； 由有限个极小项组成的析取范式称为主析取范式； 由有限个极大项组成的合取范式称为主合取范式。

18 命题逻辑公式的范式 1.极小项和极大项的性质 一般来说，对于n个命题变元，则应有 个不同的极小项和 个不同的极大项。
对于两个命题变元P，Q来说，由于每个P，Q可以取命题变元自身和其否定，所以其对应的极小项和极大项分别有四项：P∧Q， ¬P∧Q，P∧¬Q，¬P∧¬Q；P∨Q， ¬P∨Q, P∨¬Q， ¬P∨¬Q。其真值表如下： 一般来说，对于n个命题变元，则应有 个不同的极小项和 个不同的极大项。 P Q P∧Q ¬P∧Q P∧¬Q ¬P∧¬Q ¬P∨¬Q ¬P∨Q P∨¬Q P∨Q 1

19 命题逻辑公式的范式 性质： (1)：没有两个不同的极小项是等价的，且每个极小项只有一组真值指派使该极小项的真值为真，因此可给极小项编码，使极小项为“T”和那组真值指派为对应的极小项编码；如极小项¬P∧¬Q∧¬R只有在P，Q，R分别取真值0，0，0时才为真，所以有时又可用 ( )来表示，又如¬P∧Q∧¬R也可用 ( )来表示。 (2)：没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假。因此可给极大项编码，使极大项为“F”的那组真值指派为对应的极大项的编码，如极大项¬P∨¬Q∨¬R只有在P，Q，R分别取真值1，1，1时才为假，所以有时又可用 来表示。

20 命题逻辑公式的范式 P Q R 极小项 极大项 m0= ¬P∧¬Q∧¬R M0= P∨Q∨R 1 m1= ¬P∧¬Q∧R
m0= ¬P∧¬Q∧¬R M0= P∨Q∨R 1 m1= ¬P∧¬Q∧R M1= P∨Q∨¬R m2= ¬P∧Q∧¬R M2= P∨¬Q∨R m3= ¬P∧Q∧R M3= P∨¬Q∨¬R m4= P∧¬Q∧¬R M4= ¬P∨Q∨R m5= P∧¬Q∧R M5= ¬P∨Q∨¬R m6= P∧Q∧¬R M6= ¬P∨¬Q∨R m7= P∧Q∧R M7= ¬P∨¬Q∨¬R 三个命题变元的真值取值与极小项和极大项的对应对位关系表

21 命题逻辑公式的范式 (3)：任意两极小项的合取必假，任意两个极大项的析取必为真。极大项的否定是极小项，极小项的否定是极大项，即
(4)：所有极小项的析取为永真公式，所有极大项的合取是永假公式，即

22 命题逻辑公式的范式 主析取范式和主合取范式的存在性和唯一性
定理:任何命题公式的主析取范式和主合取范式存在且唯一，即任何命题公式都有且仅有一个与之等价的主合取范式和主析取范式。 证明：(证明该定理的方法与过程实际也就是求一个公式的主析取范式和主合取范式的方法，主要有两种不同的方法，一是真值表技术，一是公式转换法) [真值表技术] 根据极小项的性质，任何一个极小项的真值解释中仅有一种解释使得其真值为真，而主析取范式是由一些极小项的析取构成，因此考虑命题公式的真值表，对命题公式的每一个为真的解释，存在且唯一存在一个对应的极小项，将所有真值解释对应的极大项做析取，得到主析取范式，由极小项的性质知，在所有解释下，该主析取范式与原命题公式的真值相同，即等价。由主析取范式的构造方式知，该主析取范式存在且唯一存在。同理，主合取范式也存在且唯一存在。 解：首先看该命题公式的真值表： P Q R ((P∧Q)→R)∧(P↔Q) 其余 0 考虑三种真值的解释，对应的极小项分别为m0，m1，m7，即¬P∧¬Q∧¬R， ¬P∧¬Q∧R，P∧Q∧R， ∴其主析取范式为： (¬P∧¬Q∧¬R)∨(¬P∧¬Q∧R) ∨ (P∧Q∧R)。 解：其真值表如下： P Q R (P→Q)↔R 其余 1 考虑四种真值为假的解释，对应的极大项为M0，M2，M5，M6 所以其主合取范式为：(P∨Q∨R) ∧(P∨¬Q∨R) ∧(¬P∨Q∨¬R) ∧( ¬P∨¬Q∨R)

23 命题逻辑公式的范式 利用真值表技术求主析取范式和主合取范式的方法：
① ：选出公式的真值结果为真的所有行，在这样的行中，找到其每一个解释所对应的极小项，将这些极小项析取即可得到相应的主析取范式； ②：选出公式的真值结果为假的所有行，在这样的行中，找到其每一个解释所对应的极大项，将这些极大项合取即可得到相应的主合取范式。

24 主析取（合取）范式的唯一性 求 (pq)  r 的主析取范式 (¬p r)  (q r)  (p¬q¬r ) （析取范式）
(¬p ¬q  r)  (¬p  q  r)  (p  q  r)  (p ¬q¬r ) (¬p ¬q  r)  (¬p  q  r)  (p¬q¬r)  (p  q  r)

25 命题逻辑的推理问题

26 命题逻辑的可判定性（decidable）

27 析取（合取）范式的存在性 求 (pq)  r 的析取范式 (¬pq)  r （消去）
(¬p r)  (q r)  (p¬q¬r ) （分配律、结合律）

28 论证 An argument in propositional logic is a sequence of propositions. All but the final proposition in the argument are called premises and the final proposition is called the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true. “如果我是马云，那么我给各位每人发一辆法拉利。” “我是马云。” ∴“我给各位每人发一辆法拉利。” “如果我是教师，那么我要上课。” “我是教师。” ∴“我要上课。”

29 论证形式 An argument form in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true. 𝑝→𝑞 𝑝 ∴ 𝑞

30 命题逻辑的“自然演绎”规则 p pq —— q ¬q pq —— ¬p pq qr ——— pr pq ¬p ——— q
假言推理 取拒式 假言三段论 析取三段论 p ——— pq pq ——— p pq ¬pr ——— qr p q ——— pq 附加 化简 合取引入 消解

31 用推理规则建立论证 “今天下午不出太阳并且比昨天冷”，“只有今天下午出太阳，我们才去游泳”，“若我们不去游泳，则我们将乘独木舟游览”，“若我们乘独木舟游览，则我们将在黄昏时回家”，结论“我们将在黄昏时回家”。 p: 今天下午出太阳，q: 今天比昨天冷，r: 我们将去游泳， s: 我们将乘独木舟游览，t: 我们将在黄昏时回家。 ¬p  q r  p ¬r  s s  t ¬p 化简 ¬r 取拒式 s 假言推理 t 假言推理

32 用推理规则及逻辑等价建立论证 已知(pq)r和 r  s, ps 是否为真？ (pq)r  (pr) (pq)
r  s  rs pr 化简 ps 消解 pr s¬r ——— ps 消解

33 注意书写论证的格式

34 命题逻辑的正确性与完备性 基于自然演绎规则的推导 基于真值表的语义蕴涵

35 论证中的谬误（举例）  

36 [练习题] 运用命题逻辑，请根据下面事实，找出凶手： a. 清洁工或者秘书谋害了经理 b. 如果清洁工谋害了经理，则谋害不会发生在午夜前 c. 如果秘书的证词是正确的，则谋害发生在午夜前 d. 如果秘书的证词不正确，则午夜时屋里灯光未灭 e. 如果清洁工富裕，则他不会谋害经理 f. 经理有钱且清洁工不富裕 g. 午夜时屋里灯灭了

37 作业 教材内容：[Rosen] 1.6 节 课后习题： 见课程网站或者微信群