离散数学命题逻辑北航

1、第一篇 数理逻辑第一章 命题逻辑 1.1命题符号化及其联结词 1.1.1 命题 命 题 真 值 原子命题 复合命题 命题：能够确定真假的陈述句 命题的真值：对于一个确定的命题，总会有一个“值”，或“真” 或“假”，称为命题的真值。 真：T或1 假：F或0p判断一个句子是否为命题的关键： 1.是否为陈述句 2.是否能确定真值，即真值是否唯一 例1.1.1 判断下列句子是否为命题（1）10是整数（2）北京是我们祖国的首都（3）雪是黑色的（4）今天是7号（5）1+11=100（6）向右看齐！（7）你吃过饭了吗？（8）我在说谎（9）我不给所有自己给自己理发的人理发 我只给所有自己不给自己理发的人理发（

2、10）别的星球上有生物（11）明天下雨有些陈述句在目前看来无法确定真值，但从事物本质而言其本身有确定的真假，所以也是命题 原子命题：不能分解为更简单的命题的命题称为原子命题 复合命题：由联结词、标点符号把几个原子命题联结起来构成的命题称为复合命题 例1.1.2 判断下列句子哪些是原子命题，哪些是复合命题？ （1）煤是白的 （2）我学英语，或者学法语 （3）2是素数 （4）如果天气好，我就去游泳1.1.2 命题表示法 命题标识符：表示命题的符号 通常使用大写英文字母A、B、C、X、Y、Z或带下标的英文字母A1、B2等来表示，也可使用数字表示例1.1.3： P：今天是7号 P1：今天是7号 6：今

3、天是7号 命题常量：一个命题标识符如表示一个确定的命题，则称为命题常量，例1.3中三个标识符都是命题常量 命题变量：如果一个命题标识符并不能表示一个确定的命题，而只表示任意命题的位置标示，就称为命题变量 命题变量可以代表任意命题，不能确定真值，故不是命题，但可以对命题变量进行指派，即利用一个确定的命题取代命题变量1.1.3 联结词 联结词是复合命题中的重要组成部分，为了便于书写及运算，需进行明确规定及符号化，五种重要的联结词有：否定（ ）、合取（ ）、析取（ ）、条件（ ）、双条件（ ）1.否定 定义1.1.1 假设P为一命题，则P的否定为一新命题，记作 P，称为非P，若P的真值为真（T或1）

4、，则P为假（F或0）；若P的真值为假（F或0），则P为真（T或1） 例1.1.4 P:今天是7号 P:今天不是7号 以表格的形式来列出P和P的所有真值情况 说明：（1）否定是一元联结词 （2）满足双重否定定律： （ P） P，其中 “”表示符号两边两个命题在任何情况下真值都相同PPTFFT2.合取 定义1.1.2 给定两个命题P和Q，把它们的合取作为一个新命题，记作PQ，读作P且Q或P与Q，满足：当且仅当P和Q真值同时为T时，PQ为T，在其它情况下，PQ均为F 例1.1.5 P：今天是晴天，Q：昨天是晴天，R：房间里有十张桌子 PQ：今天和昨天都是晴天 PR：今天是晴天且房间里有十张桌子 P和

5、R在自然语言中没有任何相关联系，PR也没有意义，但在数理逻辑中仍然是一个命题 以真值表来表示合取的定义： 性质：（1）PP P （2）PQ QP （3）(PQ)R P(QR) （4）PT P ，PF F （5）P P F 说明：是二元联结词 PQPQTTTTFFFTFFFF3.析取 定义1.1.3 给定两个命题P和Q，把它们的析取作为一个新命题，记作PQ，读作P或Q，满足：当且仅当P和Q真值同时为F时，PQ为F，在其它情况下，PQ均为T 例1.1.6 （1） P：同学们学过英语，Q：同学们学过日语 PQ：同学们学过英语或日语 （2）选小张或小王做班长 （3）小李小李现在在宿舍或在教室自然语言中

