当前位置:首页 >> 数学 >>

1-3 命题逻辑


请交作业一

复习思考题2
1. 重要等值式填空: ① A?B ? _______ ② A?B ? _____________________ ③ ?(A?B) ? _______ ④ ?(A?B) ? _______ 2. 共有________个三元真值函数。 3. A ? 0 ?______, A ? 1 ?________。
4. 写一个属于矛盾式的简单合取式_________。 5. 写一个属于重言式的简单析取式_________。

第1章 命题逻辑
1.1 命题符号化及联结词
1.2 命题公式及分类 1.3 等值演算 1.4 范式 1.5 联结词全功能集 1.7 推理理论

求下列公式的析取范式与合取范式
((p?q)?r)?p
解:原式? (? (p?q) ?r ) ?p (消去左边第一个?) ? ?(? (p?q) ?r ) ?p (消去左边第二个?) ? ((p?q) ? ?r ) ?p (德摩根律) ? (p?q ?p) ? (?r ?p) (分配律) ? (p?q) ? (p??r) 最后两式已为合取范式(两个简单析取式构成) 继续: (p?q) ? (p??r) ? p?(q ? ?r) (分配律) 这一步得到析取范式(由两个简单合取式构成)

极小项
? 定义
? n个命题变项的简单合取式,其中每个命题变项与其 否定不同时出现,而二者之一必出现且仅出现一次, 这样的简单合取式称为极小项。 如:两个命题变元p和q,其极小项为:

?

p ? q,p ? ?q, ?p ? q, ?p ? ?q ? 说明
?
? m11 m3 m10 m2 m01 m1 m00 m0

n个命题变项产生2n个极小项,它们互不等值
用 mi 表示第 i 个极小项,每个小项的 n个变元排序相同。 (按下标或字典顺序),分别记为 m 0 , m 1 ,? ? ? m 2 n ? 1

?

其中i是该极小项成真赋值的十进制表示.

极小项
? 由p, q, r三个命题变项形成的极小项
极小项 ?p ? ?q ? ?r ?p ? ?q ? r ?p ? q ? ?r 成真赋值 000 001 010 名称 m0 m1 m2

?p ? q ? r
p ? ?q ? ?r p ? ?q ? r p ? q ? ?r p?q?r

011
100 101 110 111

m3
m4 m5 m6 m7

主析取范式
? 主析取范式
? 若命题公式A的析取范式中的简单合取式全是 极小项,则称该析取范式为A的主析取范式 ? 如:若命题变项为p, q, r 时,主析取范式:

(?p??q?r) ? (?p?q?r) ? m1?m3 ? 定理
? 任何命题公式都存在着与之等值的主析取范式, 并且是 惟一的.

? 求主析取范式的方法
? 等值演算法和真值表法

用等值演算法求主析取范式的步骤
1. 求A的析取范式A?; 2. 若A?的某简单合取式B中不含某命题变项或其否 定,则将B展成如下形式: B? B?1 ? B ? (pi ? ?pi ) ? (B ? pi) ?(B ? ?pi) 3. 将重复出现的命题变项、矛盾式及重复出现的极 小项都“消去”。 4. 将极小项按由小到大的顺序排列,并用Σ表示之, 如 m1 ? m2 ? m6 用 ?(1,2,6) 表示。

求公式 ((p?q)?r)?p 的主析取范式
解法1: ((p?q)?r)?p ? p ? (q ? ? r) (析取范式) ① p ? p ?(?q?q) ? (?r ?r) ?(p??q??r)?(p??q?r)?(p?q??r)?(p?q?r) ? m4?m5?m6?m7 ② (q??r) ? (q??r) ? (?p?p) ? (?p?q??r) ? (p?q??r) ? m2?m6 ③ ②, ③代入①并排序,得主析取范式: ((p?q)?r)?p? m2?m4?m5? m6?m7 ? ?(2, 4, 5, 6, 7)

求公式 ((p?q)?r)?p 的主析取范式
解法2: ((p?q)?r)?p (析取范式)

? p ? (q ? ? r ) ? m1xx ? mx10

? ( m100 ? m101 ? m110 ? m111)

?(m010 ? m110)
? ?(2, 4, 5, 6, 7)

求公式 ((p?q)?r)?p的主析取范式
p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p?q 0 0 1 1 1 1 1 1 (p?q)?r ((p?q)?r)?p 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1

((p?q)?r)?p? ?(2, 4, 5, 6, 7)

主析取范式的用途1
(1) 求公式的成真赋值和成假赋值 ? 如前面例子中得到 ((p?q)?r)?p? ?(2, 4, 5, 6, 7)
? 其成真赋值为: 010, 100, 101, 110, 111 ? 则其余的赋值为成假赋值

000, 001, 011

主析取范式的用途2
(2) 判断公式的类型
设A含n个命题变项,则 ? A为重言式?A的主析取范式含2n个极小项
? ? ? 如命题变项为p, q 时, A ? ?(0,1,2,3) 如 A ?0

