xmu 离散数学 卢杨班作业详解【1-3章】

第一章 命题逻辑

常用latex数学公式

符号	代码
$\vee$	$\vee$
$\wedge$	$\wedge$
$\to$	$\rightarrow$
$\Rightarrow$	$\Rightarrow$
$\Rightarrow$	$\Rightarrow$
$\iff$	$\Leftrightarrow$
$\leftrightarrow$	$\leftrightarrow$
$\neg$	$\neg$

$\underset{R_2\to R_2-R_1}{\overset{Substractrow1fromrow2}{\to }}(A_3)$

$A\underset{下方文字}{\overset{上方文字}{\to }}B$

1.

(12)

p:4是2的倍数 q:4是3的倍数

原命题$\iff$p$\vee$q

是复合命题

(16)

是简单命题

(18)

p:4是素数

$\Gamma$p是复合命题

4.

(1)

p:今天是1号 q:明天是2号

原命题$\iff$p$\to$q

1. p为真，q也为真

   p$\to$q为真

2. p为假，q也为假

   p$\to$q为真，p$\to$q为重言式

(2)

p:今天是1号 q:明天是3号

原命题$\iff$p$\to$q

1. p为真，则q为假

   则p$\to$q为假

2. p为假则

   q无论真假，p$\to$q都为真

5

(1)

p:王威为100米冠军 q:王威为200米冠军

p$\wedge$q

(3)

p:天气冷 q:老王来了

p$\wedge$q

(6)

p:天下雨 q：他乘车上学

p$\leftrightarrow$q 或 (p$\wedge$q)$\wedge$($\neg$p$\wedge$$\neg$q)

(8)

p:经一事 q:长一智

$\neg$p$\to$$\neg$q

6

(1)p$\vee$(q$\wedge$r)

q$\wedge$r=0

p$\vee$(q$\wedge$r)=0

(2)(p$\leftrightarrow$q)$\wedge$($\neg$q$\vee$s)

p$\leftrightarrow$q=0

(p$\leftrightarrow$q)$\wedge$($\neg$q$\vee$s)=0

(3)(p$\wedge$(q$\vee$s))$\to$((p$\vee$q)$\wedge$(r$\wedge$s))

q$\vee$s=1

p$\wedge$(q$\vee$s)=0

蕴含式前件为0，整个公式真值为1

(4)$\neg$(p$\vee$(q$\to$($\neg$p$\wedge$r)))$\to$(r$\vee$$\neg$s)

q真值为0

q$\to$($\neg$p$\wedge$r)=1

p$\vee$(q$\to$($\neg$p$\wedge$r)=1

$\neg$(p$\vee$(q$\to$($\neg$p$\wedge$r)))=0

$\neg$(p$\vee$(q$\to$($\neg$p$\wedge$r)))$\to$(r$\vee$$\neg$s)=1

(5)($\neg$p$\wedge$$\neg$q)$\to$(r$\wedge$s)

$\neg$p$\wedge$$\neg$q=1

r$\wedge$s=1

($\neg$p$\wedge$$\neg$q)$\to$(r$\wedge$s)=1

7

(2)

p：那房子有三室一厅 q:面积在100$m^2$以上 r:老王要房子

符号化原命题：p$\wedge$q$\to$r

p q r	p$\wedge$q	p$\wedge$q$\to$r
0 0 0	0	1
0 0 1	0	1
0 1 0	0	1
0 1 1	0	1
1 0 0	0	1
1 0 1	0	1
1 1 0	1	0
1 1 1	1	1

由真值表可知，除了在房子有三室一厅且面积在100$m^2$ 以上，老王不要房子，其余情况命题为真

9

(2)((p$\to$q)$\wedge$(q$\to$p))$\leftrightarrow$(p$\leftrightarrow$q)

(p$\leftrightarrow$q)$\leftrightarrow$(p$\leftrightarrow$q) (等值等价式)

为重言式

10

(3)

$\neg$(p$\leftrightarrow$q)$\iff$((p$\vee$q)$\wedge$$\neg$(p$\wedge$q))

(p$\vee$q)$\wedge$$\neg$(p$\wedge$q)

$\iff$ $\neg$($\neg$(p$\vee$q)$\vee$$\neg$$\neg$(p$\wedge$q)) (德摩根律)

$\iff$ $\neg$($\neg$(p$\vee$q)$\vee$(p$\wedge$q)) (双重否定律)

$\iff$$\neg$((($\neg$p$\wedge$$\neg$q)$\vee$p)$\wedge$(($\neg$p$\wedge$$\neg$q)$\vee$q))) (德摩根律+分配律)

