离散数学-第一章命题逻辑

离散数合式公式、公式、范式、推理理论等。 1.1命题：命题是具有唯一真、假值的陈述注意：由命题的定义知：(1)一个命题或是真的或是；(2)一个命题不能既不是真的也不是； 1.1例1.1.1下面的句子是否(1)中国的首都 (3)地球外的星球上也有人(5)(6x+1不超过5我正在说谎 1.1简单命题：若一个命题是一个简单陈述句，则称通常用大写字母P、Q、R…等表示命题和原子命复合命题：由原子命题与逻辑联结词组合而成的例非3+1比53+1比5大蕴含明天是晴 1.1常用的逻辑联结词有以下5个(1)否定词┐：设P是一个命题，那么┐P是一 P1001例 是一个大城市┐P 不是一个大城 (2)合取词：设P，Q是命题，那么PQ也一个命题，称为P和Q的合取，读作P并且QPQP000010100111 例P:Q:明天下PQPQP

：今天下雨而且明天：今天与明天都下：这两天都下 (3)析取

：设P，Q是命题P

个命题，称为P和Q的析取，读作P或者QPQP000011101111 例(a)P：今晚我写字，Q：今晚我看P

：今晚我写字或今天晚上我在家看书或去看不能表PQ (4蕴涵：设P，Q是命题，那么P也是一个命题，称为由前件P和后件Q所组PQP001011100111 例P：天不下雨，Q：草木P

：如果天不下雨，那么草木枯黄P：桔子是紫色的，Q：大地是不平P

：如果桔子是紫色的，那么大地是 蕴涵式P→Q通常有多种方式叙述给

P

Q

QQ

为命题P

的逆命题，反命题，逆 (5)等值词：设P，Q是命题，那么P PQP001010100111 例1.1.2试将下列命题符号(a)如果你不看，则我也不看(b)一边吃饭，一边看书解(a)设P：你看；Q；我看，则该题可符号化为

Q设P：吃饭，Q：看书，则该命可符号化为P 例将下列命题符号我今天进城，除非下仅当你走我将留下(aP:上午天下雨Q:R:我在家看书S我在家看

Q)(P

(R

P:我今天进 Q:天下QP:你走 Q:我留Q 命题变元：以{T，F}为其变域的变命题常元：T和F定义1.2.1命题逻辑的合式公式归纳定义如下单个命题变元和命题常元是合式公式若A，B是合式公式,

(A)

(AB)(A

,(A

,(A

也是合式公式 例

(R

是合式公式

不是合式公式 题的真值依赖于代换变元的那些命题的 为了减少括号的使用，我们作以下约定最外层的括号可以省略联结词的优先级为例1.2.2

Q)

可以简写为(

Q)

(P(Q

可以简

PQ

Q)

PQ 定义1.2.2设A是合式公式C的一部分且A本身例1.2.3公

F((

Q

R)

R))子公式为：F

(PQ

(P Q (P 元P1,P2,…,Pn题公式1,Pi2,,Pir是其中r个不同题变元，用合式公式B1

B2,,

同时分取代A

P,ii ii

,,iri

的每一处出现所得到的合公式称为A的一个代入实例例1.2.5

A(P,

(P

(P

B(P

Q)则用B取代P所得到的代入实例为 例1.2.6

A(P,Q)

(P

P)，用(P

和(Q

P)分别取代P和Q代入实例为

(Q

((Q

例1.2.8在公式

(P

Q)(R

(P

Q))中用公式(P

去替换第二次出现的子公(P

得到公式F(

Q)(R

用(R得到公式

去替换子公式(R

(P

F(

Q)(R

定义1.3.1

这n个命题变元的合式公式

一组真值赋值，称为对A的一组解释I~

~,其中 12

I(i)

例1.3.2合式公

A(P,Q,R)

PQ

中有3命题变元，因此它有8种解I0

000

I1

001

I2

010

I3

011I4

100

I5

101

I6

110

I7

111 例1.3.3设公

A(P,Q,

(P

Q)(P

,其解I

，那么I(

1)(0

10定义1.3.3设A是合式公(1)若A在任何解释下为真，则称A为重言式或式；(2)若A在任何解释下为假，则称A为式或永假式； 例1.3.4构造下列公式的真值表

P

PPPPPQP 1101110011011111 定义1.3.4若AB是式，则称A恒等于或A等价于B，记为A辑恒等式

AB为关于逻辑恒等式有以下性质①AAA

BAA

BC

ACABAB 1.3公例证明

┐P1P1P1(P1P2)(P1P20011111011011110011001110000

是式，A是用Bi取代的代入实例

A

AB1B2,Bn)

的任何解释I

在I下的真值为 令A的解

I

~

在I下的真值与 在I

下的真值相IA)1

IA1 1.3公

P

Q)

P

QR)

Q 习题1、2(3),4)、3习题1、2(3)、3(2)、12)3(2) 定理1.3.2设A是C的子公式，

A

B替换C中A的一处或多处出现得到公式D，CD证C与D不同之处在于C中A的若干处出现换以BA

，故在公式C、D中出现的变元的一指派下，A与B有相同的真值因而C与D也有相同的真值

CD 1.3公例1.3.6证明式

(P

R (P

(P

(PR)(PPRP 1.3公(P

Q)(R

(P

P)

Q)(RQ)(RT(PQ)(RQ)

Q)(RQ)(PR)T 1.3公例1.3.7

P

Q)

P

P

Q)

P

P

(P

P)(P

Q)F(P

Q)

P

PP

(P

P)(P

Q)T(P

P 1.3公定义1.3.5设有A是仅含联的公式，在A，T，F分别换

T所得到的公式称为A的对偶式，记为A*例1.3.9

A(P,Q,

(P

Q)

的对偶式解A(PQ

Q)

Q)

PQA的对偶

A*(P

Q) 1.3公定理1.3.3

是仅含联

的公式，

证对公式A的结构应用归纳法(1)基础：当A为Pi、T、F时，A*分别为Pi，F、T。

FT便知当A是由一个变元或常元构成式(1)成立 1.3公(2)归A1(P1,P2,…,Pn)、A2(P1,P2,…,Pn对(1)成立即(1

(1

A*(P,P,,P 下面证

(

)式(1)也成立 1.3公

A*(P,P,,P 1.3公(2)A

A*(P,P,,P)A*(P,P,,P 情形(3)：类似于情形(2) 定理1.3.4（对偶定理）设A和B为仅含联结词，

的公式，P1,P2,…,Pn是其所有题变元若

A

A

A(1,P2,,Pn

B(1,P2,,Pn

Pn)A

知A

是式， 1.3公 式

Pi(1i

取代上式中的Pi(1

i

真*(1

*(1

1.3公定义1.3.6

A

是重言式，则

AB蕴涵式，记为AB。读作“A蕴涵B”

有下列一些性质①AAA

B

AC③A

当且仅

A

BAAB

1.3公但也可以用下列方法证明 例1.3.11证明

)(1

P(P

Q)为真则 为真，PQ为真，因此为Q真。所以

证法2

为假，下面分两种情况讨论

为真

P

为假，因而

(P

Q) 1.3公P为假

P(P

所以

定理1.3.5设A和B为仅含联结词，的式，P1,P2,…,Pn是其所有题变元，

A则B*

A*因A

B(1,P2,,Pn)

1.3公A

知A

是式，是式

Pi(1i

取代上式中

in)，得*(1*(1

B*

定义1.4.1命题变元和命题变元的否定称为文字，并定义1.4.2基本和的归纳定①文字是基本和②若A，B是基本和

A

PQ

是基本和 定义1.4.3合取范式的归纳定义如下①基本和是合取范式②若A，B是合取范式

(A

是合取范式例

,

P

(

Q

(P

是合取范式定义1.4.4设B是合取范式，A是合式公AB，则称B是A的合取范 例1.4.1求

合取范式解

((P

((Q

R)((P

Q

R)

R

定义1.4.5n个命题变元的极大项PP PP

Pbn，

0或nin个变元可构成2n个不同的极大项ni例如3个变元P,Q,R可构造8个极大项M0:

Q

M1:

Q

M2:

QM3:PQ

M4:

Q

M5:

QM6:

Q

M7:

Q 定义1.4.6主合取范式的归纳定义如下①极大项是主合取范②若A,B是主合取范式，则A

是主合取范例

PQ

(

Q

(P

QR)是有三个命题变元P，Q，R的主合取范式定义1.4.7设B是主合取范式，A是合式公A

B，则称B是A的主合取范规 式的主合取范式为T 例1.4.2求的主合取范式解(P

Q)

((

Q)P)((

Q)(P

P)(QP)(P

R)(Q(QP)(PR)(Q

Q(R

(P

(QQ)

R)((

P)Q

Q

R)

QR)(P

Q

R)(P

Q

(0,2,4,5) 例1.4.3用真值表法

(PQ)

的主合取范PQR(PQ)(P00000011010001111000101011011111原式的合取范式为

M5 例1.4.4通过求合取范式，证明P(Q解

R)

(P

P(Q

QRM6Q(P

R)

QPRM6所以

(Q

(P

1.4定义1.4.8基本积的归纳定义为①文字是基本积②若A，B是基本积

A

是基本积例如

是基本积 1.4定义1.4.9析取范式的归纳定义如下①基本积是析取范式②若A，B是析取范式，则AB)

是析取范式例

P

P

，(P

Q

(P

是析取范式定义1.4.10设B是析取范式，A是合式公式。A

，则称B是A的析取范 1.4例1.4.5求

析取范式解

PQ))

QR

QR 1.4定义1.4.11n个命题变元的极小项PP PP

Pbn，

0或nin个变元可构成2n个不同的极小项ni例如3个变元P,Q,R可构造8个极小项m0:

m0:

Qm3:

Q

m4:

m5:

Qm6:

Q

m7:

Q 1.4定义1.4.12主析取范式的归纳定义如①极小项是主析取范式②若A，B是主析取范式，则A

是主析取范例

PQ

(P

Q

(P

QR)是有三个命题变元P，Q，R的主析取范式规定永假式的主析取范式为F 1.4例1.4.6

(PQ)

的主析取范式解(P

Q)

PQR

QR

Q

R

Q

1.4例1.4.7用真值表法求(P

Q)

R)的主析取范PQPQR(PQ)(P00000011010001111000101011011111式的主析取范式为m1m3m6 1.4

Q)

(1,3,6,7)

例1.4.8

Q)

R)

的主范解主合取范

Q)

R)

Q)

R)

Q)

R)(PQ)R 1.4(P

Q

P)(P

(P

Q

(P

QR)(P

Q

M3

主析取范式为(2,4,5,6,7)

习题4(4)5(2)23(1)4 1.5定义1.5.1

是一个推理规则，当且仅

A1

AnB

A2,,

称为推理规则的前提，B称为推规则的结论常用的推理规则附加规

A 1.5化简规

ABMP规则（假言推理

A,AB拒取析

AB,AB,B 1.5假合取引

AB,BAA构造性二

AB,

AB在推理的过程的任何时候都可以引入前 1.5定义1.5.2

H1

Hn

C，则称C是一H1,

的有效结论,记为H1H2,Hn例1.5.1设P：今天下雨，Q：这里通行困难，R：们按时到达。

(PQ)

R)

R证①P 前提②Q 前③P

前提⑤

③,④,拒取 1.5常用的证明方法前件明为