命题公式.pptVIP

2004年11月 计算机系软件教研室 中国地质大学计算机系软件教研室  第1讲 命题公式 主讲人 吴杰 中国地质大学计算机学院 主要内容 1 命题的基本概念 2 命题联结词及真值表 3 命题公式与命题符号化 4 命题公式的分类 5 命题公式的等值演算 6 范式 1.1 命题与联结词 命题 能够分辨真假的陈述句叫做命题(Proposition)。 该定义有两层含义： (1)命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题； (2)这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假 1.1 命题与联结词 作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用1（或字母T）表示真，用0（或字母F）表示假。 1.1 命题与联结词 命题的分类 原子命题（Automic Proposition）：是指不能再分解为更简单命题的命题； 复合命题（Compound Proposition）：是指由若干命题用联结词组成的新命题。 例如“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是复合命题。 1.1 命题与联结词 命题常元 真值确定的原子命题称为命题常元。 命题变元 真值不确定的原子命题称为命题变元。 如果命题符号P代表命题常元则意味它是某个具体命题的符号化，如果P代表命题变元则意味着它可指代任何具体命题。本书中如果没有特别指明，通常来说命题符号P等是命题变元，即可指代任何命题。 1.1 命题与联结词 命题联结词及真值表 否定词“?”（或“?”） 否定词（Negation） 是一元联结词。相当于自 然语言中的“非”、“不”等， 真值表如右图。 1.1 命题与联结词 合取词“∧” 合取词（Conjunction） 是二元联结词。相当于自然 语言中的“与” 、“并且” 、 “而且” 、“也”等，真值表 如右图。 1.1 命题与联结词 析取词“∨” 析取词（Disjunction） 是二元联结词。相当于自然 语言中的“或”、“要么… 要么…”等，真值表如右图。 1.1 命题与联结词 蕴含词“?” 蕴含词（Implication） 是二元联结词。相当于自然 语言中的“若…则…”、“如果 …就…”、“只有…才…”， 真值表如右图。 1.1 命题与联结词 等价词“? ” 等价词（Equivalence） 是二元联结词。相当于自然语 言中的“等价”、“当且仅当”、 “充要条件”等，真值表如右图。 我们给联结词规定优先级顺序：?的优先级最高，接着依次是?，?，→和?。 1.2 命题公式 命题公式（Propositional Formula）归纳定义如下： （1）命题变元是命题公式； （2）如果α是命题公式，则?α也是命题公式； （3）如果α和β是命题公式，则α?β，α?β，α→β，α?β均是命题公式； （4）只有有限次地利用（1）—（3）形成的符号串才是命题公式。 1.2 命题公式 例如，?(P?Q)，P→(P?Q)等都是命题公式，而CP→Q，?R→P等不是命题公式。 命题逻辑里讨论的对象是命题公式，而日常生活中的推理问题是用自然语言描述的，因此要进行推理演算必须先把自然语言符号化（或形式化）成逻辑语言，即命题公式。然后再根据逻辑演算规律进行推理演算。 1.2 命题公式 命题符号化 指把一个用自然语言叙述的命题相应地写成由命题变元、联结词和圆括号表示的命题公式。符号化应该注意下列事项： 确定给定句子是否为命题。 句子中连词是否为命题联结词。 要正确地表示原子命题和适当选择命题联 结词。 1.2 命题公式 命题公式的分类 变元组：设n元公式α中所含有的不同命题元为P1,P2,…,Pn，我们把这些命题变元组成的变元组(P1,P2,…,Pn)称为α的变元组。 完全指派：α的变元组(P1,P2,…,Pn)的任意一组确定的值都称为该公式α关于该变元组(P1,P2,…,Pn)的完全指派。 1.2 命题公式 部分指派：如果仅对变元组中部分变元赋以确定的值，其余变元没有赋以确定的值，则这样的一组值称为该公式α关于该变元组(P1,P2,…,Pn)的部分指派。 例 设α=(P?(Q→R))?S，其变元组为(P,Q,R,S)。(P,Q,R,S)=(1,0,1,1)为α的完全指派，(P,Q,R,S)=(0,0,1,S)为α的部分指派。 1.2 命题公式 成真指派 对于任