离散数学谓词逻辑

谓词逻辑习题课第九周.11第1页命题符号化讨论在给定解释下谓词公式真值判断公式是不是永真式，并加以说明转换前束合取范式推理证实第2页1.将以下命题符号化(1)没有不犯错误人(2)发光不都是金子(3)一切人都不一样高(4)并不是全部汽车都比火车快(5)不论黑猫白猫，抓住老鼠就是好猫(6)有唯一偶素数(7)对平面上任意两点，有且仅有一条直线经过这两点第3页(1)没有不犯错误人①存在不犯错误人是不可能。②只要是人，必定犯错误。 设M(x):x是人，F(x):x犯错误 命题符号化为①┐(x)(M(x)∧┐F(x))

②(x)(M(x)→F(x))(2)发光不都是金子

①不是发光东西都是金子。②存在着发光东西不是金子。 设L(x)：x是发光东西，G(x)：x是金子。 命题符号化为

①┐(x)(L(x)→G(x))

②(x)(L(x)∧﹁G(x))

第4页(3)一切人都不一样高设F(x):x是人,H(x,y),x与y相同,L(x,y):x与y一样高，

命题符号化为

(x)(F(x)

y(F(y)

H(x,y)

L(x,y)))

或

(x)y(F(x)

F(y)

H(x,y)

L(x,y))(4)并不是全部汽车都比火车快设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快，命题符号化为

(x)y(F(x)

G(y)

H(x,y))

或(x)y(F(x)

G(y)

H(x,y))第5页（5）不论黑猫白猫，抓住老鼠就是好猫

需要考虑问题： ①只是限制黑猫白猫，还是包含其它颜色猫？ ②是指最少抓住一只就能够，还是抓住全部？设C(x):x是猫,W(x):x是白,B(x):x是黑

G(x):x是好,M(x):x是老鼠,

K(x):x抓住y

命题符号化为

(x)y(C(x)∧M(y)∧(B(x)∨W(x))∧K(x,y))→G(x))

第6页

(6)有唯一偶素数设：Q(x):x是偶数,P(x):x是素数,

E(x,y):x＝y

命题符号化为：

(x)(Q(x)

P(x)y(Q(y)

P(y)

E(x,y)))

(7)对平面上任意两点，有且仅有一条直线经过这

两点设P(x):x是一个点,L(x):x是一条直线

R(x,y,z):z经过x,y,E(x,y):x等于y

命题符号化为

(x)y(P(x)∧P(y)∧﹁E(x,y))→z(L(z)∧R(x,y,z)∧u((L(u)∧R(x,y,u))→E(u,z)))第7页2.讨论在给定解释下谓词公式真值（1）

x(P→Q(x))∨R(a)

D={-2,3,6}

,P:2>1,Q(x):x≤3,R(x):x>5,a:5（2）

x

y(P(x)∧Q(x,y)) D={1,2}，

P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTTTFF第8页（1）

x(P→Q(x))∨R(a)

D={-2,3,6}

,P:2>1,Q(x):x≤3,R(x):x>5,a:5

x(P→Q(x))∨R(a)(P→

xQ(x))∨R(a)(P→(Q(-2)∧Q(3)∧Q(6)))∨R(5)(T→(T∧T∧F))∨F(T→F)∨F

F∨F

F（2）

x

y(P(x)∧Q(x,y)) D={1,2}，

P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTTTFF

真值为F第9页3.判断以下公式是不是永真式，并加以说明（1）(

xP(x)→

xQ(x))↔

x(P(x)→Q(x))解：不是永真式，取解释以下

D={1,2}

P(1)P(2)Q(1)Q(2)

F

T

F

T

在该解释下xP(x)为T，xQ(x)为F，所以xP(x)→

xQ(x)为F；而(P(1)→Q(1))为T，(P(2)→Q(2))为T，所以x(P(x)→Q(x))为T；综上该公式不是永真式第10页4.转换前束合取范式(1)将谓词公式(

x)[(

y)P(x)

(

z)Q(z,y)

(

y)R(x,y)]化为与之等价前束合取范式第一步，取消多出量词：

(

x)[P(x)

(

z)Q(z,y)

(

y)R(x,y)]第二步，约束变量换名：

(

x)[P(x)

(

z)Q(z,y)

(

w)R(x,w)]第三步，消去条件联结词：

(

x)[

(P(x)

(

z)Q(z,y))

(

w)R(x,w)]第四步，将

深入：

(

x)[(

P(x)

(

z)Q(z,y))

(

w)

R(x,w)]

(

x)[(

P(x)

(

z)

Q(z,y))

(

w)

R(x,w)]第五步，将量词提前：

(

x)(

z)(

w)[(

P(x)

Q(z,y))

R(x,w)]

(

x)(

z)(

w)[(

P(x)

R(x,w))

(

Q(z,y)

R(x,w))

]第11页5.推理证实：(1)(x)(P(x)∨Q(x)(x)P(x)∨(x)Q(x)因为(x)P(x)∨(x)Q(x)(x)P(x)→(x)Q(x)⑴(x)P(x)P(附加前提)⑵(x)

P(x)T⑴E⑶P(a)ES⑵⑷(x)(P(x)∨Q(x)P⑸P(a)∨Q(a)US⑷⑹Q(a)T⑶⑸I⑺(x)Q(x)EG⑹⑻(x)P(x)→(x)Q(x)CP第12页(2)

xP(x)∨

xQ(x)

x(P(x)∨Q(x))(1)

x(P(x)∨Q(x)) P(假设)(2)

x

(P(x)∨Q(x)) T(1)E(3)

(P(c)∨Q(c)) ES(2)(4)

P(c)∧

Q(c) T(3)E(5)

P(c) T(4)I(6)

x

P(x) EG(5)(7)

xP(x) T(6)E(8)

xP(x)∨

xQ(x) P (9)

xQ(x) T(7)(8)I(10)Q(c) US(9)(11)

Q(c) T(4)I(12)Q(c)∧

Q(c) T(10)(11)I第13页

(3)每个大学生不是文科生就是理工科生，有大学生是优等生，小张不是理工科生，但他是优等生，所以假如小张是大学生，他就是文科生。

设A(x):x是大学生,B(x):x是文科生,C(x):x是理工科生，D(x):x是优等生,

a:小张

x(A(x)→(

B(x)→C(x))),

x(A(x)∧D(x))

C(a)∧D(a)

A(a)→B(a)第14页x(A(x)→(

B(x)→C(x))),x(A(x)∧D(x))

C(a)∧D(a)

A(a)→B(a)⑴A(a)P(附加前提)⑵x(A(x)→(

B(x)→C(x)))P⑶A(a)→(

B(a)→C(a))US⑵⑷B(a)→C(a))T⑴⑶I⑸C(a)∧D(a)P⑹C(a)T⑸I⑺B(a)T⑷⑹I⑻B(a)T⑺E⑼A(a)→B(a)CP第15页(4)全部有理数是实数，一些有理数是整数，所以一些实数是整数。

设Q(x):x是有理数R(x):x是实数I(x):x是整数

(x)(Q(x)→R(x)),(x)(Q(x)∧I(x))

(x)(R(x)∧I(x))⑴(x)(Q(x)∧I(x))P⑵Q(a)∧I(a)ES⑴⑶Q(a)T⑵I⑷I(a)T⑵I⑸(x)(Q(x)→R(x))P⑹Q(a)→R(a)US⑸

⑺R(a)T⑶⑹I⑻R(a)∧I(a)T⑷⑺I⑼(x)(R(x)∧I(x))EG⑻第16页(5)小杨、小刘和小林为高山俱乐部组员，该俱乐部每个组员是个滑雪者或登山者。没有一个登山者喜欢雨。而全部滑雪者都喜欢雪。凡是小杨喜欢，小刘就不喜欢。小杨喜欢雨和雪。试证实该俱乐部是否有个是登山者而不是滑雪者组员。假如有，他是谁？设：M(x):x是高山俱乐部组员。H(x):x是滑雪者。

D(x):x是登山者。L(x,y):x喜欢y。

a:小杨；b:小刘；c:小林；d:雨；e:雪。第17页M(x):x是高山俱乐部组员。H(x):x是滑雪者。

D(x):x是登山者。L(x,y):x喜欢y。a:小杨；b:小刘；c:小林；d:雨；e:雪。命题符号化为：M(a),M(b),M(c),(x)(M(x)→(H(x)∨D(x))),(x)(D(x)∧L(x,d)),(x)(H(x)→L(x,e))(x)(L(a,x)→

L(b,x)),L(a,d)∧L(a,e)⑴L(a,d)∧L(a,e)P⑵L(a,e)T⑴⑶(x)(L(a,x)→

L(b,x))P⑷L(a,e)→

L(b,e))US⑶⑸

L(b,e))T⑵⑷I11⑹(x)(H(x)→L(x,e))P⑺H(b)→L(b,e))US⑹⑻

H(b)