从上节真值表和命题的等价公式推证中可以看到，有些命题公式，无论对分量作何种指派，其对应的真值都为t或都为f，这两类特殊的命题公式在今后的命题演算中极为有用。为此，下面做详细的讨论。
定义1-5.1 给定有命题公式，若无论对分量做怎样的指派，其对应的真值为t，则称该命题公式为重言式或永真公式。
定义1-5.2 给定一命题公式,若无论对公式再哟怎样的指派,其对应的真值永为f,则称该命题为矛盾式或永假公式.
定理1-5.1 任何两个重言式的合取或析取,仍然是一个重言式.
证明设a和b为两个重言式,则不论a和b的分量指派任何真值,总有a为t,b为t,故a∧bt,a∨bt.
定理1-5.2一个重言式,对同一分量都用任何合式公式置换,起结果仍为一重言式.
证明由于重言式的真值与分量的指派无关,故对同一分量以任何合式公式置换后,重言式的真值仍永为t.
对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果.
例题1证明（（p∨s）∧r）∨┓（（p∨s）∧r）为重言式.
证明因为p∨┓pt,如以（（p∨s）∧r））置换p即得
（（p∨s）∧r））∨┓（（p∨s）∧r）t
定理1-5.3设a、b为两个命题公式,ab当且仅当ab为一个重言式.
证明若ab,服务器托管网则a、b有相同真值,即ab永为t.
若ab为重言式,则ab永为t,故a、b的真值相同,即ab.
例题2证明┓（p∧q）
证明由上节例题4中表1-4.4可知,┓（p∧q）
┓（p∧q）
我门知道,联结词可以用→来表达.即：ab（a→b）∧（b→a）
下面讨论a→b的重言式.
定义1-5.8当且仅当p→q是一个重言式时,我们称“p蕴含q”,并记作pq.
因为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）
因此要证明pq,只需证明┓q┓p,反之亦然.要证pq,即证p→q是重言式。对于p→q来说,除p的真值取t,q的真值取f这样一种指派时,p→q的真值为f外,其余情况,p→q的真值为t.故要证pq,只需对条件命题p→q的前件p,指定真值为t,若由此推出q的真值亦为t,则p→q是重言式,即pq成立;同理,如对条件命题p→q中,假定服务器托管网后件q的真值取f,若由此推出p的真挚为f,即推出了┓q→┓p,故pq成立.
表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∧qp |
1 |
|
p∧qq |
2 |
|
pp∨q |
3 |
|
┓pp→q |
4 |
|
qp→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 |
|
(pq)∧（rs）（pr） |
14 |
就象联结词和→的关系一样,等价式与蕴含式之间也有紧密的联系.
定理1-5.4设p、q为任意两个命题公式,p q的充分必要条件是pq且qp.
证明若pq,则pq为重言式，因为pq（p→q）∧（q→p）,故p→q为t且q→p为t,即pq,qp成立.反之,若pq且qp,则p→q为t且q→p为t,因此pq为t, pq是重言式,即pq.
这个定理也可作为两个公式等价的定义.
蕴含有下面几个常用的性质:
（1）设a、b、c为合式公式,若ab且a是重言式,则b必是重言式.
证明因为a→b永为t,所以,当a为t时,b必永为t.
（2）若ab,bc,则ac,即蕴含关系是传递的.
证明由ab,bc,即a→b,b→c为重言式.所以（a→b）∧（b→c）为重言式.
由表1-5.2的(11)式,（ab）∧（b→c）a→c,故由性质(1),a→c为重言式.即ac.
（3）若ab,且ac,那末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）若ab且bc,则a∨cb.
证明 因为a→b为t,c→b为t,故（┓a∨b）∧（┓c∨b）为t.
即(┓a∨┓c)∨b为t或a∨c→b为t.
所以 a∨cb
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
文章目录 概述 背包问题 01背包问题： 代码示例 部分背包 代码示例 完全背包 代码示例 多重背包 代码示例 总结提升 概述 动态规划（Dynamic Programming）是一种通过将问题划分为相互重叠的子问题来解决问题的算法思想。其核心思想是通过保存已…
