离散数学(第4讲)

冯伟森Email：fws365@05二月2023离散数学计算机学院2023/2/5计算机学院2主要内容1、联结词的完备集2、命题公式的蕴涵

1）九类蕴涵关系

2）蕴涵关系的基本性质1.4联结词的完备集2023/2/5计算机学院3前面我们已经介绍了最常见的6种逻辑联结词。他们都和自然语言中使用的联结词紧密相关，易于理解。不同联结词产生的真值表是互不相同的，根据对含两个命题变元的公式的解释方式看，共有2*2=4种不同的解释，因而公式的真值表相应有2*2*2*2=16种可能结果。对其中每一种真值表都应该存在相应的联结词。下面从真值表取值情况的角度定义几个新的联结词。2023/2/5计算机学院4PQ1

2

3

4

567

8

9

10

11

12131415161

1100

10

01011101110000001101101100110001010101101010101001001110010111000Q→PP→QPQPQPQ～Q～PP∧QＰ∨QTF下面是含两个命题变元的所有公式的真值表所能取得的情况：2023/2/5计算机学院5PQP↑Q111001000111定义

1.14

设P和Q是命题公式，分别称P↑Q和P↓Q为“与非”和“或非”命题公式。其相应的真值表如下所示：

2023/2/5计算机学院6PQP↓Q111001000001由真值表可以看出P↑Q～（P∧Q）,P↓Q～（P∨Q）2023/2/5计算机学院7

根据联结词↑和↓的定义，不难证明下面的等价式。①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q

～（～P∧～Q）P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q

～（～P∨～Q）P∧Q2023/2/5计算机学院8这些等价式告诉我们，↑可由∧和～表示出来，↓可由∨和～表示出来，反过来，↑和↓都可以单独表示出所有已知联结词，它们的这一性质使得在逻辑电路设计中只用一种门式电路元件就能实现任何电路功能，当然，元件的数量通常也显得更多。2023/2/5计算机学院9还有一个二元联结词“

”,称为条件否定，可以用下面的真值表定义：PQP

Q11100100

0

1

0

0显然，P

Q～(P→Q)2023/2/5计算机学院10PQ123456789101112131415161

1100

10

01011101110000001101101100110001010101101010101001001110010111000至此我们定义了9个联结词，其中1个一元联结词，8个二元联结词。那么，还能不能定义出新的联结词呢？下面是含两个命题变元的所有公式的真值表所能取得的情况：2023/2/5计算机学院11显然公式1是永真式，2代表矛盾式，3代表Ｐ∨Q，4代表Q→P,5代表P→Q，6代表P↑Q，7是P，8是Q，9代表PQ，10代表PQ，11代表～Q，12代表～P，13代表P↓Q，14代表Q

P,15代表P

Q，16代表P∧Q，可见，已定义的9个联结词就是全部可以定义的联结词。2023/2/5计算机学院12

定义

1.15设S是由某些联结词构成的集合，如果每个逻辑联结词的功能都能够由S中的联结词实现，则称S是联结词的一个功能完备集；进一步，如果去掉S中的任何一个联结词后，至少有一个联结词的功能不能由S中剩余的联结词实现时，则称S是逻辑联结词的一个最小功能完备集。2023/2/5计算机学院13根据定义,我们知道{↑}、{↓}是最小的功能完备集，那么{～，∨，∧}是不是最小功能完备集？由于P∨Q～(～P∧～Q)，可见∨可由{～，∧}表达；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表达，这说明{～，∨，∧}不是最小功能完备集，但是在实际应用中，普遍采用的功能完备集却是{～,∨,∧},这也是逻辑系统中最主要的3个常用联结词。2023/2/5计算机学院14§1．6

命题公式的蕴涵定义1.18设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记AB。定理1.11

ABiffA→B为永真式。注意：蕴含和条件联结词→是完全不同的。→是命题联结词，A→B是一个命题公式；是公式间关系符，AB不是一个命题公式，仅表示A，B间的蕴含关系。2023/2/5计算机学院15基本蕴含（关系）式（蕴含定律）I1：P∧QP，P∧QQ

I2:～（P→Q）P，～（P→Q）～Q

I3：PP∨Q，QP∨Q

I4：～PP→Q，QP→Q√I5：P∧（P→Q）

Q

假言推论√I6：～Q∧（P→Q）～P拒取式（否定式假言推论）√I7：～P∧（P∨Q）

Q析取三段论√I8：（P→Q）∧（Q→R）

P→R

假言三段论扩充法则简化法则2023/2/5计算机学院16基本蕴含（关系）式（续）√I9：（P∨Q）∧（P→R）∧（Q→R）

R

二难推论I10：（P→Q）∧（R→S）（P∧R）→（Q∧S）√I11：（PQ）∧（QR）

PR

等价三段论√I12：（P∨Q）∧（～P∨R）

Q∨R

归结原理

[解释：（～P→Q）∧（P→R）

Q∨R]2023/2/5计算机学院17蕴含关系的性质①自反性AA②反对称性:

如果AB，BA，

iffAB③AB且A为永真式，则B必为永真式2023/2/5计算机学院18

④传递性，如果AB，BC，则AC【证明】由已知条件AB，且BC，根据定理1.11

(A→B）∧（B→C）是永真式；再由假言三段论，应有（A→B）∧（B→C）

A→C；再根据性质3，A→C也必是永真式，即AC。■2023/2/5计算机学院19。⑤

如AB，AC，iffAB∧C【证明】“”由

AB

且

AC得到AB和AC都是永真式，于是（AB）∧（AC）也是永真式；但是，（AB）∧（AC）（～A∨B）∧(～A∨C)～A∨(B∧C)A→(B∧C)，所以A(B∧C)是永真式，即AB∧C。2023/2/5计算机学院20“”从证明过程看，性质5反过来也对，即由

AB∧C可以得到AB

且

AC。

⑥如AB，CB，则A∨CB⑦A∧BCiffAB→C

该性质是推理演绎中CP规则的基础⑧

A

Biff

A∧～B是矛盾式

该性质是反证法的基础2023/2/5计算机学院21定理1.12

ABiff

～B～A

该定理提供了逆向思维的基础2023/2/5计算机学院22例1-6.1考虑以下语句，并将其前提和结论符号化。1)、前提：

1.如果明天天晴，我们准备外出旅游。P→Q

2．明天的确天晴。 P结论：我们外出旅游。 Q上述例子可描述为：P→Q，PQ(假言推论)2)、前提：1.如果一个人是单身汉，则他不幸福。P→Q2.如果一个人不幸福，则他死得早。

Q→R结论：单身汉死得早。

P→R上述例子可描述为：

P→Q，Q→RP→R(假言三段论)2023/2/5计算机学院23例1-6.1(续1)3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提如下：

前提：

1.凶手为王某或陈某。

P∨Q 2.如果王某是凶手，则他在作案当晚必外出。

P→R 3.王某案发之晚并未外出。

～R结论：陈某是凶手。

Q则上述例子可描述为：

P→R，～R～P

(拒取式)

P∨Q，～PQ

(析取三段论)2023/2/5计算机学院24例1-6.1(续2