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

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页


赞助商链接
相关文章:
...第一章 集合与常用逻辑用语 第2课 命题与简易逻辑(...
第 2 课 命题与简易逻辑 1.命题 (1)命题的定义:可以判断真假的陈述句叫做命题. (2)四种命题的形式: 命题命题命题命题 逆否命题 表述形式 (3)...
选修1-1第一章常用逻辑用语复习课_图文
选修1-1第一章常用逻辑用语复习课_高二数学_数学_高中教育_教育专区。第一章...3. 第一章常用逻辑用语复习课教学目标 1. 理解命题的概念;了解逻辑联结词“或...
第一章常用逻辑用语
第一章常用逻辑用语 - 第一章常用逻辑用语 一、选择题 1 ).① 是非整数;②5 是 10 的约数或是 26 的约数;③逻 5 辑联结词有“或”“非”“且”;④...
章末检测3:第一章 常用逻辑用语
章末检测3:第一章 常用逻辑用语 - 章末检测卷(一) (时间:120 分钟 满分:150 分) 一、选择题(本大题共 10 小题,每小题 5 分,共 50 分) 1.若命题...
数学选修2-1第一章常用逻辑用语典型例题含解析
数学选修2-1第一章常用逻辑用语典型例题含解析_高二数学_数学_高中教育_教育...原命题为真,故其逆否命题为真. 否命题:若 x≤0 或 x≥5,则|x-2|≥3...
...第一章 §1.3简单的逻辑联结词检测试题 新人教A版选...
【步步高】2014-2015学年高中数学 第一章 §1.3简单的逻辑联结词检测试题 新...含有逻辑联结词的命题的真假判断 p 真真假假 q 真假真假 p∨q真 真真假 p...
高中数学必修三与选修1-1第一章常用逻辑用语
任丘一中北校区 2015—2016 学年第一学期高二年级阶段考一 高二年级数学(理)试题考试范围:必修三与 2-1 第一章常用逻辑用语 命题人:于丹 时间 90 分钟 总分:...
第一章:命题逻辑
3页 免费 第一章命题逻辑(包含的... 155页 免费 离散数学教案 39页 免费...1.1 命题符号化及联结词 [教学重点] 命题的概念和六个联结词的定义 [教学目的...
离散数学第一章命题逻辑知识点总结
数理逻辑部分 第1章 命题逻辑 1.1 命题符号化及联结词 命题: 判断结果惟一的...(5) 中“与”联结的是两个名词,整个句子是一个简单命题. 3.析取式与析取...
第一章 命题逻辑
第一章 命题逻辑 若命题标识符 P 表示一个确定的命题, 则称 P 为命题常量,...定义 1.8.3 (析取范式) 一个命题公式 A 称为析取范式, 当且仅当 A 可...
更多相关标签: