欢迎来到天天文库
浏览记录
ID:50504065
大小:2.42 MB
页数:29页
时间:2020-03-10
《离散数学 第2版 教学课件 作者 王元元 离散第10讲 重言式.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、计算机专业基础课程授课人:王元元单位:计算机理论教研室指挥自动化学院计算机系-2-第10讲逻辑等价式和逻辑蕴涵式PowerPointTemplate_Sub1命题与逻辑联结词2逻辑等价式和逻辑蕴涵式3范式4证明技术(补充)逻辑等价式和逻辑蕴涵式《离散数学》第10讲Page34to38-4-第10讲逻辑等价式和逻辑蕴涵式内容提要重言式重要的逻辑等价式重要的逻辑蕴含式代入与替换原理逻辑等价式和逻辑蕴涵式的证明方法-5-第10讲逻辑等价式和逻辑蕴涵式重言式(tautology,同义反复,重复)设A为一命题公式若对A中所有命
2、题变元的任一组指派,A均取真的真值,则称A为重言式或永真式。若对A中所有命题变元的任一组指派,A均取假的真值,则称A为永假式或不可满足式。如果至少存在一组指派使A取真的真值,则称A为可满足式(satisfactableformula)。-6-第10讲逻辑等价式和逻辑蕴涵式重言式的证明要证明一个公式为永真式(或永假式),列出该公式的真值表,然后看真值表的最后一列。若全为1,则为永真式,若全为0,则为永假式。证明:p∨┐p为永真式,p∧┐p为永假式,(p∧(p→q))→q为永真式p┐pp∧┐pp∨┐p01011001pq
3、p→qp∧(p→q)p∧(p→q)→q00101011011000111111-7-第10讲逻辑等价式和逻辑蕴涵式逻辑等价式(logicallyequivalent)当命题公式AB为永真式时,称A逻辑等价于B,记成A┝┥B蕴涵命题A→B和其逆否命题┐B→┐A等价:A→B┐B→┐A为永真式即:A→B┝┥┐B→┐A逻辑等价:使A为真的指派一定使B为真;使A为假的指派一定使B为假。是逻辑联结词,而┝┥不是逻辑联结词,它仅仅是一种记号。A┝┥B表示AB为永真式。逻辑等价具有以下性质:自反性:A┝┥A对称性:若A┝┥B
4、,则B┝┥A传递性:若A┝┥B,B┝┥C,则A┝┥C-8-第10讲逻辑等价式和逻辑蕴涵式逻辑等价式的证明证明:┐(A∨B)┝┥┐A∧┐BABA∨B┐(A∨B)┐A┐B┐A∧┐B┐(A∨B)┐A∧┐B000111110110100110100101111000011)假设(┐(A∨B))=1,要证(┐A∧┐B)=1得(A∨B)=0,得(A)=0且(B)=0;从而(┐A)=1且(┐B)=1,得到(┐A∧┐B)=1。2)假设(┐(A∨B))=0,要证(┐A∧┐B)=0得(A∨B)=12.1)(A)
5、=1:得(┐A)=0,得到(┐A∧┐B)=02.2)(B)=1:得(┐B)=0,得到(┐A∧┐B)=0德摩根律┐(A1∨A2)┝┥┐A1∧┐A2┐(A1∨A2∨…∨An)┝┥┐A1∧┐A2∧…∧┐An┐(A1∧A2)┝┥┐A1∨┐A2┐(A1∧A2∧…∧An)┝┥┐A1∨┐A2∨…∨┐An-9-第10讲逻辑等价式和逻辑蕴涵式问题1我和他不都是傻子p:我是傻子q:他是傻子我和他都是傻子不成立:┐(p∧q)我不是傻子或者他不是傻子:┐p∨┐qpq┐(p∧q)┐p∨┐q┐(p∧q)┐p∨┐q0011101111
6、1011111001A与B等价是说AB永真-10-第10讲逻辑等价式和逻辑蕴涵式逻辑等价式的证明证明:A→B┝┥┐A∨BABA→B┐A┐A∨BA→B┐A∨B000110111)假设(A→B)=1,要证(┐A∨B)=11.1)(A)=0:得(┐A)=1,得到(┐A∨B)=11.2)(B)=1:到(┐A∨B)=02)假设(A→B)=0,要证(┐A∨B)=0得(A)=1且(B)=0;从而(┐A)=0,得到(┐A∨B)=0。1101110011011111-11-第10讲逻辑等价式和逻辑蕴涵式一
7、些重要的逻辑等价式E1┐┐A┝┥A双重否定律E2A∨A┝┥A,A∧A┝┥A幂等律E3A∨B┝┥B∨A,A∧B┝┥B∧A交换律E4(A∨B)∨C┝┥A∨(B∨C)结合律(A∧B)∧C┝┥A∧(B∧C)E5A∧(B∨C)┝┥(A∧B)∨(A∧C)分配律A∨(B∧C)┝┥(A∨B)∧(A∨C)-12-第10讲逻辑等价式和逻辑蕴涵式一些重要的逻辑等价式E6┐(A∨B)┝┥┐A∧┐BDeMorgan律┐(A∧B)┝┥┐A∨┐BE7A∨(A∧B)┝┥A吸收律A∧(A∨B)┝┥AE8A→B┝┥┐A∨B蕴涵表达式E9AB┝┥(A→
8、B)∧(B→A)等值表达式E10A∨t┝┥t,A∧f┝┥f0-1律A∨f┝┥A,A∧t┝┥A-13-第10讲逻辑等价式和逻辑蕴涵式一些重要的逻辑等价式E11A∨┐A┝┥t排中律E12A∧┐A┝┥f矛盾律E13┐t┝┥f,┐f┝┥tE14A∧B→C┝┥A→(B→C)输出律E15A→B┝┥┐B→┐A逆反律E16(A→B)∧(A→┐B)┝┥┐A归缪律
此文档下载收益归作者所有