离散数学第1章命题逻辑

离散数学(Ⅰ)

东北大学离散数学课程组2023最新整理收集do

something什么是离散数学？数学的研究对象根据其数据类型可以分为两种：

连续对象，如长度、温度、面积等。

离散对象，如商店商品，学生所学课程等。离散数学是研究离散对象的结构以及它们之间相互关系的科学。为什么学习离散数学？离散数学是计算机科学与技术的理论基础。计算机正是在离散数学中的图灵机的理论指导下诞生的(1936提出图灵机---1946诞生计算机)。现代计算机理论与技术的许多分支，比如：数据结构、编译原理、操作系统、数据库原理、软件工程、网络等都用到离散数学中的基本概念、基本思想、基本方法。培养学生的数学修养和逻辑思维能力。正如著名的物理学家劳厄所说：“重要的不是获得知识，而是发展思维能力。”第一篇数理逻辑

逻辑学起源于2000多年前的古希腊，按其发展过程可分为传统逻辑与现代逻辑。许多著名人物都对逻辑学的发展做出过杰出贡献。亚里士多德和弗朗西斯·培根是传统逻辑的代表，分别创立了演绎推理和归纳推理。

什么是逻辑？“逻辑”是英语Logic的译音，源于古希腊文，原意主要指言语、思想、理性、规律性等。逻辑学起源于2000多年前的古希腊。逻辑学也称为形式逻辑，是关于思维形态的结构及其规律的科学。也就是说，逻辑学研究人思维的形态结构和一般规律。什么是思维的形态结构？思维形态是人们在思维过程中用以反映客观现实的具体形式，即概念、判断、推理。人们思维的形态结构：概念

判断

推理

人的思维形态主要表现为推理推理：

由若干个已知的判断(前提)，推出新的判断(结论)的思维过程。如何能正确的思维？

概念清楚，判断正确，推理合乎逻辑。比如：王刚问李明：“学离散数学有用吗？”李明说：“当然有用了，离散数学是计算机学科的理论基础嘛。”李明的回答实际上包含了三句话的推理：计算机学科的理论基础是有用的，离散数学是计算机学科的理论基础，所以，离散数学是有用的。“计算机学科的理论基础是有用的”这句话对交际双方来说是不言而喻的，所以在表达中被省略。

逻辑学可分为传统逻辑与现代逻辑。

亚里士多德和弗朗西斯·培根是传统逻辑的代表，分别创立了演绎推理和归纳推理。归纳推理：由若干个别事实推出一般结论。如：铜能导电，铁能导电，锡能导电，铅能导

电，……

一切金属都导电。演绎推理：由一般规律推出个别事实。如：所有的金属都导电。(一般规律，大前提)铜是金属。(个别事实，小前提)铜能导电。(个别结论，结论)我们主要研究演绎推理。现代逻辑的开创者是德国的莱布尼兹，在十八世纪初，他提出要把逻辑处理成演算，即数理逻辑。又过了二百多年，罗素与怀特海总结了现代逻辑的发展，建立了命题演算与谓词演算两个完整的体系。

什么是数理逻辑？数理逻辑是用数学的方法研究逻辑。

“数学方法”：建立一套有严格定义的符号体系，即建立一套形式语言，来研究逻辑。所以数理逻辑也称为“符号逻辑”。

数理逻辑分为命题逻辑和谓词逻辑两部分。第一章命题逻辑

第一节命题与命题真值什么是命题？

命题是表达判断的陈述句。一个判断只有两种可能：正确的判断或者错误的判断。把这种“正确”或者“错误”赋予命题，就得到命题的真值。命题的真值：命题的真值只有两个：“真”或“假”。命题的真值为真：一个命题所表达的判断与客观情况一致，记作T(True)。命题的真值为假：一个命所题表达的判断与客观情况不一致，记作F

(False)。例如：“这面旗帜是红色的。”是命题，并且与客观事实相符，所以该命题真值为T。判断一句话是否是命题有两个关键：（1）是陈述句；（2）有且只有一个真值。例:判定下面这些句子哪些是命题?⑴2是个素数。⑵雪是黑色的。⑶2020年人类将到达火星。⑷如果天不下雨并且我有时间，我就去看电影。⑸x+y<5⑹请打开书！⑺您去吗？⑻我正在说谎。

从这句话引出一个问题：说自己正在说谎这句话本身是不是谎话？若真值为T，那么他就正在说谎话，“我正在说谎”这话就是假的；若真值为F，那么他就没有说谎，“我正在说谎”这句话就是真的。所以这句话没有真值，不是命题。

“我正在说谎”这句话是在逻辑学上称为“悖论”，从它的真可以推断它的假，从它的假又可以推断它的真。命题的种类：原子命题(简单命题)：不能再分解成更简单陈述句的命题。复合命题(分子命题)：由若干个连结词、标点符号及原子命题复合构成的命题。命题的表示：在本课程的系统里，用大写字母表示。例：

P：今天下雨。

Q1：小王是大学生。作业第8页:(1)(3)(5)(6)

第二节逻辑联结词简单命题可以用大写字母表示，复合命题如何表示？复合命题由若干个连结词、标点符号及原子命题复合构成的命题复合命题用“逻辑联结词”将原子命题联结起来表达。归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：

(1)否定“”(2)合取“∧”

(3)析取“∨”(4)异或“”

(5)蕴涵“”(6)等价“”（1）否定“”表示：“并非…”，“不…”等。用于对一个命题P的否定，写成

P，并读成“非P”。例：P：2是素数。

P：2不是素数。定义：设P为一命题，P

的否定是一个新命题，记作

P。

P的真值与P的真值相反。

真值表：

PPTFFT因为数理逻辑研究的是人的思维规律，所以在规定逻辑连结词的真值表的时候，一定要符合人的语言与思维的习惯。（2）合取“∧”表示：“并且”、“不但…而且...”、“既…又...”、“尽管…还…”等。例：P：小王能唱歌。Q：小王能跳舞。P∧Q：小王能歌善舞。

真值表应该如何规定？PQP∧QTTTTFFFTFFFF定义：两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P和Q的真值均为T时，P∧Q的真值为T，其它情况下，P∧Q的真值均为F。

连接词“或者”的表达分为两种情况：可兼取的或，即两件事情可以同时发生。用析取“∨”表达。不可兼取的或，即两件事情不能同时发生。用异或（也称排斥或）“

”表达。（3）

析取“∨”例：P：小王能唱歌。Q：小王能跳舞。

P∨Q：小王能唱歌或者能跳舞。小王能唱歌与小王能跳舞可以同时发生，我们用析取“∨”表达。“∨”的真值如何规定？真值表：PQP∨QTTTTFTFTT

FFF定义：两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P和Q的真值均为F

时，P∨Q的真值为F

，其它情况下，P∨Q的真值均为T。

（4）异或“”例：P：十二次列车早晨8:30开。

Q：十二次列车早晨9:00开。

PQ：十二次列车早晨8:30或者9:00开。两件事不能同时发生，用“异或”。P∨Q与PQ的真值表应该有什么不同？

PQPQFFFFTTTFT

TTF当且仅当P与Q的真值相同时，PQ的真值为F

，真值不同时为T。

（5）条件“”表示“如果…那么…”，“若…则…”等。例：P：土壤缺少水分。Q：这颗植物会死亡。

P

Q：

如果土壤缺少水分，这颗植物就会死亡。称P是P

Q的前件，Q是P

Q的后件。也可以说P是Q的充分条件，Q是P的必要条件。P

Q的真值应该如何定义？P：土壤缺少水分。Q：这颗植物会死亡。

PQP

Q

TTT

TFF

FTTFFT善意规定当且仅当

P为T，Q为F时，P

Q的真值为F；而在其它情况下，P

Q的真值均为T。注意“善意规定”。

例：P：天气好。Q：我去公园。1.如果天气好,我就去公园。P

Q2.只要天气好,我就去公园。P

Q3.天气好,我就去公园。P

Q4.仅当天气好,我才去公园。Q

P5.只有天气好,我才去公园。Q

P6.我去公园,仅当天气好。Q

P

用“”表达必须前件是后件的充分条件，即若前件成立，后件一定成立。这一点要特别注意!!!它决定了哪个作为前件，哪

个作为后件。（6）等价(双条件）“

”

表示“当且仅当”、“充分必要”等。例：P：⊿ABC是等边三角形。

Q：⊿ABC是等角三角形。

PQ

：⊿ABC是等边三角形当且仅当它是等角三角形。PQ的真值表：按思维习惯，PQ，QP应同时成立。

PQP

Q

TTT

FFTTFFFTF

当且仅当P与Q的真值相同时，PQ的真值为T，否则为F。PQPQFFFFTTTFTTTFPQP

QFFTFTFTFFTTTPQ⇔

(P

Q)比较下面二表：可以把这6种逻辑联结词看成是6种运算，因为有运算结果；其运算的对象是命题；运算规则是每个连结词的真值表。在后面的代数系统部分大家可以看到，运算的概念是很广的，运算实际上是一种映射。逻辑联结词看成是6种运算，其运算的对象是命题；运算规则是每个连结词的真值表。PQ

PP∧QP∨QPQP

QP

QFFTFFFTTFTTFTTTFTFFFTTFFTTFTTFTT“”为一元运算；

因为一个命题P可以确定P的真值。

“∧，∨，，

，

”

均为二元运算。

因为它们的真值必须由两个运算对象确定。练习：填空已知P∧Q为T，则P为()，Q为()。已知P∨Q为F，则P为()，Q为()。已知P为F，则P∧Q为()。已知P为T，则P∨Q为()。已知P∨Q为T，且P为F，则Q为()。已知P

Q为F，则P为()，Q为()。已知P为F，则P

Q为()。已知Q为T，则P

Q为()。已知

P

Q为F，则P为()，Q为()。已知P为T，P

Q为T，则Q为()。已知

Q为T,P

Q为T，则P为()。已知PQ为T，P为T,则Q为().已知PQ为F，P为T,则Q为().PP的真值为().P

P的真值为()。第三节命题符号化

命题符号化，就是将自然语言表达的句子用符号化的命题公式来表达。命题符号化的步骤：

(1)先将语句分解成原子命题。(2)将每个原子命题用大写字母表示。注意每个原子命题都必须是一个完整的句子。(3)用确切的逻辑联结词联结原子命题，构成给定命题的符号表达式。例1将下列命题符号化，并讨论它们的真值：⑴是无理数当且仅当加拿大位于亚洲。

解：令P：是无理数，真值为T；Q：加拿大位于亚洲，真值为F；符号化为：P

Q，真值为F。⑵除非a能被2整除，否则a不能被4整除。

其中a是一给定正整数。解：令P：a能被2整除；Q：a能被4整除；

“除非a能被2整除，否则a不能被4整除”的含义与“如果a不能被2整除，则a不能被4整除”一样，也等价于说“如果a能被4整除，则a一定能被2整除”。

所以⑵表达为：

P

Q，也即QP。

当Q为T，P一定为T。也即没有Q为T，P为F的情况发生，所以其真值为T。例2符号化下列命题

⑴如果小张与小王都不去，则小李去。

⑵如果小张与小王不都去，则小李去。解：令P：小张去。Q：小王去。R：小李去。

⑴命题符号化为：(P∧

Q)

R⑵命题符号化为：

(P∧Q)

R

或(P∨

Q)

R例3符号化下面命题：仅当天不下雨且我有时间，才上街。

解：令

P：天下雨。Q：我有时间。R：我上街。

分析：由于“仅当”是表示的是“必要条件”。即我上街，一定是天不下雨且我有时间时；而天不下雨且我有时间时我不一定上街。

所以该命题表达为：R(P∧Q)例4

符号化下面命题：

若天不下雨，我就上街；否则在家。解：令P：天下雨。Q：我上街。R：我在家。该命题可符号化为：(PQ)(PR)∧

注意：中间的联结词一定是“∧”，不能是“∨”，也不是“”。

在考虑用什么联结词时，一定要考虑哪种逻辑联结词的真值表最符合命题描述的情况。因为原命题表示：“天不下雨时我做什么，天下雨时我又做什么”这两种情况，其中有一种情况是假的，则题中的说法就不正确，所以中间的联结词一定是“∧”。例5

一个人起初说，“占据空间的有质量的而且不断变化的叫物质”；后来他改说，“占据空间的有质量的叫物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。解：令P：某物占据空间；Q：某物有质量；R：某物不断变化；S：某物叫物质。

起初：(P∧Q∧R)

S

后来：((P∧Q)

S)∧(S→R)

例5令P：北京比天津人口多。Q：2+2=4。R：乌鸦是白色的。求下面复合命题的真值：(P(Q∨R))∧((Q∨

R)

P)解：P的真值为T，Q的真值为T，R的真值为F。(P(Q∨R))∧((Q∨

R)

P)的真值

为T作业第11页：（1）第12页：（5）（6）（7）第4节

命题公式及其赋值

一、命题公式

先看一个命题公式：P：3是素数。(P

F)∨(QR)∧T在命题公式中有三种数据类型：命题常项：即命题的真值。常值命题：即具体命题。命题变元：用大写字母表示的任一命题。命题变元本身不是命题，因为它没有固定真值，只有给它赋值，才变成命题。将一个命题常项或常值命题赋予命题变元的过程称为给命题变元赋值，也称为对命题变元作指派。合式公式（合法的命题公式）定义：⑴单个命题变元、常值命题及命题常项是合式公式。⑵若A是合式公式，则

A是合式公式。⑶若A和B是合式公式，则(A∧B)，(A∨B)，(A

B)

(A

B)都是合式公式。⑷

当且仅当有限次地应用⑴，⑵，⑶所得到的符号串是合式公式。合式公式也称为命题公式，简称为公式。例：下面的式子是合式公式：

(P∧Q)，(PR)，((P∧Q)∨R)下面的式子不是合式公式(P∧Q，PR，P∧Q∨R为了简化命题公式，约定：

(1)最外层括号可省；

(2)不影响运算次序的括号可省。运算次序由高到低为:,∧,∨,,

合式公式：

(P∧Q)，(PR)，((P∧Q)∨R)可以简化成：

P∧Q，

PR，

(P∧Q)∨R，

P∧Q∨R二、命题公式的真值表一个含有命题变元的命题公式不是命题，因为它没有固定真值，但是给其中的所有命题变元赋值以后它就有了唯一的真值。

将所有各种赋值情况汇列成表，即为该命题公式的真值表。例：命题公式(PQ)∨Q的真值表如下所示：PQP

P

Q(PQ)∨QFFTTFTFTTTFFFTTTFTTT构造真值表的步骤：由于每个命题变元都有两种赋值可能性(T,F)，所以含有n(n≥1)个命题变元的命题公式真值表有2n行。将n个命题变元按字母次序排列。将F记为0，T记为1，按照二进制数的次序赋值。赋值从00…0开始，然后按二进制加法依次加1，直到11…1为止。对每个赋值，计算命题公式的真值。例：构造P(Q

R)的真值表PQRQ

RP(Q

R)000FFFTT001FFTTT010FTFFT011FTTTT100TF

F

T

T101TF

T

T

T110TT

F

F

F111TT

T

T

T第5节

命题公式的等价

看下面三个公式的真值表：PQP

Q

P∨Q

Q

PFFTTFTFTTTFTTTFTTTFT从真值表可以看出，不论对P、Q作何种赋值，P

Q、

P∨Q和

Q

P的真值都相同。

P

Q

P∨Q

Q

P等价定义：A、B是含有命题变元P1,P2,…,

Pn

的命题公式，如不论给P1,P2,…,

Pn

何种赋值，A和B的真值均相同，则称命题公式A与B等价，记作A

B。若两个命题公式的真值表相同，

则它们等价。基础等价公式：

⑴对合律

P

P⑵幂等律P∨P

PP∧P

P⑶交换律P∨Q

Q∨PP∧Q

Q∧P⑷结合律P∨(Q∨R)(P∨Q)∨RP∧(Q∧R)(P∧Q)∧R⑸分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)

PP∧(P∨Q)

P⑺底·摩根定律

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q⑻同一律P∨F

PP∧T

P⑼零律P∨T

TP∧F

F⑽互补律P∨

PTP∧

P

F⑾P

Q

P∨Q

⑿

P

Q

Q

P⒀

PQ(P

Q)∧(Q

P)⒁PQ(P∨Q)∧(P∨

Q)

⒂

PQ(P∧Q)∨(

P∧

Q)PQP∨Q

(P∨Q)

P

Q

P∧

QFFFTTTTFTTFTFFTFTFFTFTTTFFFF例：证明底·摩根定律

(P∨Q)

P∧

Q证明：构造两个命题公式的真值表：因为(P∨Q)与

P∧

Q的真值表相同，所以等价。等价公式的证明方法：方法1：列真值表。方法2：用等价公式变换。(用置换定律)置换定律：A是一个命题公式，X是A中的一部分且也是合式公式，如果X

Y，用Y代替A中的X得到公式B，则A

B。例1：

求证(

P∨Q)→(P∧Q)

P证明：(

P∨Q)→(P∧Q)

(

P∨Q)∨(P∧Q)(公式E11)

(

P∧

Q)∨(P∧Q)(底·摩根定律)

(P∧

Q)∨(P∧Q)(对合律)

P∧(

Q∨Q)(分配律)

P∧T(互补律)

P(同一律)公式E11

：P

Q

P∨Q例题2.求证吸收律P∧(P∨Q)

P证明P∧(P∨Q)

(P∨F)∧(P∨Q)(同一律)

P∨(F∧Q)(分配律)

P∨F(零律)

P(同一律)例题3.化简

(P∧Q)→(

P∨(

P∨Q))解:

(P∧Q)→(

P∨(

P∨Q))

(P∧Q)∨((

P∨

P)∨Q)(E16,结合)

(P∧Q)∨(

P∨Q)(对合律，幂等律)

(P∧Q)∨(Q∨

P)(交换律)

((P∧Q)∨Q)∨

P(结合律)

Q∨

P(吸收律)公式

：P

Q

P∨Q对偶式：在一个只含有联结词

、∨、∧的公式A中，将∨换成∧，∧换成∨，T换成F，F换成T，其余部分不变，得到另一个公式A*，称A与A*互为对偶式。

例如：AA*PPQ∧RQ∨R(P∨T)∧Q(P∧F)∨Q定理

令A(P1,P2,…,Pn)是一个只含有联结词

、∨、∧的命题公式，则

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

此定理可以反复地使用底-摩根定律证明。

推论：A(

P1,

P2,…,

Pn)

A*(P1,

P2,…,

Pn)

应用上述定理可以直接将“”放到命题变元的前面。

例如：

(((P∧Q)∨(P∧Q))∨R)((P∨Q)∧(P∨Q))∧R等价“”是关系符号，不是运算符号，它表明的是两个命题公式之间的关系。等价的性质：

1)有自反性：对任何命题公式A，均有A

