（数理逻辑部分）
一、选择或填空
1、下列哪些公式为永真蕴含式？( )
(1)Q=>Q→P (2)Q=>P→Q (3)P=>P→Q (4)P(PQ)=>P
答：（1），（4）
2、下列公式中哪些是永真式？( )
(1)(┐PQ)→(Q→R) (2)P→(Q→Q) (3)(PQ)→P (4)P→(PQ)
答：（2），（3），（4）
3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>PQ (2) PQ=>P (3) PQ=>PQ
(4)P(P→Q)=>Q (5) (P→Q)=>P (6) P(PQ)=>P
答：（2），（3），（4），（5），（6）
4、公式x((A(x)B(y，x)) z C(y，z))D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z
5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！
答：（1） 是，T （2） 是，F （3） 不是
1
（4） 是，T （5） 不是 （6） 不是
6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
答：所有人都不是大学生，有些人不会死
7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校
答：（1） QP （2） PQ （3） PQ （4）PQ
8、设个体域为整数集，则下列公式的意义是( )。
(1) xy(x+y=0) (2) yx(x+y=0)
答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0
9、设全体域D是正整数集合，确定下列命题的真值：
(1) xy (xy=y) ( ) (2) xy(x+y=y) ( ) (3) xy(x+y=x) ( ) (4) xy(y=2x) ( )
答：（1） F （2） F （3）F （4）T
10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( )
(1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立
答：（1）
11、命题“2是偶数或-3是负数”的否定是（ ）。
答：2不是偶数且-3不是负数。
2
12、永真式的否定是（ ）
(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
答：（2）
13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ))可化简为（ ）。
答：P ，QP
14、谓词公式x(P(x) yR(y))Q(x)中量词x的辖域是（ ）。
答：P(x) yR(y)
15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。
答：x(R(x)Q(x))
二、求下列各公式的主析取范式和主合取范式： 1、(P→Q)R
解：(P→Q)R(PQ )R
(PR)(QR) （析取范式）
(P(QQ)R)((PP)QR)
(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)（主析取范式）
((P→Q)R)(PQR)(PQR)(PQR)
(PQR)( PQR)（原公式否定的主析取范式）
(P→Q)R(PQR)(PQR)(PQR)
3
(PQR)(PQR)（主合取范式）
2、(PR)(QR)P
解： (PR)(QR)P（析取范式）
(P(QQ)R)((PP)QR)(P(QQ)(RR)) (PQR)(PQR)(PQR)(PQR)
( PQR)( PQR)(PQR)(PQR)
(PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式)
（(PR)(QR)P）
(PQR)(PQR）
（原公式否定的主析取范式） (PR)(QR)P (PQR)(PQR)（主合取范式）
3、(P→Q)(RP)
解：(P→Q)(RP)
(PQ)(RP)（合取范式）
(PQ(RR))(P(QQ))R)
(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)（主合取范式）
((P→Q)(RP))
(PQR)(PQR)(PQR)(PQR)
(PQR)（原公式否定的主合取范式）
(P→Q)(RP)
(PQR)(PQR)(PQR)(PQR)(PQR) （主析取范式）
4、Q→(PR)
解：Q→(PR)
4
QPR（主合取范式） （Q→(PR)）
(PQR)(PQR)(PQR)(PQR) （原公式否定的主合取范式） (PQR)(PQR)(PQR）
Q→(PR)
(PQR)(PQR)(PQR)(PQR)(PQR) （主析取范式） (PQR)(PQR）
5、P→(P(Q→P))
解：P→(P(Q→P))
P(P(QP)) PP T (主合取范式)
(PQ)(PQ)(PQ)(PQ)（主析取范式）
6、(P→Q)(RP)
解： (P→Q)(RP)(PQ)(RP)
(PQ)(RP)（析取范式） (PQ(RR))(P(QQ)R)
(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)（主析取范式）
((P→Q)(RP))(PQR)(PQR)(PQR)
(PQR)(PQR)（原公式否定的主析取范式）
(P→Q)(RP)(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
7、P(P→Q)
解：P(P→Q)P(PQ)(PP)Q
5
T(主合取范式)
(PQ)(PQ)(PQ)(PQ)（主析取范式）
8、(R→Q)P
解：(R→Q)P(RQ )P
(RP)(QP) （析取范式） (R(QQ)P)((RR)QP)
(RQP)(RQP)(RQP)(RQP) (PQR)(PQR)(PQR)（主析取范式）
((R→Q)P)(PQR)(PQR）(PQR)
(PQR)(PQR)（原公式否定的主析取范式）
(R→Q)P(PQR)(PQR)(PQR)
(PQR)(PQR)（主合取范式）
9、P→Q
解：P→QPQ（主合取范式）
(P(QQ))((PP)Q)
(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)（主析取范式）
10、 PQ
解： PQ （主合取范式）
(P(QQ))((PP)Q） (PQ)(PQ)(PQ)(PQ） (PQ)(PQ)(PQ)（主析取范式）
6
三、证明：
1、P→Q，QR，R，SP=>S
证明：
(1) R 前提 (2) QR 前提 (3) Q （1），（2） (4) P→Q 前提 (5) P （3），（4） (6) SP 前提 (7) S （5），（6）
2、A→(B→C)，C→(DE)，F→(DE),A=>B→F
证明：
(1) A 前提 (2) A→(B→C) 前提 (3) B→C （1），（2）
(4) B 附加前提 (5) C （3），（4） (6) C→(DE) 前提 (7) DE （5），（6） (8) F→(DE) 前提 (9) F （7），（8）
7
(10) B→F CP
3、PQ， P→R, Q→S => RS
证明：
(1) R 附加前提 (2) P→R 前提 (3) P （1），（2） (4) PQ 前提 (5) Q （3），（4） (6) Q→S 前提 (7) S （5），（6） (8) RS CP，（1），（8）
4、(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R => P
证明：
（1） P 假设前提 （2） P→R 前提 （3） R （1），（2） （4） (P→Q)(R→S) 前提 （5） P→Q （4） （6） R→S （5） （7） Q （1），（5） （8） S （3），（6） （9） (Q→W)(S→X) 前提
8
（10） Q→W （9） （11） S→X （10） （12） W （7），（10） （13） X （8），（11） （14） WX （12），（13） （15） (WX) 前提
（16） (WX)(WX) （14），（15）
5、(UV)→(MN), UP, P→(QS)，QS =>M
证明：
(1) QS 附加前提 （2） （3） （4） （5） （6） （7） （8） （9）
P→(QS) 前提 P （1），（2） UP 前提 U （3），（4） UV （5） (UV)→(MN) 前提 MN (6),(7) M （8）
6、用真值表法证明ＰＱ (ＰＱ)(ＱＰ)
证明、
列出两个公式的真值表：
9
P Q PQ （PQ）（QP） F F F T T F T T T T F F F F T T 由定义可知，这两个公式是等价的。
7、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?
前提: (1) 若A队得第一，则B队或C队获亚军;
(2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) A 队获第一; 结论: (5) D队不是亚军。
证明、
设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A（BC），CA，DB，A；结论符号化为 D。 本题即证明 A（BC），CA，DB，AD。 （1） A 前提 （2） A（BC）前提 （3） BC （1），（2） （4） CA 前提 （5）
C （1），（4）
10
（6） B （3），（5） （7） DB 前提 （8） D （6），（7）
8、用推理规则证明PQ, (QR),PR不能同时为真。
证明、
(1) PR (2) P (3) PQ (4) Q (5) (QR) (6) QR (7) Q (8) QQ 。
前提 (1) 前提 (2),(3) 前提 (5) (6) (4),(7)
11
因篇幅问题不能全部显示，请点此查看更多更全内容