第1章---数理逻辑课件.ppt

《第1章---数理逻辑课件.ppt》由会员分享，可在线阅读，更多相关《第1章---数理逻辑课件.ppt（313页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1第1章 数理逻辑1.1命题1.2重言式1.3范式1.4联结词的扩充与归约1.5推理规则和证明方法1.6谓词和量词1.7谓词演算的永真公式1.8谓词演算的推理规则第1章 数理逻辑2第1章 数理逻辑 1.1 命 题1.1.1 基本概念断言是一陈述语句。一个命题是一个或真或假而不能两者都是的断言。如果命题是真，我们说它的真值为真;如果命题是假，我们说它的真值是假。3第1章 数理逻辑例 1.1-1 下述都是命题:(1)今天下雪;(2)3+3=6;(3)2 是偶数而 3 是奇数;(4)陈涉起义那天，杭州下雨;(5)较大的偶数都可表为两个质数之和。4第1章 数理逻辑以上命题中，(1)的真值取决于今天的天

2、气;(2)和(3)是真;(4)已无法查明它的真值，但它是或真或假的，故将它归属于命题;(5)目前尚未确定其真假，但它是有真值的，应归属于命题。5第1章 数理逻辑例 1.1-2 下述都不是命题:(1)x+y 4。(2)x=3。(3)真好啊!(4)你去哪里?(1)和(2)是断言，但不是命题，因为它的真值取决于x 和y的值。(3)和(4)都不是断言，所以不是命题。下边我们再看一个例子。6第1章 数理逻辑例 1.1-3 一个人说:“我正在说谎”。他是在说谎还是在说真话呢?如果他讲真话，那么他所说的是真，也就是他在说谎。我们得出结论如果他讲真话，那么他是在说谎。另一方面，如果他是说谎，那么他说的是假;因

3、为他承认他是说谎，所以他实际上是在说真话，我们得出结论如果他是说谎，那么他是讲真话。7第1章 数理逻辑从以上分析，我们得出他必须既非说谎也不是讲真话。这样，断言“我正在说谎”事实上不能指定它的真假，所以不是命题。这种断言叫悖论。若一个命题已不能分解成更简单的命题，则这个命题叫原子命题或本原命题。例1.1-1 中(1)、(2)、(4)、(5)都是本原命题，但(3)不是，因为它可写成“2 是偶数”和“3 是奇数”两个命题。命题和本原命题常用大写字母P、Q、R表示。如用P 表示“4 是质数”，则记为 P:4 是质数8第1章 数理逻辑1.1.2 命题联结词命题和原子命题常可通过一些联结词构成新命题，这

4、种新命题叫复合命题。例如 P:明天下雪 Q:明天下雨是两个命题，利用联结词“不”、“并且”、“或(者)”等可分别构成新命题:“明天不下雪”;“明天下雪并且明天下雨”;“明天下雪或者明天下雨”等。9第1章 数理逻辑即“非P”;“P 并且Q”;“P 或Q”等。在代数式x+3 中，x、3 叫运算对象，+叫运算符，x+3 表示运算结果。在命题演算中，也用同样的术语。联结词就是命题演算中的运算符，叫逻辑运算符或叫逻辑联结词。常用的联结词有以下 5 个。10第1章 数理逻辑1.否定词 设P 表示命题，那么“P 不真”是另一命题，表示为 P，叫做P 的否定，读做“非P”。由排中律知:如果P 是假，则 P 是

5、真，反之亦然。所以否定词可以如表1.1-1 所示定义。11第1章 数理逻辑12第1章 数理逻辑这张表叫真值表。定义运算符的真值表，可指明如何用运算对象的真值来决定一个应用运算符的命题的真值。真值表的左边列出运算对象的真值的所有可能组合，结果命题的真值列在最右边的一列。为了便于阅读，我们通常用符号T(true)或 1 代表真，符号F(false)或 0 代表假。一般在公式中采用T 和F，在真值表中采用 1 和 0。这样，以上真值表可写成表1.1-2所示的形式。13第1章 数理逻辑表1.1-214第1章 数理逻辑例 1.1-4(1)P:4 是质数。P:4 不是质数。或 4 是质数，不是这样。(2)

