math-chap1-1.离散数学_命题逻辑.ppt

《math-chap1-1.离散数学_命题逻辑.ppt》由会员分享，可在线阅读，更多相关《math-chap1-1.离散数学_命题逻辑.ppt（59页珍藏版）》请在三一文库上搜索。

1、庄伯金 ,1,第一章,命题逻辑 课件下载地址：,庄伯金 ,2,主要内容,命题的基本概念 等值演算 范式 推理理论,庄伯金 ,3,命题的基本概念,命题的定义 能判断真假的陈述句 命题的两个关键要素 必须是陈述句 能明确地判断真假 命题的真值 判断为正确的命题，其真值为真（1）； 判断为错误的命题，其真值为假（0）。,庄伯金 ,4,命题的例,4是素数。 x大于y。 充分大的偶数等于两个素数之和。(歌德巴赫猜想) 2020年5月1日北京的天气是雨天。 请不要吸烟！ 这朵花真美丽啊！ 我正在说假话。 你现在好吗？,庄伯金 ,5,命题符号化,命题常用小写字母表示，如p：4是素数 命题的真值表示： 1表示

2、真 0表示假 简单命题 不能被分解为更简单的陈述句的命题 也称为原子命题 命题常项与命题变项 命题常项：真值可以确定； 命题变项：真值可以变化。本质不是命题。,庄伯金 ,6,复合命题及联结,复合命题：由简单命题通过联结词联结而成的命题。 常见联结词 否定联结词 合取联结词 析取联结词 蕴涵联结词 等价联结词,庄伯金 ,7,例 P：今天是星期二。 p：今天不是星期二。 q：所有人都来上课了。 q：不是所有人来上课了。 有人没来上课。,否定式,定义：复合命题“非p”称为p的否定式，记作p。为否定联结词。 p为真当且仅当p为假。即p表示对p的真值取反。,庄伯金 ,8,例 小李既勤奋又聪明。 小李不仅

3、勤奋而且聪明。 小李虽然聪明，但是不勤奋。 小李和小王都很勤奋。 小李和小王是同学。 注：并不是所有的“和”、“与”都表示合取关系。,合取式,定义：复合命题“p并且q”称为p与q的合取式，记作pq。 为合取联结词。 pq为真当前仅当p与q同时为真。其他情况时pq为假。,庄伯金 ,9,例 小李爱唱歌或者爱打篮球。 小李在打篮球或者在踢足球。 小李可以坐火车或者乘飞机回家。,析取式,定义：复合命题“p或者q”称为p与q的析取式，记作pq。为析取联结词。 pq为假当且仅当p与q同时为假。其他情况pq为真。,庄伯金 ,10,析取式,自然语言中的“或”具有二义性，与析取式中的“或”含义不完全相同。 析取

4、式可表示“相容或”和“不同时为真排斥或”； “能同时为真的排斥或”可用“异或”关系表示。,庄伯金 ,11,蕴涵式,定义：复合命题“如果p，则q”称为p与q的蕴涵式，记作pq。 pq为假当前仅当p为真且q为假。其他情况时， pq为真。,自然语言中p与q具有联系，而数理逻辑中p与q可以没有联系。 例 如果336，则雪是黑的。 如果3+36，则雪是黑的。,庄伯金 ,12,蕴涵式,pq在逻辑上表明p为q的充分条件，q为p的必要条件。 例 只要a能被4整除，则a一定能被2整除。 a能被4整除，仅当a能被2整除。 除非a能被2整除，a才能被4整除。 只有a能被2整除，a才能被4整除。 只有a能被4整除，a

5、才能被2整除。,庄伯金 ,13,等价式,定义：复合命题“p当且仅当q”称为p与q的等价式，记作pq。称作等价联结词。 pq为真当且仅当p与q真值相同。其他情况时，pq为假。,pq在逻辑上表明p与q互为充要条件。 例： 若今天为1号，则明天是2号，反之亦然。 今天是雨天当且仅当雪是黑的。,庄伯金 ,14,基本复合命题真值表,庄伯金 ,15,联结词的优先顺序,() ,庄伯金 ,16,练习,判断下列命题的真值 若224，则336 若224，则336 若224，则336 若224，则336 224当且仅当336 224当且仅当336 224当且仅当336 224当且仅当336,庄伯金 ,17,练习,将

6、下列命题符号化 2是偶数又是素数 他一边吃饭一边看电视 如果天下雨，他就乘公共汽车上班 只有天下雨，他才乘公共汽车上班 不经一事，不长一智,庄伯金 ,18,练习,设p、q的真值为0，r、s的真值为1，求下列命题公式的真值 p(qr) (pr)(qs),庄伯金 ,19,命题公式,命题常项（命题常元）：简单命题，真值唯一确定。 命题变项（命题变元）：真值可以变化的陈述句。 命题常项和命题变元都用小写字母表示。 合式公式（命题公式）：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。,庄伯金 ,20,合式公式的定义,递归定义 1. 单个命题变项是合式公式，并称为原子命题公式； 2. 若A是

7、合式公式，则(A)也是合式公式； 3. 若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式； 4. 只有有限次地应用13形式的符号串才是合式公式。 子公式定义 若A为合式公式，B为A的一部分，且B也是合式公式，则称B为A的子公式。,庄伯金 ,21,公式的赋值,定义 设A为一命题公式，p1, p2, , pn, 为所有在A中出现的命题变项。给p1, p2, , pn指定一组真值，称其为A的一个赋值或解释。 若指定的一组赋值使A的真值为真，则称这组值为A的成真赋值。 若指定的一组赋值使A的真值为假，则称这组值为A的成假赋值。 将一个命题公式在所有赋值下的情况列成表，称为这个公

8、式的真值表。 n个命题变项共有2n组赋值。,庄伯金 ,22,例,p(qr)的真值表,庄伯金 ,23,例,p(pq)的真值表,庄伯金 ,24,例,p(pq)的真值表,庄伯金 ,25,重言式（永真式）： 所有的赋值都是A的成真赋值。 矛盾式（永假式）： 所有的赋值都是A的成假赋值。 可满足式： 至少存在一组赋值使A为真。,庄伯金 ,26,等值演算,等值式（等价式） 设A，B为两命题公式，若AB为重言式，则称A与B为等值式，记为AB。 不是逻辑联结词，表示对任意的赋值，A与B的值相同。 是等价联结词，它与不能混为一谈。 等值式的性质（等价关系的通性） 自反性：AA； 对称性：若AB，则BA； 传递性

9、：若AB和BC，则AC。,庄伯金 ,27,例,pq与pq是否等值？,庄伯金 ,28,基本等值规律(1),双重否定律 AA 等幂律 AAA AAA 交换律 ABBA ABBA 结合律 A(BC)(AB)C A(BC)(AB)C,庄伯金 ,29,基本等值规律(2),分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 德.摩根律 (AB)AB (AB)AB 吸收律 A(AB)A A(AB)A,庄伯金 ,30,基本等值规律(3),零律 A11 A00 同一律 A0A A1A 排中律 AA1 矛盾律 AA0,庄伯金 ,31,基本等值规律(4),蕴涵等值式 ABAB 等价等值式 AB(AB)(

10、BA) (AB)(BA) 假言易位 ABBA 等价否定等值式 ABAB 归谬论 (AB)(AB)A,庄伯金 ,32,置换规则,设(A)为含公式A的命题公式，(B)为用公式B置换了A的命题公式，若AB，则(A)(B)。 利用等值规律及置换规则可以进行等值演算。 例 (pq)(qp) (qp)p (pq)(qp) (pq) r (p(pq)r,庄伯金 ,33,联结词的完备集,问题：含n个命题变项的命题公式其真值表的可能性有多少种？ n元真值函数：F：0,1n0,1为n元真值函数。 联结词完备集：设S是一个联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。

11、 , , , , , ,庄伯金 ,34,对偶,对偶的定义：在仅含有, , 的命题公式A中，将换成， 换成，若A中含0或1，将0换成1，1换成0，所得的命题公式称为A的对偶式，记为A*。 定理：设A和A*互为对偶式， p1, p2, , pn是出现在A和A*中的全部命题变项，若将A和A*写成n元函数形式，则： (1)A(p1, p2, , pn)A*(p1,p2, ,pn) (2) A(p1,p2, ,pn)A*(p1, p2, , pn) 对偶原理：设A、B为两命题公式，若AB，则A*B*。,庄伯金 ,35,范式的概念,命题公式的规范表示方法 析取范式 合取范式 文字：命题变项及其否定式统称文

12、字 简单析取式 仅有有限个文字构成的析取式 简单合取式 仅有有限个文字构成的合取式 定理： 一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式,庄伯金 ,36,析取范式,定义 由有限个简单合取式构成的析取式 例 pq (pq)r 析取范式性质 析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式,庄伯金 ,37,合取范式,定义: 由有限个简单析取式构成的合取式 例 pq (pq)r 合取范式性质 合取范式是重言式，当且仅当它的每个简单析取式是重言式,庄伯金 ,38,范式存在定理,定理：任一命题公式都存在与之等值的析取范式（合

13、取范式）。 求范式的步骤 利用蕴涵等值式和等价等值式消去联结词 、。 用双重否定律消去否定联结词，利用德.摩根律将否定联结词内移。 利用分配律求析取范式或合取范式。 例： (pq)r,庄伯金 ,39,范式的求解,例： (pq)r,庄伯金 ,40,极小项与极大项,极小项的定义 在含n个命题变项的简单合取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。 极大项的定义 在含n个命题变项的简单析取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。 n个命题变项共可形成2n个极小项和

14、2n个极大项。,庄伯金 ,41,极小项的成真赋值,每个极小项仅有一个成真赋值 每个极小项的成真赋值均不相同 可以利用不同的成真赋值区别每个极小项，给予标记,庄伯金 ,42,极大项的成假赋值,每个极大项仅有一个成假赋值 每个极大项的成假赋值均不相同 可以利用不同的成假赋值区别每个极大项，给予标记,庄伯金 ,43,主析取范式与主合取范式,主析取范式的定义 若A的命题公式由若干个极小项进行析取构成，则称该析取范式为A的主析取范式 从主析取范式中很容易得到成真赋值 主合取范式的定义 若A的命题公式由若干个极大项进行合取构成，则称该合取范式为A的主合取范式 从主合取范式中很容易得到成假赋值 定理：任何命

15、题公式都存在与之等值的主析取（合取）范式，且唯一。,庄伯金 ,44,主析取范式的求解方法(1),用等值演算求得析取范式 依次扫描析取范式中的每个简单合取式B 若B为极小项，则继续扫描下一个 若B不为极小项，将不含的命题变项p及其否定式p用等值变换添入BB(pp) (Bp)(Bp) 消去重复出现的命题变项、极小项和矛盾式。,庄伯金 ,45,主析取范式的求解方法(2),根据公式构造真值表 写出每个公式成真赋值对应的极小项 将极小项进行析取，即得主析取范式,庄伯金 ,46,主析取范式,例：求(p(qr)(p(qr),庄伯金 ,47,主合取范式的求解方法(1),用等值演算求得合取范式 依次扫描合取范式

16、中的每个简单析取式B 若B为极大项，则继续扫描下一个 若B不为极大项，将不含的命题变项p及其否定式p用等值变换添入BB (pp) (Bp)(Bp) 消去重复出现的命题变项、极大项和重言式。,庄伯金 ,48,主合取范式的求解方法(2),根据公式构造真值表 写出每个公式成假赋值对应的极大项 将极大项进行合取，即得主合取范式,庄伯金 ,49,主合取范式,例：求(p(qr)(p(qr),庄伯金 ,50,主析取范式与主合取范式,主析取范式与主合取范式之间的关系？,庄伯金 ,51,推理的形式结构,设两命题公式A、B，若AB为重言式，则称A蕴涵B，记为AB。 设A1、A2、.、An、B为命题公式，若A1A2

17、. An B，则称B为A1、A2、.、An的逻辑结论或有效结论，也称B可由一组前提A1、A2、.、An逻辑推出。记为A1，A2，.，AnB。 正确推理的本质是A1A2. AnB为重言式。 当A1A2. An为假时，不论B是真是假， A1A2. AnB均为真。所以B为有效结论并不意味B为真。,庄伯金 ,52,推理的基本方法,简单证明法： 证明A1A2. AnB是重言式，即A1A2. AnB1。 真值表法 等值演算法 主析取范式法 例：若a能被4整除，则a能被2整除。因为a能被2整除，所以a能被4整除。,庄伯金 ,53,推理的基本方法(2),直接构造证明法 由给定的一组前提出发，利用推理规则逐步演

18、算得到结论。 常用推理规则 前提引入规则：在证明过程的任何步骤都可以将前提引入使用 结论引入规则：在推理中，若已证出结论B，则B可以引入到以后的推理中作为前提使用 置换规则：命题公式中任何子公式都可以用等值公式置换 化简规则： AB A， AB B 附加规则： AAB,庄伯金 ,54,常用推理规则,假言推理规则：AB，AB 拒取式规则：AB，BA 析取三段论：AB，AB 假言三段推理：AB，BCAC 等价三段论：AB，BCAC 构造性二难规则：AB，CD，ACBD 破坏性二难规则： AB，CD，BDAC 合取引入规则：A，BAB,庄伯金 ,55,常用推理规则,证明：若a是实数，则它不是有理数就

19、是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数，所以a是无理数。,庄伯金 ,56,推理的基本方法(3),间接构造证明法 附加前提证明法 A1A2. AnBC A1A2. AnB C 归谬法 A1A2. AnB A1A2. AnB 0,庄伯金 ,57,推理的基本方法(3),例：证明p(qr)，sp，qsr 例：如果小张守第一垒并且小李向B队投球，则A队将获胜。A队未取胜或者A队成为联赛第一名。A队没有成为联赛的第一名。小张守第一垒。因此小李没向B队投球。,庄伯金 ,58,作业(1),P33 1.5 (3)(4)(7) P33 1.6 (3)(4),庄伯金 ,59,作业(2),P34 1.7 (4)(9)(10) P34 1.8 (2) P34 1.9 (3) P34 1.10 (2)(3) P34 1.11 (1) (2)(3),