? A为矛盾式? A的主析取范式不含任何极小项 ? A为可满足式?A的主析取范式中 至少含一个极小项
? 如A ? ?(0,1,3)

用主析取范式判断公式的类型
[P20例1.17]
(1)?(p?q) ?q

? ?(? p ? q) ? q
?p??q?q ?0

(矛盾式)

用主析取范式判断公式的类型
[P20例1.17] (3) (p?q) ?q ? (? p ? q )? q ?q ? mx1 ? m01 ? m11
吸收律: A?(A?B)?A

? ?(2,3)

(可满足式)

用主析取范式判断公式的类型
(2) ((p?q) ? p)? q ? ? ((? p ? q )? p) ? q ? (p ? ? q ) ? ? p ? q ? m10 ? m0x ? mx1 ? m10 ? m00 ? m01 ? m01 ? m11 ? m0 ? m1 ? m2? m3 ??(0,1,2,3) (重言式)

主析取范式的用途3
(3) 判断两个公式是否等值
如 p?q ? ? p? q ? m0x ? mx1 ? m00 ? m01 ? m01 ? m11 ? m0 ? m1 ? m3 ? ?(0,1,3)

? p ? (p ? q) ? m0x ? m11 ? m00 ? m01 ? m11 ? m0 ? m1 ? m3 ? ?(0,1,3) 所以 p ? q ? ? p ? (p ? q)

主析取范式的应用举例
例:甲、乙、丙、丁四人参 加考试,有人问他们, 谁的成绩最好, 甲说:“不是我” 乙说:“是丁” 丙说:“是乙: 丁说:”不是我” 四人的回答只有一人符合 实际,问是谁的成绩最 好?若只有一人成绩最 好,他是谁?
解此类问题的步骤为: ① 将简单命题符号化 ② 写出各复合命题

③ 写出由②中复合命题组
成的合取式 ④ 求③中所得公式的主析 取范式

主析取范式的应用举例
例:甲、乙、丙、丁四人参 解 ① 加考试,有人问他们,谁 设A:甲的成绩最好 的成绩最好, B:乙的成绩最好, 甲说:“不是我” C:丙的成绩最好 乙说:“是丁” D:丁的成绩最好, 丙说:“是乙” ② (1) (?A ?? D ?? B ? D) 丁说:“不是我” (2) ( A ? D ?? B ? D) 四人的回答只有一人符合 (3) ( A ?? D ? B ? D) 实际,问是谁的成绩最好? (4) ( A ?? D ?? B ?? D) 若只有一人成绩最好,他 是谁?

主析取范式的应用举例
② (1) (?A ?? D ?? B ? D) (2) ( A ? D ?? B ? D) (3) ( A ?? D ? B ? D) (4) ( A ?? D ?? B ?? D) ③ (1) ~ (4)构成的析取式为 (?A ??D ??B ? D) ?(A ?D ?? B ? D) ?( A ??D ? B ? D) ?(A ??D ?? B ??D)

主析取范式的应用举例
④ 求③中所得公式的主析取范式

(?A ??D ??B ? D) ?(A ?D ?? B ? D) ?( A ??D ? B ? D) ?(A ??D ?? B ??D) ?(A ?D ?? B ?D) ?(A ?? D ?? B ??D) ? (A ?? B ? D) ?(A ?? B ?? D) 所以,只有一人成 绩最好的是甲。 ? m10x1 ?m10x0 ?m1001 ? m1011 ? m1000 ? m1010
甲、丁并列 成绩最好
甲、丙、丁并列 成绩最好 甲、丙并列 成绩最好

极大项
? 定义
? n个命题变项的简单析取式,其中每个命题变项与其 否定不同时出现,而二者之一必出现且仅出现一次, 这样的简单析取式称为极大项。 如:两个命题变元p和q,其极大项为:

?

p ? q, p ? ?q , ?p ? q , ?p ? ?q
M00 M01 M10 M11

? 说明
? ? n个命题变项产生2n个极大项,它们互不等值 用 Mi 表示第 i 个极大项,每个小项的 n 个变元排序相同。 (按下标或字典顺序),分别记为 M 0 , M 1 , ? ? ? M n
2 ?1

? 其中i是该极大项成假赋值的十进制表示. (正变项:0,变元的否定:1)

由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
成真 赋值

极大项 名称 m0 m1 m2 m3 m4 m5 m6 m7 公式 p?q?r p ? q ??r p ? ?q ? r p ? ?q ??r ?p ? q ? r ?p ? q ??r ?p ? ?q ? r ?p ? ?q ??r
成假 赋值

名称 M0 M1 M2 M3 M4 M5 M6 M7

000 001 010 011 100 101 110 111

000 001 010 011 100 101 110 111

主合取范式
? 主合取范式
? 由极大项构成的合取范式
? 如,n=3, 命题变项为p, q, r 时,主合取范式:

(p?q??r)?(?p?q??r) ? M1?M5
? 定理
? ? 任何命题公式都存在着与之等值的主合取范式 , 并且 是惟一的. 求主合取范式的方法

? 等值演算法和真值表法

用等值演算法求主合取范式的步骤
1. 求A的合取范式A ?; 2. 若A ?的某简单析取式B中不含某命题变项或 其否定,则将B展成如下形式: B ?B?0 ? B ? (pi ? ? pi ) ? (B ? pi) ? (B ? ? pi) 3. 将重复出现的命题变项、重言式及重复出现 的极大项都“消去”。 4. 将极大项按由小到大的顺序排列,并用 ? 表 示之,如 M1 ? M2 ? M6 用 ?(1,2,6) 表示。

求公式((p?q)?r)?p 的主合取范式
解 1: ((p?q)?r)?p ? (p?q) ? (p??r) (合取范式) ①

p?q ? (p?q) ?(r ? ?r )
?(p?q?r )?( p?q ??r) ? M000 ? M001 p??r ? (p??r) ? (q ? ?q ) ? (p?q ??r) ?(p? ?q ??r) ②

? M001 ? M011
②, ③代入①并排序,得主合取范式:



原式?M0 ? M1 ? M3? ?(0,1,3)

求公式((p?q)?r)?p的主合取范式
解2: ((p?q)?r)?p
? (p?q) ? (p??r) ? M00x ? M0x1 ? M000 ? M001 ? M001 ? M011 ? M0 ? M1 ? M3 ? ?(0,1,3) (合取范式)
极小项 mi 与极大 项Mi的关系—— ?mi ? Mi ?Mi ? mi

((p?q)?r)?p ? p ? (q ? ? r) (析取范式) ? m1xx ? mx10 ? ( m100 ? m101 ? m110 ? m111)?(m010 ? m110) ? ?(2, 4, 5, 6, 7)

由主析取范式求主合取范式举例
? 已知命题公式A含3个命题变项,其成真 赋值为000、010、100、110,求主析取 范式和主合取范式. ? 解:主析取范式为: ?(0, 2, 4, 6) 因为成假赋值为:001、011、101、111 所以,主合取范式为 ?(1, 3, 5, 7)

作业3
P33: 12 P34: 15


相关文章:
数学选修2-1 命题与逻辑结构
数学选修2-1 命题逻辑结构_高三数学_数学_高中教育_教育专区。数学选修2-1 ...2 4.命题“ ax ? 2ax ? 3 ? 0 不成立”是真命题,则实数 a 的取值...
高中数学(人教A版 选修2-1)活页规范训练:1-3-1,1-3-2,1...
(人教A版 选修2-1)活页规范训练:1-3-1,1-3-2,1-3-3 简单的逻辑联结...答案 A 4.命题 p:方向相同的两个向量共线,q:方向相反的两个向量共线,则...
命题逻辑1.1-1.4
31页 1财富值 第一章 命题逻辑(1.7) 42页 1财富值 1-3逻辑联结词与四种命题 暂无评价 39页 1财富值 第一章 命题逻辑(1.1-1.2) 35页 免费如...
1.3简单的逻辑联结词 教学设计 教案
(1)12 能被 3 整除; (2)12 能被 4 整除; (3)12 能被 3 整除且能被 4 整除; 二、知识建构 归纳总结: 一般地,用逻辑联结词“且”把命题 p 和命题...
高二数学选修2-1逻辑命题经典练习题
高二数学选修2-1逻辑命题经典练习题_数学_高中教育_教育专区。圆梦教育高二数学...“a≠1 或 b≠2”是“a+b≠3”的( ) A、充分不必要条件 B、必要不...
集合、命题及逻辑联结词1
集合、命题逻辑联结词1_高三数学_数学_高中教育_教育专区。轮复习,专题练习...{x|x≥a},且 A∪B=R,则实数 a 的取值范围是___. 三、解答题(共 41...
选修1-1第一章:命题与逻辑结构词知识点题型归纳
,?p ? x ? . 全称命题的否定是特称命题. 主要考点题型: 1命题真假的判断 2、充分必要条件的判定 3、含有个量词的否定 4、由含有逻辑连词的命题的真假...
离散数学 同步测试1、命题逻辑
64页 免费 第章(命题逻辑)课件 41页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
第1章 命题逻辑参考答案1
1命题逻辑参考答案1 离散数学答案!离散数学答案!隐藏>> 第1命题逻辑参考答案 2.(1)不是命题(2)不是命题(3)不是命题 (4)是命题.令 P:所有的人...
1.3简单的逻辑联结词教案
1.3简单的逻辑联结词教案_数学_高中教育_教育专区。1.3 简单的逻辑联结词 1...学生很容易看到,在第(1)组命题中,命题③是由命题①②使用联结词“且” 联结...
更多相关标签: