离散
初三 散文 1670字 55人浏览 我是麦子6

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

承担不来

离散

一. 名词解释:

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, >