离散数学 第一章 命题逻辑 15重言式与蕴含式

从上节真值表和命题的等价公式推证中可以看到,有些命题公式,无论对分量作何种指派,其对应的真值都为t或都为f,这两类特殊的命题公式在今后的命题演算中极为有用。为此,下面做详细的讨论。

定义1-5.1 给定有命题公式,若无论对分量做怎样的指派,其对应的真值为t,则称该命题公式为重言式或永真公式。

定义1-5.2 给定一命题公式,若无论对公式再哟怎样的指派,其对应的真值永为f,则称该命题为矛盾式或永假公式.

定理1-5.1 任何两个重言式的合取或析取,仍然是一个重言式.

证明设a和b为两个重言式,则不论a和b的分量指派任何真值,总有a为t,b为t,故a∧bût,a∨bût.

定理1-5.2一个重言式,对同一分量都用任何合式公式置换,起结果仍为一重言式.

证明 由于重言式的真值与分量的指派无关,故对同一分量以任何合式公式置换后,重言式的真值仍永为t.

对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果.

例题1证明((p∨s)∧r)∨┓((p∨s)∧r)为重言式.

证明 因为p∨┓pût,如以((p∨s)∧r))置换p即得

((p∨s)∧r))∨┓((p∨s)∧r)ût

定理1-5.3设a、b为两个命题公式,aûb当且仅当a«b为一个重言式.

证明 若aûb,则a、b有相同真值,即a«b永为t.

若a«b为重言式,则a«b永为t,故a、b的真值相同,即aûb.

例题2证明┓(p∧q)û (┓p∨┓q)

证明 由上节例题4中表1-4.4可知,┓(p∧q)« (┓p∨┓q)为重言式,故据定理1-5.3

┓(p∧q)û (┓p∨┓q)

我门知道,联结词«可以用→来表达.即:a«bû(a→b)∧(b→a)

下面讨论a→b的重言式.

定义1-5.8当且仅当p→q是一个重言式时,我们称“p蕴含q”,并记作pûq.

因为p→q不是对称的,即p→q与q→p不等价,对p→q来说, q→p称为它的逆换式;

┓p→┓q称为它的反换式; ┓q→┓p称为它的逆反式,它们之间的关系如表1-5.1所示.

从表1-5.1中看出:(p→q)û(┓p→┓q)
(q→p)û(┓q→┓p)

因此要证明pþq,只需证明┓qþ┓p,反之亦然.要证pþq,即证p→q是重言式。对于p→q来说,除p的真值取t,q的真值取f这样一种指派时,p→q的真值为f外,其余情况,p→q的真值为t.故要证pþq,只需对条件命题p→q的前件p,指定真值为t,若由此推出q的真值亦为t,则p→q是重言式,即pþq成立;同理,如对条件命题p→q中,假定后件q的真值取f,若由此推出p的真挚为f,即推出了┓q→┓p,故pþq成立.

表1-5.1

p

q

┓p

┓q

p→q

┓q→┓p

q→p

┓p→┓q

t

t

f

f

t

t

t

t

t

f

f

t

f

f

t

t

f

t

t

f

t

t

f

f

f

f

t

t

t

t

t

t

     

例题1推证┓q∧(p→q)þ┓p

证法1假定┓q∧(p→q)为t,则┓q为t,且(p→q)为t.有q为f, p→q为t,则必须p为f,则┓p为t.

证法2假定┓p为f,则p为t.
(a):若q为f,则p→q为f,┓q∧(p→q)为f.
(b):若q为t,则┓q为f,┓q∧(p→q)为f.
所以┓q∧(p→q)þ┓p成立.

表1-5.2所列各蕴含式都可如上述推理方法证明:

表1-5.2

p∧qþp

1

p∧qþq

2

pþp∨q

3

┓pþp→q

4

qþp→q

5

┓(p→q)þp

6

┓(p→q)þ┓q

7

p∧(p→q)þq

8

┓q∧(p→q)þ p

9

┓p∧(p→q)þq

10

(p→q)∧(q→r)þp→r

11

(p∨q)∧(p→r)∧(q→r)þ r

12

(p→q)∧(r→s)þ(p∧r)→(q∧s)

13

(p«q)∧(r«s)þ(p«r)

14

就象联结词«和→的关系一样,等价式与蕴含式之间也有紧密的联系.

定理1-5.4设p、q为任意两个命题公式,pû q的充分必要条件是pûq且qûp.

证明 若pûq,则p«q为重言式,因为p«qû(p→q)∧(q→p),故p→q为t且q→p为t,即pþq,qþp成立.反之,若pþq且qþp,则p→q为t且q→p为t,因此p«q为t, p«q是重言式,即pûq.

这个定理也可作为两个公式等价的定义.

蕴含有下面几个常用的性质:
(1)设a、b、c为合式公式,若aób且a是重言式,则b必是重言式.
       证明 因为a→b永为t,所以,当a为t时,b必永为t.
(2)若a
þb,bþc,则aþc,即蕴含关系是传递的.
       证明 由aþb,bþc,即a→b,b→c为重言式.所以(a→b)∧(b→c)为重言式.
   由表1-5.2的(11)式,(a®b)∧(b→c)þa→c,故由性质(1),a→c为重言式.即aþc.
(3)若aþb,且aþc,那末aþ (b∧c).
       证明 由假设a→b, a→c为重言式.设a为t,则b、c为t,故b∧c为t.因此,a→(b∧c)为t.
       若a为f,则b∧c不论有怎样的真值,a→(b∧c)为t.
 所以, a
þ (b∧c)
(4)若aþb且bþc,则a∨cþb.
       证明  因为a→b为t,c→b为t,故(┓a∨b)∧(┓c∨b)为t.
       即(┓a∨┓c)∨b为t或a∨c→b为t.
       所以   a∨c
þb

原文地址:https://www.cnblogs.com/emanlee/p/1799097.html