$\iff$$\neg$((($\neg$p$\vee$p)$\wedge$($\neg$q$\vee$p))$\wedge$(($\neg$p$\vee$q)$\wedge$($\neg$q$\vee$q))) (分配律)

$\iff$$\neg$((1$\wedge$($\neg$q$\vee$p))$\wedge$(($\neg$p$\vee$q)$\wedge$1))) (排中律)

$\iff$$\neg$(($\neg$q$\vee$p)$\wedge$($\neg$p$\vee$q)) (同一律)

$\iff$$\neg$((q$\to$p)$\wedge$(p$\to$ q)) (蕴含等值式)

$\iff$$\neg$(p$\leftrightarrow$q) (等价等值式)

11

(1)

已知A$\vee$C$\iff$B$\vee$C

则A$\vee$C$\leftrightarrow$B$\vee$C为重言式

若 (A$\vee$C$\leftrightarrow$B$\vee$C)$\leftrightarrow$(A$\leftrightarrow$B)成立

则A$\leftrightarrow$B为重言式，则A$\iff$B成立

A$\vee$C$\leftrightarrow$B$\vee$C

$\iff$((A$\vee$C)$\to$(B$\vee$C))$\wedge$((B$\vee$C)$\to$(A$\vee$C)) 等价等值式

$\iff$($\neg$(A$\vee$C)$\vee$(B$\vee$C))$\wedge$($\neg$(B$\vee$C)$\vee$(A$\vee$C)) 蕴含等值式

$\iff$(($\neg$A$\wedge$$\neg$C)$\vee$(B$\vee$C))$\wedge$(($\neg$B$\wedge$$\neg$C)$\vee$(A$\vee$C)) 德摩根律

$\iff$(((B$\vee$C)$\vee$$\neg$A)$\wedge$((B$\vee$C)$\vee$$\neg$C))$\wedge$(((A$\vee$C)$\vee$$\neg$B)$\wedge$((A$\vee$C)$\vee$$\neg$C)) 分配律

$\iff$(B$\vee$C$\vee$$\neg$A)$\wedge$(B$\vee$1)$\wedge$(A$\vee$C$\vee$$\neg$B)$\wedge$(A$\vee$1) 排中律

$\iff$ (B$\vee$C$\vee$$\neg$A)$\wedge$(A$\vee$C$\vee$$\neg$B) 同一律

$\iff$C$\vee$((B$\vee$$\neg$A)$\wedge$(A$\vee$$\neg$B)) 分配律

$\iff$C$\vee$((A$\to$B)$\wedge$(B$\to$A)) 蕴含等值式

$\iff$C$\vee$(A$\leftrightarrow$B) 等价等值式

与A$\leftrightarrow$B不等值

A$\iff$B不一定成立

(3)

已知$\neg$A$\iff$$\neg$B

则$\neg$A$\leftrightarrow$$\neg$B为重言式

$\neg$A$\leftrightarrow$$\neg$B

$\iff$A$\leftrightarrow$B

故A$\leftrightarrow$B也为重言式

A$\iff$B成立

13

(2)(p$\to$(q$\wedge$$\neg$p))$\wedge$$\neg$r$\wedge$q

$\iff$($\neg$p$\vee$(q$\wedge$$\neg$p))$\wedge$$\neg$r$\wedge$q (蕴含等值式)

$\iff$$\neg$(p$\wedge$$\neg$(q$\wedge$$\neg$p))$\wedge$$\neg$r$\wedge$q (德摩根式)

17

(3)(p$\vee$(q$\wedge$r))$\to$(p$\vee$q$\vee$r)

$\iff$$\neg$(p$\vee$(q$\wedge$r))$\vee$(p$\vee$q$\vee$r) (蕴含等值式)

$\iff$($\neg$p$\wedge$($\neg$q$\vee$$\neg$r))$\vee$p$\vee$q$\vee$r (两次德摩根式)

$\iff$($\neg$p$\wedge$$\neg$q)$\vee$($\neg$p$\wedge$$\neg$r)$\vee$p$\vee$q$\vee$r (分配律)

$\iff$(($\neg$p$\wedge$$\neg$q)$\wedge$(r$\vee$$\neg$r))$\vee$($\neg$p$\wedge$$\neg$r)$\vee$p$\vee$q$\vee$r (排中律)

$\iff$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$$\neg$r)$\vee$p$\vee$q$\vee$r (分配律)

$\iff$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$p$\vee$q$\vee$r