6、Q:这些都是男同学。Q:这些不都是男同学。(翻译成“这些都不是男同学”是错的。)15第1章 数理逻辑2.合取词如果P 和Q 是命题，那么“P 并且Q”也是一命题，记为P Q，称为P 和Q 的合取，读做“P 与Q”或“P 并且Q”。运算符定义如表1.1-3 所示。从真值表可知P Q 为真，当且仅当P和Q 俱真。例 1.1-5 P:王华的成绩很好，Q:王华的品德很好。P Q:王华的成绩很好并且品德很好。16第1章 数理逻辑表1.1-317第1章 数理逻辑3.析取词如果P 和Q 是命题，则“P 或Q”也是一命题，记作P Q，称为P 和Q 的析取，读做“P 或Q”。运算符定义如表1.1-4 所示。从真

7、值表可知P Q 为真，当且仅当P 或Q 至少有一个为真。18第1章 数理逻辑表1.1-419第1章 数理逻辑例 1.1-6(1)P:今晚我写字，Q:今晚我看书。P Q:今晚我写字或看书。“或”字常见的含义有两种:一种是“可兼或”，如例1.1-6 中的或，它不排除今晚既看书又写字这种情况;一种是“排斥或”，例如“人固有一死，或重于泰山，或轻于鸿毛”中的“或”，它表示非此即彼，不可兼得。运算符表示可兼或，排斥或以后用另一符号表达。20第1章 数理逻辑(2)P:今年是闰年;Q:今年她生孩子。P Q:今年是闰年或者今年她生孩子。逻辑运算符可以把两个无关的命题联结成一新命题，作如此规定是因为有关和无关的

8、界线难以划分，而如此规定不会妨碍应用。21第1章 数理逻辑4.蕴含词如果P 和Q 是命题，那么“P 蕴含Q”也是命题，记为PQ，称为蕴含式，读做“P 蕴含Q”或“如果P，那么Q”。运算对象P 叫做前提、假设或前件，而Q 叫做结论或后件。运算符定义如表1.1-5 所示。命题PQ 是假，当且仅当P 是真而Q 是假。22第1章 数理逻辑表1.1-523第1章 数理逻辑例 1.1-7(1)P:天不下雨，Q:草木枯黄。PQ:如果天不下雨，那么草木枯黄。(2)R:G 是正方形，S:G 的四边相等。RS:如果G 是正方形，那么G 的四边相等。(3)W:桔子是紫色的，V:大地是不平的。WV:如果桔子是紫色的，

9、那么大地是不平的。24第1章 数理逻辑在日常生活中用蕴含式来断言前提和结论之间的因果或实质关系，如例1.1-7 中的(1)和(2)，这样的蕴含式叫形式蕴含。在命题演算中，一个蕴含式的前提和结论并不需要有因果和实质联系，这样的蕴含式叫实质蕴含，如例1.1-7 中的(3)，桔子的颜色和大地的外形之间没有因果和实质关系存在，但蕴含式WV 是真，因为前提是假而结论是真。采用实质蕴含作定义，是因为在讨论逻辑和数学问题中，这不仅是正确的，而且应用方便。25第1章 数理逻辑蕴含式PQ 可以用多种方式陈述:“若P，则Q”;“P 是Q 的充分条件”;“Q 是P 的必要条件”;“Q 每当P”;“P 仅当Q”等。如

10、例1.1-7(2)中的RS可陈述为“G 是正方形的必要条件是它的四边相等”。给定命题PQ，我们把QP，P Q，Q P 分别叫做命题PQ 的逆命题、反命题和逆反命题。26第1章 数理逻辑5.等值词如果P 和Q 是命题，那么“P 等值于Q”也是命题，记为P Q，称为等值式，读做“P 等值于Q”。运算符定义如表1.1-6 所示。比较表1.1-5 和表1.1-6 易知，如果P Q 是真，那么PQ 和QP 俱真;反之如果PQ 和QP 俱真，那么P Q 是真。由于这些理由，P Q 也读做“P 是Q 的充要条件”或“P 当且仅当Q”。27第1章 数理逻辑表1.1-628第1章 数理逻辑从以上 5 个定义可看

