计算机数学1 -5 重言式与蕴含式

1-5重言式与蕴含式

一1.定义：公式A中分量作任何指派，其值皆为真，则称A为

重言式或永真式。公式A中分量作任何指派，其值皆为假，

则称A为矛盾式或永假式。

2.重言式也就是上节课中遇到的永真式，矛盾式即永假式,

这两类公式在今后的命题演算中极为有用，下面我们讨论

重言式的一些性质。对矛盾式也有类似的性质。

定理：若A和B是重言式，则A/\B,AvB都是重言式。

证：A和B为重言式，则不论A和B的分量指派何真值，总

有A为T,B为T,A/\B<=T,A\B口;故A/B,A\B为重言式。

1-5重言式与蕴含式

定理：若A是重言式，对A中同一分量用某一合式公式替换到/；

则才也是重言式。

证：由A为T,与A中分量的指派无关，将A中分量均用某一公式

替换为N；则/为「所以/也是重言式。

以上两定理是重言式的性质。

例:Pvp^重言式，pvP^iT,P以((PS4W)替换,

贝ij((PS)41)v收S)用尸T。

注意：必须将所有的变量作替换。

1-5重言式与蕴含式

3.定理A是重言式,iffA3（即/N的重言式）。

证：FANB是重言式，即A.B同为T或同为F,所以2B（真

值相同）

U若AoB,则A与B同为T或同为F。所以A会B永为T,即

ANB是重言式。

二1.定义：若上凶（条件式）是重言式，则称P蕴含Q,记作

P0（蕴含式），条件式是单向的，一共有四种条件式

PTQ原式QfP逆换式

[P—Q反换式iQfP逆反式

1-5重言式与蕴含式

pQ-iP「QPfQQT-QfP

TTFFTTTT

TFFTFTTF

FTTFTFFT

FFTTTTTT

可以看出①—Q与QfP不是等价的②而条件式与逆反式是相互

等价的

P">Qo-QfTQTo-P--Q

1-5重言式与蕴含式

2.因而证明P=Q就可有两种不同的证明方法。

要证PnQ,只要证P-Q是重言式(即

P=F时,Q=T

P=T时,Q=T时,Q为T

因而方法(1)若P=T能推出Q为T.则—Q=T,所以人Q

(2)由P-兔0~^Q——1户可得

P=。o=」P,若=丁能推出

「尸为T即可。

若。=尸时能推出P=尸则P=＞。也成立

举例说明

1-5重言式与蕴含式

例：推证―\QA(P―>Q)=>―\P

证1.设—。)为T,则「。为丁目/一。为了二。为

F且PfQ为T，故尸为尸,・,.「？=丁.从而蕴含式成立。

证2.设「尸为冗则尸为T\分情况讨论如下

(1).0=TT=F\则A(PfQ)=F.

(2).0=尸，P_0=尸，J.「0人-0)=F.

故成立.

1-5重言式与蕴含式胆

可看出P=Q含义：若P为真，则Q必为真，P条件=结论Q

另夕卜，对于。人。口《可写作乙。=凡（证法）

书上P21表1—5.2有14个蕴含式，可用上述方法证明，这

里就不讲了，请自己看学会应用它们.

我们已经知道o（P-人（Q-P）

（真值表）P15例5

3.类似的，我们介绍了=>,它与。有什么样的关系呢？

1-5重言式与蕴含式

定理：P°Q,iffP=Q且Q=P

证：=PoQ

/.P「.PfQ与Q-P是重言式，

.•.（PnQ）且（QnP）

=P=。且、3,所以PTQ与QT是重言式

所以（PTQ）A（QT）也是重言式，故

P^H|■:言式，PoQ。

4.蕴含式有如下一些性质：

1）：若A=B,且A是重言式，则B也是重言式.

1-5重言式与蕴含式

证：/^=T,A=T,所以B=T故B是重言式.

(2)若A=>B,B=>C,贝l」AnC(传递性)

证：TV>B=T,B-C=T,所以(A-B)7B->C)=T

又(A—B)A(B^C)=A-C,所以A-)C=T

故A=C.

(3)若A=>B,且AnC,则A^BAC

(4)若QB,且C=B则AvC=B.

这两个性质书上有证明，不介绍了。

1-6其他联结词

我们已定义了「，人~一结词，但这

些联结词还不能很好的直接表达命题间的联系

，，我们再定义四个联结词，使命题间的联系

表达更明朗化

1.不可兼析取（异或）

定义：己。是两个命题组成，称作尸和。的不可兼析取

记作人。,切”。不为相同真值时，鼠Q为T,否则为尸

1-6其他联结词

尸

给出了真值表，才能唯一

确定一个联结词

1-6其他联结词

\/有必下性质：—

(X).JP^7Qo?交换彳聿

(2>(尸A<=>尸结作彳聿

(3).尸A<=>(?/\2)，(尸人衣)_

一人对于v的分配律

(4).?\/2O(?人［2)X/(「尸A2)

/u、“一八它是双条件的否定，而不是

(5)0二。一「(尸名

(6).PyP<=>F„F^yJP<=>尸)T7P<=^>―\尸

1-6其他联结词

对于\/有如下定理：

定理：若凡则区ROP,且

P7Q'R是一矛盾式。

证：P\/R<=>Pv(Fv2)0(PvP)v2=F\^Q<=>Q

其余类似可证

1-6其他联结词

2.条件否定P,Q是两个命题公式，称做P和Q的条件否定，记作

PjQ"否定条件式”，当且仅当P为T,Q为F时为T,

其余为F。与我们定义的一正好相反。

PQP-^Q

TTF

TFT

FTF

FFF

p——CfQ)

1-6其他联结词

3.与非P和Q的与非记作尸个Q当且仅当P和Q的真值都为T时

尸个4F,其余为T。

PQ

TTF

TFT

FTT

FFT

p个。。人。）

1-6其他联结词

对于“个”有如下几个性质：

（1）.FTFo^（FAF）oY

（2）.（尸个。）个（P个。）。「（尸个。）。尸人。

4.或非P和Q的或非记作尸J。，当且仅当P和Q的真值都

为F时pjQ的真值为T,否则八。的真值都为F。

PQ\P^Q

TTF

尸「（尸\/Q）

TFF

FTIF

FFT

1-6其他联结词

对”卜于有如下性质：

(1).FJPo")oY

(2).(PjQ)J(PjQ)o「(PjQ)oPvQ

⑶.(尸)。)〃。」。)=(「夕)」「。=月人。

除了以下几个联结词外，没有其他联结词了，也就是这九个联结词

足够表达命题关系了。我们命题公式的定义就可以推广为由这九个

联结词依照一定规律构成的。

两个命题变元，可构成24个不等价的命题公式。(对于两个命

题变元，命题公式的真值情况即真值的取值数目共有24，恰

可构成22一个不等价的命题公式；

1-6其他联结词

对于n个命题变元，命题公式的真值情况即真值的取值数目共

有2〃个，恰可构成2?‘个不等价的命题公式，即n个命题变元

组成不等价的命题公式个数为22'个。）

☆对22个真值情况，每一种均可取｛T,F｝两种，所以

共有22个命题公式，又只要有一个真值取值不同，

就不等价，所以有个不等价的命题公式。

1-6其他联结词

1-6其他联结词

PQ联结10111213141516

词9

TTTFTFTFTF

TFTFFTFTTF

FTTFTFFTFT

FFFTTFTFTF

P7QQ^-^P

尸JQP^QP~QQTP

1-6其他联结词

两个命题变元至多有16个联结词，但这里有九个就够用了。

(除T,F及变元本身外)

又⑴■护-Q)A(Q-P),■可由△与f表示

(2)p—>Q―p、Q—>—由一।与

(3)P人Qo「JPxz-nQ)

P7—1(—iP/\—人~^^7口JHR—i才目JEILZjo

~I,Z\,,>，,\/}^^{—I，/\}表^1^o

