第三章命题演算王元元.ppt

1、1,第三章,命题演算,2,重点:范式 掌握命题的概念；掌握五个基本的命题联结词的概念； 掌握命题公式的概念；了解什么是成真赋值，什么是成假赋值；掌握重言式和矛盾式的概念，并能用真值表法和命题演算法判断一个命题公式是重言式还是矛盾式；熟练掌握命题演算的基本定律；熟练掌握利用命题演算等值演算的方法证明两个命题公式等价；等值演算法和真值表法；掌握蕴涵式的概念；熟练掌握基本的蕴涵公式； 掌握命题演算证明的三种方法。掌握析取范式、合取范式、主析取范式、主合取范式的概念；熟练掌握利用求任意命题公式的主析取范式和主合取范式的方法：,3,3.1 命题与逻辑联结词,一、命题： 对确定的对象作出判断的陈述句 。

2、该定义有3层含义： (1)确定的对象； (2)命题是一个陈述句； (3)能根据客观事实判断命题的真假。,4,一、命题,例： 1.雪是黑的。 2.好大的雪啊！ 3.陈胜、吴广起义的那天杭州下雨。 4.2008年10月1日舟山天晴。 5. x+y0 6.我正在说谎。,5,类似（6）的悖论,我说的这句话是假的。 我只给哪些不给自己刮胡子的人刮胡子。,6,7.雪不是白的。 8.今晚我去商店或者去打球。 9.若数a是4的倍数，则它一定是2的倍数。 逻辑联结词或命题联结词,一、命题,7,二、原子命题和复合命题,原子命题或原子(atoms) 不含有逻辑联结词的命题。 复合命题(compositive pro

3、positions) 由原子命题和逻辑联结词共同组成的命题。,8,三、命题的表示,为了能用数学方法来研究命题之间的逻辑关系和推理，需要将命题符号化。 原子命题通常记为p，q，r，s等小写拉丁字母。f表示恒假命题，t表示恒真命题。,9,三、命题的表示,1 用单个字母表示某一具体命题，这时该符号称为“命题常元”。 2 用单个字母表示任一命题，这时该符号称为“命题变元”。它们是以“真、假”为取值范围的变元。,10,四、逻辑联结词,下面介绍五个常用的逻辑联结词： 、 1)否定词(negation) 用符号 表示 设p表示一命题，那么p表示命题p的否定。 p读作“并非p”或“非p”。 规定：p真时p假，

4、而p假时p真。,11,否定词(negation) 真值表,p,p,0,1,1,0,12,注：用否定词“并非”代替自然语言中的“不”时，应注意保持原语句的意义。如： p整数都是自然数 则p表示：,13,2)合取词(conjunction)“并且”(and),用符号表示。 设p，q表示两命题，那么pq表示合取p和q所得的命题， pq读作“p并且q”或“p且q”。 规定：p和q同时为真时pq真，否则pq为假。,14,2)合取词(conjunction)“并且”(and),p,q,pq,0 0 1 1,0 1 0 1,0 0 0 1,15,例：,p: 教室里有10名女同学。q: 教室里有15名男同学。

5、 命题“教室里有10名女同学与15名男同学”， 可表示为pq。,16,例：,a: 今天下雨了。b: 教室里有100张桌子。 可知ab就是命题 今天下雨了并且教室里有100张桌子.,17,析取词(disjunction)“或”(or),用符号表示。 pq读作“p或者q”，“p或q”。 设p，q表示两命题，那么pq表示p和q的析取， 规定：当p和q有一为真时，pq为真，只有当p和q均假时pq为假。,18,p,q,pq,0 0 1 1,0 1 0 1,0 1 1 1,析取词(disjunction)“或”(or),19,例：,p: 我选修人工智能。 q: 我选修算法理论。 则pq: 我选修人工智能或

6、选修算法理论。,20,在自然语言中的“或”具有二义性，有时“或”是可兼的，有时是不可兼或(即排斥或)。而逻辑连接词中的或是可兼的。 例如：(1) 张三或者李四考了90分。 (2) 第一节课上数学课或者上英语课。 (3) 人固有一死，或重于泰山，或轻于鸿毛 。,析取词(disjunction)“或”(or),21,合取词(conjunction)“并且”(and),p,q,pq,0 0 1 1,0 1 0 1,0 1 1 0,22,4.蕴涵词(implication)“如果，那么”(ifthen),用符号表示。 pq的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的

7、必要条件”，“q当p”，“p仅当q”等等。 设p，q表示两命题，那么pq表示命题“如果p，那么q”。,23,蕴涵词(implication)“如果，那么”(ifthen),规定：当p真而q假时，命题pq为假，否则均认为pq为真。,24,p,q,p q,0 0 1 1,0 1 0 1,1 1 0 1,蕴涵词(implication)“如果，那么”(ifthen),25,例：,如果我拿到奖学金，我请客。,pq中的p称为蕴涵前件，q称为蕴涵后件。 数学中还常把qp，pq，qp分别叫做pq的逆命题，否命题，逆否命题。,26,5.双向蕴涵词(two-way implication)“当且仅当”(if a

8、nd only if)，,用符号表示之。 pq读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。 设p，q为两命题，那么pq表示命题“p当且仅当q”，“p与q等价”， 规定：当p与q同真值时pq为真，否则为假。,27,例：,p:ABC是等腰三角形 q:ABC中有两个角相等 命题p q就是ABC是等腰三角形当且仅当ABC中有两个角相等。,28,五、命题公式,定义3.1 归纳定义命题公式(proposition formula)： (1)命题常元和命题变元是命题公式，也称为原子公式或原子。 (2)如果A，B是命题公式，那么(A)，(AB)，(AB)，(AB)，(AB)也是命题公式。 (3)只