A。

2)有对称性：若AB，则BA。3)有传递性：若AB且BC，则AC。作业第17页：（1）b)c)d)

（2）题改为化简第18页：（6）第19页：（7）（8）

画真值表证明：PQ(P∧Q)∨(

P∧

Q)

第6节重言式与重言蕴涵式PP∨PP∧PFTFTTF

P∨P为重言式(永真式)；

P∧P为矛盾式(永假式)。重言式(矛盾式)定义：若公式A

T，则A为重言式或永真式。若公式A

F，则A为矛盾式或永假式。例：证明(P∧(PQ))Q

为重言式。方法1：列真值表PQ

PQP∧(PQ)

P∧(PQ))QFFTFTFTTFTTFFFTTTTTT永真公式真值表的最后一列全是“T”。方法2：等价公式变换(P∧(PQ))Q

(P∧(P∨Q))Q

((P∧P)∨(P∧Q))Q

(F∨(P∧Q))Q

(P∧Q)Q

(P∧Q)∨Q

(P∨

Q)∨Q

P∨(

Q∨Q)

P∨T

T定理

设A,B为两个命题公式，A⇔B当且仅当A↔B是一个重言式。证明：若A⇔B，则不论对A、B做何种赋值，A与B的真值都相同，于是A↔B⇔T，即A↔B是一个重言式。若A↔B是一个重言式，则A↔B⇔T，于是不论在何种赋值下，A与B的真值均相同，即A⇔B。重言蕴涵式定义：当且仅当A

