离散数学1.1-1.4
- 格式：doc
- 大小：226.00 KB
- 文档页数：16
第1章命题逻辑数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科。
这里所指的数学方法就是引进一套符号体系的方法。
所以数理逻辑又称符号逻辑，它是从量的侧面来研究思维规律的。
计算机及计算机科学与数理逻辑有着十分密切的关系。
人们说数字电子计算机是数理逻辑与电子学结合的产物，这话不假。
现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。
本课程介绍的是数理逻辑最基本的内容，也是与计算机科学关系最为密切的：命题逻辑和谓词逻辑（一阶逻辑）1.1 命题符号化及联结词1.1.1 命题及其表示法命题：能判断真假的陈述句。
真值：一个命题总具有一个“值”，即“真”（用T或1表示）或“假”（用F或0表示），称为真值。
一切没有判断内容的句子，无所谓是非的句子，如感叹句、疑问句、祈使句等都不是命题。
例1：（1）2是素数（2）雪是黑色的（3）2+3=5（4）明年十月一日是晴天。
（5）这朵花多好看呀！（6）明天下午有会吗？（7）请关上门！（8）x+y>5（9）地球外的星球上也有人。
（10）我学英语，或者我学日语。
判断的关键：1.是否是陈述句；2.真值是否是唯一的。
简单命题（原子命题）：不能分解为更简单的陈述句。
复合命题：由联结词、标点符号把几个原子命题联结起来的命题。
表示法：一个符号表示的是命题常项还是命题变项由上下文决定。
1.1.2 联结词（也称真值联结词或逻辑联结词或逻辑运算符）p,q为两个命题否定非p(p的否定) ⌝p p为假 1合取p并且q(p和q)p∧q∧p与q同时为真 2 既…又…,不仅…而析取P或q p∨q∨p与q至少一个为真 3 相容或蕴涵如果p则q p→q→⌝(P为真且q为假) 4 只要p就q，p仅当等价P当且仅当q p↔q↔p，q真值相同 5将复合命题符号化的步骤是1）分析出简单命题，符号化2）用联结词联结简单命题例2：将下列各命题符号化（1）3不是偶数（2）李平即聪明又用功（3）李平虽然聪明，但不用功（4）李平不但聪明，而且用功（5）李平不是不聪明，而是不用功（6）李文与李武是兄弟（7）王燕学过法语或英语（8）派小王和小李中的一人去开会（9）只要不下雨，我就骑自行车上班（除非下雨，否则我就骑自行车上班）（10）只有不下雨，我才骑自行车上班（如果下雨，我是不骑自行车上班）（11）若2+2=4，则太阳从东方升起（12）若2+2≠4，则太阳从东方升起（13）若2+2=4，则太阳从西方升起（14）若2+2≠4，则太阳从西方升起（15）燕子飞回南方，春天来了。
（分析真值）（16）2+2=4当且仅当3不是奇数（分析真值）（17）小王是游泳冠军或百米赛跑冠军（18）小王现在在宿舍或图书馆里（19）选小王或小李中的一人当班长（20）如果我上街，我就去书店看看，除非我很累（21）王一乐是计算机系的学生，他生于1968或1969年，他是三好学生（22）一个人起初说“占据空间的，有质量的而且不断变化的叫做物质”；后来他改说“占据空间的有质量的叫做物质，而物质是不断变化的”。
解：p：它占据空间r：它不断变化q：它有质量s：它是物质提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词1.2 命题公式及分类命题公式：由命题常项或命题变项组成的复合命题形式。
合式公式：（1）单个命题常项或变项p,q,r,…,p i,q i,r i,…，0，1是合式公式；（2）如果A是合式公式，则（⌝A）也是合式公式；（3）如果A，B是合式公式，则（A∧B），（A∨B），（A→B），（A↔B）也是合式公式（4）只有有限次地应用（1）—（3）组成的符号串才是合式公式合式公式也称命题公式或公式。
例3：（1）⌝（p∨q）; p→（p→q）; （p∧q）↔r（2）pq→r ; ⌝p∨q）→r ; （（⌝p→q）→（q→p））)命题公式的层次的定义：（1）若A是单个命题（常项或变项），p,q,r,…,p i,q i,r i,…，0，1，则称A是0层公式。
（2）称A是n+1(n≥0)层公式是指A符合下列情况之一：①A=⌝B,B是n层公式；②A= B∧C，其中B，C分别为i层和j层公式，且n=max(i,j);③A= B∨C，其中B，C的层次同②④A= B→C，其中B，C的层次同②⑤A= B↔C，其中B，C的层次同②（3）若A的最高层次为k，则称A是k层公式例4：⌝(⌝p∧q) →(r∨s)对一个公式的解释和赋值定义如下：’设A为一个命题公式，p1, p2,…，p n为出现在A中的所有的命题变项。
给p1, p2,…，p n指定一组真值，称为对A的一个赋值或解释。
若指定的一组值使A的值为真，则称这组值为A的成真赋值，若使A的值为假，则称这组值为A的成假赋值。
例：公式A=p∧q→r，110是A的一个赋值，即另p=1,q=1,r=0,110是一个成假赋值；那么111，011，010是A的成真赋值。
含n个命题变项的命题公式，共有2n组赋值。
将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表。
构造真值表的步骤：（1）找出命题公式中所含的所有命题变项，列出所有可能赋值（2）从低到高写出各层次（3）计算命题公式的值例5：（1）基本真值表（2）例2中的（15）设A为一个命题公式（1）若A在它的各种赋值下取值为真，则称A为重言式或永真式（2）若A在它的各种赋值下取值为假，则称A为矛盾式或永假式（3）若A至少存在一组赋值是成真赋值，则称A为可满足式重言式是可满足式，但可满足式不一定是重言式提示：判断命题公式类型的方法之一是真值表。
1.3 等值演算n个命题变项只能生成n22个真值不同的命题公式设A,B为两个命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A⇔BA⇔B不是命题公式可通过判断A与B的真值表是否相同，来判断A与B是否等值。
24个重要的等值式：⌝∧∨→↔⇔根据已知的等值式，推演出另外一些等值式的过程称为等值演算。
置换定理：设φ(A)是含命题公式A的命题公式，φ(B)是用命题公式B置换了φ(A)中的A之后得到的命题公式。
如果A⇔B，则φ(A)⇔φ(B)。
等值演算的用途：（1）验证两个公式等值（2）判别命题公式的类型（3）解决实际问题例6：用途1p→(q→r)⇔(p∧q) →r解：p→(q→r)⇔⌝p∨(q→r) （蕴涵等值式）⇔⌝p∨(⌝q∨r) （蕴涵等值式）⇔(⌝p∨⌝q)∨r (结合律)⇔⌝(p∧q)∨r (德·摩根律)⇔(p∧q) →r（蕴涵等值式）例7：用途2(1)q∨⌝((⌝p∨q) ∧p)(2)(p∨⌝p) →((q∧⌝q) ∧r)(3)(p→q) ∧⌝p例8：用途3A,B,C,D 4人做百米竞赛，观众甲、乙、丙预报比赛的名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试问实际名次如何（无并列者）？解：p i,q i,r i,s i表示A,B,C,D第i名，i=1,2,3,4①(r1∧⌝q2) ∨(⌝r1∧q2) ⇔1②(r2∧⌝s3) ∨(⌝r2∧s3) ⇔1③(p2∧⌝s4) ∨(⌝p2∧s4) ⇔1①∧②⇔1 C不能既第一又第二，B和C不能都第二，所以④(r1∧⌝q2∧⌝r2∧s3) ∨(⌝r1∧q2⌝r2∧s3) ⇔1③∧④⇔1 A，B不能同时第二，D不能第三又第四，所以1⇔p2∧⌝s4∧r1∧⌝q2∧⌝r2∧s3所以C第一，A第二，D第三，B第四。
作业：p30-32 1.4 1.5 1.6 1.7 1.8 1.10(4)1.4 联结词全功能集p,q为两个命题排斥或/异或p,q之间恰有一个成立p∨q∨p,q中恰有一个为真(p∧⌝q) ∨(⌝p∧q)与非P与q的否定p↑q↑p，q不同时为真⌝(p∧q)或非P或q的否定p↓q↓p,q同时为假⌝(p∨q)性质：（1）A∨B⇔B∨A（2）(A∨B)∨C⇔A∨(B∨C)（3）A∧(B∨C)⇔(A∧B)∨(A∧C)（4）A∨B⇔(A∧⌝B) ∨(⌝A∧B)（5）A∨B⇔⌝(A↔B)（6）A∨A⇔F, F∨B⇔B, T∨B⇔⌝B（7）A↑A⇔⌝A（8）A∧B⇔(A↑B)↑(A↑B)（9）A∨B⇔(A↑A)↑(B↑B)（10）A↓A⇔⌝A（11）A∨B ⇔(A↓B)↓(A↓B)（12）A∧B⇔(A↓A)↓(B↓B)一个n(n≥1)维卡氏积{0,1}n到{0,1}的函数称为一个n元真值函数。
设F是一个n元真值函数，则可记为F：{0,1}n→{0,1}（n个命题变项只能生成n22个真值不同的命题公式——见1.3节）n个命题变元共可以生成n22个不同的真值函数，每个真值函数可以对应无穷多个命题公式，它们彼此都是等值的。
在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。
例1：{⌝,∧,∨,→,↔}若任一真值函数都可以用仅含某一联结词集中的联结词的命题公式表示，则称该联结词集为全功能集。
若一个联结词的全功能集中不含冗余的联结词，则称它是极小全功能集。
例2：用下列联结词中的联结词写出F的一个命题公式{⌝,→}；{⌝,∧} ；{⌝,∨} ；{↑}；{↓}例3：若已知{⌝,→}是全功能集，证明{⌝,∨}也是全功能集。
证明由于{⌝,→}是全功能集，因而任一真值函数均可仅由含{⌝,→}中的联结词的命题公式表示。
而对于任意的命题形式，A，B，有A→B⇔⌝A∨B因而任一个真值函数均可由含{⌝,∨}中的联结词的命题公式表示，所以它是全功能集。
⌝∧∨→↔⇔(((())))。
