离散数学第一章命题逻辑知识点总结_离散数学命题逻辑总结

离散数学第一章命题逻辑知识点总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学命题逻辑总结”。

数理逻辑部分

第1章

命题逻辑 1.1 命题符号化及联结词

命题: 判断结果惟一的陈述句

命题的真值: 判断的结果

真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题

注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题与联结词按一定规则复合而成的命题

简单命题符号化

用小写英文字母 p, q, r, … ,pi,qi,ri(i≥1）表示 简单命题

用“1”表示真，用“0”表示假

例如，令 p：

是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1

联结词与复合命题 1.否定式与否定联结词“”

定义 设p为命题，复合命题 “非p”（或 “p的否定”）称

为p的否定式，记作p.符号称作否定联结词，并规定p 为真当且仅当p为假.2.合取式与合取联结词“∧”

定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q.∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真

注意：描述合取式的灵活性与多样性

分清简单命题与复合命题

例 将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解 令

p：王晓用功，q：王晓聪明，则

(1)p∧q

(2)p∧q

(3)p∧q.令 r : 张辉是三好学生，s :王丽是三好学生

(4)r∧s.(5)令 t : 张辉与王丽是同学，t 是简单命题.说明:

(1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”

定义 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q.∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例

将下列命题符号化

(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解 令 p:2是素数, q:3是素数, r:4是素数, s:6是素数,则(1),(2),(3)均为相容或.分别符号化为: p∨r , p∨q, r∨s,它们的真值分别为 1, 1, 0.而(4),(5)为排斥或.令 t :小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为

(t∧u)∨(t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧w)∨(v∧w), 又可符号化为 v∨w , 为什么? 4.蕴涵式与蕴涵联结词“” 定义 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.pq 的逻辑关系：q 为 p 的必要条件

“如果 p，则 q ” 的不同表述法很多：

若 p，就 q

只要 p，就 q

p 仅当 q

只有 q 才 p

除非 q, 才 p 或

除非 q, 否则非 p.当 p 为假时，pq 为真

常出现的错误：不分充分与必要条件

5.等价式与等价联结词“”

定义 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.说明:

(1)pq 的逻辑关系:p与q互为充分必要条件

(2)pq为真当且仅当p与q同真或同假

联结词优先级:(),, , , , 

同级按从左到右的顺序进行

以上给出了5个联结词：, , , , ，组成 一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ;如果出 现的联结词同级，又无括号时，则按从左到右 的顺序运算;若遇有括号时，应该先进行括号 中的运算.注意: 本书中使用的 括号全为园括号. 命题常项

 命题变项

1.2 命题公式及分类

 命题变项与合式公式  命题常项：简单命题

 命题变项：真值不确定的陈述句

 定义 合式公式(命题公式, 公式)递归定义如下： (1)单个命题常项或变项 p,q,r,…,pi ,qi ,ri ,…,0,1 

是合式公式

(2)若A是合式公式，则(A)也是合式公式

(3)若A, B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式 (4)只有有限次地应用(1)~(3)形成的符号串才是合式公式  说明: 元语言与对象语言,外层括号可以省去

合式公式的层次 定义

(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).例如

公式

p p

pq

(pq)r

((pq)r)(rs)

公式的赋值

定义 给公式A中的命题变项 p1, p2, … , pn指定

一组真值称为对A的一个赋值或解释

成真赋值: 使公式为真的赋值

成假赋值: 使公式为假的赋值

说明：

0层

1层

2层

3层

4层



赋值=12…n之间不加标点符号，i=0或1.

A中仅出现 p1, p2, …, pn，给A赋值12…n是  指 p1=1, p2=2, …, pn=n



A中仅出现 p, q, r, …, 给A赋值123…是指  p=1,q=2 , r=3 …



含n个变项的公式有2n个赋值. 真值表

真值表: 公式A在所有赋值下的取值情况列成的表

例 给出公式的真值表

A=(qp)qp 的真值表

例

B = (pq)q 的真值表

例

C=(pq)r 的真值表

命题的分类

重言式

矛盾式

可满足式

定义 设A为一个命题公式

(1)若A无成假赋值，则称A为重言式(也称永真式)

(2)若A无成真赋值，则称A为矛盾式(也称永假式)

(3)若A不是矛盾式，则称A为可满足式

注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式

A=(qp)qp，B =(pq)q，C=(pq)r

1.3 等值演算

 等值式 定义 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式

说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现.例如，在(pq)((pq)(rr))中，r为左边 公式的哑元.用真值表可验证两个公式是否等值 请验证：p(qr)(pq)r

p(qr)

(pq)r

 基本等值式

双重否定律 : AA

等幂律：

AAA, AAA

交换律:

ABBA, ABBA

结合律:

(AB)CA(BC)

(AB)CA(BC)分配律:

A(BC)(AB)(AC)

A(BC)(AB)(AC)德·摩根律:

(AB)AB

(AB)AB

吸收律:

A(AB)A, A(AB)A

零律:

A11,A00 同一律:

A0A，A1A

排中律:

AA1 矛盾律:

AA0

 等值演算:

由已知的等值式推演出新的等值式的过程

置换规则：若AB, 则(B)(A)等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式

(3)置换规则

应用举例——证明两个公式等值 例1 证明 p(qr)(pq)r

证

p(qr)

p(qr)

（蕴涵等值式，置换规则）

(pq)r

（结合律，置换规则）

(pq)r

（德摩根律，置换规则）

(pq)r

（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）

因为每一步都用置换规则，故可不写出

熟练后，基本等值式也可以不写出

应用举例——证明两个公式不等值 例2 证明: p(qr)

(pq)r

用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假.方法一

真值表法（自己证）

方法二

观察赋值法.容易看出000, 010等是左边的 的成真赋值，是右边的成假赋值.方法三

用等值演算先化简两个公式，再观察.应用举例——判断公式类型

例3 用等值演算法判断下列公式的类型

(1)q(pq)解

q(pq)

 q(pq)

（蕴涵等值式）

 q(pq)

（德摩根律）

 p(qq)

（交换律，结合律）

 p0

（矛盾律）

 0

（零律）

由最后一步可知，该式为矛盾式.(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)

（蕴涵等值式）

(pq)(pq)

（交换律）

 1 由最后一步可知，该式为重言式.问：最后一步为什么等值于1？

(3)((pq)(pq))r)

解

((pq)(pq))r)

(p(qq))r

（分配律）

 p1r

（排中律）

 pr

（同一律）

这不是矛盾式，也不是重言式，而是非重言式的可 满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1 说明：演算步骤不惟一,应尽量使演算短些

1.5 对偶与范式 对偶式与对偶原理

定义 在仅含有联结词, ∧,∨的命题公式A中，将 ∨换成∧, ∧换成∨，若A中含有0或1，就将0换成 1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A

定理 设A和A*互为对偶式，p1,p2,…,pn是出现在A和

A*中的全部命题变项，将A和A*写成n元函数形式，则(1) A(p1,p2,…,pn) A*( p1,  p2,…,  pn)

(2)A( p1,  p2,…,  pn)  A*(p1,p2,…,pn)定理（对偶原理）设A，B为两个命题公式，若A  B，则A*  B*.析取范式与合取范式

文字:命题变项及其否定的总称

简单析取式:有限个文字构成的析取式

如 p, q, pq, pqr, …

简单合取式:有限个文字构成的合取式

如 p, q, pq, pqr, …

析取范式:由有限个简单合取式组成的析取式

A1A2Ar, 其中A1,A2,,Ar是简单合取式

合取范式:由有限个简单析取式组成的合取式

A1A2Ar , 其中A1,A2,,Ar是简单析取式 范式:析取范式与合取范式的总称

公式A的析取范式: 与A等值的析取范式

公式A的合取范式: 与A等值的合取范式 说明：

单个文字既是简单析取式，又是简单合取式

pqr, pqr既是析取范式，又是合取范式(为什么?)

命题公式的范式

定理

任何命题公式都存在着与之等值的析取范式 与合取范式.求公式A的范式的步骤：

(1)消去A中的, （若存在）

(2)否定联结词的内移或消去

(3)使用分配律

对分配（析取范式）

对分配（合取范式）

公式的范式存在，但不惟一

求公式的范式举例

例 求下列公式的析取范式与合取范式

(1)A=(pq)r

解

(pq)r

(pq)r

（消去）

 pqr

（结合律）

这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式）

(2)B=(pq)r

解

(pq)r

(pq)r

（消去第一个）

 (pq)r

（消去第二个）

(pq)r

（否定号内移——德摩根律）

这一步已为析取范式（两个简单合取式构成）

继续：

(pq)r

(pr)(qr)

（对分配律）

这一步得到合取范式（由两个简单析取式构成）

极小项与极大项

定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一 次，而且第i（1in）个文字出现在左起第i位上，称这样 的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项

2n个极小项（极大项）均互不等值

用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:

mi  Mi , Mi  mi

主析取范式与主合取范式

主析取范式: 由极小项构成的析取范式

主合取范式: 由极大项构成的合取范式

例如，n=3, 命题变项为p, q, r时，(pqr)(pqr) m1m3 是主析取范式

(pqr)(pqr) M1M5 是主合取范式

A的主析取范式: 与A等值的主析取范式 A的主合取范式: 与A等值的主合取范式.定理

任何命题公式都存在着与之等值的主析取范 式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：

(1)先求析取范式（合取范式）

(2)将不是极小项（极大项）的简单合取式（简

单析取式）化成与之等值的若干个极小项的析

取（极大项的合取），需要利用同一律（零

律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并 按角标从小到大顺序排序.求公式的主范式

例 求公式 A=(pq)r的主析取范式与主合取范式.(1)求主析取范式

(pq)r

(pq)r ,（析取范式）

①

(pq)

(pq)(rr)

(pqr)(pqr)

 m6m7 , r

(pp)(qq)r

(pqr)(pqr)(pqr)(pqr)

 m1m3m5m7

③

②, ③代入①并排序，得

(pq)r  m1m3m5 m6m7（主析取范式）

(2)求A的主合取范式

(pq)r

(pr)(qr),（合取范式）

①

pr

 p(qq)r

(pqr)(pqr)

 M0M2, qr

(pp)qr

(pqr)(pqr)

 M0M4

②, ③代入①并排序，得

(pq)r  M0M2M4

（主合取范式）主范式的用途——与真值表相同(1)求公式的成真赋值和成假赋值

例如

(pq)r  m1m3m5 m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成②③

假赋值和成真赋值.(2)判断公式的类型

设A含n个命题变项，则

A为重言式A的主析取范式含2n个极小项

A的主合取范式为1.A为矛盾式 A的主析取范式为0

 A的主合取范式含2n个极大项

A为非重言式的可满足式

A的主析取范式中至少含一个且不含全部极小项

A的主合取范式中至少含一个且不含全部极大项

例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习.选派必须 满足以下条件：

(1)若赵去，钱也去；

(2)李、周两人中至少有一人去；

(3)钱、孙两人中有一人去且仅去一人；

(4)孙、李两人同去或同不去；

(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出 国？

解此类问题的步骤为：

① 将简单命题符号化

② 写出各复合命题

③ 写出由②中复合命题组成的合取式

④ 求③中所得公式的主析取范式

解 ① 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.②(1)(pq)

(2)(su)

(3)((qr)(qr))

(4)((rs)(rs))

(5)(u(pq))

③(1)~(5)构成的合取式为

A=(pq)(su)((qr)(qr))

((rs)(rs))(u(pq))④

A (pqrsu)(pqrsu)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:

A (pq)((qr)(qr))(su)(u(pq))

((rs)(rs))

（交换律)B1=(pq)((qr)(qr))

((pqr)(pqr)(qr))（分配律）

B2=(su)(u(pq))

((su)(pqs)(pqu))

（分配律）

B1B2 (pqrsu)(pqrsu)

(qrsu)(pqrs)(pqru)再令 B3 =((rs)(rs))得 A  B1B2B3

(pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律

要求：自己演算一遍

1.6 推理理论 推理的形式结构

推理的形式结构—问题的引入

推理举例:

(1)正项级数收敛当且仅当部分和有上界.(2)若

推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法 • 真值表法

• 等值演算法

判断推理是否正确 • 主析取范式法

• 构造证明法

证明推理正确

说明：当命题变项比较少时，用前3个方法比较方 便, 此时采用形式结构“造证明时，采用“前提:

”.而在构 , 结论: B”.推理定律与推理规则 推理定律——重言蕴涵式

构造证明——直接证明法 例 构造下面推理的证明：

若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解 设 p：明天是星期一，q：明天是星期三，r：我有课，s：我备课 推理的形式结构为

例 构造下面推理的证明:

2是素数或合数.若2是素数，则

是无理数.若

是无理数，则4不是素数.所以，如果4是

素数，则2是合数.用附加前提证明法构造证明 解 设 p：2是素数，q：2是合数，r：

是无理数，s：4是素数 推理的形式结构

前提：p∨q, pr, rs

结论：sq 证明

① s

附加前提引入

②pr

前提引入

③rs

前提引入

④ps

②③假言三段论

⑤p

①④拒取式

⑥p∨q

前提引入

⑦q

⑤⑥析取三段论 请用直接证明法证明之