离散数学-数理逻辑课件.pptVIP

离 散 数 学;教材与参考资料;课程主要内容;目的、意义和要求;学习要求;学习考查方法;第一篇 数理逻辑第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、真值表;基本复合命题真值表汇总; p q ; p q ; p q r;4、命题公式的分类;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、真值表法判断公式是否等值; p q r p?(q?r) (p?q)?r (p?q)?r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 ;4、基本等值式;（3）交换律：;（7）吸收律：;（10）零律：;（13）矛盾律：; (1) 代入规则 代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。;(2) 置换规则 ;(3)? 等值演算 等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。 ;;（同一律）;例6 用等值演算法判断下列公式的类型 (1) q??(p?q) 解 q??(p?q) ? q??(?p?q) （蕴涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交换律，结合律）