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

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页


赞助商链接
相关文章:
《离散数学》第一章至第七章_习题详解_图文
《离散数学》第一章至第七章_习题详解 - 第一章 命题逻辑基本概念 课后练习题答案 1、是命题的为(1)、(2)、(3)、(6)、(7)、(10)、(11)、(12)、(...
...第一章第2课时 命题及逻辑联结词
2011届高三数学一轮复习教案:第一章第2课时 命题逻辑联结词 隐藏>> taoti....3 > 6 . 其中,不是命题的有___①②④___. 2.一般地若用 p 和 q 分别...
选修2-1第一章《常用逻辑用语》单元测试题1
选修2-1第一章《常用逻辑用语》单元测试题1_数学_高中教育_教育专区。选修 2...14.把下面不完整的命题补充完整,并使之成为真命题:若函数 f(x)=3+log2x ...
第一章 常用逻辑用语 第二讲简单逻辑联结词
第一章 第二讲 常用逻辑用语 简单逻辑联结词、全称量词与存在量词 [知识梳理]...2.“ p 且 q ”记作 ;“ p 或 q ”记作 ;“非 p ”记作 3.命题 ...
高中数学必修三与选修1-1第一章常用逻辑用语
任丘一中北校区 2015—2016 学年第一学期高二年级阶段考一 高二年级数学(理)试题考试范围:必修三与 2-1 第一章常用逻辑用语 命题人:于丹 时间 90 分钟 总分:...
第一章常用逻辑用语单元测试题
第一章常用逻辑用语单元测试题_数学_高中教育_教育专区。第一章 常用逻辑用语周...1 ? 0 2 3.在命题“若抛物线 y ? ax2 ? bx ? c 的开口向下,则 x ...
人教版高中数学选修2-1第一章《常用逻辑用语》全部教案
人教版高中数学选修2-1第一章《常用逻辑用语》全部教案 - 高中数学(选修 2-1) 教 案 孔德友 庐江县第三中学 1.1 命题及其关系 第一课时 1.1.1 命题 ...
四种命题间的相互关系教案
四种命题间的相互关系教案 - 公开课教案,提供出来供大家分享... 1.1.3 四种命题的相互关系教材分析:本节课高中数学人教版选修 1-1 第一章常用逻辑用于第一大节...
人教课标版(B版)高中数学选修1-1第一章 常用逻辑用语命...
人教课标版(B版)高中数学选修1-1第一章 常用逻辑用语命题与量词教案 - 一.考场传真 1.已知集合 A ? {?2,0,2} , B ? {x | x 2 ? x ? 2 ? 0...
...数学-选修1-1-第一章 常用逻辑用语___1.1 命题及其...
人教A版-数学-选修1-1-第一章 常用逻辑用语___1.1 命题及其关系_1.1_...命题 C.互为逆否命题 3.以下说法错误的是 A.如果一个命题的逆命题为真命题...
更多相关标签: