命题公式

《命题公式》由会员分享，可在线阅读，更多相关《命题公式（42页珍藏版）》请在金锄头文库上搜索。

1、离散数学 中国地质大学 计算机学院第第1 1讲讲 命题公式命题公式主讲人 吴杰中国地质大学计算机学院 1离散数学 中国地质大学 计算机学院主要内容 1 1 命题的基本概念命题的基本概念2 2 命题联结词及真值表命题联结词及真值表3 3 命题公式与命题符号化命题公式与命题符号化4 4 命题公式的分类命题公式的分类5 5 命题公式的等值演算命题公式的等值演算6 6 范式范式2离散数学 中国地质大学 计算机学院命题能够分辨真假的陈述句叫做命题(Proposition)。 该定义有两层含义：(1)命题是陈述句。其他的语句，如疑问句、祈使 句、感叹句均不是命题；(2)这个陈述句表示的内容可以分辨真假，而

2、且不 是真就是假，不能不真也不假，也不能既真又假1.1 命题与联结词3离散数学 中国地质大学 计算机学院作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈 述句是假命题。通常用1（或字母T）表示真，用0（或字母F）表示假。1.1 命题与联结词4离散数学 中国地质大学 计算机学院 命题的分类原子命题（Automic Proposition）：是指不能再分解为更简单命题的命题；复合命题（Compound Proposition）：是指由若干命题用联结词组成的新命题。例如“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天

3、天晴我就去打球或者游泳”都是复合命题。 1.1 命题与联结词5离散数学 中国地质大学 计算机学院命题常元 真值确定的原子命题称为命题常元。命题变元 真值不确定的原子命题称为命题变元。如果命题题符号P代表命题题常元则则意味它是某个具体命题题的符号化，如果P代表命题变题变 元则则意味着它可指代任何具体命题题。本书书中如果没有特别别指明，通常来说说命题题符号P等是命题变题变 元，即可指代任何命题题。1.1 命题与联结词6离散数学 中国地质大学 计算机学院命题联结词及真值表否定词“”（或“”）否定词（Negation）是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。1.1 命题与联结词

4、P P0 11 07离散数学 中国地质大学 计算机学院合取词“”合取词（Conjunction）是二元联结词。相当于自然语言中的“与” 、“并且” 、“而且” 、“也”等，真值表如右图。1.1 命题与联结词P Q P Q0 0 00 1 01 0 01 1 18离散数学 中国地质大学 计算机学院析取词“”析取词（Disjunction）是二元联结词。相当于自然语言中的“或”、“要么要么”等，真值表如右图。1.1 命题与联结词P Q PQ0 0 00 1 11 0 11 1 19离散数学 中国地质大学 计算机学院蕴含词“”蕴含词（Implication）是二元联结词。相当于自然语言中的“若则”、

5、“如果就”、“只有才”，真值表如右图。1.1 命题与联结词P QP Q0 0 10 1 11 0 01 1 110离散数学 中国地质大学 计算机学院等价词“ ” 等价词（Equivalence） 是二元联结词。相当于自然语 言中的“等价”、“当且仅当”、 “充要条件”等，真值表如右图。我们给联结词规定优先级顺序：的优先级最 高，接着依次是，和。1.1 命题与联结词P Q PQ0 0 10 1 01 0 01 1 111离散数学 中国地质大学 计算机学院1.2 命题公式命题公式（Propositional Formula）归纳定义如下：（1）命题变元是命题公式；（2）如果是命题公式，则也是命题公

6、式；（3）如果和是命题公式，则，均是命题公式；（4）只有有限次地利用（1）（3）形成的符号串才是命题公式。12离散数学 中国地质大学 计算机学院1.2 命题公式例如，(PQ)，P(PQ)等都是命题题公式，而CPQ，RP等不是命题题公式。命题逻辑题逻辑 里讨论讨论 的对对象是命题题公式，而日常生活中的推理问题问题 是用自然语语言描述的，因此要进进行推理演算必须须先把自然语语言符号化（或形式化）成逻辑语逻辑语 言，即命题题公式。然后再根据逻逻辑辑演算规规律进进行推理演算。13离散数学 中国地质大学 计算机学院1.2 命题公式命题符号化指把一个用自然语言叙述的命题相应 地写成由命题变元、联结词和圆括

7、号表示 的命题公式。符号化应该注意下列事项： u确定给定句子是否为命题。 u句子中连词是否为命题联结词。 u要正确地表示原子命题和适当选择命题联 结词。14离散数学 中国地质大学 计算机学院1.2 命题公式命题公式的分类变元组：设n元公式中所含有的不同命题元为P1,P2,Pn，我们把这些命题变元组成 的变元组(P1,P2,Pn)称为的变元组。完全指派：的变元组(P1,P2,Pn)的任意一组确定的值都称为该公式关于该变元组(P1,P2,Pn)的完全指派。15离散数学 中国地质大学 计算机学院1.2 命题公式部分指派：如果仅对变元组中部分变元赋以确定的值，其余变元没有赋以确定的值，则这样的一 组值

8、称为该公式关于该变元组(P1,P2,Pn)的部分指派。例 设设=(P(QR)S，其变变元组为组为 (P,Q,R,S)。(P,Q,R,S)=(1,0,1,1)为为的完全指派，(P,Q,R,S)=(0,0,1,S)为为的部分指派。16离散数学 中国地质大学 计算机学院1.2 命题公式成真指派对对于任一公式，凡使得为为真的指派，不 管是完全指派还还是部分指派，都称为为的成真指 派。成假指派凡使得为为假的指派，也不管是完全指派还还 是部分指派，都称为为的成假指派。例 设设=(P(QR)(RS)，则则完全指派 (P,Q,R,S)=(0,1,0,1)和部分指派 (P,Q,R,S)=(0,1,0,S)都是的

9、成真指派，而指派 (P,Q,R,S)=(1,0,1,0)为为的成假指派。17离散数学 中国地质大学 计算机学院1.2 命题公式子公式（Sub Formula）：设为命题公式，为中的一个连续的符号串，且为命题公式，则称为的子公式。例如，设公式=(PQ)(P(QR)，则(PQ)，(QR)，(P(QR)等都是的子公式，而(PQ)，(P(Q，(QR)等都不是的子公式，因为它们本身不是公式。18离散数学 中国地质大学 计算机学院1.2 命题公式重言式/永真式（Tautology）：若公式的所有 完全指派均是成真指派，则公式称为重言式或 永真式。矛盾式/永假式（Absurdity）：若公式的所有 完全指派

10、均是成假指派，则公式称为矛盾式或 永假式。可满足式（Contingency）：若公式中有成真指 派，则公式称为可满足式。19离散数学 中国地质大学 计算机学院1.2 命题公式对定义的几点说明1）是可满足式的等价定义是：至少存在一个成真指派。2）重言式一定是可满足式，但反之不真。因而，若公式是可满足式，且它至少存在一个成假指派，则称为非重言式的可满足式。20离散数学 中国地质大学 计算机学院1.2 命题公式3）真值表可用来判断公式的类型：若真值表最后一列全为1，则公式为重言式；若真值表最后一列全为0，则公式为矛盾式；若真值表最后一列中至少有一个1，则公式为可满足式。21离散数学 中国地质大学 计

11、算机学院1.3 等值演算等值式设，是两个命题公式，若，构成的等价式为重言式，则称公式与是等值（Equivalent）的，记作。22离散数学 中国地质大学 计算机学院1.3 等值演算注意：注意：定义中给出的符号与是两个完全 不同的符号。不是命题联结词而是公式 间的关系符号，不表示一个公式，即 不代表命题，它表示公式与公式有等值 关系，而是命题联结词，是一个公 式，表示某个命题。然而这两者之间有密 切的联系，即的充要条件是公式 为重言式。23离散数学 中国地质大学 计算机学院1.3 等值演算下面给给出16组组重要的等值值式（在后面的推理演算中以大写字母E加以引用），这这些等值值式也称作命题定律，其

12、正确性可以用真值值表加以证证明。（1）双重否定律 ()（2）等幂律 ， 24离散数学 中国地质大学 计算机学院1.3 等值演算（3）交换律 ， （4）结合律 ()()，()()（5）分配律 ()()()（对的分配律）()()()（对的分配律）25离散数学 中国地质大学 计算机学院1.3 等值演算（6）德摩根律()，()（7）吸收律()， ()（8）零一律11， 0026离散数学 中国地质大学 计算机学院1.3 等值演算（9）同一律0， 1 （10）排中律1 （11）矛盾律0 （12）蕴含等值式27离散数学 中国地质大学 计算机学院1.3 等值演算（13）假言易位 （14）等价等值式()()，(

13、)() （15）等价否定等值式 （16）归谬论()()28离散数学 中国地质大学 计算机学院1.3 等值演算等值演算由已知的等值值式推演出另外一些等值值式的过过程称为为等值演算。代入定理 对对于重言式中的任一命题变题变 元出现现的每一处处均用同一命题题公式代入，得到的仍是重言式。29离散数学 中国地质大学 计算机学院1.3 等值演算置换定理 设A是公式的一个子公式且AB。如果将公式中的子公式A置换成公式B之后，得到的公式是，则。30离散数学 中国地质大学 计算机学院1.3 等值演算比较较代入定理和置换换定理的区别别: 代入定理 置换换定理 使用 对对象 任意重言式 任一命题题公式 代换换 对对

14、象 任一命题变题变 元 任一子公式 代换换 物 任一命题题公式 任一与代换对换对 象等值值的命题题 公式 代换换 方式 代换换同一命题变题变 元的所有出 现现 代换换子公式的某些出现现 代换换 结结果 仍为为重言式 与原公式等值值 31离散数学 中国地质大学 计算机学院1.3 等值演算限制性命题公式如果命题公式中只出现命题变元、命题常元 、命题联结词、和，则称为限制性命题公式。对偶式在限制性公式中，将联结词换成，将换 成，将0换成1，将1换成0，所得到的公式称为 的对偶式，记为*。32离散数学 中国地质大学 计算机学院1.4 范式原子命题“P”及其否定“P”统称文字。 文字或者一些文字的合取称为质合取式。 文字或者一些文字的析取称为质析取式(或 称子句)。 P与P称为互补对。例如，P，P，PQ，PQR等都是 质合取式，P，Q，PQ，PQR等都是 质析取式。33离散数学 中国地质大学 计算机学院1.4 范式定理（1）质合取式为矛盾式的充要条件：它包含有一个互补对；（2）质析取式为重言式的充要条件：它包含有一个互补对。34离散数学 中国地质大学 计算机学院1.4 范式析取范式与合取范式若干个质合取式的析取式称为析取范式。亦 即该