B是重言式，则称A重言(永真)蕴涵B，记作A

B。

即当且仅当A

BT，则A

B。

AB可以理解成由A可推出B，即

由A为真，可以推出B也为真。重言蕴涵式的两种基本证明方法：考察A

B的真值表，如果A

B为永真式，则前件A为真，后件B为假的情况就不会出现。

PQP

Q

TTT

TFF

FTTFFT所以只要证明前件为真，后件为假的情况不发生，A

B即为永真式。有下面两种证明方法：例1求证P∧(P→Q)Q证明：

假设P∧(P→Q)为T，

则P为T并且(P→Q)为T，于是Q为T，

所以P∧(P→Q)Q成立。1.假设前件A为真，若在此假设下能推出后件B也为真，则AB成立。例2求证：

((A∧B)

C)∧

D∧(

C∨D)

A∨

B证明：设前件((A∧B)

C)∧

D∧(

C∨D)为真。则

((A∧B)

C)、

D、(

C∨D)均为真。

D为T，则D为F，由

C∨D为T，于是

C为T，即C为F，再由((A∧B)

C为T，则(A∧B)为F，即

(A∧B)为T，于是

A∨

B为T，因此

((A∧B)

C)∧

D∧(

C∨D)

A∨

B。例：求证PP∨Q，QP∨Q证明：

假设P∨Q为F，则P为F，Q为F，所以

PP∨Q，QP∨Q成立。2.假设后件B为假，若在此假设下能推出前件A也为假，则AB成立。例2求证：((A∧B)

C)∧

D∧(

C∨D)

A∨

B证明：假设后件A∨

B为F，则A与B均为T。1.如C为F，则(A∧B)

C为F，所以前件((A∧B)

C)∧

D∧(

C∨D)为F2.如C为T，则⑴若D为T，则

D为F，所以前件((A∧B)

C)∧

D∧(

C∨D)为F。

⑵若D为F，则

C∨D为F，

所以前件((A∧B)

C)∧

D∧(

C∨D)为F。综上((A∧B)

C)∧

D∧(

C∨D)

A∨

B成立。基础的重言蕴涵公式：I1P∧Q

PI2P∧Q

QI3P

P∨QI4Q

P∨QI5

P

P

QI6Q

P

QI7

(P

Q)

PI8

(P

Q)

QI9P,Q

P∧QI10

P∧(P∨Q)

QI11P∧(P

Q)

QI12

Q∧(P

Q)

PI13(P

Q)∧(Q

R)

P

RI14A

B(A∨C)(B∨C)I15A

B

(A∧C)(B∧C)重言蕴含“

”是关系符，不是运算符。重言蕴含的性质：

1)有自反性：对任何命题公式A，有A

A。

2)有传递性：若AB且BC，则AC。

3)有反对称性：若AB且BA，则

AB。

4)若AB且AC，则AB∧C。

5)若AB且CB，则A∨CB。定理：设A，B为任意两个命题公式，A

B的

充要条件是A

B且B

A。证明：若A

B，则ABT，而

AB(A→B)∧(B→A)，于是A→BT且

B→AT，即A

B且B

A成立。

若A

B且B

A，则A→BT且B→AT，

于是(A→B)∧(B→A)T。而

AB(A→B)∧(B→A)，于是ABT，

即知A

B成立。思考：⑴若

AB是否有AB?解：若

AB则A→BT而

A→BB→A，于是B→AT，

