离散数学期末复习题

离散数学期末复习题

一、选择题

1、永真式的否定是（2） (2) 永假式

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)P?Q?R

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑵P??Q(3)

提示：R??(P?Q)?P??Q 4、下列表达式错误的有⑷ ⑷P?(?P?Q)?P?Q 5、下列表达式正确的有⑷ ⑷?(P?Q)??Q

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

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑵?x(L(x)??y(J(y)?A(x,y)))

8、谓词公式?x(P(x)??yR(y))?Q(x)中的 x是⑶ ⑶既是自由变元又是约束变元 9、下列表达式错误的有⑴

⑴?x(A(x)?B(x))??xA(x)??xB(x) 10、下列推导错在⑶

①?x?y(x?y) P

②?y(z?y) ③(z?Cz) ④?x(x?x) ⑶④

11、下列推理步骤错在⑶

①?x?yF(x,y)

②?yF(z,y) ③F(z,c) ④?xF(x,c) ⑤?y?xF(x,y) ⑶③→④

US① ES② UG③

P US① ES② UG③ EG④

12、设个体域为{a,b}，则?x?yR?x,y?去掉量词后，可表示为⑷

⑷?R?a,a??R?a,b????R?b,a??R?b,b??

提示：原式??yR?a,y???yR?b,y??R?a,a??R?a,b??R?b,a??R?b,b? 二、填充题

1、一个命题含有n个原子命题，则对其所有可能赋值有2 种。

- 1 -

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

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

5、公式?(P?Q)?(P??(Q??S))的对偶公式为?(P?Q)?(P??(Q??S))。 6、设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的逻辑符号可化为S?P?Q?R 。 7、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为?P?Q； “虽然你努力了，但还是失败了”的翻译为P?Q。

8、令A(x)：x会叫，B(x)：x是狗，C(x)：x会咬人，则命题“会叫的狗未必会咬人” 的符号化为?x(A(x)?B(x)??C(x))。

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

10、令A（x）:x是自然数，B（x,y）：x 小于y，则命题“存在最小的自然数” 的符号化为?x(A(x)??y(A(y)??B(y,x)。

三、计算题

1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式

（1）（P?Q）?（?P∨Q）； （2）?（P?Q）∧Q； （3）（P?Q）∧?R；

解 （1）、（2）和（3）的真值表如表1、表2和表3所示：

表1 P Q P?Q ?P∨Q （P?Q）?（P∨Q） 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 表2 P Q P?Q ?（P?Q） ?（P?Q）∧Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 表3 P Q R P?Q ?R （P?Q）∧?R 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 由上述真值表可知，（1）为永真式，（2）为永假式，（3）为可满足式。

- 2 -

2nnn2n（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?xL(x,y)的真值。

解：?y?xL(x,y)??y(L(2,y)?L(3,y))?(L(2,2)?L(3,2))?(L(2,3)?L(3,3))

?(1?0)?(0?1)?0?0?0。

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∧1?0。

四、证明题

1、证明下列逻辑恒等式：

（1）Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ) 证明、用真值表法证明

P Q P?Q （P?Q）?（Q?P）

F F T T

F T F F

T F F F

T T T T

由定义可知，这两个公式是等价的。 （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） (P?Q)?(R?Q)?((P?R)?Q)

证明 ： 左?((?P?Q)?(?R?Q))?((?P??R)?Q)

?(?(P?R)?Q)?(P?R?Q)?右

（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)

?证明：左??x?(F?x???G?x?)???x?F?x???G?x????(?xF?x???x?G?x?) ????xF?x????xG?x??????xG?x???xF?x???右

（7）求证：?x?F?x??G?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）(析取三段论)

- 3 -

???

（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)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x) 证明：①?xP(x) P（ 附加前提）

②P(e)

T①ES ③(?x)(P(x)?Q(x)) P ④P(e)?Q(e) T③US

⑤Q(e) T②④(假言推理) ⑥(?x)Q(x)

T⑤EG

- 4 -