6、或有多种理解，（1）为可兼或，而（2）和（3）为不可兼或，析取定义中或为可兼或 真值表： 性质：（1）PP P （2）PQ QP （3）(PQ)R P(QR) （4）PT T ，PF P （5）P P T 说明：是二元联结词PQPQTTTTFTFTTFFF4.条件 定义1.1.4 给定两个命题P和Q，把它们的条件命题作为一个新命题，记作PQ，读作如果P，那么Q，满足：当且仅当P真值为T, Q的真值为F时， PQ为F，在其它情况下， PQ均为T，其中称P为前件或前提，Q为后件或结论 例1.1.7 （1）P：某动物为哺乳动物，Q：该动物为胎生 PQ：如果某动物为哺乳动物，那么它必为胎生 （2）P：

7、雪是黑的，Q：太阳从西边升起 PQ：如果雪是黑的，那么太阳从西边升起（3）P：我去上海，Q：我给你买新衣服 PQ：如果我去上海，那么我给你买新衣服 四种情况：P真，Q真，则PQ为真 P真，Q假，则PQ为假 P假，Q真，则PQ为真 P假，Q假，则PQ为真 真值表：PQPQTTTTFFFTTFFT 说明：（1）“”为二元联结词 （2）前件为F时,条件命题必为T （3）自然语言中，“如果P那么Q”中P与Q之间往往具有一定的内在联系，但在数理逻辑中PQ中的P与Q不一定有相互关系练习：将下列命题符号化（1）只要天不下雨，我就骑自行车上班（2）只有天不下雨，我才骑自行车上班（3）除非下雨，否则我就骑自行车

8、上班（4）如果下雨，我就不骑自行车上班5.双条件 定义1.1.5 给定两个命题P和Q，把它们的双条件命题作为一个新命题，记作P Q，读作P当且仅当Q，满足：当且仅当P与Q的真值相同时， PQ为T，在其它情况下， PQ均为F 例1.1.8 （1）P：两个三角形全等，Q：两个三角形三组对应边相等 PQ：两个三角形全等当且仅当它们的三组对应边都相等 （2）P：5+58，Q：2是素数 PQ：5+58当且仅当2是素数（3）P：a2+b2=0，Q：a=0, b=0 PQ ：a2+b2=0当且仅当a=0, b=0 真值表 说明：（1）为二元联结词 （2）同样可以无因果对应关系，根据联结词的定义判断命题真值

9、PQPQ TTTTFFFTFFFT 例1.1.9 分析下列各命题的真值（1）2+2=4当且仅当3是奇数（2）2+2=4当且仅当3不是奇数（1）2+24当且仅当3是奇数（2）2+24当且仅当3不是奇数1.2 命题公式与翻译1.2.1 命题公式定义1.2.1 命题公式即合式公式，规定为：（1）单个命题变量本身是一个合式公式；（2）如果A是一个合式公式，那么 A也是合式公式；（3）如果A和B都是合式公式，那么AB, AB, AB, AB都是合式公式；（4）只有有限次使用（1）-（3）组成的符号串才是合式公式 例1.2.1 判断下列公式哪些是合式公式 (1) PQR (2) (PQ)R (3) (PQ

10、R) (4) (PQ)(QR)(ST) (5) PQR1.2.2 命题符号化 命题逻辑中，利用之前介绍的五种联结词和合式公式的定义可将复合命题用符号来表示，称为命题符号化，命题符号化的步骤如下：（1）找出各原子命题并分别用命题标识符表示；（2）使用适合的 联结词，将原子命题联结起来，组成复合命题的符号化形式例1.2.2 将下列命题符号化（1）小王是游泳冠军或百米赛跑冠军 （ PQ ）（2）选小王或小李中的一人做班长 （(PQ)(PQ)）（3）小张现在在宿舍或者在教室 （(PQ)） 例1.2.3 将下列命题符号化（1）如果我上街，我就去书店看看，除非我很累（ (PR )Q）（2）小王是电子工程学

