离散数学下册自测题及答案

（一）填空题。（36分）

1.我们规定逻辑连接符¬、∧、∨、→、⇆的运算次序依次是_____，____，____。

2.设G 是公式，P1，P2，…，Pn 是G 中的所有变量，给P1，P2，…，Pn 任意指定一组真值，则称作的G 一个_____，G 在它的所有_____下的真值所成的表格称为_____。

3.设G 是恒假的当且仅且当G 在其所有解释下均为_____，当且仅当G 主析取范式为_____，主合取范式包含所有的_____。

4.合取范式是恒真的当且仅当构成它的每一个_____都至少包含一个_____。析取范式是恒假的当且仅当构成它的每一个_____都至少包含一个_____。

5.任意命题公式都存在与之等价的_____，都有唯一的与之等价的_____。

6.设A1，A2，…，An，B 是公式，A1∧A2∧…∧An→B 恒真，则称A1，A2，…，An______B，B 是A1，A2，…，An 的_____，也称从A1，A2，…，An_____B，记为_____。

（二）判断题。（36分）

1.使用真值表判断下列公式是否是恒真式、恒假式或可满足式：

(1)(P⇆Q)∧¬(Q→R);

(2)Q∨¬(¬(P∨Q)∧P);

(3)¬(P→(Q→P))⇆¬(P→(P→¬Q))。

2.使用真值表判断下列每组公式中前一个公式与后一个（或二个）公式是否是等价的，为什么？

(1)P→(Q→R),Q→(P→R),¬R→(Q→¬P);

(2)¬(P⇆Q),(P∨Q)∧¬(P∧Q),(P∧¬Q)∨¬(P∧Q);

(3)P→(Q∨R),(P∧¬Q)→R。

3.使用真值表判断下列每组公式中前一个公式是否可以推出后一个公式？ 为什么？

(1)(P→Q)→(Q→R),(P→R);

(2)P∧Q∨R,(P∧Q)∨(P∧R);

(3)Q→R,(P∨Q)→(P∨R)。

4.判断下列公式哪些是子句、短语、析取范式、合取范式、主析取范式、主合取范式？

① P∨¬Q;② ¬P∨Q∨¬R;

③ ¬P∧¬Q;④ P∧¬P∧¬Q∧¬R;

⑤ (P∨¬Q)∧¬(P∨Q∨¬R);

⑥ (P∨¬P∨¬Q∨¬R)∧(Q∨R∨¬R);

⑦ (P∧¬Q∧¬R)∨¬(Q∧¬P)∨(Q∧¬R);

⑧ (¬(P∧¬Q)∧¬R∧Q)∨(R∧¬R);

⑨ ¬(P∨Q)∧¬(Q∨P);

⑩ ¬(P∧¬Q∧R)∨¬(P∧Q∧R)∨(P∧Q∧¬R)∨(P∧Q∧R)。

5.求¬（P→R）∧（P⇆Q）的主合取范式和主析取范式。

6.求范式判断公式（P→Q）→P 是否是恒真式、恒假式或可满足式？

（三）计算与证明题。（28分）

1.写出下列各式的真值表。

(1)¬P∧Q;(2)(P→Q)→(P∧Q)。

2.证明：命题P∨¬（P∧Q）是恒真式。

3.证明：德·摩根规则：

¬(P ∧Q)⇔¬P ∨¬Q

4.证明：Q→（P∨（P∧Q））⇔Q→P。(www.xing528.com)

【自测题答案】

（一）填空题

1¬.;∧、∨;→、⇆

2.解释；解释；真值表

3.假；F；极大项

4.子句；互补对；短语；互补对

5.析取范式和合取范式；主析取范式和主合取范式

6.蕴涵；逻辑结果；可以推出；A1，A2，…，An⇔B

（二）判断题

1.(1)

是可满足的

(2)

是恒真的

(3)

是恒假的

2.(1)

是等价的

(2)

是等价的

(3)

是等价的

3.(1)

可以

(2)

不可以

可以

4.①②是子句，③④是短语，①②③④⑦⑧⑩是析取范式，①②③④⑤⑥⑨是合取范式，①②⑨是主合取范式，③⑩是主析取范式。

5.

主析取范式为：（P∧Q∧R）∨（P∧Q∧¬R）∨¬（P∧¬Q∧R）。

主合取范式为：¬（P∨Q∨¬R）∧¬（P∨Q∨R）∧（P∨¬Q∨¬R）∧（P∨¬Q∨R）∧（P∨Q∨R）。

6.（P→Q）→P⇔¬¬（P∨Q）∨P⇔（P∧¬Q）∨P⇔P，是可满足的。

（三）计算与证明题

1.（1）解：

（2）解：

2.证明：构造P∨¬_（P∧Q）的真值表

3.证明：构造真值表：

4.证明：构造真值表：