离散数学：第1章 命题逻辑基本概念

离散数学教材及参考书教材：

离散数学：屈婉玲，耿素云，张立昂，高等教育出版社参考书：

离散数学（第4版）：RichardJohnsonBaugh，电子工业出版社

离散数学：左孝凌，李为鑑，刘永才，上海科学技术文献出版社

离散数学及其应用（第6版）：KennethH.Rosen，机械工业出版社2计算机科学与工程学院绪论：课程安排讲授内容：数理逻辑（第一、二、三、四、五章）集合论（第六、七、八章）代数结构（第九、十章）成绩构成：

平时（作业、考勤）＋期末（无半期考试）

随机点名，三次没到者无成绩作业：

每周三交作业3计算机科学与工程学院绪论：什么是离散数学研究离散量的结构及相互关系的数学科学离散结构：集合、关系、图等

离散量是指分散开来的、不存在中间值的量研究对象:有限或可数个元素自然数、整数，真假值，有限节点等计算机技术的支撑科学：计算机只能处理离散的或离散化了的数量关系4计算机科学与工程学院绪论：学习意义

E.W.Dijkstra（荷兰计算机科学家，提出了程序设计中常用的GOTO语句的三大危害；解决有向图中最短路径问题的Dijkstra算法）：

我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻二十岁的话，就要回去学逻辑。

学科意义：计算机科学技术的基础和工具5计算机科学与工程学院绪论：离散数学与计算机科学数据结构基础离散结构数据库原理软件工程操作系统编译原理人工智能可计算性理论……6计算机科学与工程学院绪论：数理逻辑逻辑学分类辩证逻辑：是研究事物发展的客观规律形式逻辑：是研究思维的概念、判断和推理的问题数理逻辑（又称符号逻辑）数学方法研究形式逻辑的一门科学，使用符号数理逻辑创始人——莱布尼兹(Leibniz,1646-1716,德)现代数理逻辑：公理化集合论、模型论、递归函数论、证明论最基本组成内容：命题演算、谓词演算应用：逻辑电路、自动控制、人工智能等7计算机科学与工程学院第一部分数理逻辑■主要内容命题逻辑基本概念

命题逻辑等值演算命题逻辑推理理论一阶逻辑基本概念一阶逻辑等值演算与推理8计算机科学与工程学院第1章命题逻辑基本概念命题与联结词命题及其分类联结词与复合命题命题公式及其赋值1.1命题与联接词命题：具有唯一真值陈述句

唯一性：或真或假但不能两者都是的命题所用符号：常用小写26个英文字母例子十是整数2100年人类将在月球生活x=3现在是几点？1+1=2我现在说假话悖论！10计算机科学与工程学院1.1命题与联接词判断下列语句是否为命题明天下雨加拿大是一个国家x+y>4注：命题是陈述句，陈述句不一定是命题命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定11计算机科学与工程学院1.1命题与联接词命题分类简单命题：不能被分解成更简单的陈述句复合命题：简单陈述句+联接词例子今天没有天晴王华的成绩很好并且品德很好小李是学数学或者计算机科学如果天下雨，那么地下湿12计算机科学与工程学院1.1命题与联接词否定联接词符号¬,读作“非”，“否定”定义：命题p

p的否定式：复合命题“p的否定”（“非p”）符号：

p

(符号称作否定联结词)

p为真当且仅当p为假例子今天没有天晴

p

p

：今天天晴ppTFFT13计算机科学与工程学院1.1命题与联接词合取联接词符号,读作“合取”定义：命题p，q

p与q的合取式：复合命题“p并且q”

符号：pq(符号称作合取联结词)

pq为真当且仅当p和q同时为真例子王华的成绩很好并且品德很好pqp：王华的成绩很好q：王华的品德很好pqpqFFFFTFTFFTTT14计算机科学与工程学院1.1命题与联接词析取联接词符号,读作“析取”定义：命题p，q

p与q的析取式：复合命题“p或q”

符号：pq(符号称作析取联结词)

pq为假当且仅当p和q同时为假例子小李是学数学或者计算机科学pqp：小李是学数学q：小李是学计算机科学pqpqFFFFTTTFTTTT15计算机科学与工程学院1.1命题与联接词析取联接词（相容或）≠“排斥或”排斥或：符号定义：命题p，q符号：pq等价于(pq)(pq)

pq为假当且仅当p和q同时为假或同时为真例子：小李在教室看书或在图书馆上网

小李在看书或者听音乐（析取）pqpqFFFFTTTFTTTF16计算机科学与工程学院1.1命题与联接词蕴含联接词符号,读作“如果…则…”、“蕴含”定义：命题p，q

p与q的蕴涵式：复合命题“如果p，则q”符号：pq(符号称作蕴含联结词)

pq为假当且仅当p为真，q为假例子

如果天下雨，那么地下湿

pqp：天下雨q：地下湿pqpqFFTFTTTFFTTT17计算机科学与工程学院1.1命题与联接词更多关于蕴含联接词…pq：q是p的必要条件其他：pq的叙述方式：“只要p，就q”，“因为p，所以q”等

p为假，pq永远为真如果给我一个支点，我能把

地球撬起来

区别于自然语言的“如果p,则q”p和q有内在联系pqpqFFTFTTTFFTTT18计算机科学与工程学院1.1命题与联接词更多例子如果天晴，则雪是白的

pq如果不天晴，则雪不是白的

pq（对给定正整数a）只要a能被4整除，则a能被2整除

pq19计算机科学与工程学院1.1命题与联接词给定命题pq它的逆命题qp它的反命题

pq它的逆反命题

qp各种命题关系

pq

qp

qppq20计算机科学与工程学院1.1命题与联接词等价式符号,读作“当且仅当”定义：命题p，qp与q的等价式：复合命题“p当且仅当q”符号：pq(符号称作等价联结词)pq为真当且仅当p与q真值相同例子

当且仅当a=2，才有a2=4pqp：a=2q：a2=4pqpqFFTFTFTFFTTT21计算机科学与工程学院1.1命题与联接词联接词的定义总结pqppqpqpqpqFFTFFTTFTTFTTFTFFFTFFTTFTTTT22计算机科学与工程学院1.1命题与联接词联接词的优先级

、、、、括号最优先同一优先级：从左到右例子：求于命题pqr含义相同的命题((p)q)r((pq))rp(qr)(pqr)23计算机科学与工程学院1.1命题与联接词例：p：北京比天津人口多q：2＋2＝4r：乌鸦是白色的求下列命题真值((¬p∧q)∨(p∧¬q))→r(q∨r)→(p→¬r)(¬p∨r)(p∧¬r)

TTF24计算机科学与工程学院1.1命题与联接词例子：符号化下面命题小强虽然不聪明，但很用功小李学过英语或者法语小李正在教室看书或在图书馆上网金无足赤，人无完人得道多助，失道寡助pqpq(pq)(pq)pq(pq)(pq)25计算机科学与工程学院1.1命题与联接词问题1：区别

x+y>4

明天下雨26计算机科学与工程学院1.1命题与联接词问题2：得道多助，失道寡助(pq)(pq)27计算机科学与工程学院1.1命题与联接词课堂练习：p：2+3=5q：大熊猫产在中国r：太阳从西部升起求下列命题真值

(r(pq))(pr)FFFTTTFF28计算机科学与工程学院1.2命题公式及其赋值

命题常项：简单命题

命题变项：表示命题的变量真值可以变化的陈述句命题变项不是命题命题变项用确定命题代入才能确定真值命题变项所用符号：常用小写26个英文字母命题变量不同于代数式的变量x+y>4的x，y不是命题变量29计算机科学与工程学院1.2命题公式及其赋值合式公式（命题公式）的递归定义：单个命题常项或命题变项是合式公式（原子命题公式）

A为合式公式，则A是合式公式

A，B为合式公式，则(AB),(AB),

(AB),(AB)为合式公式4.有限次应用1-3形成的字符串为合式公式

