第一章 命题逻辑4.ppt

离散数学
第一章命题逻辑
2/38
回顾
对偶原理
定义,
三条原理:非运算与对偶,等价,永真蕴含
析取范式和合取范式
基本积,基本和
基本和的积,基本积的和
主析取范式和主合取范式
极小项(积),极大项(和),基—二进制数—十进制数—描述符
极小项的和,极大项的积,两者的关系。
3/38
求范式步骤:
(2) 否定消去或内移。
(3) 利用分配律。
(1) 消去联结词
回顾
4/38
命题演算的推理理论
数理逻辑的一个主要任务就是提供一套推理规则,给定一些前提,利用所提供的推理规则,推导出一些结论来,这个过程称为演绎或证明。
生活中:
倘若认定前提是真的,从前提推导出结论的论证是遵守了逻辑推理规则,则认为此结论是真的,并且认为这个论证过程是合法的。
数理逻辑中:
不关心前提的真实真值,把注意力集中于推理规则的研究,依据这些推理规则推导出的任何结论,称为有效结论,而这种论证则被称为有效论证。
5/38
有效结论
定义:设A和B是两个命题公式,当且仅当AB是个永真式,即AB,则说B是A的有效结论,或B由A可逻辑的推出。
可把该定义推广到有n个前提的情况。
6/38
有效结论
定义:
例:
H1:今天晴天或者今天下雨。
H2:今天不是晴天。
C:今天下雨。
7/38
证明有效结论的方法
1,真值表法
思路:“证明使前提集合取值为真的那些组真值指派,也一定使结论取值为真”。
例:考察结论C是否是下列前提H1,H2,H3的结论。
(1) H1:P→Q,H2:P,C:Q
P
Q
H1
H2
C
H1Λ H2→C
0
0
1
0
0
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
8/38
真值表法
(2)
真值表构造如下:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
1
1
0
1
0
1
0
1
0
1
1
1
1
0
0
0
0
9/38
真值表法
(3)
0 0
0 1
1 0
1 1
1
1
0
0
0
1
1
1
0
0
0
1
10/38
真值表法
例:一份统计表格的错误或者是由于材料不可靠,或者是由于计算有错误;这份统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误。
解:
设P:一份统计表格的错误是由于材料不可靠。
Q:一份统计表格的错误是由于计算有错误。
于是问题可符号化为:
(PQ)PQ