离散数学-数理逻辑.ppt

离散数学教材与参考资料课程主要内容目的、意义和要求学习要求学习考查方法第一篇数理逻辑第1章导论（1）定义（2）方法（3）内容（4）分支§1.2数理逻辑的发展简史起源阶段创立阶段完善阶段§1.3数理逻辑的地位和作用第2章命题逻辑2.1命题逻辑基本概念§2.1.1命题与联结词注意：（1）感叹句、祈使句、疑问句都不是命题
（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题中国的首都在北京。
1+1=10
请开门！
x+y=1
明年10月1日是晴天。
本命题是假的。
李红既学英语又学日语。（2）几个基本概念
真命题与假命题
命题变元与命题常元例2（1）简单命题与复合命题
（2）联结词的定义
（3）联结词的优先级（1）简单命题与复合命题（2）联结词的定义合取词（∧）例3将下列命题符号化.析取词（∨）相容或与排斥或例4将下列命题符号化，并指出其真值蕴涵词（）蕴涵词的其它表述方式例5设p:天冷,q:小王穿羽绒服，将下列命题符号化等价词（）例6求下列复合命题的真值：分析找出
简单命题分析找出
简单命题例8试将下列命题符号化：
如果你不看电影，那么我也不看电影
小王一边吃饭，一边看书（3）联结词的优先级1、分析下列各命题的真值
（1）2+2=4当且仅当3是奇数
（2）2+2=4当且仅当3不是奇数
（3）2+2≠4当且仅当3是奇数
（4）2+2≠4当且仅当3不是奇数课堂练习（2）§2.1.2合式公式及其分类1.命题语言的字母表（1）合式公式(命题公式,公式)的定义（2）合式公式的层次（3）公式的赋值实例3、真值表基本复合命题真值表汇总pqpqpqr4、命题公式的分类2、判断下列命题公式的类型
（1）
（2）
2.2命题逻辑等值演算§2.2.1等值式与等值演算(1)是元语言符号,不要混同于和=。
(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相
同,即A与B有相同的真值表。
(3)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值。2、性质3、真值表法判断公式是否等值pqrp(qr)(pq)r(pq)r
000101
001111
010101
011111
100111
101111
110000
1111114、基本等值式（3）交换律：（7）吸收律：（10）零律：（13）矛盾律：(1)代入规则
代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。(2)置换规则(3)等值演算
等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。（同一律）例6用等值演算法判断下列公式的类型
(1)q(pq)
解q(pq)
q(pq)（蕴涵等值式）
q(pq)（德摩根律）
p(qq)（交换律，结合律）
p0（矛盾律）
0（零律）
该式为矛盾式.例6(续)例6(续)例7：应用题解：设p：矿样为铁，q：矿样为铜，r：矿样为锡，则可得：确擅迅三檬昭项射递芭蝉层衍奈棒边踪越帘肖离欢溃漠奢诗矗佩而拇同重离散数学-数理逻辑离散数学-数理逻辑拦漠钥蝴宣止秋活的颐棍劈床笛售患秀携穆菇踞划补悼赦趁嘿鞠淘卞疯即离散数学-数理逻辑离散数学-数理逻辑等值演算不能直接证明两个公式不等值.证明两个公式不
等值的基本思想是找到一个赋值使一个成真,另一个成假.

例8证明:p(qr)(pq)r
方法一真值表法
方法二观察法.容易看出000使左边成真,使右边成假.
方法三先用等值演算化简公式,再观察.2、证明§2.2.2联结词完备集2元真值函数定义2.13设S是一个联结词集合,如果任何n(n1)元真值
函数都可以由仅含S中的联结词构成的公式表示,则称S是
联结词完备集

定理2.1下述联结词集合都是完备集:
(1)S1={,,,,}
(2)S2={,,,}
(3)S3={,,}
(4)S4={,}
(5)S5={,}
(6)S6={,}举例与非、或非P80-81：
2.10，2.12，2.13（2），2.15（1），2.16，
2.18（1），2.19（2），2.20，2.21（1），2.22（2），
2.23（1）（3）