离散数学（第二版） 课件 邹丽娜 2.1-2.2命题逻辑

离散数学第2章命题逻辑2.1命题与联结词目录2.2命题公式及其赋值2.3等值演算2.4范式2.5命题逻辑推理2.1命题与联结词逻辑逻辑学三段论归纳法演绎逻辑数理逻辑命题逻辑集合论谓词逻辑递归论经典命题逻辑非经典命题逻辑2.1命题与联结词命题：是由形式语言描述的。形式语言：不属于自然语言，严谨的语法规则。例如：民间算命(诡辩)：父在母先亡。我的车没锁(?)这张照片里有小明和小刚的爸爸（?）张三告诉李四他英语考试挂了(?)

2.1命题与联结词命题：是由形式语言描述的。形式语言：不属于自然语言，严谨的语法规则。例如：民间算命(诡辩)：父在母先亡。我的车没锁(?)这张照片里有小明和小刚的爸爸（?）张三告诉李四他英语考试挂了(?)

父在，母先亡

我得车没配备锁这张照片里有小明，还有小刚的爸爸张三告诉李四，李四英语考试挂了

2.2命题及命题联结词定义2.1

能够判断真假的陈述句称为命题。例2.1

请问下列语句中哪些是命题？哪些不是命题？北京是中国的首都。

5-2＝10.C语言是一种计算机程序设计语言。如果温度达到零度以下，则水会结成冰。鸟会飞，但鸡不会飞。猪八戒是猪么？香格里拉真是太美丽了！杨七是高个子。关键：陈述句、有唯一的真值每个命题的真假称为命题的“真值”。可表示为真、假或T、F或1、02.2命题及命题联结词定义2.1

能够判断真假的陈述句称为命题。例2.1

请问下列语句中哪些是命题？哪些不是命题？北京是中国的首都。

5-2＝10.C语言是一种计算机程序设计语言。如果温度达到零度以下，则水会结成冰。鸟会飞，但鸡不会飞。猪八戒是猪么？香格里拉真是太美丽了！杨七是高个子。关键：陈述句、有唯一的真值每个命题的真假称为命题的“真值”。可表示为真、假或T、F或1、0√√√√×××√理解“命题”概念应注意的问题情境(时间和地点)、判断技术、判断能力。

2025年1月1日是晴天

2050年是世界末日火星上有生命

理解“命题”概念应注意的问题情境(时间和地点)、判断技术、判断能力。

2019年1月1日是晴天

2019年是世界末日火星上有生命

以上3个都是命题。

悖论：不属于命题（特殊）例如：我正在说假话

说谎实话实话说谎悖论故事在萨维尔村，理发师挂出一块招牌：“我只给村里所有那些不给自己理发的人理发。”有人问他：“你给不给自己理发？”理发师顿时无言以对。悖论故事国王要处死一些囚犯，但处死之前允许他们说一句话，说假话就绞刑，说真话就砍头，有一人说：我将要被绞刑。命题的真值每个命题的真假称之为命题的“真值”。真值可以表示为（真、假）（T、F）（1、0）例如：

（1）8是素数。（2）

是无理数。真值为1真值为0

命题命题凡是能分辨其真假的语句叫做命题。该命题可以取一个“值”，称为真值。只有“真”和“假”两种只有陈述句才可能是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论不是命题陈述句的判断结果不惟一确定的不是命题命题的真值可随时间、环境、人物的不同而不同

（1）

4为素数。练习，判断下列句子是否为命题（8）

这朵花真美丽啊！（7）

请不要吸烟！（6）

π大于吗？（5）

2050年元旦是晴天。（4）

火星上有水。（3）

x

大于y,其中x和y是任意的两个数。（2）

是无理数。√√√√××××假命题真命题简单命题与复合命题简单命题（原子命题）：命题不能再分解猪八戒是猪z孙悟空是神仙s唐僧是神仙t唐僧取回真经q复合命题：由命题联结词和其他命题组成的命题

例如：∧∨﹁—><—>猪八戒不是猪﹁z

孙悟空和唐僧都是神仙、s∧t

如果唐僧取回真经，就会是神仙q->t

命题连接词----否定联结词设p是一个命题，则

p

也是一个命题，读作“非”，表示命题的否定

p

p0110否定联结词是一个一元运算．例如p：上海是沿海城市．

p

：上海不是沿海城市．命题连接词----合取联结词设p，q为二命题，复合命题“p并且q”称为p与q的合取式，记作p

q，读成“p合取q”

全真即为真：p

q为真当且仅当p与q同时为真。pqp

q001101010001例如：

p：2

2=5

q：雪是黑的．

p

q：2

2=5并且雪是黑的．命题连接词----析取联结词设p，q为二命题，复合命题“p或q”称为p、q的析取式，记作

p

q

，读成“p析取q”

全假即为假：p

q为真，当且仅当p与q中至少一个为真．pqp

q001101010111例如：r：今天下雨s：今天刮风r

s：今天下雨或者刮风设p，q都是命题，则p

q也是一个命题，称为蕴涵式，读作“如果p，则q”；p称为前件，q称为后件。p

q为假，当且仅当p真q假．命题连接词----蕴涵联结词pqp

q11

001001

1011P：明天晴q：我请你吃饭p

q如果明天晴,则我请你吃饭守承诺没守承诺“善意推定”天若有情天亦老p

q这是一个前件为假的命题，是永真式。命题连接词----等价联结词设p，q都是命题，则p↔q也是一个命题，称为与的等价式，读作“p与q同真假”或“p与q等价”；pqp↔q001101011001例如：u：燕子飞回北方v：春天来了u↔v：燕子飞回北方春天来了．命题联结词联结词记号记法真值结果否定┐┐p┐p为真当且仅当P为假合取∧p∧q全真即为真析取∨p∨q全假即为假蕴涵→p

→q满足条件却不守承诺：p为真q为假结果为假。等价↔p

↔

q相同为真，不同为假总结2.1.3用命题公式描述实际问题例2.7用命题公式表示下列命题：(1)李明这学期选修了三门计算机课和一门英语课。用命题公式表示实际问题—步骤：

1.找原子命题，用符号p,q,r,s等表示。

2.找命题间的关系。2.1.3用命题公式描述实际问题(2)李明这学期选修了数据库原理、数据结构、离散数学和英语四门课。2.1.3用命题公式描述实际问题(3)如果明天不下雨，我就上街买书。 注意问题：（1）不必关心命题是真的还是假的（2）也不必分析命题是否有实用意义（3）也不必关系命题之间是否有联系。例如:

（1）若2+2=4，则地球是运动的（2）有外星人存在，当且仅当雪是黑的2.1.3用命题公式描述实际问题命题联结词说明：联结词与自然语言之间的对应并非一一对应联结词自然语言┐否定：不、非、没、无、否等∧并存：并且、也、不但…而且…、既…又…、不仅…而且…、虽然…但是…等等，逗号“，”

选择性：“或者…或者…”、“可能…也可能…”、“要么…要么…”、“不是…就是…”等→充分：如果…，则…、只要…就…、有…就…、一旦…就…；必要：只有…才…、除非…才↔等价、当且仅当、充分必要、相同、相等、一样、等同等等；命题联结词∧查理不是没有钱，而是不想买汽车。.布朗和卡特都是大学生。是简单命题，可表示为p

布朗和卡特是大学同学。（1）张晓静爱唱歌或爱听音乐。（2）张晓静可以挑选202房或203房。（3）张晓静只能挑选202房或只能挑选203房。（1）令p:张晓静爱唱歌；q:张晓静爱听音乐，则：p∨q（2）令r:张晓静住202房；s:张晓静住203房，则:r∨s（3）令r:张晓静住202房；s:张晓静住203房，则:(r∧┐s)∨(┐r∧s)命题联结词∨【与

对应的词语】充分条件：如果…则…、只要…就…、一旦…就…

必要条件：只有…才…、除非…才…、除非…否则不…

(1)如果天下雨，他就乘公共汽车上班(2)只要天下雨，他就乘公共汽车上班(3)只有天下雨，他才乘公共汽车上班(4)除非天下雨，否则他不乘公共汽车上班u：天下雨,v：他乘公共汽车上班

(1)u

v(2)u

v

(3)v

u(¬u

¬v),

(4)v

u(¬u

¬v)p

q¬p

¬qq

p【与↔对应的词语】汉语中表示同真同假判断的联结词有：当且仅当、充分必要条件等。命题联结词符号化下列命题蓝色和黄色可以调配成绿色蓝色黄色都是常用颜色李平是山西人或陕西人李冰只能选学英语或只能选学法语种瓜得瓜，种豆得豆明天不是雨夹雪我就去上学明天不下雨也不下雪我则去上学符号化下列命题蓝色和黄色可以调配成绿色蓝色黄色都是常用颜色李平是山西人或陕西人李冰只能选学英语或只能选学法语种瓜得瓜，种豆得豆明天不是雨夹雪我就去上学明天不下雨也不下雪我则去上学pp∧qp∨q(p∧┐q)∨(┐p∧q)(p

q)∧(r

s)(¬p

¬q)→r¬(p

q)→

r习题，拍照反馈到学习通讨论区4-6题提问:符号化下列命题提问:符号化下列命题¬p

¬qr¬p→¬q¬p→¬qp↔qp

qp

q

r

sp→

q(p→

r)(q→¬r)提问:符号化下列命题提问:符号化下列命题2.2命题公式及其赋值【形式系统】

用形式语言描述的系统称为形式系统（或称符号系统）。形式语言中的语句是由一些事先选定的符号（主要是数学符号）按严格的语法规则构成的字符串。【命题逻辑】一个形式系统，用于描述命题逻辑的语言是一种形式语言，这种形式语言有其自身特有的符号及语法规则。命题常项与命题变元一个有确定真值的命题称为一个命题常项。真假确定，常用a,b,c等表示例如：“2+2=4”是一个命题常项，它的值是1“雪是黑色的”是一个命题常项，它的值是0命题变元是真值可以变化的陈述句。常用p，q，r等表示．命题变元赋值前不是命题，赋值后才为命题。例如：有命题集合A={他吃饭，他睡觉，他跑步}命题变元p在A范围内取值，比如p取值为“他吃饭”合式公式定义2.5命题逻辑中合法的命题结构称为合式公式，或命题公式,简称公式。合式公式归纳定义如下：(1)单个命题常项或变元是公式；(2)如果A是公式，则﹁A也是公式;(3)若A,B是公式，则(A∧B)

，(A∨B)，(A→B)，(A↔B)都是公式；(4)所有的公式都是有限次应用(1)～(3)而产生的，除此之外，没有别的公式。合式公式例：设A,B,C,D都是公式，请问下列符号串中哪些是合式公式？哪些不是合式公式？合式公式√×√√××例：设A,B,C,D都是公式，请问下列符号串中哪些是合式公式？哪些不是合式公式？联结词的优先级顺序

联结词符的优先级顺序:(1)括号(2)¬(3)

(4)

↔公式简写法则：公式最外层括号可以省略（

A）的括号可以省略根据运算符优先级省略括号省略括号不能影响公式解释联结词的优先级顺序不同级的计算直接可以省略括号（p

q）->rp

q->r原则上，同级的计算直接必须加上括号p

q

r(p

q)

r或(p

q)

rp->q->r(p->q)->r或p->(q->r)p↔q↔r(p↔q)↔r或p↔(q↔r)但都是、、¬，可以省略括号p

q

rp

q

r¬¬¬q

合式公式的树状展开

(AB)((C)(DC))ABA

B(C)(DC)(C)DCCDC

子公式（子式）子公式（子式）例2.175678ABCD提交40页8：写出子公式个数。单选题1分练习w

q

r

¬q

w

q(w

q)r40页8：写出子公式个数。公式的层次【公式的层次】定义2.7：设A是一合式公式，则定义：

１）若公式A是单个的命题变元，则称A为0层合式。２）称公式Ａ是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)。３）若公式Ａ的层次为k，则称A是k层公式。公式的层次例2.181234ABCD提交习题40页9：指出下列公式的层数单选题1分1234ABCD提交习题40页9：指出下列公式的层数单选题1分1234ABCD提交习题40页9：指出下列公式的层数单选题1分4层3层4层公式的层次习题40页9：指出下列公式的层数公式的赋值命题有真假值，命题公式也有真假值，它的真假值由命题变元的真假值所决定。命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成ｙ(命题公式)＝ｆ(x)，(x为命题变元)例子：公式pqr真值为T的解释p:3是奇数；q:7是奇数；r:3乘7是奇数真值为F的解释p:3是奇数；q:7是奇数；r:3乘7是偶数公式的赋值定义2.10：设命题公式Ａ中有n个不同的命题变元p1,…pn,n为正整数。该变元组的任意一组确定的值(α1,…αn)称为对Ａ的一个赋值。凡使命题公式Ａ取真的赋值称为Ａ的成真赋值。凡使命题公式Ａ取假的赋值称为Ａ的成假赋值。含n个命题变元的公式共有2n个不同的赋值。pq¬（（p∨q）

p）001011100110公式的真值表及其构造命题公式的真值表:公式A在所有赋值情况列成表。步骤如下：

1）找出公式中所含的全体命题变元并列出所有赋值。

2）按从低到高的顺序写出公式的各个层次。

3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。pqp∨q（p∨q）

p¬（（p∨q）

p）00001011011011011110例．构造命题公式¬((p∨q）

p)的真值表：可满足式:若A至少存在一组赋值使的真值为1。例题：重言式(永真式):A的每一组赋值都使A的真值为1例2-19写出下列公式的真值表(***)(p->¬q)v(r↔q)pqr¬qp->¬q

r↔q(p->¬q)vr↔q)00011110011101010010101101111001111101110111000001110011命题公式的分类定义2.12设A是一个命题公式:重言式(永真式):A的每一组赋值都使A的真值为1；矛盾式(永假式):A的每一组赋值都使A的真值为0；可满足式:若A至少存在一组赋值使的真值为1。命题公式的分类重言式重言式可满足式例2.20命题公式的分类矛盾式可满足式000为一组成真赋值100为一组成假赋值例构造公式¬(p→q)q

r的真值表pqr

p→q¬(p→q)¬(p→q)q¬(p→q)q

r0000111100110011010101011111001100001100000000000000