而尸D0O「(尸尸—£_^QO「(尸—。)

1-6其他联结词

尸」（PV。）

所以这四行可由前五个联结词表示，从而几个联结词可由

｛「'｝或｛-A底示，而｛「｝,｛A｝,卜｝或｛A~｝不能表示上述几个

联结词。

因为（1）二元联结词不能用一元联结词表示，所以｛1｝不

是最小联结词。

（2）—能否由△或V表达？不能

<>

良设-P^,（/）A7?）A,,•A•••）

或（…―.、），右边分量2凡■■均取值为T,则合成

为T,而左边为F,矛盾

1-6其他联结词

-人）■或｛「》｝才是最小联结词组。

又-1Pop个。

Pv0o（pTp）T（0Te）所以他也是最小联结词组

同理「popJ尸尸八00（尸（尸），（0，0）所

以｛】｝也是最小联结词组

所以我们共介绍的几个联结词，可由｛「,△｝或｛「'｝，｛»，"｝

表达出来。

书83（4）逆换式与逆反式表示：

（a）P：天下雨Q：我去

原命题:Pf~^Q

1-6其他联结词

逆换式：—尸叙述：若我不去，则天下雨

逆反式：「p我去则天不下雨

(b)仅当你走我将留下。

P：你走Q：我留下

原式：QTP

PQ原命题Q—>

TTTT

TFTT

FTFF

FFTT

1-6其他联结词

逆换式：P-Q你走则我留下

逆反式「?一「。你不走，我就不留下

（c）:P：我能获得更多帮助Q：我能完成这个任务

原式：-iP->-\Q

逆换式：-'Q-—

逆反式：QfP如果我能完成这个任务，则我能获

得更多帮助

巴9（4）/个。。「（尸人。）0「（（「』?）4（。』。））

o（（尸J尸）J（QJQ））J（（?J尸）J（。J。））

依据：Y0尸JP

尸/\Q=（尸J尸）J（QJQ）

1-6其他联结词

(6)，，仅“不服从结合律

仅以”仅为例：(尸T0)TR0「(「(P△°)A7?)o(尸A。)vT?F

PT(QTH)oTPA「(QAR))oV(°AA)T

如P为F,Q为T,R为T,所以不等价。

1-6其他联结词

我们在介绍命题的十个定律时，发现除对合律外，其

它定律都是成对出现的。（交换律、结合律、幕等律、分配

律、De・Morgen律、同一律、否定律、吸收律、零律）把这

样公式称为具有对偶规律。

比如：De・Morgen律这样的公式称为具有对偶规律

」（P八Q）o5x/「Q,「（P-5人］Q

对偶式也是一种重要的式子，今天我们学习对偶式与范式

1-7对偶与范式

我们分两部分学习，先学习对偶式

-、1.定义在给定的命题公式中，将联结词▽换成△，将△换

成V,若有特殊变元F和T亦相互取代，所得公式

A*称为A的对偶式。显然A也是A*的对偶式

（必须将A先化为仅含有一S人形式后再变，遇到其他联结

词只能先化为一

N——>XX/十

4XX——>^4务

-F—>T—十

NT—>尸N*

1-7对偶与范式

例如：N=((P▼Q)八R)▼T

对偶=((FA2)v7?)AF

又如N=P个。0「(P'Q)

，0「(八0)

o尸J0

注意：“「”不变

2.对偶有如下定理。

设A和A*是对偶式，V，U，•一，丹是出现在A和A*中的原

子变元，则

1-7对偶与范式

TC，多・・・，A）o/*（M，/,・・・,戈）

4（W，/,・・・,^）oY*C，...M）

证：由德摩根定律

」（八Q）o「P「Q

故—4（匕多・・・,匕）=/*（«,7^・・，•）

同理/（超,「鸟，…，土）0-4*（匕鸟，…,与）

对公式A,可化为与之等价的只含（形式，由DM律，将

A中分量改为否定，取对偶后,正好与之否定等价。

1-7对偶与范式

3.定理

设耳,P29...9匕是出现在公式/和6中的所有原子变元，如果^9B,A*QB\

证：若力=丛所以）■言式。设46中出现的所有变元为6,

即/（6,8,...,修）^^■^■^,..4）是重言式，而对重言式中同一分量用任何公式置换

结果仍是重百式，所以/（-\P1,-1舄，…,-\Pn）--£）是重百式。

即/（—i4！匕）=6（—!4,—1巴,...,—！匕）,所以—i/（|,g,...，E?）=-15（［,%...,£）

%*（1,%...,£）=6*（4,鸟,...,匕）,所以/*=B\

对于一公式4我们可有多种与之等价的式子，为了找到一个形式上比较规范的公式,

引进范式。

二、对偶性比较简单，下面我们着重讨论范式。

首先为什么引进范式（规范的式子），因为对一个公式而言,

1-7对偶与范式

可有多个与之等价的式子，因而对于两个公式，我们一般很难

看出它们是否等价，但如果我们有一种范式，使得每公式对应

的这种范式是唯一的，则判断两公式A、B是否等价，只须将它

们均化为这种范式，看是否一样就行了。这种范式我们称为主

范式。

为介绍主范式我们首先引进范式的概念。

范式、主范式主析取范式（小项）

主合取范式（大项）

1.定义⑴/具有下列形式：4八4△・・・△4521）且4是变元或它的否定所组成的

析取式,则称/是一个合取范式。

1-7对偶与范式

(2)Z具有下列形式：4vA2V...V47(^1)

且4是命题变元或它的否定所组成的

合取式，则称/是一个析取范式。

1-7对偶与范式

女口：N=（尸X/「0X/R）八（「尸y0）—I。

4力24

力是一合取范式。又如「Pv（PAQ）v（P△［。AA）是一析取范式。

但若公式仅含有一项如P△Q,则既可看作析取式,又可看作合取式。

任一公式/可用｛「,▽,A｝表示，把一个公式化为合取式或析取范式是可行的

步骤：1.将所有的联结词化归为JA及

2.利用德摩根律将否定移至各变元前面。

3.用分配律、结合律将之化为合取范式或析取范式。

例1.（?△-R））TS化为合取范式。

原式o（/）△（「Qv火）…S。］（。人（「Qv£0vSo「八vmvS

o-tPv（Q△「X）vSo（「PvS）v（Q△［X）oJ。vSvQ）△（「PvSv」火）

1-7对偶与范式雕

例2.「（？vQ）的析取范式。

A5）V（—lAA-15）

原式=（「（？V2）A（FA。））V（（Fve）A」（？AQ））

=（「？△「。△P△Q）v（（八。）△（「Pv「Q））

=（「P-Q八P八0）74P「P）7（Q八a/Q）71QLQ»

FFF

O（QA「P）V（PA「Q）

化时思想，明确目标,析取。V0...V。合取。A。…A（）

一个公式化成合取或析取范式不是唯一的。如

1-7对偶与范式

PA(2VA)O(PA2)V(PAA)O(PVP)A(2VP)A(PVA)A(2VA)

合取析取合取

所以不是唯一的

2.为了使任一公式都有唯一的公式与之相对应，引进小项。

我们下面讨论主范式。先讨论主析取范式。

1-7对偶与范式

a.定义n个命题变元，由变元和它的否定构成的一个合

取式，要求每个变元和其否定不能同时出现，且两者之一

必须出现且仅出现一次，这样的合取式称为小项或布尔合

取。

两个命题变元p,1P八Q,PlQT八QT「Q

三个命题变PAQ八R「PAQAR

元P、Q、R

P/\Q/\―\R―\P/\Q/\―iR

8个小项

PA—\QAR-iPA—\QAR

P△一八一iR―\PA―\QA—iR

1-7对偶与范式

n个变元有2,个小项。

对于两个命题元，列真值表看看，每个小项有何特点?

F

F

F

T

可以看出（1）各个小项不等价。

（2）每个小项只有一组指派，使它为T,其他均为

Fo且可由这组指派写出小项。

对三个变元的小项同样有上述性质表1—7.21F

1-7对偶与范式

b.对小项，我们可以用二进制进行编码。

P/\Q/\-.R=m^=m

A—10=x(y

P1uz.

PA—\OAR=m1inU1,=3

P/\―\Q/\―\R—m.g

―PA―\Q—munun=mun

P/\O/\—\R=m=

1一命题变元，0—命题否定nUin1uz

任给一个编号可写出对应小项：

—\PA—\O/\R="UcmU1=Tn.1

PA—\Q/\―iR=mn(JnUnU=U

1-7对偶与范式

C.小项有如下性质：