数理逻辑复习题

2023年12月14日发(作者：会泽中考数学试卷真题)

数理逻辑复习题

一、选择题

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所示：

P Q P Q P ∨Q （P Q ）（P ∨Q ）

0 0 0 1 1 0 1 1

1 1 0 1

1 1 0 1

1 1 1 1

P Q

P Q

（P Q ） （P Q ）∧Q

0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0

P Q R

P Q

R

（P Q ）∧

R

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0

1 1 1 1 0 0 1

1 0 1 0 1 0 1 1 0 1 0 0 0 1

1 1 1 1 0 0

（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}，求x y （x+y=4）的真值。 解：x y

（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）Ｐ?Ｑ? (Ｐ→Ｑ)∧(Ｑ→Ｐ) 证明、用真值表法证明

由定义可知，这两个公式是等价的。 （2）P →(Q →P)??P →(P

→?Q)

证明、P →(Q →P)??P ∨(?Q ∨P) ?P ∨(?P ∨?Q)

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

P Q P ?Q （P →Q ）∧（Q →P ） F F F T T F T T T T F F F F T T

(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 Q

T ⑸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 队不是亚军。

证明、设A ：A 队得第一;B: B 队获亚军;C: C 队获亚军;D: D 队获亚军; 则前提符号化为A →（B ∨C ），C →?A ，D →?B ，A ；结论符号化为 ?D 。 本题即证明 A →（B ∨C ），C →?A ，D →?B ，A ??D 。 （1） A P （2） A →（B ∨C ） P

（3） B ∨C T （1），（2）(假言推理) （4） C →?A P

（5） ?C T （1），（4）(拒取式) （6） B T （3），（5）(析取三段论) （7） D →?B P

（8） ?D T （6），（7）(拒取式) 故该结论有效

2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。 解 设P ：今天天气好，Q ：考试准时进行，A (e )：e 提前进入考场，个体域：考生的集合，则命题可符号化为：P x A (x )，xA

(x )Q ?Q P 。

(1)P x A (x ) P (2)P xA (x ) T (1) (3)xA (x )P T (2) (4)xA (x )Q P

(5)(xA (x )Q )∧(Q xA (x )) T (4) (6)Q xA (x ) T (5) (化简律)

(7)Q P T (6)(3)

（假言三段论） 3、所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。 解：设Q(x)：x 是有理数，R(x)：x 是实数，Z(x)：x 是整数。

命题形式化：))()(()),()((x Z x Q x x R x Q x ∧?→?? ))()((x Z x R x

∧?。

证明：（1）))()((x Z x Q x ∧? P (2) )()(a Z a Q ∧ T(1) ES (3) )(a

Q T(2) (化简律) (4) ))()((x R x Q x →? P (5) )()(a R a Q → T(4)US

(6) )(a R T(3)(5) (假言推理) (7) )(a Z T(2) (化简律) (8) )()(a Z a R

∧ T(6)(7) (合取引入)

(9) ))()((x Z x R x ∧? T (8) EG