子公式B：给定合式公式AB是A的一部分B是合式公式30计算机科学与工程学院1.2命题公式及其赋值符号说明大写字母A，B表示合式公式公式简写法则：公式最外层括号可以省略（A）的括号可以省略根据运算符优先级省略括号

省略括号不能影响公式解释31计算机科学与工程学院1.2命题公式及其赋值合式公式的树状展开

(AB)((C)(DC))ABAB(C)(DC)(C)DCCDC32计算机科学与工程学院1.2命题公式及其赋值例子(AB)C(pq)(qr)(B)pqr33计算机科学与工程学院1.2命题公式及其赋值公式层次若公式A是单个的命题变元，则称A为0层合式称公式Ａ是n+1(n≥0)层公式是指下面情况之一A＝¬B，B是n层公式A＝BΛC，其中B，C分别为i层和j层公式，且n＝max(i,j)A＝B∨C，其中B，C的层次及n同(b)A＝B

C，其中B，C的层次及n同(b)A＝B

↔

C，其中B，C的层次及n同(b)若公式Ａ的层次为k，则称A是k层公式层次≠联接词数34计算机科学与工程学院1.2命题公式及其赋值例子：p,q,r,s为命题变元((pq)r)s(pq)(qr)(pqr)s

(pqr)43535计算机科学与工程学院1.2命题公式及其赋值命题公式的真值命题变项的常量化：常项替换（解释）例子：公式pqr真值为T的解释p:3是奇数；q:7是奇数；r:3乘7是奇数真值为F的解释p:3是奇数；q:7是奇数；r:3乘7是偶数赋值命题变项赋真命题命题变项的真值为T命题变项赋假命题命题变项的真值为F36计算机科学与工程学院1.2命题公式及其赋值命题变项赋值A中命题变项：p1,…pn对p1,…pn赋值v：v(pi)=i，i{T,F}对A的真值递归定义v(B)=Tiffv(B)=Fv(BC)=Tiffv(B)=v(C)=Tv(BC)=Fiffv(B)=v(C)=Fv(BC)=Fiffv(B)=T，v(C)=Fv(BC)=Tiffv(B)=v(C)赋值（解释）简写：12…,nn个变项的公式，共有2n个不同赋值37计算机科学与工程学院1.2命题公式及其赋值命题变项赋值成真赋值：v(A)=T成假赋值：v(A)=F例子：公式(pq)rFFF(p=F,q=F,r=F)TFF?(pq)rFFF38计算机科学与工程学院1.2命题公式及其赋值

真值表：A所有赋值列成表真值表构造：找出A中命题变项：p1,…pn列出2n个赋值（2进制加法形式）从高到低写成公式各个层次各个赋值：计算各层的真值39计算机科学与工程学院1.2命题公式及其赋值pqpq(pq)p¬((pq)p)FFFFTFTTFTTFTTFTTTTF例¬((pq)p)40计算机科学与工程学院1.2命题公式及其赋值pqrqrp(qr)FFFFFFFTFFFTFFFFTTTTTFFFTTFTFTTTFFTTTTTT例p(qr)41计算机科学与工程学院1.2命题公式及其赋值p

q¬p¬qp

↔

qpq¬p¬q公式FFTTTTTFTTFFFTTFFTFFTTTFFTTT例(p

↔

q)

↔(pq¬p¬q)42计算机科学与工程学院1.2命题公式及其赋值命题公式分类：A重言式(永真式)：v(A)=T，对任意v矛盾式(永假式)：v(A)=F，对任意v可满足式：v(A)=T，对某个v关系重言式是可满足式，反之不一定成立真值判断法重言式：真值表最后一列全为T矛盾式：真值表最后一列全为F可满足式：真值表最后一列至少一个T43计算机科学与工程学院1.2命题公式及其赋值真值表有限性：给定n个命题变项共有22n个真值表例题：下列哪些具有相同真值？pqqp(pq)(pq)p44计算机科学与工程学院1.2命题公式及其赋值p

qpqqp