$\iff$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$(p$\wedge$q)$\vee$(p$\wedge$$\neg$q)$\vee$(p$\wedge$q)$\vee$($\neg$p$\wedge$q)$\vee$(q$\wedge$r)$\vee$($\neg$q$\wedge$r)

$\iff$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$(p$\wedge$q$\wedge$r)$\vee$(p$\wedge$q$\wedge$$\neg$r)$\vee$(p$\wedge$$\neg$q$\wedge$r)$\vee$(p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$(p$\wedge$q$\wedge$r)$\vee$(p$\wedge$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$q$\wedge$r)$\vee$($\neg$p$\wedge$q$\wedge$$\neg$r)$\vee$(p$\wedge$q$\wedge$r)$\vee$($\neg$p$\wedge$q$\wedge$r)$\vee$(p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$r)

$\iff$m${}_{001}$$\vee$m${}_{000}$$\vee$m${}_{010}$$\vee$m${}_{000}$$\vee$m${}_{111}$$\vee$m${}_{110}$$\vee$m${}_{101}$$\vee$m${}_{100}$$\vee$m${}_{111}$$\vee$m${}_{110}$$\vee$m${}_{011}$$\vee$m${}_{010}$$\vee$m${}_{111}$$\vee$m${}_{011}$$\vee$m${}_{101}$$\vee$m${}_{001}$

$\iff$m${}_1$ $\vee$m${}_0$$\vee$m${}_2$$\vee$m${}_0$$\vee$m${}_7$$\vee$m${}_6$$\vee$m${}_5$$\vee$m${}_4$$\vee$m${}_7$$\vee$m${}_6$$\vee$m${}_3$$\vee$m${}_2$$\vee$m${}_7$$\vee$m${}_3$$\vee$m${}_5$$\vee$m${}_1$

$\Leftrightarrow$1

成真赋值为 000 ,001, 010 ,011 ,100,101,110,111

19

(1)

p$\to$(q$\to$r)与q$\to$(p$\to$r)

1. p$\to$(q$\to$r)

   $\iff$$\neg$p$\vee$($\neg$q$\vee$r)

   $\iff$($\neg$p$\wedge$q)$\vee$($\neg$p$\wedge$$\neg$q)$\vee$(p$\wedge$$\neg$q)$\vee$($\neg$p$\wedge$$\neg$q)$\vee$(q$\wedge$r)$\vee$($\neg$q$\wedge$r)

   $\iff$($\neg$p$\wedge$q$\wedge$r)$\vee$($\neg$p$\wedge$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$(p$\wedge$$\neg$q$\wedge$r)$\vee$(p$\wedge$$\neg$q$\neg$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$(p$\wedge$q$\wedge$r)$\vee$($\neg$p$\wedge$q$\wedge$r)$\vee$(p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$r)

   $\iff$m${}_{011}$$\vee$m${}_{010}$$\vee$m${}_{001}$$\vee$m${}_{000}$$\vee$m${}_{101}$$\vee$m${}_{100}$$\vee$m${}_{001}$$\vee$m${}_{000}$$\vee$m${}_{111}$$\vee$m${}_{011}$$\vee$m${}_{101}$$\vee$m${}_{001}$

   $\iff$m${}_3$$\vee$m${}_2$$\vee$m${}_1$$\vee$m${}_0$$\vee$m${}_5$$\vee$m${}_4$$\vee$m${}_1$$\vee$m${}_0$$\vee$m${}_7$$\vee$m${}_3$$\vee$m${}_5$$\vee$m${}_1$

   $\iff$m${}_7$m${}_5$$\vee$m${}_4$$\vee$m${}_3$$\vee$m${}_2$$\vee$m${}_1$$\vee$m${}_0$

2. q$\to$(p$\to$r)

   $\iff$($\neg$q$\wedge$p$\wedge$r)$\vee$($\neg$q$\wedge$p$\wedge$$\neg$r)$\vee$($\neg$q$\wedge$$\neg$p$\wedge$r)$\vee$($\neg$q$\wedge$$\neg$p$\wedge$$\neg$r)$\vee$(q$\wedge$$\neg$p$\wedge$r)$\vee$(q$\wedge$$\neg$p$\neg$r)$\vee$($\neg$q$\wedge$$\neg$p$\wedge$r)$\vee$($\neg$q$\wedge$$\neg$p$\wedge$$\neg$r)$\vee$(q$\wedge$p$\wedge$r)$\vee$($\neg$q$\wedge$p$\wedge$r)$\vee$(q$\wedge$$\neg$p$\wedge$r)$\vee$($\neg$q$\wedge$$\neg$p$\wedge$r)

   $\iff$ m${}_{101}$$\vee$m${}_{100}$$\vee$m${}_{001}$$\vee$m${}_{000}$$\vee$m${}_{011}$$\vee$m${}_{010}$$\vee$m${}_{001}$$\vee$m${}_{000}$$\vee$m${}_{111}$$\vee$m${}_{101}$$\vee$m${}_{011}$$\vee$m${}_{001}$

   $\iff$m${}_5$$\vee$m${}_4$$\vee$m${}_1$$\vee$m${}_0$$\vee$m${}_3$$\vee$m${}_2$$\vee$m${}_1$$\vee$m${}_0$$\vee$m${}_7$$\vee$m${}_5$$\vee$m${}_3$$\vee$m${}_1$

   $\iff$m${}_7$m${}_5$$\vee$m${}_4$$\vee$m${}_3$$\vee$m${}_2$$\vee$m${}_1$$\vee$m${}_0$

等值

23

p:赵去 q:钱去 r:孙去 s:李去 t:周去

• p$\to$q
• s$\vee$t
• (q$\wedge$$\neg$r)$\vee$($\neg$q$\wedge$r)
• r$\leftrightarrow$s
• t$\to$(p$\wedge$q)

$\iff$(p$\to$q)$\wedge$(s$\vee$t)$\wedge$(r$\leftrightarrow$s)$\wedge$(t$\to$(p$\wedge$q))$\wedge$((q$\wedge$$\neg$r)$\vee$($\neg$q$\wedge$r))

$\iff$ ($\neg$p$\vee$q)$\wedge$ (s$\vee$t)$\wedge$(r$\to$s)$\wedge$(s$\to$r)$\wedge$( $\neg$t$\vee$(p$\wedge$q))$\wedge$((q$\wedge$$\neg$r)$\vee$($\neg$q$\wedge$r)) (蕴含等值式 等价等值式 蕴含等值式)

$\iff$($\neg$p$\vee$q)$\wedge$ (s$\vee$t)$\wedge$($\neg$r$\vee$s)$\wedge$($\neg$s$\vee$ r)$\wedge$( $\neg$t$\vee$p)$\wedge$($\neg$t$\vee$q)$\wedge$((q$\wedge$$\neg$r)$\vee$($\neg$q$\wedge$r)) (蕴含等值式 分配律)

$\iff$($\neg$p$\vee$q)$\wedge$ (s$\vee$t)$\wedge$($\neg$r$\vee$s)$\wedge$($\neg$s$\vee$ r)$\wedge$( $\neg$t$\vee$p)$\wedge$($\neg$t$\vee$q)$\wedge$ ((q$\wedge$$\neg$r)$\vee$$\neg$q)$\wedge$((q$\wedge$$\neg$r)$\vee$r) (分配律)

$\iff$($\neg$p$\vee$q)$\wedge$ (s$\vee$t)$\wedge$($\neg$r$\vee$s)$\wedge$($\neg$s$\vee$ r)$\wedge$( $\neg$t$\vee$p)$\wedge$($\neg$t$\vee$q)$\wedge$($\neg$q$\vee$q)$\wedge$($\neg$q$\vee$$\neg$r)$\wedge$(r$\vee$q)$\wedge$(r$\vee$$\neg$r) (分配律)

$\iff$ ($\neg$p$\vee$q)$\wedge$ (s$\vee$t)$\wedge$($\neg$r$\vee$s)$\wedge$($\neg$s$\vee$ r)$\wedge$( $\neg$t$\vee$p)$\wedge$($\neg$t$\vee$q)$\wedge$($\neg$q$\vee$$\neg$r)$\wedge$(r$\vee$q) (排中律)

1变8.。。。8*8=64个式子

24

(3)

p:今天是1号 q:明天是5号

前提：p$\to$q，$\neg$q

结论:$\neg$p

((p$\to$q)$\wedge$$\neg$q)$\Rightarrow$$\neg$p (拒取式)

推理正确

26

(1)归谬法

前提:$\neg$(p$\wedge$$\neg$q),$\neg$q$\vee$r,$\neg$r

结论:$\neg$p

$\neg$(p$\wedge$$\neg$q)$\wedge$ ($\neg$q$\vee$r)$\wedge$$\neg$r$\wedge$p

$\iff$($\neg$p$\vee$q)$\wedge$($\neg$q$\vee$r)$\wedge$$\neg$r$\wedge$p (德摩根律)

$\iff$($\neg$p$\vee$q$\vee$r)$\wedge$($\neg$p$\vee$q$\vee$$\neg$r)$\wedge$(p$\vee$$\neg$q$\vee$r)$\wedge$($\neg$p$\vee$$\neg$q$\vee$r)$\wedge$(q$\vee$$\neg$r)$\wedge$($\neg$q$\vee$$\neg$r)$\wedge$(p$\vee$q)$\wedge$(p$\vee$$\neg$q)

$\iff$($\neg$p$\vee$q$\vee$r)$\wedge$($\neg$p$\vee$q$\vee$$\neg$r)$\wedge$(p$\vee$$\neg$q$\vee$r)$\wedge$($\neg$p$\vee$$\neg$q$\vee$r)$\wedge$(p$\vee$q$\vee$$\neg$r)$\wedge$($\neg$p$\vee$q$\vee$$\neg$r)$\wedge$(p$\vee$$\neg$q$\vee$$\neg$r)$\wedge$($\neg$p$\vee$$\neg$q$\vee$$\neg$r)$\wedge$(p$\vee$q$\vee$r)$\wedge$(p$\vee$q$\vee$$\neg$r)$\wedge$(p$\vee$$\neg$q$\vee$r)$\wedge$(p$\vee$$\neg$q$\vee$$\neg$r)

$\iff$m${}_{100}$$\wedge$m${}_{101}$$\wedge$m${}_{010}$$\wedge$m${}_{110}$$\wedge$m${}_{001}$$\wedge$m${}_{101}$$\wedge$m${}_{011}$$\wedge$m${}_{111}$$\wedge$m${}_{000}$$\wedge$m${}_{001}$$\wedge$m${}_{010}$$\wedge$m${}_{011}$

$\iff$m${}_4$$\wedge$m${}_5$$\wedge$m${}_2$$\wedge$m${}_6$$\wedge$m${}_1$$\wedge$m${}_5$$\wedge$m${}_3$$\wedge$m${}_7$$\wedge$m${}_0$$\wedge$m${}_1$$\wedge$m${}_2$$\wedge$m${}_3$

$\Leftrightarrow$1故为矛盾式，于是证明了推理的正确性(2)附加前提证明法前提:p$\rightarrow$(q$\rightarrow$s),q,p$\veeKaTeX parse error: Can't use function '$' in math mode at position 5: \neg$̲ r 结论：r$\righta…\neg$r(前提引入)r(附加前提引入)p(析取三段论)p$\rightarrow$(q$\rightarrow$s)(前提引入)q$\rightarrow$s (假言推理)
q (前提引入)
s (假言推理)

(3)附加前提证明法
前提:p$\to$q
结论:p$\to$(p$\wedge$q)
p$\to$q (前提引入)
p (附加前提引入)
q (假言推理)
q$\wedge$p

27

p:他是理科生 q:他学好数学 r:他是文科生
前提:p$\to$q,$\neg$r$\to$p,$\neg$q
结论:p
p$\to$q (前提引入)
$\neg$q (前提引入)
$\neg$p (拒取式)
$\neg$r$\to$p (前提引入)
$\neg$$\neg$r (拒取式)

第二章 一阶逻辑

1.

(4)每列火车都比某些汽车要快

F(x):x 是火车 G(x):x是汽车 H(x,y):x比y快

$\forall$x(F(x)$\to$ $\exists$y(G(y)$\wedge$H(x,y)))

(5)某些汽车比所有火车都慢

F(x):x 是火车 G(x):x是汽车 H(x,y):x比y慢

$\exists$x(G(x)$\wedge$$\forall$y(F(y)$\to$H(x,y)))

(6)每位父亲都喜爱自己的孩子

F(x):x是父亲 G(x):x是孩子 H(x,y):x喜爱y L(x,y):y是x的孩子

$\forall$x$\forall$y(F(x)$\wedge$G(y)$\wedge$L(x,y)$\to$H(x,y))

(7)对于任意给定的正实数，都存在比它大的实数

F(x):x是实数 G(x,y):x>y

$\forall$x(F(x)$\wedge$G(x,0)$\to$$\exists$y(F(y)$\wedge$(y,x)))

课本例题2.5

(1)所有的兔子比所有的乌龟跑得快

F(x):x是兔子 G(x):x是乌龟 H(x,y):x比y跑的快

$\forall$x$\forall$y(F(x)$\wedge$G(y)$\to$H(x,y))

(2)有的兔子比所有的乌龟跑得快

$\exists$x(F(x)$\wedge$$\forall$y(G(y)$\to$H(x,y)))

(3)不存在同样高的两个人

F(x):x是人 G(x,y):x y同样高 H(x,y):x!=y

$\forall$x$\forall$y(F(x)$\wedge$F(y)$\wedge$H(x,y)$\to$ $\neg$G(x,y))

2.

(4)$\forall$x$\forall$y$\exists$z(x-y=z)

对于任意的x,y，存在z，可满足x-y=z成立

为真

(8)$\exists$x$\forall$y(x+y=2y)

有的x等于任意的y

3.

(3)F(z)$\to$($\neg$$\forall$x$\forall$yG(x,y,z))

指导变项为x,y

G(x,y,z)中的x是约束的

G(x,y,z)中的y是约束的

F(z)和G(x,y,z)中的z是自由的

6.

给定解释I如下:

个体域D={2,3},f(2)=3,f(3)=2,F(2,2)=0,F(2,3)=0,F(3,2)=1,F(3,3)=1

求下列各式在I下的真值

$\forall$x$\forall$y(F(x,y)$\to$F(f(x),f(y)))

x=2,y=2时,F(2,2)=0，蕴含式前件为假，整体为真

x=2,y=3时,同理为真

x=3,y=2时，F(3,2)=1, f(x)=2,f(y)=3,F(f(x),f(y))=F(2,3)=0 为假

故$\forall$x$\forall$y(F(x,y)$\to$F(f(x),f(y)))为假

9.

设个体域D={a,b,c}，消去下列各式中的量词

在有限个体域时中消去量词等值式

(2)$\forall$x(F(x)$\wedge$$\exists$yG(y))

$\iff$ $\forall$xF(x)$\wedge$$\exists$yG(y) ($\exists$yG(y)中不含约束变项x)

$\iff$ $\forall$xF(x)$\wedge$(G(a)$\vee$G(b)$\vee$G©) (存在量词的消去量词等值式)

$\iff$ (F(a)$\wedge$F(b)$\wedge$F©)$\wedge$(G(a)$\vee$G(b)$\vee$G©) (全称量词的消去量词等值式)

(4)$\exists$x$\exists$y(F(x)$\to$G(y))

$\iff$ $\exists$x$\exists$y($\neg$F(x)$\vee$G(y)) (蕴含等值式)

$\iff$ $\exists$x($\neg$F(x)$\vee$ $\exists$yG(y)) ($\neg$F(x)中不含约束变项y)

$\iff$ $\exists$x$\neg$F(x)$\vee$ $\exists$yG(y) ($\exists$yG(y)中不含约束变项x)

$\iff$ $\neg$ $\forall$xF(x)$\vee$ $\exists$yG(y) (量词否定等值式)

$\iff$ $\neg$(F(a)$\wedge$F(b)$\wedge$f©)$\vee$(G(a)$\vee$G(b)$\vee$G©) (消去量词等值式)

10.

给出下列公式的类型

(4)$\neg$F(x)$\to$(F(x)$\to$$\forall$yG(x,y))

p=F(x) q=$\forall$yG(x,y)

运用代换实例可转换为

$\iff$ $\neg$p$\to$(p$\to$q)

$\iff$ $\neg$p$\to$($\neg$p$\vee$q)

$\iff$p$\vee$$\neg$p$\vee$q

$\iff$ 1

12.

证明F(x)$\to$$\forall$xF(x)不是永真式

个体域为1,2,3

F(x):x为奇数

$\iff$ F(x)$\to$(F(1)$\wedge$F(2)$\wedge$F(3)) (量词消去等值式)

当x=1时，蕴含式前件为真，后件为假

公式为假，故不是永真式

13.

求下列各式的前束范式

(1)($\neg$ $\exists$xF(x)$\vee$ $\forall$yG(y)) $\wedge$ $\forall$zH(z)

$\iff$ ($\forall$x$\neg$F(x)$\vee$$\forall$yG(y))$\wedge$$\forall$zH(z)

$\iff$ ($\forall$x($\neg$F(x)$\vee$$\forall$yG(y)))$\wedge$ $\forall$zH(z) (辖域扩张)

$\iff$ $\forall$x$\forall$y($\neg$F(x)$\vee$G(y))$\wedge$$\forall$zH(z) (辖域扩张)

$\iff$$\forall$z ($\forall$x$\forall$y($\neg$F(x)$\vee$G(y))$\wedge$H(z)) (辖域扩张)

$\iff$ $\forall$z $\forall$x($\forall$y($\neg$F(x)$\vee$G(y)$\wedge$H(z)) (辖域扩张)

$\iff$ $\forall$z $\forall$x$\forall$y(($\neg$F(x)$\vee$G(y))$\wedge$H(z)) (辖域扩张)

(2)$\exists$xF(x)$\vee$ $\forall$xG(x)$\to$$\forall$x$\exists$yH(x,y)

$\exists$xF(x)$\vee$ $\forall$zG(z)$\to$$\forall$m$\exists$yH(m,y) (换名规则)

$\iff$ $\exists$x$\exists$z(G(z)$\vee$F(x))$\to$ $\forall$m$\exists$yH(m,y) (两次辖域扩张)

$\iff$ $\forall$x($\exists$z(G(z)$\vee$F(x))$\to$$\forall$m$\exists$yH(m,y))

$\iff$ $\forall$x $\forall$y(G(z)$\vee$F(x)$\to$$\forall$m$\exists$yH(m,y))

$\iff$ $\forall$x $\forall$y($\neg$ $\forall$m$\exists$yH(m,y)$\to$$\neg$(G(z)$\vee$F(x))) (假言易位)

$\iff$ $\forall$x $\forall$y($\exists$m$\neg$$\exists$yH(m,y)$\to$$\neg$(G(z)$\vee$F(x)))

$\iff$ $\forall$x $\forall$y($\exists$m$\forall$ y$\neg$ H(m,y)$\to$$\neg$(G(z)$\vee$F(x))) (量词否定等值式)

$\iff$ $\forall$x$\forall$y$\forall$m$\exists$y($\neg$H(m,y)$\to$ $\neg$(G(z)$\vee$F(x))) (两次辖域扩张)

$\iff$ $\forall$x$\forall$y$\forall$m$\exists$y(G(z)$\vee$F(x)$\to$H(m,y)) (假言易位)

一阶逻辑推理理论

12.

指出下面推理中的错误

(6)

5.使F(x)$\wedge$G(x)成真的x不一定使H(x)$\wedge$R(x)成真

13.

(1)

前提:$\exists$xF(x)$\to$$\forall$y((F(y)$\vee$G(y))$\to$R(y)), $\exists$xF(x)

结论:$\exists$xR(x)

(1) $\exists$xF(x) (前提引入)

(2)F© (EI规则)

(3)$\exists$xF(x)$\to$$\forall$y((F(y)$\vee$G(y))$\to$R(y)) (前提引入)

(4)$\forall$y((F(y)$\vee$G(y))$\to$R(y)) (假言推理)

(5)F©$\vee$G©$\to$R© (UI规则)

(6)F©$\vee$ G© (2附加)

(7)R© (5假言推理)

(8)$\exists$xF(x) (EG规则)

15.

每个在银行存款的人都能得到利息，所以，若没有人得到利息，则没有人在银行存款

F(x):x在银行存款 G(x):x得到利息

前提: $\forall$x(F(x)$\to$G(x))

结论:$\neg$$\forall$xG(x)$\to$$\neg$$\forall$xF(x)

(1)$\neg$$\forall$xG(x) (附加前提引入)

(2)$\exists$x$\neg$G(x) (量词否定等值式)

(3)$\neg$G© (EI规则)

(4)$\forall$x(F(x)$\to$G(x)) (前提引入)

(5) $\forall$x($\neg$G(x)$\to$$\neg$F(x)) (假言易位)

(6)$\neg$G©$\to$ $\neg$F© (UI规则)

(7)$\neg$ F© (假言推理)

(8)$\exists$x$\neg$F(x) (EG规则)

(9)$\neg$ $\forall$xF(x) (量词否定等值式)

第三章 集合

2

(2)$S_2$={2,5}

4

(2)P(A)={{$\varnothing$}{1},{{2,3}},{1,{2,3}}

7

（2） ((A$\cup$B$\cup$C)-(B$\cup$C))$\cup$A
= ((A$\cup$B$\cup$C)$\cap$~(B$\cup$C))$\cup$A

=(A$\cup$B$\cup$C$\cup$A)$\cap$((~B $\cap$~ C)$\cup$A)

=(A$\cup$B$\cup$C)$\cap$((~B$\cup$A)$\cap$( ~C$\cup$A))

=(A$\cup$((B$\cup$C)$\cap$~B))$\cap$( ~C$\cup$A)

=(A$\cup$((B$\cap$~B)$\cup$(C$\cap$ ~B)))$\cap$( ~C$\cup$A)

=(A$\cup$(C$\cap$~B))$\cap$( ~C$\cup$A)

=A$\cup$((C$\cap$~B)$\cap$ ~C)

=A

8

(3)A$\cap$(~B$\cup$C)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TqL7GdUx-1678010764001)(课外学习资料/所需图片/QQ截图20221014232149.png)]

10

A={x|读《每周新闻》的人} B={x|读《时代》杂志的人} C={x|读《幸运》杂志的人}

E={x|所有被调查的人}

已知:

|E|=60;|A|=25;|B|=26;|C|=26;|A$\cap$C|=9;|A$\cap$B|=11;|B$\cap$C|=8；|E-(A$\cup$B$\cup$C)|=8;

(1)求全部阅读三种杂志的人：|A$\cap$B$\cap$C|

已知:|A$\cup$B$\cup$C|=|A|+|B|+|C|-|A$\cap$B|-|A$\cap$C|-|B$\cap$C|+|A$\cup$B$\cup$C|=25+26+26-9-11-8+|A$\cap$B$\cap$C|=60-8

|A$\cap$B$\cap$C|=3

(2)求仅阅读…的人数

|A-B-C|=|A$\cap$~B$\cap$ ~C|=|A$\cap$(E-(B$\cup$C))|=|(A$\cap$E)-(A$\cap$(B$\cup$C))|=|A-(A$\cap$B)$\cup$(A$\cap$C)|=|A|-|(A$\cap$B)$\cup$(A$\cap$C))|=|A|-(|A$\cap$B|+|A$\cap$C|-|A$\cap$B$\cap$A$\cap$C|)=25-(11+9-3)=8

同理

|B-A-C|=|B|-(|A$\cap$B|+|B$\cap$C|-|A$\cap$B$\cap$C|)=26-(11+8-3)=10

|C-B-A|=|C|-(|A$\cap$C|+|B$\cap$C|-|A$\cap$B$\cap$C|)=26-(9+8-3)=12

12

(2)证明:(A-B)-C=(A-C)-(B-C)

1. 公式法

   =(A$\cap$~C)$\cap$ ~(B$\cap$ ~C)

   =(A$\cap$~C)$\cap$( ~B$\cup$C) (德摩根律)

   =((A$\cap$~C)$\cap$C)$\cup$((A$\cap$ ~C)$\cap$ ~B) ($\cup$ $\cap$ 的分配律)

   =$\varnothing$ $\cup$((A$\cap$ ~C)$\cap$ ~B) (零律)

   =(A$\cap$ ~B$\cap$ ~C)

   =(A-B)-C

2. 基本定义法

   x$\in$ (A-C) $\wedge$ x$\notin$(B-C)

   $\iff$ x$\in$A$\wedge$x$\notin$C$\wedge$ $\neg$ (x$\in$B$\wedge$x$\notin$C)

   $\iff$ x$\in$A$\wedge$x$\notin$C$\wedge$ (x$\notin$B$\vee$ x$\in$C) (德摩根律)

   $\iff$ (x$\in$A$\wedge$ x$\notin$C$\wedge$ x$\notin$B)$\vee$(x$\in$A$\wedge$ x$\notin$C$\wedge$x$\in$C) ($\vee$ $\wedge$ 的分配律)

   $\iff$ (x$\in$A$\wedge$ x$\notin$C$\wedge$ x$\notin$B)$\vee$ $\varnothing$ (零律)

   $\iff$ (x$\in$A$\wedge$ x$\notin$B)$\wedge$x$\notin$C ($\wedge$ 的结合律)

   $\iff$ x$\in$(A$\cap$ ~B)$\wedge$ x$\notin$C

   $\iff$ x$\in$((A$\cap$~B)$\cap$ ~C)

   $\iff$ x属于(A-B)-C

13.

证明：C$\subseteq$A$\wedge$ C$\subseteq$B $\iff$ C$\subseteq$A$\cap$ B

$\forall$ x(x$\in$C$\to$x$\in$A)$\wedge$ $\forall$x(x$\in$C$\to$x$\in$B) (根据基本定义)

$\iff$ $\forall$x((x$\in$C$\to$x$\in$A)$\wedge$(x$\in$C$\to$x$\in$B)) (量词分配等值式)

$\iff$ $\forall$x(($\neg$x$\in$C$\vee$x$\in$A)$\wedge$ ($\neg$ x$\in$C$\vee$x$\in$B)) (蕴含等值式)

$\iff$ $\forall$x($\neg$x$\in$C$\vee$(x$\in$ A$\wedge$x$\in$B)) ($\vee$ $\wedge$ 的分配律)

$\iff$$\forall$x($\neg$x$\in$C$\vee$x$\in$(A$\cap$B)) (交集的基本定义)

$\iff$ $\forall$x(x$\in$C$\to$x$\in$(A$\cap$B)) (蕴含等值式)

$\iff$ C$\subseteq$ (A$\cap$B) (子集的基本定义)