習題(第二章一階邏輯)080923演示教學

離散數(shù)學習題課（二）主講姜虹第二章一階邏輯（習題）

1.將下列命題用0元謂詞符號化：1）小王學過英語和法語。2）除非李健是東北人，否則他一定怕冷。3）2大于3僅當2大于4。4）3不是偶數(shù)。5）2或3是素數(shù)。F(X):小王學過X。a:英語，b:法語。F(a)∧F(b)。F(X):X是東北人。G(X):X一定怕冷。a:李健。F(a)G(a)。F(X，Y):X>Y。a:2，b:3，c:4。F(a，b)F(a，c)。F(X):X是偶數(shù)。a:3。F(a)F(X):X是素數(shù)。a:2，b:3。F(a)∨F(b)。第二章一階邏輯（習題）

2.在一階邏輯中將下列命題符號化，并討論個體域為(a),(b)時命題的真值。1）凡有理數(shù)都能被2整除。2）有的有理數(shù)都能被2整除。其中，(a)個體域為有理數(shù)集合。(b)個體域為實數(shù)集合。1-a）F(X):X能被2整除。ｘＦ(ｘ)。假1-b）G(X):X是有理數(shù)。ｘ（G(X)F(X)）。假2-a）F(X):X能被2整除。ｘＦ(ｘ)。真2-b）G(X):X是有理數(shù)。ｘ（G(X)∧F(X)）。真第二章一階邏輯（習題）

3.在一階邏輯中將下列命題符號化，并討論個體域為(a),(b)時命題的真值。1）對任意的x，均有。2）存在x，使得x+5=9。其中，(a)個體域為自然數(shù)集合。(b)個體域為實數(shù)集合。1-a）F(X):ｘＦ(ｘ)。真1-b）G(X):X是自然數(shù)。ｘ（G(X)F(X)）。真2-a）F(X):ｘＦ(ｘ)。真2-b）G(X):X是自然數(shù)。ｘ（G(X)∧F(X)）。真第二章一階邏輯（習題）

4.在一階邏輯中將下列命題符號化。1）在北京賣菜的人不全是外地人。2）烏鴉都是黑色的。3）有的人天天鍛煉身體。F(X):X是在北京賣菜的人，G(X):X是外地人。ｘ（F(X)G(X)），ｘ（F(X)∧G(X)）2）F(X):X是烏鴉，G(X):X是黑色的。ｘ（F(X)G(X)），ｘ（F(X)∧G(X)）3）F(X):X是人，G(X):X天天鍛煉身體。ｘ（F(X)G(X)），ｘ（F(X)∧G(X)）第二章一階邏輯（習題）

5.在一階邏輯中將下列命題符號化。1）火車都比輪船快。2）有的火車比有的輪船快。3）不存在比所有火車都快的汽車。4）凡是汽車就比火車慢是不對的。1）F(X):X是火車，G(X):X是輪船人，L（X，Y）:X比Y快。ｘy（F(X)∧G(Y)L(X,Y))。2）G(X):X是汽車。ｘy（F(X)∧G(Y)∧L(X,Y))4）G(X):X是汽車。M（X，Y）:X比Y慢。(ｘy（F(x)∧G(y)M(Y,X))。3）G(X):X是汽車。ｘ（G(X)∧y(F(y)L(X,Y))。第二章一階邏輯（習題）

6.將下列命題符號化，個體域為R，并指出其真值。1）對所有的X，都存在Y，使得X·Y=0。2）存在著X，對所有的Y，都有X·Y=0。3）對所有的X，都存在Y，使得Y=X+1。4）對所有的X，Y都有X·Y=Y·X。1）F（X，Y）:X·Y=0，ｘyF（X，Y）。真2）F（X，Y）:X·Y=0，ｘyF（X，Y）。真4）F（X，Y）:X·Y=Y·X，ｘyF（X，Y）。真3）F（X，Y）:Y=X+1，ｘyF（X，Y）。真第二章一階邏輯（習題）

7、將下列各公式翻譯成自然語言,個體域為整數(shù)集,并判斷各命題的真假。1）ｘyz(x-y=z)。2）ｘy(x·y=1)。3）ｘyz(x+y=z)。2）對任意的整數(shù)X,都存在整數(shù)Y,使得x·y=1。假3）存在整數(shù)X,對任意的整數(shù)Y和Z,都使得x+y=z。假1）對任意的整數(shù)X和Y,都存在整數(shù)Z,使得x-y=z。真第二章一階邏輯（習題）

8、指出下列各公式中的指導變元,量詞的轄域,各變元的自由出現(xiàn)和約束出現(xiàn)。1）ｘ（F(X)G(X,Y))。2）ｘF(X,Y)yG(X,Y))。3）ｘy(F(X,Y)∧G(Y,Z))∨XH(X,Y,Z)。2）指導變元:X,Y，轄域:（ｘ）:F(X,Y),（y）:G(X,Y)，自由出現(xiàn):X，Y,約束出現(xiàn):X，Y。3）指導變元:X，Y，Z，轄域:（ｘ）:F(X,Y)∧G(Y,Z)（y）:F(X,Y)∧G(Y,Z)（X）:H(X,Y,Z)自由出現(xiàn):Y，Z約束出現(xiàn):X，Y。1）指導變元:X,轄域:F(X)

G(X,Y),自由出現(xiàn):Y,約束出現(xiàn):X。第二章一階邏輯（習題）

9、給定解釋I如下:a）個體域D為實數(shù)集合R。b）D中特定元素a=0。c）特定函數(shù)f(x,y)=x-y。d）特定謂詞F(x,y):x=y，G(x,y):x<y。說明下列公式在I下的含義，并指出各公式的真值。1）ｘY（G(X,Y)F(X，Y))。2）ｘY（F(f(x,y),a)G(X,Y))。3）ｘy(G(X,Y)F(f(x,y),a))4）ｘY（G(f(x,y),a)F(X,Y))。第二章一階邏輯（習題）

解:1）ｘY（（x<y)(x=y))。任意的實數(shù)X和Y，如果x小于y，則x不等于y。真2）ｘY（（x-y=0)(x<y))。任意的實數(shù)X和Y，如果x-y=0，則x<y。假3）ｘy((x<y)(x-y=0))。任意的實數(shù)X和Y，如果x小于y，則x-y不等于0。真4）ｘY（(x-y<0)(x=y))。任意的實數(shù)X和Y，如果x-y小于0，則x等于y。假第二章一階邏輯（習題）

10、給定解釋I如下:a）個體域D為自然數(shù)集合N。b）D中特定元素a=2。c）特定函數(shù)f(x,y)=x+y，g(x,y)=x·y。d）特定謂詞F(x,y):x=y。說明下列公式在I下的含義，并指出各公式的真值。1）ｘF(g(x,a)，x))。2）ｘY（F(f(x,a),y)F(f(y,a),x))。3）ｘyzF(f(x,y),z)。4）ｘF(f(x,x),g(x,x))。第二章一階邏輯（習題）

解:1）ｘ（x·2=x)。任意的自然數(shù)X，都有x·2=x。假2）ｘY（（x+2=y)(y+2=x))。任意的自然數(shù)X和Y，如果x+2=y，則y+2=x。假3）ｘyz(x+y=z)。任意的自然數(shù)X和Y，都存在自然數(shù)z，使得x+y=z。真4）ｘ（x+x=x·x)。存在自然數(shù)X和Y，使得x+x=x·x。真第二章一階邏輯（習題）

11.判斷下列各式的類型：1）F(x,y)(G(x,y)F(x,y))。2）ｘ（F(x)F(x))y(G(y)∧G(y))。3）ｘyF(x,y)ｘyF(x,y)。4）ｘyF(x,y)yxF(x,y)。5）ｘy(F(x,y)F(y,x))。6）（ｘF(x)yG(y)）∧yG(y)。第二章一階邏輯（習題）

解:1）P(QP)PQP1，用F(x,y)代替上式中的P，用代替上式中的Q，得F(x,y)(G(x,y)F(x,y))是永真的。2）因為F(x)F(x)F(x)F(x)1，所以ｘ（F(x)F(x))1。因為y(G(y)∧G(y))0，所以ｘ（F(x)F(x))y(G(y)∧G(y))是永假式。第二章一階邏輯（習題）

3）D:R,F(x,y):x>y,ｘyF(x,y):對任意的實數(shù)x,存在實數(shù)y,使得x>y。真ｘyF(x,y):存在實數(shù)x,對任意的實數(shù)y,使得x>y。假所以,ｘyF(x,y)ｘyF(x,y)為假。D:N,F(x,y):x>y,ｘyF(x,y):對任意的自然數(shù)x,存在自然數(shù)y,使得x>y。假ｘyF(x,y):存在自然數(shù)x,對任意的自然數(shù)y,使得x>y。假所以,ｘyF(x,y)ｘyF(x,y)為真。綜上,ｘyF(x,y)ｘyF(x,y)為可滿足的。第二章一階邏輯（習題）

4）D:R,F(x,y):x>y,ｘyF(x,y):存在實數(shù)x,對任意的實數(shù)y,使得x>y。假yxF(x,y):對任意的實數(shù)y,存在實數(shù)x,使得x>y。真所以,ｘyF(x,y)yxF(x,y)為真。D:N,F(x,y):x<y,ｘyF(x,y):存在自然數(shù)x,對任意的自然數(shù)y,使得x<y。真yxF(x,y):對任意的自然數(shù)y,存在自然數(shù)x,使得x<y。假所以,ｘyF(x,y)yxF(x,y)為假。綜上,ｘyF(x,y)yxF(x,y)是可滿足的。第二章一階邏輯（習題）

5）D:R,F(x,y):x>y,ｘy(F(x,y)F(y,x)):對任意的實數(shù)x和y,如果x>y,則y>x。假D:R,F(x,y):x+y=2,ｘy(F(x,y)F(y,x)):對任意的實數(shù)x和y,如果x+y=2,則y+x=2。真綜上,ｘy(F(x,y)F(y,x))是可滿足的。第二章一階邏輯（習題）

6）（PQ）∧Q（PQ）∧QP∧Q∧Q0,用ｘF(x)和yG(y)分別替換上式中的P,Q,可得（ｘF(x)yG(y)）∧yG(y)是永假的。第二章一階邏輯（習題）

12.證明下列各式既不是永真的也不是永假的：1）ｘ（F(x)y(G(y)∧H(x,y)))。2）ｘy（F(x)∧G(y)H(x,y))。第二章一階邏輯（習題）

1）D:N,F(x):x是偶數(shù),G(x):x是奇數(shù),H(x,y):x≥y。ｘ（F(x)y(G(y)∧H(x,y))):對任意的自然數(shù)x，如果x是偶數(shù)，則存在奇數(shù)y，使得x≥y。假D:N,F(x):x是偶數(shù),G(x):x是奇數(shù),H(x,y):x≠y。ｘ（F(x)y(G(y)∧H(x,y))):對任意的自然數(shù)x，如果x是偶數(shù)，則存在奇數(shù)y，使得x≠y。真綜上，ｘ（F(x)y(G(y)∧H(x,y)))既不是永真的也不是永假的。第二章一階邏輯（習題）

2）D:N,F(x):x是偶數(shù),G(x):x是奇數(shù),H(x,y):x≥y。ｘy（F(x)∧G(y)H(x,y)):對任意的自然數(shù)x和y，如果x是偶數(shù)，y是奇數(shù)，則x≥y。假D:N,F(x):x是偶數(shù),G(x):x是奇數(shù),H(x,y):x≠y。ｘy（F(x)∧G(y)H(x,y)):對任意的自然數(shù)x和y，如果x是偶數(shù)，y是奇數(shù)，則x≠y。真綜上，ｘy（F(x)∧G(y)H(x,y))既不是永真的也不是永假的。第二章一階邏輯（習題）

13.給出下列各式的一個成真解釋和一個成假解釋：1）ｘ（F(x)G(x))。2）ｘ（F(x)∧G(x)∧H(x))。3）ｘ（F(x)∧y(G(y)∧H(x,y)))。第二章一階邏輯（習題）

1）成真解釋:D:N,F(x):X是偶數(shù)，G(x):X是奇數(shù)，ｘ（F(x)G(x)):任意的自然數(shù)X，或是偶數(shù)，或是奇數(shù)。成假解釋:D:N,F(x):X是3，G(x):X是4，ｘ（F(x)G(x)):任意的自然數(shù)X，或是3，或是4。第二章一階邏輯（習題）

2）成真解釋:D:N,F(x):X是偶數(shù)，G(x):X是素數(shù)，H(x):X整除所有偶數(shù)。ｘ（F(x)∧G(x)∧H(x)):存在自然數(shù)X，既是偶數(shù)，又是素數(shù)，又能整除所有偶數(shù)。成假解釋:D:N,F(x):X是偶數(shù)，G(x):X是素數(shù)，H(x):X是奇數(shù)。ｘ（F(x)∧G(x)∧H(x)):存在自然數(shù)X，既是偶數(shù)，又是素數(shù)，又是奇數(shù)。第二章一階邏輯（習題）

3）成真解釋:D:N,F(x):X是偶數(shù)，G(x):X是奇數(shù)，H(x，y):x<y。ｘ（F(x)∧y(G(y)∧H(x,y))):存在偶數(shù)X，對任意的奇數(shù)y，使得x<y。成假解釋:D:N,F(x):X是偶數(shù)，G(x):X是奇數(shù)，H(x，y):x>y。ｘ（F(x)∧y(G(y)∧H(x,y))):存在偶數(shù)X，對任意的奇數(shù)y，使得x>y。第二章一階邏輯（習題）

14.設個體域D={a,b,c}，消去下列各式的量詞：1）ｘy（F(x)∧G(y))。2）ｘy（F(x)G(y))。3）ｘF(x)yG(y)。4）ｘ(F(x)yG(y))。第二章一階邏輯（習題）

14.設個體域D={a,b,c}，消去下列各式的量詞：1）ｘy（F(x)∧G(y))ｘ((（F(x)∧G(a))(（F(x)∧G(b))（F(x)∧G(c)))((（F(a)∧G(a))(（F(a)∧G(b))（F(a)∧G(c)))∧((（F(b)∧G(a))(（F(b)∧G(b))（F(b)∧G(c)))∧((（F(c)∧G(a))(（F(c)∧G(b))（F(c)∧G(c)))。第二章一階邏輯（習題）

15.設個體域D={1,2}，請給出解釋I1和I2，使得下面公式在I1下是真命題，在I2下是假命題：1）ｘ（F(x)∧G(x))。2）ｘ(F(x)G(x))。第二章一階邏輯（習題）

15.I1:D={1,2}，F(xiàn)(x):X是有理數(shù)，G(x)：X是實數(shù)；I2:D={1,2}，F(xiàn)(x):X是偶數(shù)，G(x)：X是奇數(shù)。在I1下，為真命題：1）ｘ（F(x)∧G(x))：存在X，既是有理數(shù)，又是實數(shù)。2）ｘ(F(x)G(x))：對任意的X，如果X是有理數(shù)，則X是實數(shù)。在I2下，為假命題：1）ｘ（F(x)∧G(x))：存在X，既是偶數(shù)，又是奇數(shù)。2）ｘ(F(x)G(x))：對任意的X，如果X是偶數(shù)，則X是奇數(shù)。第二章一階邏輯（習題）

16.給定公式A=ｘF(x)ｘF(x)，1）解釋I1，D={a}，證明A在I1下的真值為1。2）解釋I2，D={a1,a2,…,an},n≥2,A在I2下的真值還一定是1嗎？為什么？第二章一階邏輯（習題）

1）解釋I1，D={a}，A=ｘF(x)ｘF(x)F(a)F(a)1，2）解釋I2，D={a1,a2,…,an},n≥2,A=ｘF(x)ｘF(x)(F(1)F(2)…F(an))(F(a1)∧F(a2)∧…F(an))A在I2下的真值不一定是1。如:D={1,2}，F(xiàn)(x):X是偶數(shù)。A=ｘF(x)ｘF(x)(F(1)F(2))(F(1)∧F(2))(01)(0∧1)0。又如:D={2，4}，F(xiàn)(x):X是偶數(shù)。A=ｘF(x)ｘF(x)(F(2)F(4))(F(2)∧F(4))(11)(1∧1)1。第二章一階邏輯（習題）

17、給定解釋I如下:a)個體域D={3，4}，b)f(3)=4,f(4)=3,c)F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1，求下列公式在I下的真值。1）xyF(x,y)。2）xyF(x,y)。3）xy（F(x,y)F(f(x),f(y)))。第二章一階邏輯（習題）

1）xyF(x,y)

x(F(x,3)

F(x,4))

(F(3,3)

F(3,4))∧(F(4,3)

F(4,4))

(0

1)∧(1

0)

1。2）xyF(x,y)

x(F(x,3)∧

F(x,4))

((F(3,3)∧

F(3,4))

(F(4,3)∧

F(4,4)))

((0

∧

1)

(1

∧

0))

0。第二章一階邏輯（習題）

3）xy（F(x,y)

F(f(x),f(y)))

x(（F(x,3)

F(f(x),f(3)))∧

（F(x,4)

F(f(x),f(4)))

(（F(3,3)

F(f(3),f(3)))∧

（F(3,4)

F(f(3),f(4)))

∧

(（F(4,3)

F(f(4),f(3)))∧

（F(4,4)

F(f(4),f(4)))

(（0

F(4,4))∧

（1

F(4,3))

∧

(（1

F(3,4))