即BA而不是AB

⑵若AB是否有AB?

解：若

AB则ABT而

AB(A→B)∧(B→A)(B→A)∧(A→B)AB

于是ABT，

即AB作业一、用证明永真蕴涵的两种基本方法证明：I10

P∧(P∨Q)

QI11P∧(P

Q)

QI12

Q∧(P

Q)

PI13(P

Q)∧(Q

R)

P

RI14A

B(A∨C)(B∨C)I15A

B

(A∧C)(B∧C)作业第19页（9）第23页（1）a)b)c)

（6）、（7）证明：

若AB且AC，则AB∧C。

若AB且CB，则A∨CB。作业思考：永真蕴涵是否有置换定律？即：A是一个命题公式，X是A中的一部分且也是合式公式，如果X

Y，用Y代替A中的X得到公式B，则A

B。是否成立？第7节范式

范式就是命题公式的规范形式，分为析取范式与合取范式。1.析取范式定义：

命题公式A如果可等价地写成如下形式：

A1∨A2∨...∨An(n≥1)，

其中每个项Ai(i=1,2,…,n)是命题变元或其

否定形式的合取式，称该公式为A的析取

范式。

因PQ(P∧Q)∨(

P∧

Q)

(P∧Q)∨(

P∧

Q)是PQ的析取范式。2.合取范式定义：

命题公式A如果可等价地写成如下形式：

A1∧A2∧...∧An(n≥1)，

其中每个项Ai(i=1,2,…,n)是命题变元或其否

定形式的析取式，称该公式为A的合取范式。

因PQ(P∨Q)∧(P∨

Q)

(P∨Q)∧(P∨

Q)是PQ的合取范式。从定义可以看出：在析取范式与合取范式中只含有联结词“

,∧,∨”。“”在命题变元之前。

求一个公式的析取范式或合取范式的步骤：⑴去掉“”和“”。⑵将“”移到命题变元前。

用公式

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)⑶用分配律、幂等律等公式进行整理，使之

成为所要求的形式。例：求(P

Q)

R的析取范式与合取范式。先求析取范式：

(P

Q)

R

(P

Q)∨R---去掉其它连结词((P∨Q)∧(P∨Q))∨R

---去掉其它连结词(P∧Q)∨(P∧Q)∨R

---“

”移到命题变元前面例：求(P

Q)

R的析取范式与合取范式。再求合取范式：

(P

Q)

R

(P

Q)∨R

---去掉其它连结词((P∧Q)∨(P∧Q))∨R

---去掉其它连结词((P∨Q)∧(P∨Q))∨R

---“

”移到命题变元前面(P∨Q∨R)∧(P∨Q∨R)

---整理注：P∧Q既是合取范式，也是析取范式。

主析取范式与主合取范式一、主析取范式

小项：是n个命题变元的合取式，其中每个变元必出现且仅出现一次(以本身或否定形式)，称这个合取式为小项。例如，含有两个变元的小项：

P∧Q、P∧Q、P∧Q、P∧Q若有n个变元，则有2n个小项。小项编码：含有n个变元的小项的角标用n位二进制码表示。变元按字母次序排列。用1表示变元本身，0表示变元的否定形式。例：m00

P∧Q

，m01

P∧Q

，

m10

P∧Q

，

m11

P∧Q

m101

P∧Q

∧R，m100

P∧Q

∧

R考察含有两个变元的所有小项的真值表：m00m01m10m11PQP∧QP∧QP∧QP∧Q00011011FFFTTFTTTFFFFTFFFFTFFFFT每个小项当且仅当其赋值与编码相同时，其真值为T；而其余2n-1组赋值均使该小项的真值为F。全体小项的析取式为永真式，记为：∑mi⇔m0∨m1∨…∨m2n-1

⇔T主析取范式定义：若一个命题公式的析取范式为A1∨A2∨...∨An(n≥1)，其中每个Ai(i=1,2,...,n)都是小项，则称之为该命题公式的主析取范式。主析取范式的求法：⑴先写出给定公式的析取范式

A1∨A2∨...∨An

。⑵为使每个Ai都变成小项，对缺少变元的项

Ai要补全变元，比如缺变元R，就用

“∧(R∨

R)”的形式补R。⑶用分配律等公式加以整理。例：求PQ的主析取范式。解：PQP∨Q---去掉其它连结词(P∧(Q∨

Q))∨((P∨

P)∧Q)---补变元(P∧Q)∨(P∧

Q)∨(P∧Q)∨(

P∧Q)

---用分配律展开

(P∧Q)∨(P∧

Q)∨(P∧Q)求主析取范式的真值表法：⑴列出给定公式的真值表。⑵找出该公式真值表中每个为“T”行的赋值

所对应的小项。

⑶用“∨”联结上述小项，即可。例：求PQ和P

Q的主析取范式

PQm00∨m01∨m11

