高等数学--第十七章数理逻辑.ppt

第十七章数理逻辑第十七章数理逻辑17.1 命题与联结词17.2 公式的相等与蕴涵17.3 谓词与量词2.1命题以及逻辑联结词2.1.1命题所谓命题是指一句有真假意义的话。例如：上海是中国最大的城市 今天是星期二 所有素数都是奇数 1+1=2命题用大写英文字母P，Q，…，P1，P2，…，表示。如果一个命题是真的，就说它的真值是1；如果一个命题是假的，就说它的真值是0。也用“1”代表一个抽象的真命题，用“0”代表一个抽象的假命题。定义2.1.1设P是一个命题，命题“P是不对的”称为P的否定，记以?P，读作非P。?P是真的当且仅当P是假的。例如：

P：吉大是中国最大的大学。?P：吉大不是中国最大的大学。定义2.1.2设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以P?Q，读作P或Q。规定P?Q是真的当且仅当P，Q中至少有一个是真的。例如：

P：今天下雨，Q：今天刮风， P?Q：今天下雨或者刮风。定义2.1.3设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以P?Q，读作P且Q。规定P?Q是真的当且仅当P和Q都是真的。例如，P：2?2=5，Q：雪是黑的，

P?Q：2?2=5并且雪是黑的。定义2.1.4设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以P?Q。规定，P?Q是假的当且仅当P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是连续的，

P?Q：若f(x)是可微的，则f(x)是连续的。由定义知，如果P是假命题，则不管Q是什么命题，命题“如果P，则Q”在命题逻辑中都被认为是真命题。例如，P：2?2=5，Q：雪是黑的，

于是，命题“如果2?2=5，则雪是黑的”是真命题。定义2.1.5设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以P?Q。规定，P?Q是真的当且仅当P，Q或者都是真的，或者都是假的。例如， P：a2+b2=a2，

Q：b=0，

P?Q：a2+b2=a2当且仅当b=0。例2.1.1如果你走路时看书，那么你会成为近视眼。令P：你走路；Q：你看书；R：你会成为近视眼。于是，上述语句可表示为（P?Q）?R。例2.1.2除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。令P：他书面通知我；Q：他口头通知我；R：我参加明天的会议。于是，上述语句可表示为(P?Q)?R。例2.1.3设P，Q，R的意义如下：

P：苹果是甜的；Q：苹果是红的；

R：我买苹果。

试用日常语言复述下述复合命题：

(1)(P?Q)?R (2)(?P??Q)??R解：(1)如果苹果甜且红，那么我买。(2)我没买苹果，因为苹果不甜也不红。2.2命题公式§2.2.1公式我们用大写的英文字母P，Q，R，…等代表一个抽象的命题，或称为命题符号。定义2.2.1命题符号称为原子。例如，Q，S，…等都是原子。定义2.2.2命题公式命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式； (2) 0、1是公式； (3) 若G，H是公式，则(?G)，(G?H)， (G?H)，(G?H)，(G?H)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3)

得到的符号串。规定：公式(?G)的括号可以省略，写成?G。整个公式的最外层括号可以省略。五种逻辑联结词的优先级按如下次序递增： ?，?，?，?，?例如，我们写符号串

P?Q?R?Q??S?R

就意味着是如下公式： ((P?(Q?R))?(Q?((?S)?R)))§2.2.2解释定义2.2.3设G是命题公式，A1,…,An是出现在G中的所有原子。指定A1,…,An的一组真值，则这组真值称为G的一个解释。设G是公式，I是G的一个解释，显然，G在I下有真值，通常记为TI(G)。例G=P?Q，设解释I，I’如下：

I： I’：

则TI(G)=1，TI’(G)=0定义2.2.4公式G在其所有可能的解释下所取真值的表，称为G的真值表。显然，有n个不同原子的公式，共有2n个解释。例：G=(P?Q)?R，其真值表如下：若公式G中出现的所有原子为A1，…，An，有时我们用{m1，…，mn}表示G的一个解释I，其中

例如，上例公式G的真值表中第二个解释就可以记为{?P，?Q，R}定义2.2.5公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；公式G称为恒假的(或不可满足的)，如果G在它的所有