友情提示：不要泄漏偶否则后果很严重 你

承担不来

离散

一. 名词解释：

a) 命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。

b) 对偶式（没讲过可不写）：在仅含有联结词与（∧）、或（∨）、非（┐）的命题公式A 中，将∨换成∧，∧换成∨，若A 中还含有0或1，则还需将其中的0换成1，1换成0，所得到的新命题公式A*就是A 的对偶式。

c) 主析取范式：所有简单合取式都是极小项的析取范式 d) 前束范式：具有形式 B x Q x Q x Q k k 2211 的一阶逻辑公式

其中Q i （1≤i ≤k) 为∀或∃，B 为不含量词的公式。

e) 谓词：用来刻画个体词性质及个体之间相互关系的词。

二. 填空：

a) 自反 传递.

b) 23

真值表 1 c) 无回路 2叉树

d) 21

e) （R(a)∧R(b)）→（S(a)∨S(b)）

f) p ⌝

三. 选择：

1~5：A 、A 、C 、D 、B

6~10: D 、D 、B 、B 、D

四. 证明：

1. 化简：（A-B-C ）⋃（（A-B ）⋂C ）⋃（A ⋂B-C ）⋃（A ⋂B ⋂C ） 解：化简如下：

（A-B-C ）=(A⋂B ⋂C )

（（A-B ）⋂C ）=(A⋂B ⋂C)

（A ⋂B-C ）=（A ⋂B ⋂C ）

(A⋂B ⋂C ) ⋃(A⋂B ⋂C) ⋃（A ⋂B ⋂C ）⋃（A ⋂B ⋂C ） =((A⋂B ) ⋂(C ⋃C)) ⋃((A⋂B) ⋂(C ⋃C)) =(A⋂B ) ⋃(A⋂B)

=A⋂(B ⋃B)

=A

2. 证明命题恒真：((P→Q) ∧(Q→R)) →(P→R) 解：证明如下：

方法一：⇔┐((┐P ∨Q) ∧(┐Q ∨R)) ∨(┐P ∨R) ⇔┐（((┐P ∨Q) ∧┐Q) ∨((┐P ∨Q) ∧R) ）∨(┐P ∨R) ⇔┐((┐P ∧┐Q) ∨(┐P ∧R) ∨(Q∧R)) ∨(┐P ∨R) ⇔┐(┐P ∧┐Q) ∧┐(┐P ∧R) ∧┐(Q∧R) ∨(┐P ∨R) ⇔(P∨Q) ∧(P∨┐R) ∧(┐Q ∨┐R) ∨(┐P ∨R)

⇔(P∨(Q∧┐R)) ∧(┐Q ∨┐R) ∨(┐P ∨R) ⇔(P∧(┐Q ∨┐R)) ∨((Q∧┐R) ∧(┐Q ∨┐R)) ∨(┐P ∨R) ⇔(P∧┐Q) ∨(P∧┐R) ∨(Q∧┐R ∧┐Q) ∨(Q∧┐R ∧┐R) ∨(┐P ∨R)

⇔(P∧┐Q) ∨(P∧┐R) ∨┐R ∨Q ∨┐P ∨R ⇔P ∨Q ∨P ∨R ∨┐R ∨┐P

⇔Q ∨1

⇔1

方法二：由传递性可知⇔(P→R) →(P→R) ⇔1

3. 形式演绎法：{P→Q ，R →S ，P ∨R}蕴涵Q ∨S 。 解：

前提：P →Q ，R →S ，P ∨R

结论：Q ∨S

① P ∨R

前提引入 ② （┐P ）→R

由1得 ③ R →S

前提引入 ④ （┐P ）→s

2、3 ⑤ p ∨S

4 ⑥ （┐S ）→p

5 ⑦ P →Q

前提引入 ⑧ （┐S ）→Q

6、7 ⑨ Q ∨S 8结论

4.<I， > a b=a+b-2 ; 证明是群。 证明：

① 封闭性：

∀a 、b ∈I 则a+b-2∈I 则a b ∈I 。封闭

② 可结合：

∀a 、b 、c ∈I

则（a b ） c=（a+b-2）+c-2=a+（b+c-2）-2=a （b c ）可结合

③ 有幺元：

若∀a 、e ∈I 且a e=a 则 a e=a+e-2=a ⇔e=2 有幺元 ④ 有逆元：

若∀a 、b ∈I 且a b=2 则a b=a+b-2=2 ⇔a 1-=b=4-a 有逆元

综上所述：封闭、可结合、有幺元、有逆元则<I， >为群。

5.R ⊆A*A 则R 自反⇔I A ⊆R 。

证明：

若<x,x>∈I A 则<x,x>∈R ∴I A ⊆R 。

若I A ⊆R 则<x,x>∈I A 则<x,x>∈R 则有自反定义可得R 是自反的。

五. 综合应用：

1.<S， >是可交换独异点，T 为S 所有幂等元集合 ，则<T， >