mathchap离散数学命题逻辑.pptx

《mathchap离散数学命题逻辑.pptx》由会员分享，可在线阅读，更多相关《mathchap离散数学命题逻辑.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、题常项：真值可以确定；命题变项：真值可以变化。本质不是命题。第4页/共59页5 5复合命题及联结复合命题：由简单命题通过联结词联结而成的命题。常见联结词否定联结词合取联结词析取联结词蕴涵联结词等价联结词第5页/共59页6 6n例nP：今天是星期二。np：今天不是星期二。nq：所有人都来上课了。nq：不是所有人来上课了。有人没来上课。否定式定义：复合命题“非p”称为p的否定式，记作p。为否定联结词。p为真当且仅当p为假。即p表示对p的真值取反。pp1001第6页/共59页7 7n例n小李既勤奋又聪明。n小李不仅勤奋而且聪明。n小李虽然聪明，但是不勤奋。n小李和小王都很勤奋。n小李和小王是同学。n

3、注：并不是所有的“和”、“与”都表示合取关系。合取式定义：复合命题“p并且q”称为p与q的合取式，记作pq。为合取联结词。pq为真当前仅当p与q同时为真。其他情况时pq为假。pqp q111100010000第7页/共59页8 8n例n小李爱唱歌或者爱打篮球。n小李在打篮球或者在踢足球。n小李可以坐火车或者乘飞机回家。析取式定义：复合命题“p或者q”称为p与q的析取式，记作pq。为析取联结词。pq为假当且仅当p与q同时为假。其他情况pq为真。pqpq111101011000第8页/共59页9 9析取式自然语言中的“或”具有二义性，与析取式中的“或”含义不完全相同。析取式可表示“相容或”和“不同

4、时为真排斥或”；“能同时为真的排斥或”可用“异或”关系表示。第9页/共59页1010蕴涵式定义：复合命题“如果p，则q”称为p与q的蕴涵式，记作pq。pq为假当前仅当p为真且q为假。其他情况时，pq为真。pqpq111100011001n自然语言中p与q具有联系，而数理逻辑中p与q可以没有联系。n例n如果336，则雪是黑的。n如果3+36，则雪是黑的。第10页/共59页1111蕴涵式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整除。第11页/共59页1212等价式定义：复合命题“p当且仅当q”称为p与q的等价式，记作pq。称作等价联结词。pq为真当且仅当p与q真值相同。其他情况时，pq为假。pqpq111100010001npq在逻辑上表明p与q互为充要条件。n例：n若今天为1号，则明天是2号，反之亦然。n今天是雨天当且仅当雪是黑的。第12页/共59页1313基本复合命题真值表pqpp qpq pqpq0010011011011010001001101111第13页/共59页1414联结词的优先顺序()第14页/共59页1515练习判断下列命题的真值若224，则336若224，则336若224，则336若22

6、4，则336224当且仅当336224当且仅当336224当且仅当336224当且仅当336第15页/共59页1616练习将下列命题符号化2是偶数又是素数他一边吃饭一边看电视如果天下雨，他就乘公共汽车上班只有天下雨，他才乘公共汽车上班不经一事，不长一智第16页/共59页1717练习设p、q的真值为0，r、s的真值为1，求下列命题公式的真值p(qr)(pr)(qs)第17页/共59页1818命题公式命题常项（命题常元）：简单命题，真值唯一确定。命题变项（命题变元）：真值可以变化的陈述句。命题常项和命题变元都用小写字母表示。合式公式（命题公式）：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的

7、符号串。第18页/共59页1919合式公式的定义递归定义1.单个命题变项是合式公式，并称为原子命题公式；2.若A是合式公式，则(A)也是合式公式；3.若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式；4.只有有限次地应用13形式的符号串才是合式公式。子公式定义若A为合式公式，B为A的一部分，且B也是合式公式，则称B为A的子公式。第19页/共59页2020公式的赋值定义设A为一命题公式，p1,p2,pn,为所有在A中出现的命题变项。给p1,p2,pn指定一组真值，称其为A的一个赋值或解释。若指定的一组赋值使A的真值为真，则称这组值为A的成真赋值。若指定的一组赋值使A的真值