11、出，联结词之意义由其真值表唯一确定，而不由命题的含义确定。使用以上 5 个联结词，可将一些语句翻译成逻辑式。翻译时为了减少圆括号(一般不用其它括号)的使用，我们作以下约定:运算符结合力的强弱顺序为、，凡符合此顺序的，括号均可省去。相同的运算符，按从左至右次序计算时，括号可省去。最外层的圆括号可以省去。29第1章 数理逻辑例如:(P Q)R)(R P)Q)可写成(P Q R)R P Q但有时为了看起来清楚醒目，也可以保留某些原可省去的括号。30第1章 数理逻辑例 1.1-8(1)设P 表示“他有理论知识”，Q 表示“他有实践经验”，则“他既有理论知识又有实践经验”可译为:P Q。31第1章 数理

12、逻辑(2)设P:明天下雨，Q:明天下雪，R:我去学校，则“如果明天不是雨夹雪则我去学校”可写成(P Q)R“如果明天不下雨并且不下雪则我去学校”可写成 P QR“如果明天下雨或下雪则我不去学校”可写成P Q R32第1章 数理逻辑“明天，我将雨雪无阻一定去学校”可写成P Q R P Q R P Q R P Q R“当且仅当明天不下雪并且不下雨时我才去学校”可写成 P Q R33第1章 数理逻辑(3)用逻辑符表达“说小学生编不了程序，或说小学生用不了个人计算机，那是不对的”。设P:小学生会编程序，Q:小学生会用个人计算机，则上句可译为(P Q)34第1章 数理逻辑(4)用逻辑符表达“若不是他生病

13、或出差了，我是不会同意他不参加学习的”。设P:他生病了，Q:他出差了，R:我同意他不参加学习，则上句可译为(P Q)R或P Q R翻译时要按逻辑关系翻译，而不能凭字面翻。例如，设P:林芬做作业，Q:林芳做作业，则“林芬和林芳同在做作业”可译为P Q，但“林芬和林芳是姐妹”就不能翻释成两个命题的合取，它是一个原子命题。35第1章 数理逻辑1.1.3 命题变元和命题公式通常，如果P 代表真值未指定的任意命题，我们就称P 为命题变元;如果P 代表一个真值已指定的命题，我们就称P 为命题常元。但由于在命题演算中并不关心具体命题的涵义，只关心其真假值，因此，我们可以形式地定义它们。以“真”、“假”为其变

14、域的变元，称为命题变元;T 和F称为命题常元。36第1章 数理逻辑习惯上把含有命题变元的断言称为命题公式。但这样描述过于表面，它没能指出命题公式的结构。因为不是由命题变元、联结词和一些括号组成的字符串都能成为命题公式，因此在计算机科学中常用以下定义。单个命题变元和命题常元叫原子公式。由以下形成规则生成的公式叫命题公式(简称公式):单个原子公式是命题公式。如果A 和B 是命题公式，则(A)、(A B)、(A B)、(AB)、(A B)是命题公式。只有有限步地应用规则和生成的公式，才是命题公式。37第1章 数理逻辑这种定义叫归纳定义，也叫递归定义。由这种定义产生的公式叫合式公式。如何构成这种定义，

15、以后将专门叙述。命题公式的真假值一般是不确定的。当命题公式中所有的命题变元代以命题时，命题公式就变为命题。在不致产生混乱时，我们把命题公式也叫做命题。38第1章 数理逻辑例 1.1-9(1)说明(P(P Q)是命题公式。解(i)P 是命题公式 根据规则(ii)Q 是命题公式 根据规则(iii)(P Q)是命题公式 根据(i)、(ii)和规则(iv)(P(P Q)是命题公式 根据(i)、(iii)和规则39第1章 数理逻辑(2)以下不是命题公式，因为它们不能由形成规则得出:Q，(PQ，PQ，(PQ)R)为了减少圆括号的使用，以后手写命题公式时，可按过去的约定省略。下面举例说明命题公式真值表的构成

16、方法。40第1章 数理逻辑例 1.1-10(1)(P Q)P)的真值表如表1.1-7 所示。41第1章 数理逻辑表1.1-742第1章 数理逻辑(2)两个命题公式如果有相同的真值，则称它们是逻辑等价命题。证明P Q 与P Q P Q 是逻辑等价命题。证 列真值表，如表1.1-8 所示。因后两列的真假值完全一致，所以它们是逻辑等价命题。43第1章 数理逻辑表1.1-844第1章 数理逻辑习 题1.设P 是命题“天下雪”;Q 是命题“我去镇上”;R 是命题“我有时间”。(1)用逻辑符号写出以下命题:如果天不下雪和我有时间，那么我去镇上。我去镇上，仅当我有时间。天不下雪。天正在下雪，我没去镇上。45

17、第1章 数理逻辑(2)对下述命题用中文写出语句。Q(R P)R Q(QR)(RQ)(R Q)2.否定下列命题:(1)上海处处清洁。(2)每一个自然数都是偶数。46第1章 数理逻辑3.说出下述每一命题的逆命题和逆反命题:(1)如果天下雨，我将不去。(2)仅当你去我将逗留。(3)如果n是大于 2 的正整数，则方程xn+yn=zn无正整数解(费尔马最后定理)。(4)如果我不获得更多帮助，我不能完成这个任务。47第1章 数理逻辑4.给P 和Q 指派真值T，给R 和S 指派真值F，求出下列命题的真值:(1)P Q R(2)P Q R(P Q)(R S)(3)(P Q)R)(P Q R)S(4)(P Q)

18、R(Q P)R S)(5)(P R)(QS)(6)P(QR P)Q S48第1章 数理逻辑5.构成下列公式的真值表:(1)Q(PQ)P(2)(P Q R)(P Q)(P R)(3)(P QQ R)P R(4)(PP Q)R)Q R49第1章 数理逻辑6.证明下列公式的真值与它们的变元值无关:(1)P(PQ)Q(2)(PQ)(P Q)(3)(PQ)(QR)(PR)(4)(P Q)(P Q P Q)50第1章 数理逻辑7.用真值表证明如果P Q 是真，那么PQ 和QP 都是真。反之，如果PQ 和QP 都是真，那么P Q 是真。8.对P 和Q 的所有值，证明PQ 与 P Q 有同样真值以及(PQ)(

19、P Q)总是真的。51第1章 数理逻辑9.一个有两个运算对象的逻辑运算符，如果交换运算对象的次序，产生一逻辑等价命题，则该逻辑运算符称为可交换的。(1)确定下述逻辑运算符哪些是可交换的:、。(2)用真值表证明你的断言。10.设*是具有两个运算对象的逻辑运算符，如果(x*y)*z和x*(y*z)逻辑等价，那么运算符*是可结合的。(1)确定逻辑运算符、中哪些是可结合的。(2)用真值表证明你的断言。52第1章 数理逻辑11.指出以下各式哪些不是命题公式，如果是命题公式，请说明理由:(1)(P)(P Q)R)(2)(PQ R)(3)P R(4)(Q(PQ)P)*12.一个形容词如果不具有它所表示的性质

20、，则称为“它谓的”(Heterological)，例如“单音节”(Monosyllabic)就是它谓的形容词，而“多音节”(Polysyllabic)就不是它谓的形容词，问“Heterological”是它谓的形容词吗?为什么这是悖论?53第1章 数理逻辑 1.2 重 言 式1.2.1 基本概念对有n个命题变元的命题公式A(P1，P2，Pn)，命题变元的真值有2n种不同的组合。每一种组合叫做一种指派，一共有2n种指派，这就是说真值表有 2n行。对应于每一指派，命题公式得到一确定的值，即命题公式成为具有真假值的命题，于是可能出现以下情况:54第1章 数理逻辑(1)对应于所有指派，命题公式均取值真

21、。这种命题公式叫重言式，或叫永真式，例如P P。(2)对应于所有指派，命题公式均取值假。这种命题公式叫矛盾式，或叫永假式，例如P P。(3)不是永真式，也不是永假式，这种命题公式叫偶然式。一个公式如果至少存在一个指派，使其值为真，则称此公式为可满足的;一个公式如果至少存在一个指派，使其值为假，则称此公式为非永真。55第1章 数理逻辑我们着重研究重言式，它最有用，因为它有以下特点:(1)重言式的否定是矛盾式，矛盾式的否定是重言式，所以研究其一就可以了。(2)重言式的合取、析取、蕴含、等值等都是重言式。这样，由简单的重言式可推出复杂的重言式。(3)重言式中有许多非常有用的恒等式和永真蕴含式。56第

22、1章 数理逻辑1.2.2 恒等式设A:A(P1,P2,Pn)，B:B(P1,P2,Pn)是两个命题公式，这里Pi(i=1,2,n)不一定在两公式中同时出现。如果A B 是重言式，则A 与B 对任何指派都有相同的真值。记为A B，叫做逻辑恒等式，读做“A 恒等于B”。57第1章 数理逻辑容易看出，A B 不过是上节的“A 和B 逻辑等价”的另一种描述方式而已。所以，A B 也读做“A 等价于B”。请注意符号 与符号 意义不同。是逻辑联结词，而 是表示A和B 有逻辑等价这个关系的符号，它的作用相当于代数中的“=”。常用的逻辑恒等式见表 1.2-1，表中符号P、Q 和R 代表任意命题，符号T 代表真