(P∧Q)∨(P∧Q)∨(P∧Q)

P

Q

m00∨m11

(P∧Q)∨(P∧Q)PQPQP

Q00TT01TF10FF11TT定理

在真值表中，一个使公式的真值为T的赋值所对应的小项的析取，即为此公式的主析取范式。思考：永真公式的主析取范式是什么样的？二、主合取范式大项定义：是n个命题变元的析取式，其中每个变元必出现且仅出现一次(以本身或否定形式)，称该析取式为大项。有n个变元，则有2n个大项。大项的编码：

大项的编码正好与小项相反。0表示变元本身，1表示变元的否定形式。如：M00P∨QM01P∨Q

M10P∨QM11P∨Q显然，Mi

mi例：

M011P∨Q∨R(P∧Q∧R)

m011

考察含有两个变元的所有大项的真值表：每个大项当且仅当其赋值与编码相同时，其真值为

F；其余2n-1组赋值均使该大项的真值为T。2.全体大项的合取式必为永假式。M00M01M10M11PQP∨QP∨QP∨QP∨Q00011011FFFTTFTTFTTTTFTTTTFTTTTF主合取范式定义：若一个命题公式的合取范式为A1∧A2∧...∧An(n≥1)，其中每个Ai(i=1,2,…,n)都是大项，则称之为该命题公式的主合取范式。求主合取范式的步骤：⑴先写出给定公式的合取范式A1∧A2∧...∧An。⑵为使每个Ai变成大项，对缺少变元的项Ai补全变元，比如缺变元R，用“∨(R∧

R)”的形式补R。⑶用分配律等公式加以整理。例：求(PQ)R的主合取范式(PQ)R(P∨Q)∨R------去掉其它连结词(P∧

Q)∨R------“

”移到命题变元前面(P∨R)∧(

Q∨R)------化成合取范式(P∨(Q∧Q)∨R)∧((P∧P)∨

Q∨R)---补变元(P∨Q∨R)∧(P∨Q∨R)∧

(P∨

Q∨R)∧(P∨

Q∨R)---用分配率整理(P∨Q∨R)∧(P∨Q∨R)∧(P∨

Q∨R)主合取范式的真值表求法：⑴列出给定公式的真值表。⑵找出该公式真值表中的每个为“F”行的赋值所对应的大项。⑶用“∧”联结上述大项，即可。定理

在真值表中，一个使公式的真值为F的赋值所对应的大项的析取，即为此公式的主合取范式。例：求PQ和P

Q的主合取范式

PQM10P∨QP

Q

M01∧M10

(P∨Q

)∧(P∨Q)PQPQP

Q00TT01TF10FF11TT思考:1.永真公式的主析取范式是什么样？是否有主合取范式？2.永假公式的主合取范式是什么样？是否有主

析取范式？3.若已知主合取范式，能否直接写出主析取范

式？例：已知A(P,Q,R)的主析取范式中含有下面小项m1，m3，m5，m7，求它的和主合取范式。解：

在真值表中，除了使命题公式A为真的赋值，其余的就是使A为假的赋值。而主析取范式中包含的小项的编码，就是使命题公式A为真的赋值

所以赋值1，3，5，7，即001，011，101，111就是使A为真的赋值。0，2，4，6，即000，010，100，110是使A为假的赋值。A(P,Q,R)

m1∨m3∨m5∨m7

M0∧M2∧M4∧M6

M000∧M010∧M100∧M110(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

∧(P∨Q∨R)例：A，B，C，D四个人中要派两个人出差，按下述三个条件有几种派法？

①

若A去则C和D中要去一个人。②B和C不能都去。

③C去则D要留下。解：令A，B，C，D分别表示A去，B去，C去，D去。①A

(CD)

A

((C∧

D)∨(

C∧D))

A∨(C∧

D)∨(

C∧D)②(B∧C)B∨C③C

DC∨D总的条件为：(A∨(C∧

D)∨(

C∧D))∧(B∨C)∧(C∨D)将几个条件的合取式化成析取范式：(A∨(C∧

D)∨(

C∧D))∧(B∨C)∧(C∨D)

(

A∨(C∧

D)∨(

C∧D))∧

(C∨(B∧D))(A∧C)∨(C∧

D∧C)∨(

C∧D∧C)

∨

(A∧B∧D)∨(C∧

D∧B∧D)∨(

C∧D∧B∧D)

(A∧C)∨(

C∧D)∨(A∧B∧D)∨(C∧

D∧B)

最后的派法要使得

(A∧C)∨(

C∧D)∨(A∧B∧D)∨(C∧

D∧B)为T。

可以取

A∧C为T，得B和D去。可以取C∧D为T，得A和D去，或者B和D去。可以取C∧

D∧B为T，得A和C去。最后得到三种派法：A和C去、A和D去、B和D去。作业

第39页：(2)c)、d),(3)b)、d),(4)a)、d)、e),(5)b)、d)(7)作业

