由P∨(P∧Q)=P可得P∧(P∨Q)=P 由P∧Q= (P∨Q) 可得 P∨Q= (P∧Q) 由F∧P =F 可得 T∨P =T
蕴含重言式
基本蕴含重言式
第182页(43)-(61),可用真值表证明 P∧Q P意味着P∧Q → P永真 P T T F F Q T F T F P∧Q T F F F P∧Q → P T T T T
�
P∧(P∨Q) Q
P, P→Q╞ Q Q, P→Q╞ P P→Q, Q→R╞ P→R P∨Q, P→R, Q→R╞ R
假言推论 拒取式 假言三段论 两难推论
命题逻辑推理
例子:假设下列推论是正确的
只要姚明上场,火箭就能赢开拓者 如果张三认真听课,姚明就答应上场 只要赢了开拓者,姚明就可以加工资
能否证明:张三不认真听课,姚明就加 不上工资了 不能
李四是计算机系的学生, 他住在312室或313室
P∧(Q∨R)∧((Q∧R)),其中:P代表"李四是计 算机系学生",Q代表"李四住312室",R代表 "李四住313室" 还可表示为:P∧((Q∧R)∨(Q∧R))
等式的证明
例1: P∧Q→R = P →(Q→R) 例2: P∧(Q∨R)∧((Q∧R))= P∧((Q∧R)∨(Q∧R)) 注意:等式A=B代表的含义是AB永真, 不是A永真或B永真
特异合取范式
定理:一公式的真值表中使其为F的指派 所对应的最大项组成的合取范式即为该 公式的特异合取范式 一个公式的特异合取范式,若命题变元 的个数及出现的顺序是确定的,则特异 合取范式是唯一的
特异合取范式
一些结论
一公式是重言式的充要条件是它的特异合取 范式为"空"(没有最大项) 一公式是矛盾的充要条件是它的特异合取范 式为包含所有的最大项 两公式相等的充要条件是他们的特异合取范 式一致
特异析取范式
特异析取范式的析取项称为最小项,n个 命题变元可以构成2n个最小项 任意公式均可化归成析取范式,又均可 以化归为若干个最小项组成的特异析取 范式 n个命题变元可以有2n个不同的指派,每 一个指派唯一对应一个最小项使其为T
特异析取范式
因此,还 可以利用 真值表构 造特异析 取范式
P T T T T F F F F Q T T F F T T F F R T F T F T F T F 最小项 P∧Q∧R P∧Q∧R P∧Q∧R P∧Q∧R P∧Q∧R P∧Q∧R P∧Q∧R P∧Q∧R
命题逻辑推理
能否证明:姚明没加上工资,那张三肯 定没认真听课
P:张三认真听课;Q:姚明上场打球 R:火箭赢开拓者;S:姚明加工资
证明:
前提条件为 P→Q, Q→R, R→S P→Q, Q→R╞ P→R P→R, R→S╞ P→S P→S, S╞ P
范式
能否将公式化归到一种标准的形式? 这种标准形式就叫做范式 析取范式与合取范式
特异合取范式
特异合取范式的合取项称为最大项,n个 命题变元可以构成2n个最大项 任意公式均可化归成合取范式,又均可 以化归为若干个最大项组成的特异合取 范式 n个命题变元可以有2n个不同的指派,每 一个指派唯一对应一个最大项使其为F
特异合取范式
因此,还 可以利用 真值表构 造特异合 取范式
P T T T T F F F F Q T T F F T T F F R T F T F T F T F 最大项 P∨Q∨R P∨Q∨R P∨Q∨R P∨Q∨R P∨Q∨R P∨Q∨R P∨Q∨R P∨Q∨R
特异合取范式
合取范式的每个合取项中,公式的所有 命题变元均出现,且以其自身或其否定 的形式出现一次且仅有一次,那么这种 范式就叫特异合取范式
(1)在合取范式中去除永真的合取项 (2)若某命题变元在一个合取项中出现多次, 化约成一次 (P∨P =P) (3)合取项中若某一命题变元未出现,则利用 P∨(Q∧Q)=P扩充之,并利用分配律展开成 多个合取项,并去除相同的合取项
定理:
"前提1,前提2,…,前提n╞ 结论"有效的充 要条件是命题公式"(前提1 ∧前提2 ∧… ∧前提n) →结论"是重言式
命题逻辑推理
若有PQ,则有P╞ Q 若有P1∧P2∧P3Q,则有 P1,P2,P3╞ Q
命题逻辑推理
一些推理规则 (183页(63)-(72)) P, P∨Q╞ Q 析取三段论
特异析取范式
定理:一公式的真值表中使其为T的指派 所对应的最小项组成的析取范式即为该 公式的特异析取范式 一个公式的特异析取范式,若命题变元 的个数及出现的顺序是确定的,则特异 析取范式是唯一的
特异析取范式
一些结论
n个命题变元可以组成也只能组成2的2n次方 个不同的公式 一公式是重言式的充要条件是它的特异析取 范式包含所有的最小项 一公式是矛盾的充要条件是它的特异析取范 式为"空"(没有最小项) 两公式相等的充要条件是他们的特异析取范 式一致
命题联结词
这4个联结词均可以用之前的5个联结词 表示
P⊕Q P↑Q P↓Q P→Q = = = = (PQ) (P∧Q) (P∨Q) (P→Q)
这9个联结词构成了联结词的全集,再没 有也不需要其他的联结词了
命题联结词
两个变元共有16种不同的联结结果取值
去除T,F,P,Q还有12种 ,→,→,各对应2种结果 P T T F F Q T F T F 命题联结词 U1 U2 U3 U4
蕴含重言式
基本蕴含重言式
P P→Q Q P→Q P∧(P∨Q) Q (P→Q)∧(Q→R) P→R
此外等价重言式可生成两个蕴含重言式
因为PQ = (P→Q)∧(Q→P) 所以若P Q (即P=Q),则有PQ且QP
命题逻辑推理
一般推理模式
一组前提,推出一个结论 前提1,前提2,…,前提n╞ 结论 1, 2,…, n 所有的前提是合取关系,与顺序无关 只有在"当所有前提都为真时,结论为真" 成立的情况下,这一推理才是有效的.
定理:一公式是矛盾的充要条件是其析 取范式的每一个析取项中均必同时包含 一个命题变元及其否定
合取范式
公式是一个合取式,每个合取项都是一 个析取式,每个析取式中的析取项只是 命题变元或命题变元的否定.
不包含蕴含和等价联结词,否定联结词只作 用在单个的命题变元前 如P∧(P∨Q)∧(P∨Q∨R)
合取范式
析取范式
公式是一个析取式,每个析取项都是一 个合取式,每个合取式中的合取项只是 命题变元或命题变元的否定.
不包含蕴含和等价联结词,否定联结词只作 用在单个的命题变元前 如P∨(P∧Q)∨(P∧Q∧R)
析取范式
任意公式均可化归成析取范式
将蕴含和等价联结词化归成∧∨ 将否定联结词深入至命题变元,并利用 P=P使命题变元前的双否定词消去 利用分配律将公式化归成析取范式 例子:求(P∨Q)P∧Q的析取范式
任意公式均可化归成合取范式
例子:求(P∨Q)P∧Q的合取范式
定理:一公式是重言式的充要条件是其 合取范式的每一个合取项中均必同时包 含一个命题变元及其否定
特异析取范式
析取范式从形式上并不唯一 但可以化约成一种唯一形式的范式
在每个析取项中,公式的所有命题变元均出现,且 以其自身或其否定的形式出现一次且仅有一次,那 么这种范式就叫特异析取范式 (1)去除永假的析取项 (2)析取项中若某命题变元出现多次,化约成一次 (3)析取项中若某一命题变元未出现,则利用 P∧(Q∨Q)=P扩充之,并利用分配律展开成多个 析取项,并去除相同的析取项
P,Q为两个命题,复合命题"P与非Q" 的 真值表为 P T T F F Q T F T F P↑Q F T T T
命题联结词
或非联结词(↓)
P,Q为两个命题,复合命题"P或非Q" 的 真值表为 P T T F F Q T F T F P↓Q F F F T
命题联结词
蕴含否定联结词(→)
P,Q为两个命题,复合命题"P→Q" 的真 值表为 P T T F F Q T F T F P→Q F T F F
命题联结词的归约
联结词
否定,合取,析取,蕴含,等价 , ∧, ∨, →, 异或,与非,或非,蕴含否定 ⊕, ↑, ↓, →
命题联结词
异或联结词(⊕)
P,Q为两个命题,复合命题"P异或Q" (即不相容的或)的真值表为 P T T F F Q T F T F P⊕Q F T T F
命题联结词
与非联结词(↑)
离散数学之数理逻辑(2)
上海交通大学软件学院 吴刚 2009年6月
内容
命题逻辑
等式的对偶定理 蕴含重言式与命题逻辑推理 范式 命题联结词的归约
回顾命题的公式化
如果我下班早, 就去商店看看, 除非我很累
P∧Q→R,其中P代表"我很累",Q代表"我下 班早",R代表"我去商店看看" 还可表示为:P →(Q→R)
等式的对偶定理
定义:设有公式A,其中仅使用了联结词 ∧∨,则将其中的联结词∧∨及命题常 量T,F分别换成∨∧和F,T后得到的公 式A*称为A的对偶公式 对偶定理:设有等式A=B,且A,B中均只 使用了联结词∧∨,则有A*=B*
即若有一个等式成立,其两边公式的对偶公 式的等式也成立
等式的对偶定理
例子:
P= P↑P P∨Q = (P↑P)↑(Q↑Q) P= P↓P 联结词的归约
P∨Q = (P↑P)↑(Q↑Q)
P T T F F Q T F T F P↑P Q↑Q P P Q Q F F T T F T F T P∨Q (P↑P)↑(Q↑Q) P Q (P P) (Q Q) T T T F T T T F
命题联结词的归约