数理逻辑_复习题及参考答案
- 格式：doc
- 大小：87.50 KB
- 文档页数：3
从一份模拟试题中抽取出来的《数理逻辑》复习题及参考答案
一、单选题（每小题2分，共20分）
1 以下语句是命题的是（ ）。
A ． y 等于x 。
B ． 每个自然数都是奇数。
C ． 请爱护环境。
D ． 你今天有空吗？
2 设α是一赋值，α(p)= α(q)=1，α(r)=0，下列公式的值为假的是（ ）。
A ．p ∧(q ∨r)
B ．(p r) ↔ (¬r q)
C ．(r q) ∧(q p)
D ．(r q)
3 以下联结词的集合（ ）不是完备集。
A ．{¬,∧,∨, ,↔}
B ．{¬,∧,∨}
C ．{¬, }
D ．{∧,∨}
4 公式A 的对偶式为A*，下列结果成立的是（ ）。
A ．A ↔A*
B ．¬A ↔A*
C ．A|=|A*
D ．¬A|=|A*
5 假设论域是正整数集合，下列自然语言的符号化表示中，（ ）的值是真的。
A ．∀x ∃yG(x,y)，其中G(x,y)表示xy=y
B ．∀x ∀yF(x,y)，其中F(x,y)表示x+y=y
C ．∃x ∀yH(x,y)，其中H(x,y)表示x+y=x
D ．∀x ∀yM(x,y)，其中M(x,y)表示xy=x
6．以下式子错误的是（ ）。
A ．∀x ¬A(x) |=| ¬∃xA(x)
B ．∀x(A(x)∧B(x)) |=| ∀xA(x)∧∀x B(x)
C ．∃x(A(x)∨B(x)) |=| ∃xA(x)∨∃x B(x)
D ．∀x(A(x)∨B(x)) |=| ∀xA(x)∨∀x B(x)
7. 下列式子（ ）不正确。
A ．{x}∈{{x}}
B ．{x}∈{{x},x}
C ．{x}⊆{{x}}
D ．{x}⊆{{x},x}
二、填空题（每小题2分，共20分）
1．句子“只有小王爱唱歌，他才会弹钢琴。
”中，把“小王爱唱歌”形式化为命题符p ，“小王会弹钢琴”形式化为命题符q ，则句子形式化为公式 。
2．公式¬(¬p ∧¬q)∨(¬p ∧q)∨t 的对偶是 。
3．公式)()(x xB x xA ∃→∀的前束范式是 。
4．公式∀xA(x)∨B(y)中，∀量词的辖域是 ，自由变元
是 。
三、计算题（30分）
1．（6分）用等值演算法计算命题公式)()(q p q p ⌝↔→⌝∨⌝的析取范式和主析取范式。
四、证明题（20分）
1．（6分）用讨论指派的方法证明A →(B →C)|=| (A →B)→(A →C)
五、综合题（10分）
在谓词逻辑自然推理系统FND 中，构造下面的证明。
要求写出所有谓词的含义，分别写出前提、结论和证明过程。
“某学术会议的每个成员都是专家也是工人。
有些成员是青年人。
所以，有些成员是青年专家。
”
参考答案
一、单选题（20分）
1 B
2 B
3 D
4 D
5 A 6．D 7. C
二、填空题（20分）
1．q →p
2．¬(¬p ∨¬q)∧(¬p ∨q)∧f
3． ))()((x B x A x ∨⌝∃
三、计算题（30分）
1． )
()()(||)
()()()()(||)()()(||)
()()(||)()(q p q p q p q q p q q p p p q p p q q p q p p q q p q p q p q p ⌝∧∨∧⌝∨∧=∧⌝∨∧⌝∨∧⌝∨∧⌝∨∧=∨∧⌝∨⌝∨∧=→⌝∧⌝→∨⌝∨⌝⌝=⌝↔→⌝∨⌝ 倒数第二步可以算做析取范式；最后一步既是析取范式也是主析取范式。
四、证明题（20分）
1．证明：当赋值α使左式为真时，有α(A)=0或α(A)=1且α(B→C)=1。
当α(A)=0时，α(A→B)＝α(A→C)＝1，所以α((A→B)→(A →C))＝1。
α(A)=1且α(B→C)=1时，有α(B)＝0或α(B)＝1且α(C)＝1。
α(A)=1且α(B)＝0时，α(A→B)＝0，α((A→B)→(A →C))＝1。
α(A)=1且α(B)＝1且α(C)＝1时，α(A→B)＝α(A→C)＝1，所以α((A→B)→(A →C))＝1。
因此A →(B →C)|= (A →B)→(A →C)。
当赋值α使右式为真时，为证α((A→B)→(A →C))＝1时有α(A→(B →C))＝1，等价于证α(A→(B →C))＝0时有α((A→B)→(A →C))＝0。
α(A→(B →C))＝0时，α(A)=1且α(B→C)=0，即α(A)=1且α(B)＝1且α(C)＝0。
此时α(A→B)＝1，α(A→C)＝0，所以α((A→B)→(A →C))＝0。
因此(A →B)→(A →C)|= A →(B →C)。
因此A →(B →C)|=| (A →B)→(A →C)。
五、综合题（10分）
解答：设谓词：S(x): x 是专家；W(x): x 是工人；Y(x): x 是青年人。
前提：);()),()((x xY x W x S x ∃∧∀
结论：))()((x Y x S x ∧∃
证明过程：
（1）)(x xY ∃ 前提引入
（2）Y(c) （1），ES
（3）))()((x W x S x ∧∀
前提引入 （4）S(c)∧W(c)
(3), US （5）S(c) (4) T, I
（6）S(c) ∧Y(c) (2)(5) T, E
（7）))()((x Y x S x ∧∃
(6), EG。
