7逻辑代数(下)谓词演算习题答案

练习5.11.指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并作适当更改，同时回答它们是否是命题：（1）x(P(x)∨Q(x))∧R（2）x(P(x)∧Q(x))∧xS(x)→T(x)（3）x(P(x)→y(B(x,y)∧Q(y))∨T(y))（4）P(x)(yx(P(x)∧B(x,y))P(x))解：（1）全称量词，辖域P(x)∨Q(x)，其中x为约束变元，x(P(x)∨Q(x))∧R是命题。不需要更改变元。（2）全称量词，辖域P(x)∨Q(x)，其中x为约束变元。存在量词，辖域S(x)，其中x为约束变元。T(x)中x为自由变元。x(P(x)∧Q(x))∧xS(x)→T(x)不是命题。公式中x既是自由变元又是约束变元，可更改变元为如下公式：x(P(x)∧Q(x))∧yS(y)→T(z)（3）全称量词，辖域P(x)→y(B(x,y)∧Q(y))∨T(y)，其中x为约束变元，存在量词，辖域B(x,y)∧Q(y)，其中y为约束变元。T(y)中y为自由变元。x(P(x)→y(B(x,y)∧Q(y))∨T(y))不是命题。公式中y既是自由变元又是约束变元，可更改变元为如下公式：x(P(x)→y(B(x,y)∧Q(y))∨T(z))不是命题。（4）全称量词，辖域x(P(x)∧B(x,y))，其中y为约束变元。存在量词，辖域P(x)∧B(x,y)，其中x为约束变元。不在量词辖域中的P(x)（第一个和第三个P(x)）中的x为自由变元。P(x)→(yx(P(x)∧B(x,y))→P(x))不是命题。公式中x既是自由变元又是约束变元，可更改变元为如下公式：P(z)→(yx(P(x)∧B(x,y))→P(z))2．对个体域{0，1}判定下列公式的真值,E(x)表示“x是偶数”：（1）x(E(x)→┐x=1)（2）x(E(x)∧┐x=1)（3）x(E(x)∧x=1)（4）x(E(x)→x=1)再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解:（1）x(E(x)→┐x=1)真x(E(x)→┐x=1)可表示成命题公式（E(0)→┐0=1）∧（E(1)→┐1=1）其中E(0)→┐0=1真，E(1)→┐1=1也真，故（E(0)→┐0=1）∧（E(1)→┐1=1）真。（2）x(E(x)∧┐x=1)假x(E(x)∧┐x=1)可表示成命题公式（E(0)∧┐0=1）∧（E(1)∧┐1=1）其中E(0)∧┐0=1真，但E(1)∧┐1=1假，故（E(0)∧┐0=1）∧（E(1)∧┐1=1）假。（3）x(E(x)∧x=1)假x(E(x)∧x=1)可表示成命题公式(E(0)∧0=1)∨(E(1)∧1=1)其中E(0)∧0=1假，E(1)∧1=1也假，故(E(0)∧0=1)∨(E(1)∧1=1)假。（4）x(E(x)→x=1)真x(E(x)→x=1)可表示成命题公式(E(0)→0=1)∨(E(1)→1=1)其中E(0)→0=1假，但E(1)→1=1真，故(E(0)→0=1)∨(E(1)→1=1)真。3．设整数集为个体域，判定下列公式的真值(表示数乘运算)：（1）xy(xy=x)（2）xy(xy=1)（3）xy(x+y=1)（4）yx(xy=x)（5）yx(x+y=1)解:（1）xy(xy=x)真（2）xy(xy=1)假（3）xy(x+y=1)真（4）yx(xy=x)真（5）yx(x+y=1)假4.用谓词公式将下列语句形式化：（1）华盛顿是美国的首都。（2）高斯是数学家，但不是文学家。（3）不劳动者不得食。（4）人无完人。（5）发亮的东西不都是金子。（6）天下乌鸦一般黑。（7）一个数既是偶数又是质数，当且仅当该数为2。（8）有的猫不捉耗子，会捉耗子的猫便是好猫。（9）凡成功者都努力奋斗，但反之不然。（10）有的汽车比有的火车跑得快。（11）一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。（12）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。解:（1）华盛顿是美国的首都；C(x,y)表示“x是y的首都”，w表示“华盛顿”，a表示美国，原句可表示为C(w,a)（2）高斯是数学家，但不是文学家。解:M(x)表示“x是数学家”，A(x)表示“x是天文学家”，g表示“高斯”，原句可表示为M(g)∧┐A(g)（3）W(x)表示“x是劳动的”，F(x)表示“x是可以得到食物的”，原句可表示为x(┐W(x)┐F(x))（4）人无完人。解:M(x)表示“x是人”，P(x)表示“x是完美的”，原句可表示为┐x(M(x)∧P(x))或者x(M(x)┐P(x))（5）L(x)表示“x是发亮的”，G(x)表示“x是金子”，原句可表示为┐x(L(x)→G(x))（6）天下乌鸦一般黑。解:W(x)表示“x是乌鸦”，B(x)表示“x是黑的的”，原句可表示为x(W(x)→B(x))或者┐x(W(x)∧┐B(x))（7）O(x)表示“x是奇数”，E(x)表示“x是偶数”，原句可表示为x(O(x)∧E(x)x=2)（8）有的猫不捉耗子，会捉耗子的猫便是好猫。解:C(x)表示“x是猫”，M(x)表示“x是耗子”，G(x)表示“x是好的”，K(x,y)表示“x会捉y”，原句可表示为x(C(x)∧y(M(y)→┐K(x,y)))∧x(C(x)∧y(M(y)→K(x,y))→G(x))（9）S(x)表示“x是成功”，H(x)表示“x是努力奋斗的”，原句可表示为x(S(x)→H(x))∧┐x(H(x)→S(x))（10）有的汽车比有的火车跑得快。解:C(x)表示“x是汽车”，T(x)表示“x是火车”，F(x,y)表示“x比y快”，原句可表示为x(C(x)∧y(T(y)∧F(x,y)))（11）M(x)表示“x是人”，B(x,y)表示“x相信y”,原句可表示为x(M(x)∧┐y(M(y)∧x≠y∧B(x,y))→┐y(M(y)∧x≠y∧B(y,x)))（12）M(x)表示“x是男人”，F(x)表示“x是女人”，H(x,y)表示“x比y高”，原句可表示为┐x(M(x)→y(F(y)∧H(x,y)))∧x(M(x)∧y(F(y)→H(x,y)))5．量词!表示“有且仅有”，!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词，,,等号“=”及谓词P(x),表示!P(x)，即写出一个通常的谓词公式使之与!xP(x)具有相同的意义。解:!xP(x)可用以下具有相同的意义的谓词公式表示x（P(x)∧y（P(y)→y=x））6.f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y=f(x)（不得使用量词!。“f(x)为实函数”可译为RF(f)）。解:RF(f)xy(y=f(x)∧┐z(z≠y∧z=f(x)))练习5.21.设个体域D=d1,…,dn，试用消去量词的方法证明下列基本逻辑等价式：（1）┐xA(x)x┐A(x)解：┐xA(x)┐（A（d1）∧A（d2）∧…∧A（dn））┐A（d1）∨┐A（d2）∨…∨┐A（dn）x┐A(x)（2）xA(x)∧Px(A(x)∧P)（P为命题常元）解：xA(x)∧P（A（d1）∧A（d2）∧…∧A（dn））∧P（A（d1）∧P）∧（A（d2）∧P）∧…∧(A（dn）∧P)x(A(x)∧P)（3）xA(x)∨xB(x)x(A(x)∨B(x))解：xA(x)∨xB(x)（A（d1）∨A（d2）∨…∨A（dn））∨（B（d1）∨B（d2）∨…∨B（dn））（A（d1）∨B（d1））∨（A（d2）∨B（d2））∨…∨（A（dn）∨B（dn））x(A(x)∨B(x))2.证明下列逻辑蕴涵式及逻辑等价式：（1）xy(P(x)Q(y))xP(x)—yQ(y)证明：xy(P(x)Q(y))xy(┐P(x)∨Q(y))x(┐P(x)∨yQ(y))x┐P(x)∨yQ(y)┐xP(x)∨yQ(y)xP(x)yQ(y)（2）xy(P(x)Q(y))xP(x)—yQ(y)证明：xy(P(x)→Q(y))xy(┐P(x)∨Q(y))x(┐P(x)∨yQ(y))x┐P(x)∨yQ(y)┐xP(x)∨yQ(y)xP(x)→yQ(y)