8、为假，则称这组值为A的成假赋值。将一个命题公式在所有赋值下的情况列成表，称为这个公式的真值表。n个命题变项共有2n组赋值。第20页/共59页2121例p(qr)的真值表pqrq rp(q r)0000000100010000111110001101011100111111第21页/共59页2222例p(pq)的真值表pqppqp(pq)00111011111000111011第22页/共59页2323例p(pq)的真值表pqpp qp(p q)00100011101000011000第23页/共59页2424重言式（永真式）：所有的赋值都是A的成真赋值。矛盾式（永假式）：所有的赋值都是A的成假

9、赋值。可满足式：至少存在一组赋值使A为真。第24页/共59页2525等值演算等值式（等价式）设A，B为两命题公式，若AB为重言式，则称A与B为等值式，记为AB。不是逻辑联结词，表示对任意的赋值，A与B的值相同。是等价联结词，它与不能混为一谈。等值式的性质（等价关系的通性）自反性：AA；对称性：若AB，则BA；传递性：若AB和BC，则AC。第25页/共59页2626例pq与pq是否等值？第26页/共59页2727基本等值规律(1)双重否定律AA等幂律AAAAAA交换律ABBAABBA结合律A(BC)(AB)CA(BC)(AB)C第27页/共59页2828基本等值规律(2)分配律A(BC)(AB)