9、有有限步引用条款(1)，(2)所组成的符号串是命题公式。,29,判断 (p(qr)， (pq),pr, p1p2 是否为命题公式。,30,五、命题公式,为使公式的表示更为简练，我们作如下约定： (1)公式最外层括号一律可省略。 (2)联结词的结合能力强弱依次为 ，(，)， (，)表示与平等。 (3)结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。,31,通常采用省略一部分又保留一部分括号的办法，这样选择就给公式的阅读带来方便。如 (p(qr) 可写成p(qr)或pqr。 (p(pr) 可写成p(pr)。,五、命题公式,32,指派 命题公式代表一个命题，但只有当公式中的每一个命题

10、变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。,设公式A为含有命题变元p1，p2，,pn的命题公式，对p1，p2，,pn分别指定一个真值,A均有一个确定的真值。称为对公式A的一组真值指派。,公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。,五、命题公式,33,五、命题公式,当A(p1,pn)中有k个联结词时，公式A的真值表应为2n行、k+n列 例：p(pq)(pq) 若是公式，给出它的真值表。,34,六、语句的形式化,利用联结词可以把许多日常语句符号化。基本步骤如下：,(1)从语句中分析出各原子命题，将它们符号化；,(2)使用合适的命题联结词，把原子命题逐个联结起

11、来，组成复合命题的符号化表示。,35,例 用符号形式表示下列命题。 (1) 我和他既是兄弟又是同学。 (2) 我和你之间至少有一个要去海南岛。 (3) 狗急跳墙。 (4) 除非他来，否则我不同他谈判。,六、语句的形式化,36,(5)如果他没来见你，那么他或者是生病了，或者是不在本地。 (6)如果袁翼和王虎不都是傻子，那么他们俩都不会去。 (7)风雨无阻，我去北京 (8)因为天下雨，所以地皮湿。,37,语句形式化要注意以下几个问题,要善于确定原子命题； 要善于识别自然语言中的逻辑联结词； 否定词的的位置要放准确； 需要的括号不能省略； 语句的形式化未必是惟一的。,38,将下列命题符号化 (1)

12、派小王或小李出差； (2) 我们不能既划船又跑步； (3) 如果你来了，那么他唱不唱歌将看你是否伴奏而定； (4) 如果李明是体育爱好者，但不是文艺爱好者，那么 李明不是文体爱好者； (5) 假如上午不下雨，我去看电影，否则就在家里看书。,解 (1) 令p：小王出差；q：小李出差。 命题符号化为pq。,(2) 令p：我们划船；q：我们跑步。则命题可 表示为(pq),(3) 令p：你来了；q：他唱歌；r：你伴奏。 则命题可表示为 p(qr),(4) 令p：李明是体育爱好者；q：李明是文艺爱好者。 则命题可表示为(p q)(p q),(5) 令p：上午下雨；q：我去看电影；r：我在家读书。 则命题

13、可表示为(p q)(pr),39,七、逻辑等价和逻辑蕴涵式,重言式 定义3-2 命题公式A称为重言式(tautology)，如果对A中命题变元的一切指派均弄真A。 因而重言式又称永真式。 A称为可满足式(satisfactable formula)，如果至少有一个指派弄真A，否则称A为不可满足式或永假式、矛盾式。 很显然，永真式是可满足式，非永真式未必是永假式，而当A是永真式(永假式)时， A必为永假式(永真式)。,40,重言式,例 构造下列命题公式的真值表，并判断它们是何种类型的公式 (1) ( pq) (pq)；,例 对任何公式A，AA是重言式，AA是矛盾式。这两个事实揭示人们通常的思维所

14、遵循的逻辑排中律和矛盾律。对任何原子命题p，p与p都是可满足式。,41,解: 令F=（pq）（p q），,F的真值表如下：,由上可知： F是重言式 。,重言式,42,重要的逻辑等价式,定义3-3 当命题公式AB为永真式时，称A逻辑等价于B，记为AB，它又称为逻辑等价式(logically equivalent)。 因此，逻辑等价式AB可以从两个角度去理解： （1）AB表示断言“AB是重言式”。 （2）AB表示“A，B等值”，或理解为“当A真时B亦真，当A假时B也假”，甚至理解为“由A真可推出B真，且由B真可推出A真”。,43,以下是一些重要的逻辑等价式，其中A，B，C表示任意命题公式： E1

15、AA 双重否定律 E2 AAA ，AAA 幂等律 E3 ABBA ，ABBA 交换律 E4 (AB)CA(BC) 结合律 (AB)CA(BC) 结合律 E5 A(BC)(AB)(AC) 分配律 A(BC)(AB)(AC),44,E6 (AB)AB 德摩根律 (AB)AB E7 A(AB)A 吸收律 A(AB)A E8 ABAB E9 A B(AB)(BA) E10 Att ， Aff E11 AfA ， AtA,45,E12 AAt ，AAf E13 tf, ft E14 ABCA(BC) E15 ABBA E16 (AB)(AB)A E17 A B(AB)(AB),46,定义3-4 当命题公

16、式AB为永真式时，称A逻辑蕴涵B，记为A B，它又称为逻辑蕴涵式(logically implication)。 同样，A B可作以下两种理解： （1）A B表示语句“AB为永真式”。 （2）A B表示“弄真A的指派均弄真B”，因而可理解为“由A真可推得B真”,或“由B假可推得A假”，但反之不然。,逻辑蕴涵式,47,一些十分重要的逻辑蕴涵式,I1 A AB，B AB I2 AB A，AB B I3 A(AB) B I4 (AB)B A I5 A(AB) B，B(AB) A I6 (AB)(BC) AC I7 (AB)(CD) (AC)(BD) I8 (AB)(BC) AC,48,A B这一形式

17、常被推广为 B，其中 为公式集合，它表示: B是 的逻辑结果，即弄真 中每一公式的指派均弄真B。 = A时，它即表示A B；当为若干个公式的集合时，它可以看作是这若干个公式的合取逻辑蕴涵B；当 = 时，它记作 B，表示“B永真”。,49,定理3-1 对任意命题公式A，B，C，A，B， （1）AB当且仅当 AB （2）A B当且仅当 AB （3）若AB，则BA （4）若AB，BC，则AC （5）若A B，则B A （6）若A B，B C，则A C （7）若A B，AA ，BB ， 则A B,50,三种证明逻辑等价式及逻辑蕴涵式的方法,（1）真值表法。为证AB，A B，可用真值表分别证明AB永真,

18、 AB永真。做法平凡,例不赘述。 （2）利用已知的永真式、逻辑等价式及逻辑蕴涵式进行推演。 （3）对指派进行讨论。为证A B，只要证任意弄真A的指派都弄真B（或证任一弄假B的指派均弄假A）。为证AB，可用此法同时证明A B，B A。,51,例：,用三种不同的方法证明： （1）(AB)A A （2）AB(AB)(AB),52,八、范式,文字(letters)：指命题常元、变元及它们的否定，前者又称正文字，后者则称负文字。 析取子句(disjunctive clauses)：指文字或若干文字的析取。例如, p , pq , pqr . 合取子句(conjunctive clauses)：指文字或若

19、干文字的合取。例如, p , pq , pqr .,53,析取范式,互补文字对(complemental pairs of letters) ：指形如L，L（L为文字）的一对字符。 定义3-6 命题公式A称为公式A的析取范式（disjunctive normal form），如果 （1）AA （2）A为一合取子句或若干合取子句 的析取。,54,析取范式,例： p(pq)r(pqr) 是一析取范式。,55,合取范式,定义3-7 命题公式A称为公式A的合取范式（conjunctive normal form）如果 （1）A A （2）A为一析取子句或若干析取 子句的合取。,56,例： p(pq)r

20、(pqr) 是一合取范式。,合取范式,57,求取范式步骤： 第一步，消去公式中的联结词和： 把公式中的pq化为pq； 把公式中的pq化为(pq)(qp)或(pq) (pq)； 第二步，将否定联结词 向内深入，使之只作用于命题变元或命题变元的否定，然后将p化为p； 第三步，利用分配律，将公式进一步化为所需要的范式。,58,析取范式和合取范式求取,例3-21 求p(pq) 的析取范式及合取范式。 p(pq)p(pq) p(pq)(p)析取范式 (pp)(pq) p(pq)(p)合取范式,59,范式,一公式的析取范式和合取范式都不是唯一的 。 一公式的合取范式与析取范式又可能是同一的。,60,析取范

21、式和合取范式,合取范式和析取范式，可分别用于识别永真式和永假式。,例 （1）(pq)pq为永真式。 （2）(q(pq)p)(qp)为永假 式。,61,范式可用来判断重言式和矛盾式,若一公式的合取范式中，所有的析取式字句都至少含有一个互补文字，则该范式及相应的公式必为重言式。若一公式的析取范式中，所有的合取字句都至少含有一个互补文字，则该范式及相应的公式必为矛盾式。,62,主析取范式与主合取范式,定义3-8 设A为恰含命题变元p1,pn的公式。公式A称为A的主析（合）取范式（majordisjunctive（conjunctive）normal form），如果A是A的析（合）取范式，并且其每个合（析）取子句中p1,pn均恰出现一次。,63,步骤： 第一步：求出该公式的析（合）取范式； 第二步：简化各子句，除去范式中所有恒假（真）的合（析）