补充题：安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。第8节

命题逻辑推理推理就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为前提。得到的新判断为前提的有效结论。推理的过程就是证明永真蕴含式的过程。

令H1,H2,…,Hn是已知的命题公式(前提)，若有H1∧H2∧....∧Hn

C则称C是H1,H2,…,Hn的有效结论，简称结论。两个推理规则：P规则(引入前提规则)：在推理过程中，可以随时引入前提。T规则(引入结论规则)：在推理过程中，如果前面有一个或几个公式重言蕴涵公式S，则可将S纳入推理过程中。基础重言蕴涵式(I类公式)I1P∧Q

PI2P∧Q

QI3

P

P∨QI4Q

P∨QI5

P

P

QI6Q

P

QI7

(P

Q)

PI8

(P

Q)

QI9P,Q

P∧QI10

P,(P∨Q)

QI11P,(P

Q)

QI12

Q,(P

Q)

PI13P

Q,Q

R

P

RI14P∨Q,P

R,Q

R

RI15A

B(A∨C)(B∨C)I16A

B

(A∧C)(B∧C)基础等价公式(E类公式):对合律

P

P交换律P∧Q

Q∧P

P∨Q

Q∨P结合律P∧(Q∧R)(P∧Q)∧RP∨(Q∨R)(P∨Q)∨R分配律

P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)吸收律P∨(P∧Q)

PP∧(P∨Q)

P底-摩根定律

(P∧Q)

P∨

Q

(P∨Q)

P∧

Q幂等律

P∨P

PP∧P

P同一律

P∨F

P

P∧T

P

零律

P∨T

TP∧F

F互补律P∨

PTP∧

P

F

P

Q

P∨Q，

P

Q

Q

PP(QR)(P∧Q)RPQ(P

Q)∧(Q

P)PQ(P∨Q)∧(P∨

Q)PQ(P∧Q)∨(

P∧

Q)

(PQ)P

Q推理方法：

直接推理

间接推理条件论证反证法一.直接推理

直接推理是由一组前提，利用P规则、T规则直接推演得到有效结论的方法。推理实际上就是证明永真蕴含的过程。为了使推理过程更加简单、明确，推理会采用另外一种书写格式。例1求证P→Q，Q→R，P

R证明：

序号前提或结论注释列

(1)PP(2)P

QP(3)QT(1)(2)I(4)Q→RP(5)RT(3)(4)I（公式：P，P→QQ）推理格式：第一列为步骤号；第二列为给定前提或得出的结论；第三列为注释列，标明是前提还是得到的结论，以及此结论是从哪几步得到的，所用公式得类型。例2求证：

(P∧Q)∧(Q∨R)∧

R

P(1)

RP(2)Q∨RP(3)QT(1)(2)I(4)

(P∧Q)P(5)

P∨

QT(4)E(6)

PT(3)(5)I注：公式：

P,P∨Q

Q

，

(P∧Q)

P∨

Q假设

(P∧Q)∧(Q∨R)∧

R为T，则

(P∧Q)，(Q∨R)，R均为T，由R，(Q∨R)为T，知Q为T；由

(P∧Q)为T，而

(P∧Q)

P∨

Q，于是

P∨

Q为T，再由Q为T，知

P为T。

例3求证：P→(Q→S)，

R∨P，Q

R→S证明：(1)QP(2)P→(Q→S)P(3)

P∨(

Q∨S)T(1)E(4)

P∨(S∨

Q)T(2)E(5)(

P∨S)∨

QT(3)E(6)

P∨ST(4)(5)I(7)P→ST(6)E(8)

R∨PP(9)R→PT(8)E(10)R→ST(7)(9)I二、条件论证如果要证明的结论是R→S的形式，则可以把结论中R→S的前件R作为附加前提，与给定的前提一起推出后件S即可。定理如果H1∧H2∧...∧Hn∧R

S，

则H1∧H2∧...∧Hn

R→S

证明：因为H1∧H2∧...∧Hn∧R

S，则

(H1∧H2∧...∧Hn∧R)

S是永真式。而(H1∧H2∧...∧Hn∧R)

S

(H1∧H2∧...∧Hn∧R)∨S

(H1∧H2∧...∧Hn)∨(

R∨S)

(H1∧H2∧...∧Hn)

(R→S)

所以(H1∧H2∧...∧Hn)

(R→S)是永真式。即H1∧H2∧...∧Hn

R→S，

定理得证。我们把上述定理写成如下规则：

CP规则(ConditionalProof)：

如果H1∧H2∧...∧Hn∧R

S，则

H1∧H2∧...∧Hn

R→S例4

P→(Q→S)，

R∨P，Q

R→S证明：(1)R

P(附加前提)

(2)

R∨P

P

(3)P

T(1)(2)I

(4)P→(Q→S)

P

(5