11、院的学生，他是1983或1984年生的，他是三好学生 （P(QR)S）五个联结词的优先级顺序：，(， )1.3 真值表与等价公式1.3.1 真值表 定义1.3.1 设A为命题公式，P1,P2,，Pn是其中出现的所有命题变量，给P1,P2,，Pn指定一组真值，称为对A的一个赋值或解释；若指定的真值使得A的值为真，则称这个赋值为A的成真赋值，否则称为成假赋值1.3.1 真值表 定义1.3.2 含n个命题变量的命题公式，共有2n组赋值，将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表 定义1.3.3 如果X是合式公式A的一部分，且X本身也是一个合式公式，那么称X是A的子公式 构造真值表的步

12、骤为：（1）从简单到复杂列出命题公式中的所有子公式（2）列出每个命题变量的所有可能的赋值组合情况（3）计算各个子公式在所有赋值组合下的真值例1.3.1 求下列公式的真值表（1） PQ （2）P(Q P)（3）(P(PQ)Q （4）(PQ)R例1.3.1中（3）在真值表中对各种赋值均为真，而（4）中取值均为假 定义1.3.4 设A是一个命题公式（1）若A在它的各种赋值情况下均为真，则A称为永真式或重言式永真式或重言式，记作T;（2）若A在它的各种赋值情况下均为假，则A称为永假式或矛盾式永假式或矛盾式，记作F;（3）若A至少存在一个赋值是成真赋值，则称A为可满足式可满足式1.3.2 公式的等价 假

13、设A是任意由P和Q两个命题变量组成的命题公式，真值表情况可能如下： A的真值表取值情况最多只可能有24种 那么，n个命题变量也只能生成22n个真值不同的命题公式，而由符号组成的合式公式却有很多种 例1.3.2 在同一个表中构造 PQ和PQ的真值表PQATTT或FTFT或FFTT或FFFT或F定义1.3.5 设A、B为两个命题公式， P1,P2,，Pn是A和B中出现的所有命题变量，给P1,P2,，Pn指定任意一组赋值，A和B的真值都相同，则称A和B是等价的或逻辑相等的，记作AB说明：（1）“”不是联结词，只是表示等价的符号 （2）“”具有自反性、对称性和传递性 例1.3.3 判断下列命题公式是否

14、等价 （1） (PQ)与 PQ （2） (PQ)与 P Q24条命题定律和等价公式，课本P15验证分配率和吸收率另外五条等价式：条件等价式： PQPQ双条件等价式：PQ(PQ) (QP)假言易位：PQQP双条件否定：PQPQ归谬论：(PQ) (PQ) P1.3.3 等值演算 定理1.3.1 （置换规则）设X是合式公式A的子公式，用公式Y置换A中的X得到公式B，若XY, 那么AB根据定理1.3.1和24条等价公式验证合式公式之间的等价性例1.3.4 验证如下的等价式（1） P(QR) (PQ)R（2）P(PQ)(PQ)（3）P(QR) R(QP)1.4 重言式和蕴含式 定理1.4.1 任何两个重

15、言式的合取和析取仍然是重言式证明：假设A,B为两个重言式，则对任意赋值，A,B真值均为T，则： AB T, AB T定理1.4.2 假设A为重言式，则对A中任何命题变量P用任何合式公式置换得到的公式B仍为重言式定理1.4.3 假设A、B为两个命题公式，A B当且仅当A B为重言式 定义1. 4 .1 当且仅当PQ为永真式时，我们称“P蕴含Q”，记作PQ例1.4.1 证明下列蕴含式（1）PQP（2） Q(PQ) P（3）(PQ) (QR) PR 基本蕴涵式（1）PQP ;（2）PQQ；（3）PPQ；（4）QPQ；（5）P(PQ)；（6）Q(PQ)；（7）(PQ)P；（8）(PQ)Q；（9）P (

16、PQ)Q；（10）Q (PQ)P；（11）P(PQ)Q；（12）(PQ)(QR)PR；（13）(PQ)(PR) (QR)R；（14）(PQ)(RS)(PR)(QS)；（1515）( (PQ)( (QR) PR说明：A, B AB 定理1.4.4 P,Q为任意两个命题公式PQ的充分必要条件是PQ且QP定理1.4.5 设A,B,C为合式公式（1）若AB，且A为永真式，则B为永真式（2）若AB，BC，则AC（3）若AB，AC，则A(BC)（4）若AC，BC，则(AB)C例1.4.2 逻辑推证公式： ABC,C, D,D, C CD D A B1.5 其它联结词和全功能集1.5 .1 其它联结词定义1

17、.5.1 设P,Q为两个命题公式，复合命题“P与Q之间恰有一个成立”，称为P与Q的排斥或，记作P Q，也称为P与Q的不可兼析取，P Q为T当且仅当P与Q中有且仅有一个为T（交换律、结合律）（性质：p24）真值表：PQP QTTFTFTFTTFFF 定理1.5.1 设P,Q,R为命题公式，若P Q R,则（1）P RQ;（2）Q RP;（3）P Q R为永假式 定义1.5.2 设P,Q为两个命题公式，复合命题“P不蕴涵Q”称为P与Q的条件否定记作P Q，P Q为T当且仅当P为T,Q为F，显然P Q (PQ)定义1.5.3 设P,Q为两个命题公式，复合命题“P与Q的否定”称为P与Q的与非式，记作P

18、Q, PQ为T当且仅当P,Q不同时为T，显然PQ (PQ)性质：p26定义1.5.4设P,Q为两个命题公式，复合命题“P或Q的否定”称为P与Q的或非式，记作PQ, PQ为T当且仅当P,Q同时为F，显然PQ (PQ)性质：p261.5 .2 联结词全功能集定义1.5.5 在一个联结词的集合中，如果一个联结词可以用集合中其余的联结词表示，则称该联结词为冗余的联结词，否则称为独立的联结词前面定义的五个联结词组成集合 ,而PQ PQ，PQ(PQ) (QP)显然，是冗余的，考虑集合 ,中是否有冗余？定义1.5.6 若合式公式都可用仅含某一联结词集合中的联结词来表示，则称该集合为全功能集，若其中不包含冗余

19、的联结词，则称它为极小的全功能集（ ,和 ,）1.6 对偶和范式 1.6.1 对偶对偶定义1.6.1 在仅含有联结词、的命题公式A中，将联结词换成，将换成，如果A中含有特殊变元T或F亦相互替代，所得的命题公式A*称为A的对偶式。例：公式（PQ）（PQ） 的对偶式为：（PQ）（PQ） 例1.6.1 写出下列公式的对偶式（1）（2）（3）PQ()()PQPR()PTR 例1.6.2 设A*（P,Q,R）为P(QR)，证明 A*(P,Q, R)A(P,Q,R) 定理1.6.1 设A和A*互为对偶式，P1,P2,Pn为其中出现的所有命题变量，则（1）A(P1,P2,Pn)A*(P1,P2,Pn) （2

20、）A(P1,P2,Pn)A*(P1,P2,Pn) 定理1.6.2（对偶原理） 设P1,P2,Pn为出现在命题公式A和B中的所有命题变量，若AB则A*B*证明：1.6.2 范式 定义1.6. 2 仅由有限个命题变元或其否定相互析取得到的公式称为简单析取式简单析取式，仅由有限个命题变元或其否定相互合取得到的公式称为简单合取式简单合取式 例如PQ为简单析取式，而PQR为简单合取式 定义1.6.3 仅由有限个简单合取式构成的析取式称为析取范式析取范式；仅由有限个简单析取式构成的合取式称为合取范式合取范式 例如（PQ）（PQR）为合取范式 ，而其对偶式（PQ）（PQR）为析取范式 定理（范式存在定理）定

21、理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。 求合取范式和析取范式步骤（1）消去除（ ， ）外的联结词（2）否定号消去或内移（3）利用分配率、结合律将公式归约为合取范式和析取范式例1.6.3 求公式(PQ) R) P的合取范式和析取范式结论：合取范式和析取范式不唯一 练习：求下列公式合取范式和析取范式（1）(PQ) R（2） (P (QR)( P ( Q R) 1.6.3 主析取范式主析取范式定义定义1.6.3 在含有n个命题变元P1，P2，Pn的简单合取式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位

22、置上（若命题变元无脚标，则按字典顺序排列，这样的简单合取式称为极小项极小项。一般来说，含有n个命题变量共有2n个极小项个极小项P33列出了含有P,Q,R三个变量的所有极小项的真值表以及所有使得极小项为T的赋值，并按二进制数给予编号 性质：（1）指派与编码同，则真值为T;（2）任两个不同极小项合取式为永假；（3）全体极小项析取为永真定义1.6.4 在含有n个命题变量的命题公式A中，若A的析取范式中的简单合取式均为极小项，则称该析取范式为主析取范式求公式PQ的主析取范式定理定理1.6.4 任何命题公式的主析取范式都是存在的且是唯一的。 求主析取范式步骤：（1）求A的析取范式A（2）若A中某些简单合

23、取式B中不含Pi或Pi，则将B展成：BB TB (Pi Pi) (B Pi ) (B Pi ) （3）将重复的极小项，永假式消去（4）将极小项按编码从小到大排序例1.6.4 求P Q R的主析取范式定理1.6.5 在真值表中，一个公式的真值为T的指派所对应的极小项的析取，即为该公式的主析取范式(另一种求解主析取范式的方法)仍以例1.6.4为例主析取范式的应用：判断公式等价，判断公式类型（永真、永假等） 例 求下列各式的主析取范式（1） (PQ) (P R)（2） P Q R（3） (PQ) R定义1.6.5 在含有n个命题变元P1，P2，Pn的简单析取式中，若每个命题变元或其否定不同时存在，但

24、二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列，这样的简单析取式称为极大项。同样含有n个命题变量共有2n个极大项P36列出了含有P,Q,R三个变量的所有极大项使得赋值为F的二进制数编码1.6.4 主合取范式主合取范式 性质性质：（1）指派与编码同，则真值为F;（2）任两个不同极大项析取式为永真；（3）全体极大项合取为永假定义定义1.6.4 在含有n个命题变量的命题公式A中，若A的合取范式中的简单析取式均为极大项，则称该合取范式为主合取范式进一步求例例1.6.3的主合取范式定理定理1.6.4 任何命题公式的主合取范式都是存在的且

25、是唯一的。 求主合取范式步骤：（1）求A的合取范式A（2）若A中某些简单析取式B中不含Pi或Pi，则将B展成：BBFB (Pi Pi) (B Pi ) (BPi ) （3）将重复的命题变量，永真式或极大项都消去（4）将极大项按编码从小到大排序求例1.6.4 中公式的主合取范式主合取范式同样可用真值表法来求解（自学）比较例题可发现：主合取范式中未包含的编码对应的极小项组合在一起即构成主析取范式 例1.6.5 求(P (QR)( P ( Q R) 的主析取范式和主合取范式1.7 推理理论 推理从前提推出结论的过程 前提已知的命题公式 结论从前提出发运用推理规则所推出的命题公式 定义1.7.1 设A,B为两个命题公式，当且仅当AB为永真式时，即AB，称B为A的有效结论，或称B可由A逻辑推出n个前提的情况： (H1H2Hn)C 称C是H1,H2,Hn的有效结论推理方法有：（1）真值表法；（2）直接证法; （