当前位置:文档之家› 数理逻辑复习题

数理逻辑复习题

一、选择题1、永真式的否定是(2)(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能2、设P :2×2=5,Q :雪是黑的,R :2×4=8,S :太阳从东方升起,则下列真命题为(1) (1)R Q P ∧→ (2)S P R ∧→ (3)R Q S ∧→ (4) )()(S Q R P ∧∨∧。

3、设P :我听课,Q :我看小说,则命题R “我不能一边听课,一边看小说”的符号化为⑵ ⑴ P Q → ⑵Q P ⌝→(3) Q P →⌝ ⑷ P Q ⌝→⌝()P Q ⌝∧ 提示:()R P Q P Q ⇔⌝∧⇔→⌝4、下列表达式错误的有⑷⑴()P P Q P ∨∧⇔ ⑵()P P Q P ∧∨⇔ ⑶()P P Q P Q ∨⌝∧⇔∨ ⑷()P P Q P Q ∧⌝∨⇔∨ 5、下列表达式正确的有⑷⑴ P P Q ⇒∧ ⑵ P Q P ⇒∨ ⑶ ()Q P Q ⌝⇒⌝→⑷Q Q P ⌝⇒→⌝)( 6、下列联接词运算不可交换的是(3)⑴∧ ⑵∨ (3)→ ⑷ ↔6、设D :全总个体域,F (x ):x 是花,M(x) :x 是人,H(x,y):x 喜欢y ,则命题“有的人喜欢所有的花”的逻辑符号化为⑷⑴(()(()(,))x M x y F y H x y ∀∧∃→ ⑵(()(()(,))x M x y F y H x y ∀∧∀→ (3) (()(()(,))x M x y F y H x y ∃∧∃→ ⑷(()(()(,))x M x y F y H x y ∃∧∀→7、设L(x):x 是演员,J(x):x 是老师,A(x , y):x 钦佩y ,命题“所有演员都钦佩某些老师”的逻辑符号化为⑵⑴)),()((y x A x L x →∀ ⑵))),()(()((y x A y J y x L x ∧∃→∀ (3) )),()()((y x A y J x L y x ∧∧∃∀ ⑷)),()()((y x A y J x L y x →∧∃∀ 8、谓词公式)())()((x Q y yR x P x →∃∨∀中的 x 是⑶⑴自由变元 ⑵约束变元 ⑶既是自由变元又是约束变元 ⑷既不是自由变元又不是约束变元 9、下列表达式错误的有⑴⑴(()())()()x A x B x xA x xB x ∀∨⇒∀∨∀ ⑵(()())()()x A x B x xA x xB x ∃∧⇒∃∧∃ (3) (()())()()x A x B x xA x xB x ∀∧⇔∀∧∀ ⑷(()())()()x A x B x xA x xB x ∃∨⇔∃∨∃10、下列推导错在⑶①)(y x y x >∃∀ P ②)(y z y >∃ US ① ③)(z C z > ES ② ④)(x x x >∀UG ③⑴② ⑵③ ⑶④ ⑷无 11、下列推理步骤错在⑶①(,)x yF x y ∀∃ P ②),(y z yF ∃ US ① ③),(c z F ES ② ④),(c x xF ∀ UG ③ ⑤),(y x xF y ∀∃EG ④ ⑴①→② ⑵②→③ ⑶③→④ ⑷④→⑤12、设个体域为{a,b},则(),x yR x y ∀∃去掉量词后,可表示为⑷⑴()()()(),,,,R a a R a b R b a R b b ∧∧∧ ⑵()()()(),,,,R a a R a b R b a R b b ∨∨∨ (3) ()()()()()()b b R a b R b a R a a R ,,,,∨∧∨ ⑷()()()()()()b b R a b R b a R a a R ,,,,∨∧∨ 提示:原式()()()()()()()(),,,,,,yR a y yR b y R a a R a b R b a R b b ⇔∃∧∃⇔∨∧∨二、填充题1、一个命题含有n 个原子命题,则对其所有可能赋值有2n种。

2、n 个命题变元可产生2n个互不等价的极小项,其中,任意两个不同极小项的合取式为矛盾式(永假式),而全体极小项的析取式为重言式(永真式),n 个命题变元可构造包括F 的不同的主析取范式类别为22n。

3、n 个命题变元可产生2n个互不等价的极大项,其中,任意两个不同极大项的析取式为重言式(永真式),而全体极小项的合取式为矛盾式(永假式),n 个命题变元可构造包括T 的不同的主合取范式类别为22n。

5、公式))(()(S Q P Q P ⌝∧⌝∨∧∨⌝的对偶公式为()(())P Q P Q S ⌝∧∨∧⌝∨⌝。

6、设P :它占据空间,Q :它有质量,R :它不断运动,S :它叫做物质。

命题“占据空间的,有质量的而且不断运动的叫做物质”的逻辑符号可化为R Q P S ∧∧↔ 。

7、P :你努力,Q :你失败。

“除非你努力,否则你将失败”的翻译为Q P →⌝; “虽然你努力了,但还是失败了”的翻译为Q P ∧。

8、令)(x A :x 会叫,)(x B :x 是狗,)(x C :x 会咬人,则命题“会叫的狗未必会咬人” 的符号化为))()()((x C x B x A x ⌝∧∧∃。

9、设P(x):x 是大象,Q(x):x 是老鼠,R(x,y):x 比y 重,则命题“大象比老鼠重”的符号化为)),()()((y x R y Q x P y x →∧∀∀。

10、令A (x ):x 是自然数,B (x,y ):x 小于y ,则命题“存在最小的自然数” 的符号化为),()(()((x y B y A y x A x ⌝→∀⋂∃。

三、计算题1、用真值表方法判断下列公式的类型,并求(3)的主析取范式与主合取范式(1)(P Q )(P ∨Q ); (2)(P Q )∧Q ; (3)(P Q )∧R ;解 (1)、(2)和(3)的真值表如表1、表2和表3所示:表1P QP QP ∨Q(P Q )(P ∨Q ) 0 0 0 1 1 0 1 11 1 0 11 1 0 11 1 1 1P QP Q(P Q ) (P Q )∧Q0 0 0 1 1 0 1 11 1 0 10 0 1 00 0 0 0P Q RP QR(P Q )∧R0 0 01110 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 11 1 1 0 0 1 10 1 0 1 0 1 00 1 0 0 0 1 0由上述真值表可知,(1)为永真式,(2)为永假式,(3)为可满足式。

(3)的主析取范式为:(0,2,6)∑;其主合取范式为(1,3,4,5,7)π。

2、给定解释I :D={2,3},L (x,y )为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式),(y x xL y ∀∃的真值。

解:(,)((2,)(3,))((2,2)(3,2))((2,3)(3,3))y xL x y y L y L y L L L L ∃∀⇔∃∧⇔∧∨∧(10)(01)000⇔∧∨∧=∨=。

3、个体域为{1,2},求xy (x+y=4)的真值。

解:xy (x+y=4)x ((x+1=4)∨(x+2=4))((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+2=4)) (0∨0)∧(0∨1)0∧10。

四、证明题1、证明下列逻辑恒等式:(1)P↔Q⇔ (P→Q)∧(Q→P) 证明、用真值表法证明由定义可知,这两个公式是等价的。

(2)P →(Q →P)⇔⌝P →(P →⌝Q)证明、P →(Q →P)⇔⌝P ∨(⌝Q ∨P) ⇔P ∨(⌝P ∨⌝Q)P Q P ↔Q (P →Q )∧(Q →P ) F F F T T F T TT T F F F F T T⇔P ∨(⌝P ∨⌝Q) ⇔P ∨(P →⌝Q) ⇔⌝P →(P →⌝Q)(3) ))(()()(Q R P Q R Q P →∨⇔→∧→证明 : 左))(())()((Q R P Q R Q P ∨⌝∧⌝⇔∨⌝∧∨⌝⇔⇔→∨⇔∨∨⌝⇔)())((Q R P Q R P 右(4)求证:x(A(x)B(x)) xA(x)xB(x)证明 :x(A(x)B(x))x(A(x)∨B(x))x A(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)(5)求证:x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x)) 证明:左x((P(x)Q(x)∧P(x))x((P(x)∨Q(x))∧P(x))x(P(x)∧Q(x))右(6)求证:x y (P (x )Q (y )) xP (x )yQ (y )证明:x y (P (x )Q (y ))x y (P (x )∨Q (y )) x (P (x )∨yQ (y ))x P (x )∨yQ (y )xP (x )∨yQ (y )xP (x )yQ (y )(7)求证:()()()()()()x F x G x xG x xF x ∀⌝∧⇔⌝∀→∃证明:左()()()()()()()()()x F x G x x F x G x xF x x G x ⇔∀⌝∨⌝⇔⌝∃∨⌝⇔⌝∃∨∃⌝()()()xF x xG x ⇔⌝∃∨⌝∀()()()xG x xF x ⇔⌝∀→∃⇔右2、用推理规则证明下列各结论是各前提的有效结论: (1)P →Q ,⌝Q ∨R ,⌝R ,⌝S ∨P=>⌝S 证明:(1) ⌝R P(2) ⌝Q ∨R P(3) ⌝Q T (1),(2)(析取三段论) (4) P →Q P(5) ⌝P T (3),(4)(拒取式) (6) ⌝S ∨P P(7) ⌝S T (5),(6)(析取三段论)(2)A →(B →C),C →(⌝D ∨E),⌝F →(D ∧⌝E),A=>B →F证明: (1) A P(2) A→(B→C) P(3) B→C T(1),(2)(假言推理)(4) B P(附加前提)(5) C T(3),(4)(假言推理)(6) C→(⌝D∨E) 前提(7)⌝D∨E T(5),(6)(假言推理)(8)⌝F→(D∧⌝E) 前提(9) F T(7),(8)(拒取式)(10) B→F CP(3)(P→Q)∧(R→S),(Q→W)∧(S→X),⌝(W∧X),P→R => ⌝P 证明:(1) P P (假设前提)(2) P→R P(3) R T(1),(2)(假言推理)(4) (P→Q)∧(R→S) P(5) P→Q T(4)(化简律)(6) R→S T(4)(化简律)(7) Q T (1),(5)(假言推理)(8) S T(3),(6)(假言推理)(9) (Q→W)∧(S→X) P(10) Q→W T(9)(化简律)(11) S→X T(9)(化简律)(12) W T(7),(10)(假言推理)(13) X T(8),(11)(假言推理)(14) W∧X T(12),(13)(合取引入)(15)⌝(W∧X) P(16)⌝(W∧X)∧(W∧X) T(14),(15)(合取引入)由(16)得出矛盾式,故⌝P为原前提的有效结论(4)x(P(x)Q(y)∧R(x)),xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x) P(2)P(a) T(1),ES(3)x(P(x)Q(y)∧R(x)) P(4)P(a)Q(y)∧R(a) T(3),US(5)Q(y)∧R(a) T(2)(4) (假言推理) (6)Q(y) T(5) (化简律) (7)R(a) T(5) (化简律) (8)P(a)∧R(a) T(2)(7) (合取引入) (9)x(P(x)∧R(x)) T(8),EG(10)Q(y)∧x(P(x)∧R(x)) T(6)(9) (合取引入) (5))()()()())()()((x Q x x P x x Q x P x ∃→∃⇒→∀ 证明:①xP(x) P ( 附加前提)②P(e)T ①ES ③))()()((x Q x P x →∀ P ④)()(e Q e P → T ③US⑤Q(e) T ②④(假言推理) ⑥)()(x Q x ∃T ⑤EG ⑦)()()()(x Q x x P x ∃→∃CP(6)()(()()()),(),()xP x x P x Q x R x xP x xQ x ∃→∀∨→∃∃(()())x y P x R y ∃∃∧证明:⑴()(()()())xP x x P x Q x R x ∃→∀∨→P ⑵()xP x ∃P⑶(()()())x P x Q x R x ∀∨→ T ⑴⑵(假言推理) ⑷)(e P T ⑵ES ⑸()xQ x ∃ P ⑹)(d QT ⑸ES ⑺()()()P d Q d R d ∨→ T ⑶US ⑻)()(d P d Q ∨ T ⑹(附加律) ⑼)(d R T ⑺⑻(假言推理)⑽)()(d R e P ∧ T ⑷⑼(合取引入) ⑾))()()((y R e P y ∧∃ T ⑽EG ⑿))()()()((y R x P y x ∧∃∃T ⑾EG(7)()()())()()()(x xQ x P x x Q x P x ∃∨∀⇒∨∀证明:(1)())()()()(x Q x x p x ∃∨∀⌝ P (假设前提) (2)())()(x Q x x P x ⌝∀∧⌝∃ T (1) (3)())(x P x ⌝∃ T (2)(化简律) (4))(e P ⌝ T (3)ES (5)()()()()x P x Q x ∀∨ P (6)()())()(x Q x P x →⌝∀ T (5) (7))()(e Q e P →⌝ T (6)US(8)()e Q T (4). (7) (假言推理)(9) ()()x Q x ⌝∀ T (2) (化简律) (10)()e Q ⌝ T(9)US(11)()()e Q e Q ∧⌝ T (8) (10) (合取引入) 由(11)得出矛盾式,故()()()x P x xQ x ∀∨∃为原前提的有效结论五、将下列命题形式化,并证明结论的有效性:1、为庆祝九七香港回归祖国,四支足球队进行比赛,已知情况如下,问结论是否有效 前提: (1) 若A 队得第一,则B 队或C 队获亚军;(2) 若C 队获亚军,则A 队不能获冠军; (3) 若D 队获亚军,则B 队不能获亚军; (4) A 队获第一;结论: (5) D 队不是亚军。

相关主题