③ ～S T①②I ④ ～S→～R P
⑤ ～R T③④I ⑥ Q∨R P
⑦ Q T⑤⑥I ⑧ Q→T P
⑨ T T⑦⑧I 即 金刚是偷窃者
23、利用消解法证明下列各蕴含式：
（3）P→(Q→R),Q→(R→S) ? P→(Q→S) 证明： P→(Q→R) ? ～P∨～Q∨R Q→(R→S) ? ～Q∨～R∨S ～（P→(Q→S)）? P∧Q∧～S
因此子句集合 = { ～P∨～Q∨R，～Q∨～R∨S，P，Q，～S } 消解过程如下：
[1] ～P∨～Q∨R p [2] P p
[3] ～Q∨R 由[1，2]归结 [4] Q p
[5] R 由[3，4]归结 [6] ～Q∨～R∨S p [7] ～S p
[8] ～Q∨～R 由[6，7]归结 [9] ～R 由[4，8]归结 [10] FLASE □ 由[5，9]归结 导出空子句
习题二
1、把下列谓词翻译成谓词公式
（1）每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数 解： R(x) -- x是实数 Ra(x) -- x是有利数
翻译如下：?(x)( Ra(x) → R(x)) ∧～?(x)( R(x) →Ra(x))∧?(x)( R(x)) ∧Ra(x)） （2）直线a和b平行当切仅当a和b不相交 解： A(x) -- x是直线 F(x，y) -- x与y平行 G（x,y) -- ｘ与ｙ相交
翻译如下：?(ａ)?(ｂ)（A(ａ)∧A(ｂ)→ (F(ａ，ｂ) ?～G（ａ,ｂ)）) （3）除非所有的会员都参加，这个活动才有意义 解： A(x) -- ｘ是会员 B(x) -- x有意义 ａ -- 这个活动 F(x，y) -- ｘ参加ｙ
翻译如下：B（ａ）→?(x)（A(x)→F(x，ａ)）
或 ～?(x)（A(x)→F(x，ａ)）→～B（ａ） （4）任何正整数不是合数就是质数 解： A(x) -- ｘ是正整数 Ｂ(x) -- ｘ是合数 Ｃ(x) -- ｘ是质数
翻译如下：?(x)（A(x)→Ｂ(x)?Ｃ(x)）
（6） 凡是存钱的人都想有利息，如果没有利息，人们就不会存钱 解： A(x) -- ｘ是存钱的人
F(x，y) -- ｘ想有ｙ P -- 存钱没有利息 Q: -- 人们不存钱 a: -- 利息
翻译如下：?(x)（A(x)→F(x，a)）∧（P→Q）
2、设论域D = {0, 1, 2}，把下列公式用不含量词的公式表示出来
（3）?(x)[ ～P(x)] ∨ ?(x)Q(x)
解：上式 ? （～P(0) ∧ ～P(1) ∧ ～P(2)）∨ Q(0) ∨ Q(1) ∨ Q(2)
3、指出下列公式中的约束变元和自由变元，并确定公式的辖域
解：略
5、把下列语句符号化，并确定相应谓词公式是永真式、可满足式、还是矛盾式
（1）如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和x+1的积也不等于0
解：设论域在任意数域集合，运用常规的数学符号，翻译如下
?(x) ?(y)( xy = 0 → (x=0 ∨ y=0)) ∧ ((x-1 ≠0) → ((x-1)(x+1) ≠ 0))
这是一个可满足式，但不是永真式，因为存在x=-1时，谓词公式不成立，但其它情况均成立，如果论域中不包含-1，为真，包含就不成立
（2）诚实的人都讲实话。小林不是诚实的，因而小林不讲实话 解： H(x) -- x诚实 T(x) -- x讲真话 a -- 小林 翻译如下： （?(x)(H(x) →T(x)) ∧～H(a)） →～T(a) 这是一个可满足式，因为否定条件命题前件，不一定后件命题一定为假。及小林虽然不诚实，但也可能讲实话
6、对于题目给定的解释，求下列各公式相应的真值
（1） A = ?(x)[ P(x) ∨Q(x)] ∧R(a)，解释 D ={1,2,3}，P(x): x2+x=2; Q(x): x是素数；R(x): x<3; a = 1
解： 根据解释，A变为 （P(1) ∨Q(1)）∧（P(2) ∨Q(2)）∧（P(3) ∨Q(2)）∧R(1)，根据P(x), Q(x), R(x)的定义，显然P(1) ∨Q(1) = 1，P(2) ∨Q(2) = 1，P(3) ∨Q(2) = 1，R(1) =1，所以整个公式解释为真 （2） A=P(a, f(b)) ∧P(b,f(a)), B=?(x) ?(y)P(y,x), C = ?(y) ?(x)P(y,x), E = ?(x) ?(y)[P(x,y) →P(f(x),f(y))]，解释：D={2,3}, a = 3, b = 2, f(2)=3, f(3) =2，P(2,2)=0, P(2,3)=0, P(3,2)=P(3,3) = 1 解： 根据解释，
A变为 P( 3, 3 ) ∧ P( 2, 2 ) = 1 ∧ 0 = 0 ， 真值为假 B变为 (P(2,2) ∨P(2,3)) ∧(P(3,2) ∨P(3,3)) = （0∨0）∧（1∨1）= 0， 真值为假 C变为 (P(2,2) ∧P(2,3)) ∨(P(3,2) ∧P(3,3)) = （0∧0）∨（1∧1）= 1， 真值为真 E变为 (P(2,2) →P(3,3)) ∧(P(2,3) →P(3,2)) ∧(P(3,2) →P(2,3)) ∧(P(3,3) →P(2,2)) = （0→1）∧（0→1）∧（1→0）∧（1→0）= 0， 真值为假
7、设论域为整数集合Z，试判定下面各公式是否是永真式，矛盾式或可满足式
2
（1）?(x)[x>-10∧x?0] 答：为假命题
（2）?(x)[2x>8∧x2-6x+5?0]
答：为真命题，当4，5使满足谓词公式 （3）?(x) ?(y)[x+y=1024]
答：为真命题，对任意整数x，y取值为1024-x及可 （4）?(y) ?(x)[xy<10∨x+y?2] 答：为真命题，y=0及成立
9、证明下列各式成立：
（1）?(x) ?(y)[P(x) →Q(y)] ??(x)P(x) →?(y)Q(y)
证明：右式 ? ?(x) ?(y)[~ P(x) ∨ Q(y)] ? ?(x) ~ P(x) ∨?(y)Q(y) ??(x)P(x) →?(y)Q(y)
10、判别?(x)[P(x) →Q(x)]? ?(x)P(x) →?(x)Q(x)是否成立，如果成立，请给出证明；如果不成立，找一个解释予以说明
解：?(x)[P(x) →Q(x)] ? ?(x)[ ～P(x) ∨Q(x)] ? ?(x) ～P(x) ∨?(x)Q(x) ? ?(x) P(x) →?(x)Q(x) 显然和?(x)P(x) →?(x)Q(x)不等价，现构造如下解释
设论域为D={a,b}，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 则?(x)[P(x) →Q(x)]解释为真，而?(x)P(x) →?(x)Q(x)解释为假，所以不等价
11、把下列公式化为等价的前束范式，再求出对应的SKolem范式
（4）?(x)[ ～P(x,0) →(?(y)P(y,f(x)) ∧?(z)Q(x,z))]
解：原式 ? ?(x)[ P(x,0) ∨(?(y)P(y,f(x)) ∧ ?(z)Q(x,z))] ? ?(x) ?(y) ?(z) [ P(x,0) ∨(P(y,f(x)) ∧ Q(x,z))]
其SKolem范式为：?(x) ?(z) [ P(x,0) ∨(P(g(x),f(x)) ∧ Q(x,z))]
13、证明下列各式成立
（1）?(x) ?(y)[P(x) ∧Q(y)] ??(x)P(x)
证明：左式 ? ?(x) P(x) ∧?(y)Q(y) ? ?(x)P(x) （2）~(?(x)P(x) ∧Q(a)) ??(x)P(x) →~Q(a)
证明：左式 ? ~?(x)P(x) ∨~Q(a) ? ?(x)P(x) →~Q(a)
15、下面给出了对?(x) [P(x) ∨Q(x)] ??(x) P(x) ∨?(x)Q(x)]的证明： （原证明过程略）
试判断这个证明是否正确。你能给出一个证明吗？
答：这个证明不正确，因为：如果 P ? Q 则~Q? ~P 而 ~ P ? ~ Q不一定成立，因此在这个证明过程中，第二步到第三步的蕴含不成立
17、判别下面各个推理是否正确，如果不正确，指出错在什么地方（题目不再重复）
（1）答：不正确，全称指定应该变为其他非x的变元，可修改为：P(y) →Q(x) （2）答：正确
（3）答：不正确，全称指定应该使用相同的个体常量，可修改为：P(a) ∨Q(a) （4）答：题目不正确，存在量词的指导变元应该是另外的变元符号
（5）答：不正确，存在量词的辖域应该包含全部的谓词，可修改为：?(x)[P(x) →Q(x) ]
（6）答：不正确，对不同的个体常元应该用不同的变元进行存在指定，可修改为：?(x)[P(x) →Q(b) ]
（7）答：不正确，推理过程中，应该先使用存在指定，然后使用全称指定
习题三
4、仔细区分集合中的关系符号 ∈ 和?，并判断下列各蕴含关系的真假 （题目内容，见课本）
（1）真，根据子集的定义，任何属于B集合的元素也属于C集合
（2）假，例如：A = {1,2} B = {{1,2}, 2, 3} C=B，1属于A，但并不是C集的元素 （3）假，例如：A={1,2} B={1,2,3} C={{1,2,3}}，A不是C的元素 （4）假，例如：A={1,2} B={1,2,3} C={{1,2,3}}，A不是C的子集 （5）假，例如：A=1 B={1,2,3} C={{1,2,3}}，A不是C的元素 （6）真，子集关系具有传递性
9、证明下列各式
（1）A∩(B-C) = (A∩B)-(A∩C)
证明：左式 = A∩(B∩~C) = (A∩B∩~C) ∪ (A∩B∩~A) = (A∩B) ∩(~C∪~A) = (A∩B) ∩ ~ (A∩C) = (A∩B)-(A∩C) = 右式 （2）A - (B∪C) = (A-B) ∩(A-C)
证明：右式 = (A∩~B)∩(A∩~C) = A∩~B∩~C = A∩~(B∪C) = A - (B∪C) = 左式 （3）(A-B)-C = A-(B∪C)=(A-C)-B
证明：(A-B)-C = A∩~B∩~C = A∩~(B∪C) = A-(B∪C) = A∩~C∩~B = (A-C)-B （4）A∩(B∪C)=(A∩B) ∪C ? C?A 证明：充分性
∵ A∩(B∪C)=(A∩B) ∪C ? (A∩B) ∪(A∩C) = (A∩B) ∪C
假设C不是A的子集，则C中必存在元素c在C中而不在A中，那么c一定不在等式的左端集合中，而一定在右端集合中，矛盾 ∴ C?A 必要性
∵ C?A ，∴ A∩C = C ，等式两端同时并上另一个集合，等式成立 ∴ (A∩B) ∪(A∩C) = (A∩B) ∪C ? A∩(B∪C)=(A∩B) ∪C （5）A∩(B⊕C) = (A∩B) ⊕(A∩C)
证明：左式 = A∩（B ∪C-B∩C）= A∩（(B ∪C) ∩(~B∪~C)）= A∩(B ∪C) ∩(~B∪~C)=AB~C + AC~B
右式 = （(A∩B) ∪(A∩C)）- （(A∩B) ∩(A∩C)）= （A∩(B∪C)）∩~（A∩B∩C）= A∩(B∪C) ∩(~A∪~B∪~C) = AB~C + AC~B 所以，左式 = 右式
10、下面三式中，哪个可得出B=C的结论
（1）A∪B=A∪C
答：不能得出此结论，因为如果 B ≠ C,但B,C都是A的子集，A∪B=A∪C成立 （2）A∩B=A∩C
答：不能得出此结论，因为B ≠ C，但A是C∩B子集，A∩B=A∩C成立
