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

3-第一章命题逻辑


1.1 命题及其表示法 1.2 联结词 1.3 命题公式与翻译 1.4 真值表与等价公式 1.5 重言式与蕴含式 1.7对偶与范式 1.8推理理论

第一章

命题逻辑
Propositional Logic

1.1 命题及其表示法 1.2 联结词 1.3 命题公式与翻译 1.4 真值表与等价公式 1.5 重言式与蕴含式 1.7对偶与范式 1.8推理理论

第一章

命题逻辑
Propositional Logic

1.3 命题公式与翻译
定义1-3.1命题合式公式 (Well-formed formula, wff )
(1)单个命题变元本身是合式公式。 (2)若A是合式公式,则(┐A)也是合式公式。 (3)若A,B是合式公式,则(A∧B),(A∨B), (A?B),(A?B)也是合式公式。

(4)当且仅当有限次地应用(1)~(3)所得到的包含命题
变元、联结词和括号的符号串是合式公式。

大连大学

信息工程学院

第10页

1.3 命题公式与翻译
例:判断下列式子是否是合适公式
?( P ? Q ), ? ( P ? Q ), ( P ? ( P ? ?Q )) ((( P ? Q ) ? (Q ? R )) ? ( S ? T )) ( P ? Q ) ? ( ?Q ) (P ? Q ( P ? Q) ? Q)

大连大学

信息工程学院

第10页

1.4 真值表与等价公式
例1 给出 ?( P ? Q) ? (?P ? ?R) 的真值表。

练习:给出下列命题公式的真值表。
(1) ?( P ? Q) ? (?P ? ?Q) (2) ?( P ? Q) ? ?P n个命题变元组成的命题公式共有2n种赋值(指派)。 定义1-4.2 设A,B为两个命题公式,若A,B构成的 双条件A?B为重言式,则称A与B是 等价的(等值的)记作A ?B。
大连大学 信息工程学院

第12页

1.4 真值表与等价公式

大连大学

信息工程学院

第12页

1.4 真值表与等价公式
定义1-4.3 如果X是合式公式A的一部分,且X本身

也是一个合式公式,则称X为公式A的
子公式。

定理1-4.1 设X是合式公式A的子公式,若X ? Y,
如果将A中的X用Y来置换,所得到公式 B与公式A等价,即A ? B。

大连大学

信息工程学院

第13页

复习
练习1:化简下面的式子。
(1) ?( P ? Q) ? (?P ? ?Q) (2) ?( P ? Q) ? ?P

大连大学

信息工程学院

第16页

1.1 命题及其表示法 1.2 联结词 1.3 命题公式与翻译 1.4 真值表与等价公式 1.5 重言式与蕴含式 1.7对偶与范式 1.8推理理论

第一章

命题逻辑
Propositional Logic

1.7 对偶与范式
一、对偶式 定义1-7.1 在给定的命题公式中,如果它仅用联结 词 ? , ?, ? ,则将联结词 ? 换成 ? ,将 ? 换成 ? , 若有特殊变元F和T亦相互取代,所得公式称为原 公式的对偶式。 例1:写出下列表达式的对偶式
( P ? Q) ? T ?( P ? Q) ? ( P ? ?(Q ? ?S )) P?Q
大连大学 信息工程学院

对偶式的作用 见书上30页 定理7.1-7.2
第16页

1.7 对偶与范式
二、范式 定义1-7.2 一个命题公式称为合取范式,当且仅当 它具有型式:

A1 ? A2 ?? ? An (n ? 1) 其中 A1 , A2 ,?, An 都是由命题变元或其否定所组成
的析取式。

合取范式的特点: (1)不出现 ? 和 ? (2)否定符号出现在变元前 (3)总体看是合取式 (4)每个合取项是析取式 (5)每个合取项中只包含命题变元或其否定。
大连大学 信息工程学院

第17页

1.7 对偶与范式
二、范式 定义1-7.3 一个命题公式称为析取范式,当且仅当 它具有型式:

A1 ? A2 ? ?? An (n ? 1) 其中 A1 , A2 ,?, An 都是由命题变元或其否定所组成
的合取式。

析取范式的特点: (1)不出现 ? 和 ? (2)否定符号出现在变元前 (3)总体看是析取式 (4)每个析取项是合取式 (5)每个析取项中只包含命题变元或其否定。
大连大学 信息工程学院

第18页

1.7 对偶与范式
二、范式

例2:判断下列各式是否为析取范式或合取范式。

( P ? Q ) ? ( P ? ?Q ? R ) ( P ? Q ) ? ( P ? (?Q ? R )) ( P ? Q ) ? ( P ? ?(Q ? R )) P ? ?( P ? Q) P ?P ? Q P ? (Q ? ?R ) ? R
大连大学 信息工程学院

第19页

1.7 对偶与范式
二、范式 合取范式和析取范式的化归步骤:见书上31页 例3:求 ( P ? (Q ? R)) ? S 合取范式。 例4:求 ?( P ? Q) ? ( P ? Q)) 析取范式。