10、(AC)A(BC)(AB)(AC)(AB)AB(AB)AB吸收律A(AB)AA(AB)A第28页/共59页2929基本等值规律(3)零律A11A00同一律A0AA1A排中律AA1矛盾律AA0第29页/共59页3030基本等值规律(4)蕴涵等值式ABAB等价等值式AB(AB)(BA)(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A第30页/共59页3131置换规则设(A)为含公式A的命题公式，(B)为用公式B置换了A的命题公式，若AB，则(A)(B)。利用等值规律及置换规则可以进行等值演算。例(pq)(qp)(qp)p(pq)(qp)(pq)r(p(pq)r第31页

11、/共59页3232联结词的完备集问题：含n个命题变项的命题公式其真值表的可能性有多少种？n元真值函数：F：0,1n0,1为n元真值函数。联结词完备集：设S是一个联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。,第32页/共59页3333对偶对偶的定义：在仅含有,的命题公式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

12、,pn)A*(p1,p2,pn)对偶原理：设A、B为两命题公式，若AB，则A*B*。第33页/共59页3434范式的概念命题公式的规范表示方法析取范式合取范式文字：命题变项及其否定式统称文字简单析取式仅有有限个文字构成的析取式简单合取式仅有有限个文字构成的合取式定理：一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式第34页/共59页3535析取范式定义由有限个简单合取式构成的析取式例pq(pq)r析取范式性质析取范式是矛盾式当且仅当它的每个简单合取式是矛盾式第35页/共59页3636合取范式定义:由有限个简单析取式构成的合

13、取式例pq(pq)r合取范式性质合取范式是重言式，当且仅当它的每个简单析取式是重言式第36页/共59页3737范式存在定理定理：任一命题公式都存在与之等值的析取范式（合取范式）。求范式的步骤利用蕴涵等值式和等价等值式消去联结词、。用双重否定律消去否定联结词，利用德.摩根律将否定联结词内移。利用分配律求析取范式或合取范式。例：(pq)r第37页/共59页范式的求解例：(pq)r3838第38页/共59页3939极小项与极大项极小项的定义在含n个命题变项的简单合取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。极大项的定义在含n个命题变

14、项的简单析取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。n个命题变项共可形成2n个极小项和2n个极大项。第39页/共59页4040极小项的成真赋值每个极小项仅有一个成真赋值每个极小项的成真赋值均不相同可以利用不同的成真赋值区别每个极小项，给予标记二元极小项二元极小项取值取值成真赋值成真赋值简记名称简记名称p q100m0p q101m1p q110m2p q111m3第40页/共59页4141极大项的成假赋值每个极大项仅有一个成假赋值每个极大项的成假赋值均不相同可以利用不同的成假赋值区别每个极大项，给予标记二元极大项二元极大项取

15、值取值成假赋值成假赋值简记名称简记名称pq000M0pq001M1pq010M2pq011M3第41页/共59页4242主析取范式与主合取范式主析取范式的定义若A的命题公式由若干个极小项进行析取构成，则称该析取范式为A的主析取范式从主析取范式中很容易得到成真赋值主合取范式的定义若A的命题公式由若干个极大项进行合取构成，则称该合取范式为A的主合取范式从主合取范式中很容易得到成假赋值定理：任何命题公式都存在与之等值的主析取（合取）范式，且唯一。第42页/共59页4343主析取范式的求解方法(1)用等值演算求得析取范式依次扫描析取范式中的每个简单合取式B若B为极小项，则继续扫描下一个若B不为极小项，

16、将不含的命题变项p及其否定式p用等值变换添入BB(pp)(Bp)(Bp)消去重复出现的命题变项、极小项和矛盾式。第43页/共59页4444主析取范式的求解方法(2)根据公式构造真值表写出每个公式成真赋值对应的极小项将极小项进行析取，即得主析取范式第44页/共59页4545主析取范式例：求(p(qr)(p(qr)第45页/共59页4646主合取范式的求解方法(1)用等值演算求得合取范式依次扫描合取范式中的每个简单析取式B若B为极大项，则继续扫描下一个若B不为极大项，将不含的命题变项p及其否定式p用等值变换添入BB(pp)(Bp)(Bp)消去重复出现的命题变项、极大项和重言式。第46页/共59页4

17、747主合取范式的求解方法(2)根据公式构造真值表写出每个公式成假赋值对应的极大项将极大项进行合取，即得主合取范式第47页/共59页4848主合取范式例：求(p(qr)(p(qr)第48页/共59页4949主析取范式与主合取范式主析取范式与主合取范式之间的关系？第49页/共59页5050推理的形式结构设两命题公式A、B，若AB为重言式，则称A蕴涵B，记为AB。设A1、A2、.、An、B为命题公式，若A1A2.An B，则称B为A1、A2、.、An的逻辑结论或有效结论，也称B可由一组前提A1、A2、.、An逻辑推出。记为A1，A2，.，AnB。正确推理的本质是A1A2.AnB为重言式。当A1A2

18、.An为假时，不论B是真是假，A1A2.AnB均为真。所以B为有效结论并不意味B为真。第50页/共59页5151推理的基本方法简单证明法：证明A1A2.AnB是重言式，即A1A2.AnB1。真值表法等值演算法主析取范式法例：若a能被4整除，则a能被2整除。因为a能被2整除，所以a能被4整除。第51页/共59页5252推理的基本方法(2)直接构造证明法由给定的一组前提出发，利用推理规则逐步演算得到结论。常用推理规则前提引入规则：在证明过程的任何步骤都可以将前提引入使用结论引入规则：在推理中，若已证出结论B，则B可以引入到以后的推理中作为前提使用置换规则：命题公式中任何子公式都可以用等值公式置换化

19、简规则：AB A，AB B附加规则：AAB第52页/共59页5353常用推理规则假言推理规则：AB，AB拒取式规则：AB，BA析取三段论：AB，AB假言三段推理：AB，BCAC等价三段论：AB，BCAC构造性二难规则：AB，CD，ACBD破坏性二难规则：AB，CD，BDAC合取引入规则：A，BAB第53页/共59页5454常用推理规则证明：若a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数，所以a是无理数。第54页/共59页5555推理的基本方法(3)间接构造证明法附加前提证明法A1A2.AnBCA1A2.AnB C归谬法A1A2.AnBA1A2.AnB 0第55页/共59页5656推理的基本方法(3)例：证明p(qr)，sp，qsr例：如果小张守第一垒并且小李向B队投球，则A队将获胜。A队未取胜或者A队成为联赛第一名。A队没有成为联赛的第一名。小张守第一垒。因此小李没向B队投球。第56页/共59页5757作业(1)P33 1.5 (3)(4)(7)P33 1.6 (3)(4)第57页/共59页5858作业(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)第58页/共59页感谢您的观看！第59页/共59页