23、命题，符号F 代表假命题。58第1章 数理逻辑表 1.2-1 逻 辑 恒 等 式59第1章 数理逻辑有些恒等式特别重要，例如E14允许蕴含式用析取式表达，E10、E11允许析取式和合取式互相表达，另外，E15、E24也是常用的。表中所有公式都可用构造真值表证明。60第1章 数理逻辑1.2.3 永真蕴含式如果AB 是一永真式，那么称为永真蕴含式，记为A B，读做“A 永真蕴含B”。常用的永真蕴含式如表 1.2-2 所示。61第1章 数理逻辑表 1.2-2 永真蕴含式62第1章 数理逻辑永真蕴含式也可用真值表证明，但也可用以下办法证明:(1)假定前件是真，若能推出后件是真，则此蕴含式是真。(2)假

24、定后件是假，若能推出前件是假，则此蕴含式是真。63第1章 数理逻辑例 1.2-1 证明 Q(PQ)P方法 1:设 Q(PQ)是真，则 Q、PQ 是真。所以，Q 是假，P 是假。因而 P 是真。故 Q(PQ)P。方法 2:设 P 是假，则P 是真。以下分情况讨论。(i)若Q 为真，则 Q 是假，所以 Q(PQ)是假。(ii)若Q 是假，则PQ 是假，所以 Q(PQ)是假。故 Q(PQ)P。64第1章 数理逻辑1.2.4 恒等式和永真蕴含式的两个性质(1)若A B、B C，则A C;若A B、B C 则A C。这一性质也可叙述为:逻辑恒等和永真蕴含都是传递的。前者留给读者自证，现证明后者。证 AB

25、 永真;BC 永真，所以(AB)(BC)永真。由公式I6得AC 永真，即A C。(2)若A B、A C，则A B C。证 A 是真时，B 和C 都真，所以B C 也真。因此AB C永真，则A B C。65第1章 数理逻辑1.2.5 代入规则和替换规则1.代入规则(Rule of Substitution)一重言式中某个命题变元出现的每一处均代入以同一公式后，所得的仍是重言式。这条规则之所以正确是由于重言式之值不依赖于变元的值的缘故。例如,P P F66第1章 数理逻辑今以R Q 代P 得(R Q)(R Q)F，仍正确。它的思想就如同在代数中，若x2-y2=(x+y)(x-y)则(a+b)2-(

26、mn)2=(a+b+mn)(a+b-mn)一样。67第1章 数理逻辑代入后所得公式称为原公式的代入实例。对非重言式通常不作代入运算，特别是偶然式，因所得代入实例的性质不确定，没有用处。例如:B:PQ原是偶然式，若用R R 代换B 中之Q，得A:P(R R)却是重言式。68第1章 数理逻辑2.替换规则(Rule of Replacement)设有恒等式A B，若在公式C 中出现A 的地方替换以B(不必每一处)而得到公式D，则C D。如果A 是合式公式C 中完整的一部分，且A 本身是合式公式，则称A 是C 的子公式，规则中“公式C 中出现A”意指“A 是C 的子公式”。这条规则的正确性是由于在公式

27、C 和D 中，除替换部分外均相同，但对任一指派，A 和B 的真值相同，所以C 和D的真值也相同，故C D。69第1章 数理逻辑应用这两条规则和已有的重言式可以得出新的重言式。例如，对公式E4:P Q Q P，我们以A B 代P，A B 代Q，就得出公式 A B A B A B A B以 A 代P，A B C 代Q，得就出公式 A(A B C)(A B C)A 70第1章 数理逻辑对公式E19:P T P，我们利用公式P P T，对其中的T 作替换(注意不是代入，对命题常元不能代入)得公式 P(P P)P 因此，我们可以说表 1.2-1 和表 1.2-2 中的字符P、Q 和R 不仅代表命题变元，而且可以代表命题公式，T 和F 不仅代表真命题和假命题，而且可以代表重言式和永假式。用这样的观点看待表中的公式，应用就更方便了。