离散数学

主讲教师：张东主讲教师：张东第一部分数理逻辑第四部分组合数学第三部分代数结构第二部分集合论第五部分图论第六部分初等数论第一部分数理逻辑第一章命题逻辑的基本概念第二章命题逻辑等值式第三章命题逻辑的推理理论第四章一阶逻辑基本概念第五章一阶逻辑等值演算与推理传统逻辑与数理逻辑逻辑一词源于希腊文，意思指：词、思想、理性、规律等。逻辑学研究的是：判别一个推理过程是否正确的标准。数理逻辑也叫符号逻辑，即用人工符号来书写逻辑法则，它是一门涉及数学、逻辑学、哲学等几门学科的横向交叉学科。传统逻辑用以表示命题形式和推理形式的是自然语言的某些词语，而自然语言是多义的，不适于用以精确地表示各种命题形式和推理形式。数理逻辑克服了这方面的局限性，以其特有的人工符号来书写逻辑法则，突出体现了方便、精确的优势。学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，一阶谓词逻辑是在它的基础上发展起来的。第一章命题逻辑的基本概念：能判断真假的陈述句。命题作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值都是唯一的。不能分解成更简单命题的称为简单命题或原子命题，例如：“4大于2”。由简单命题通过联结词联结而成的命题，称为复合命题，例如：“4大于2，并且4能被2整除”。1.1命题与联结词例1：判断下列句子是否为命题（1）4是素数。（2）x大于y。（4）2050年元旦是晴天。（5）π大于2吗？（6）请不要吸烟！（7）我正在说假话。←是假命题←不是命题，真假不能确定←是命题，真值目前未知←不是命题，祈使句←不是命题，疑问句←不是命题，是悖论（3）地球是行星。←是真命题判断给定陈述句是否为命题，关键是判断它是否有唯一的（客观存在的）真值。命题的符号化1、用小写字母p、q、r、s等表示原子命题；2、用“1”表示真，用“0”表示假；3、定义常用的5种逻辑联结词。比如例1中的几个命题可以表示为：p：4是素数。q：地球是行星。r：2050年元旦是晴天。比如上例中，p的真值为0，q的真值为1，r的真值现在还不知道。1、否定联结词“ᆨ”设p为命题，复合命题“非p”称为p的否定式，记作ᆨp，规定ᆨp为真当且仅当p为假。例如：p：2是奇数。ᆨp：2不是奇数。运算定义：pᆨp0110常用的5种逻辑联结词常用的5种逻辑联结词2、合取联结词“∧”设p，q为两个命题，复合命题“p并且q”称为p与q的合取式，记作p∧q，规定p∧q为真当且仅当p与q同时为真。例如：p：张晓静喜欢美术。q：张晓静喜欢音乐。则“p∧q”表示：张晓静喜欢美术和音乐。运算定义：pqp∧q0011010100013、析取联结词“∨”设p，q为两个命题，复合命题“p或q”称为p与q的析取式，记作p∨q，规定p∨q为假当且仅当p与q同时为假。例如：p：张晓静喜欢美术。q：张晓静喜欢音乐。则“p∨q”表示：张晓静喜欢美术或音乐。运算定义：pqp∨q001101010111常用的5种逻辑联结词3、析取联结词“∨”常用的5种逻辑联结词析取联结词“∨”与自然语言中的“或”不完全一样。自然语言重的或具有二义性，用它有时具有相容性（即，它联结的两个命题可以同时为真），有时具有排斥性（即，它联结的两个命题不能同时为真），通常将这两种不同意义的“或”分别称为相容或和排斥或。相容或：排斥或：张晓静喜欢美术或音乐。张晓静只能选202或203中的一个房间。张晓静是江西或安徽人。p：张晓静选202房间q：张晓静选203房间p∨q张晓静只能选202或203中的一个房间。00000110111111103、析取联结词“∨”常用的5种逻辑联结词张晓静只能选202或203中的一个房间。令p：张晓静选202房间，q：张晓静选203房间。能否用p∨q来表示该命题？列表比较符号命题与自然语言命题的真值：10不能表示！001010011011113、析取联结词“∨”常用的5种逻辑联结词令p：张晓静选202房间，q：张晓静选203房间。列表比较符号命题与自然语言命题的真值：pq（p∧ᆨq）∨（ᆨp∧q）张晓静只能选202或203中的一个房间。可以用（p∧ᆨq）∨（ᆨp∧q）来表示该命题。00张晓静只能选202或203中的一个房间。001010011011113、析取联结词“∨”常用的5种逻辑联结词张晓静是江西或安徽人。令p：张晓静是江西人，q：张晓静是安徽人。列表比较符号命题与自然语言命题的真值：能否用p∨q来表示该命题？p：张晓静是江西人q：张晓静是安徽人p∨q张晓静是江西或安徽人。11可以。或相容或排斥或主观排斥客观排斥张晓静喜欢美术或音乐。张晓静只能选202或203中的一个房间。张晓静是江西人或安徽人。其中“相容或”和“客观排斥或”可以用p∨q来表示，“主观排斥或”则用（p∧ᆨq）∨（ᆨp∧q）来表示。常用的5种逻辑联结词3、析取联结词“∨”4、蕴涵联结词“→”运算定义：pqp→q001101011101设p，q为两个命题，复合命题“如果p，则q”称为p与q的蕴涵式，记作p→q，并称p是蕴涵式的前件，q为蕴涵式的后件。规定p→q为假当且仅当p为真且q为假。例如：p：张辉举得起80公斤的杠铃。q：张辉举得起60公斤的杠铃。则“p→q”表示：如果张辉举得起80公斤的杠铃，他就举得起60公斤的杠铃。常用的5种逻辑联结词常用的5种逻辑联结词4、蕴涵联结词“→”在使用联结词→时，要特别注意以下几点：(1)在自然语言里，p→q有许多不同的叙述方式。例如：“只要p，就q”，“因为p，所以q”，“只有q，才p”等，我们对其符号化时要抓住“p→q”的本意，即p是q的充分条件，q是p的必要条件。(2)作为推理“如果p，则q”的形式化，当p为假时，无论q的值如何，p→q的值都应为真。(3)数理逻辑是研究抽象的推理，因此前件p和后件q之间可以没有任何内在的联系。例如允许出现这样的命题：“如果32，则雪是白的。”常用的5种逻辑联结词4、蕴涵联结词“→”例2：将下列命题符号化，并判断它们的真值：（1）如果3+3=6，则雪是白的。（2）只要3+3≠6，雪就不是白的。（3）除非3+3=6，雪才是白的。（4）除非3+3=6，否则雪是白的。（5）只有3+3≠6，雪才是白的。令p：3+3=6，q：雪是白的。则p、q的值都为1.p→q真值为1ᆨp→ᆨq真值为1q→p真值为1ᆨq→p真值为1q→ᆨp真值为05、等价联结词“↔”运算定义：pqp↔q001101011001常用的5种逻辑联结词设p，q为两个命题，复合命题“p当且仅当q”称为p与q的等价式，记作p↔q，规定p↔q为真当且仅当p与q同时为真或同时为假。例如：p：△是等腰三角形。q：△两底角相等。则“p↔q”表示：△是等腰三角形当且仅当△两底角相等。常用的5种逻辑联结词五种逻辑联结词相当于五种逻辑运算符，它们在一起还可以组成更为复杂的复合命题。五种逻辑联结词的运算优顺序为（），ᆨ，∧，∨，→，↔对于同一优先级，按从左到右的顺序进行。例3：求复合命题ᆨp→q→（ᆨp∧r）的真值，其中p，q，r的值都为1。答：计算结果应为0。1.2命题公式及其赋值将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式。简单命题的真值是确定的，又称为命题常项。相应的取值0或1的变元称作命题变项。可以用命题变项表示真值可以变化的陈述句。命题变项不是命题。（1）单个的命题变项和命题常项是合式公式，并称为原子命题公式。（2）若A是合式公式，则ᆨA也是合式公式。（3）若A，B是合式公式，则A∧B，A∨B，A→B，A↔B是合式公式。（4）有限次的应用（1）~（3）形成的符号串是合式公式。合式公式也称为命题公式，简称为公式。思考：命题公式是不是命题？答：不是，命题公式含有命题变项。例如：p∧q是合式公式，ᆨ(p∧q)也是合式公式。而pq→r，p→(q→r等不是合式公式。注：1、这里的大写字母A、B等表示任意合式公式，称为元语言符号（起框架作用）。而p、p∧q等具体的公式称为对象语言符号（可代入框架，构成命题公式）。2、要求有限次的使用5种逻辑联结词。例如：p→p→p→…→p不是合式公式。公式层次的定义（1）若公式A是单个的命题变项，则称A为0层公式。（2）称A是n+1（n≥0）层公式是指下面情况之一：（a）A=ᆨB，B是n层公式；（b）A=B∧C，其中B，C分别为i层和j层公式，且n=max(i,j)；（c）A=B∨C，其中B，C的层次及n同（b）；（d）A=B→C，其中B，C的层次及n同（b）；（e）A=B↔C，其中B，C的层次及n同（b）；（3）若公式A的层次为k，则称A是k层公式。例4：判断ᆨ(p∧ᆨq)∨(r↔(s∧ᆨq))是多少层公式？答：是4层公式。命题公式的解释设p1、p2、p3、…、pn是出现在公式A中的全部命题变项，给p1、p2、p3、…、pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组真值使A为1，则称这组值为A的成真赋值；若使A为0，则称这组值为A的成假赋值。每组赋值按下标或字母表顺序直接列出。例如：对公式(r∧ᆨp)→q赋值001，代表p=0，q=0，r=1。最后计算结果为0，则001是该公式的一个成假赋值。不难看出，含n（n≥1）个命题变项的公式共有2ⁿ个不同的赋值。110100100111真值表将命题公式A在所赋值下取值情况列成表，称作真值表。构造真值表的具体步骤：（1）找出公式中所含的全体命题变项p1、p2、p3、…、pn（若无下标就按字母顺序排列），列出2ⁿ个赋值，赋值从00…0开始，然后按二进制加法依次写出每个赋值，直到11…1为止。（2）按从低到高的顺序写出公式的各个层次。（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。例如，试作出公式ᆨ(p→q)∨q的真值表。pq00011011p→qᆨ(p→q)ᆨ(p→q)∨q例5：请作出合式公式(r→(p∧q))↔ᆨp的真值表，并找出该公式所有的成真赋值。pqr000001010011100101110111p∧qᆨp(r→(p∧q))(r→(p∧q))↔ᆨp00000011111100001010101110100100pqp∧q000000010010100100111111pᆨp0101010110101010rp∧q(r→(p∧q))001100001100001100011111ᆨp(r→(p∧q))(r→(p∧q))↔ᆨp111100111100010001010010pqr(r→(p∧q))↔ᆨp00010010010101101000101111001110该合式公式的成真赋值为：000、010、101如果两个公式A与B的真值表对所有赋值最后一列都相同，则称这两个真值表相同，而不考虑构造真值表的中间过程。例如，下列两个公式的真值表是相同的。pqp→q001011100111pqᆨpᆨp∨q0011011110001101设公式A、B中共含有命题变项p1、p2、p3、…、pn，而A（或B）不全含有这些命题变项，称这些命题变项为A（或B）的哑元。A（或B）的取值与哑元无关，因此在讨论A与B是否有相同的真值表时，可将A、B都看成含p1、p2、p3、…、pn的命题公式。例如，设公式A为p→q，公式B为(p→q)∧(r↔r)，则公式A、B中共含有命题变项p、q、r，其中r是A的哑元。通过真值表，可以确定公式A、B有相同的真值表。pqrp→q(p→q)∧(r↔r)0001100111010110111110000101001101111111根据公式在各种赋值下取值情况，可按下述定义将命题公式进行分类。定义：设A为任意一命题公式。（1）若A在它的各种赋值下取值均为真，则称A是重言式或永真式。（2）若A在它的各种赋值下取值均为假，则称A是矛盾式或永假式。（3）若A不是矛盾式，则称A是可满足式。注：永真式一定是可满足式。例