大连大学

信息工程学院

第20页

1.7 对偶与范式
三、主范式

(1)主析取范式
?每个析取项中所有变元都要出现 ?每个变元只出现一次(命题变元或其否定) 主析取范式的化归步骤:见书上36页 例5:试求 P ? Q 和 ?( P ? Q) 的主析取范式。

例6:试求 P ? (( P ? Q) ? ?(?Q ? ?P)) 主析取范式。
大连大学 信息工程学院

第20页

1.7 对偶与范式
三、主范式 定义1-7.4 n个变元的合取式,称作布尔合取或小项, 其中每个变元与它的否定不能同时存在,但 两者必须出现且仅出现一次。 定义1-7.5 对于给定的命题公式,如果有一个等价 公式,它仅由小项的析取所组成,则该等价式称为 原式的主析取范式。 定理1-7.3 在真值表中,一个公式的真值为T的指派 所对应的小项的析取,即为此公式的主析取范式。
大连大学 信息工程学院

第20页

1.7 对偶与范式
三、主范式

(2)主合取范式
?每个合取项中所有变元都要出现 ?每个变元只出现一次(命题变元或其否定) 主合取范式的化归步骤:见书上38页

例7:试求 ( P ? Q) ? (?P ? R) 的主合取范式。 例8:试求 P ? (( P ? Q) ? ?(?Q ? ?P)) 主合取范式。
大连大学 信息工程学院

第20页

1.7 对偶与范式
三、主范式 定义1-7.6 n个变元的析取式,称作布尔析取或大项, 其中每个变元与它的否定不能同时存在,但 两者必须出现且仅出现一次。 定义1-7.7 对于给定的命题公式,如果有一个等价 公式,它仅由大项的合取所组成,则该等价式称为 原式的主合取范式。 定理1-7.3 在真值表中,一个公式的真值为T的指派 所对应的大项的合取,即为此公式的主合取范式。
大连大学 信息工程学院

第20页

1.7 对偶与范式
例9:用真值表求 ( P ? Q) ? (?P ? R) 的主合取范式。 例10:求 P ? Q) ? (?P ? R) 的成真指派。 ( 例11:某科研所要从3名科研骨干A,B,C中挑选1~2 名出国进修,由于工作需要,选派需满足如 下条件: 问:有几种 (1)若A去,则C同去; 选派方案 (2)若B去,则C不能去; 分别都是什 (3)若C不去,则A或B可以去。 么?
大连大学 信息工程学院

第21页


相关文章:
第一章 命题逻辑
第一章 命题逻辑 若命题标识符 P 表示一个确定的命题, 则称 P 为命题常量,...定义 1.8.3 (析取范式) 一个命题公式 A 称为析取范式, 当且仅当 A 可...
第一章命题逻辑知识地图
第一章命题逻辑知识地图_其它课程_高中教育_教育专区。《离散数学》知识地图 第...A 也是一个命题公式; (3)若 A、B 是命题公式,则 A∧B、A∨B、A?B 和...
第一章 命题逻辑
第一章 命题逻辑逻辑学是研究推理过程规律一门科学。数理逻辑则是用数学的方法研究...从本章开始,我们用三章的篇幅介绍数理逻辑的基本内容:命题逻辑、谓词逻辑 和非...
第一章 命题逻辑
3页 免费 第一章命题逻辑(包含的... 155页 免费 离散数学实验 6页 1下载...数理逻辑和计算机科学有许多重合之处,例如:计算机科学中的程序语言学、语义学、 ...
第一章 命题逻辑
第一章 命题逻辑 习题与解答⒈ 判断下列语句是否为命题,并讨论命题的真值。 ⑴ 2x ? 3 ? 0 。⑵ 前进! ⑶⑷⑸⑹⑺解⒉⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾ 如果 ...
第一章命题逻辑,第一讲命题,逻辑联结词及真值表
第一章 命题逻辑第一讲 命题、 命题、联结词及真值表命题的定义: 命题的定义...如果是真,称该命题为真命题 真命题 比如 : 太阳从东方升起 1+2=3 如果是...
选修1-1第一章:命题与逻辑结构词知识点题型归纳
选修1-1第一章:命题逻辑结构词知识点题型归纳_数学_高中教育_教育专区。高二...充分必要条件的判定 3、含有一个量词的否定 4、由含有逻辑连词的命题的真假和...
第一章命题逻辑
第三章_有穷自动机 74页 2财富值 第1章 命题逻辑 11页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
高二数学下期选修2-1第一章命题和简易逻辑测试题
高二数学下期选修 2-1 第一章命题和简易逻辑测试题答案 一选择题:A C B B D A D C C C 二填空题:11: 15 ③ 解答题 16:解: ,即 不等式 , 是...
高中数学选修1-1命题知识点、考点、典型例题
高二数学选修 1-1 知识点第一章:命题逻辑结构 知识点: 1、命题:用语言、...3、对于两个命题,如果一个命题的条件和结论分别是另一个命题的结论和条件,则...
更多相关标签: