《数理逻辑》期末考试试题

《数理逻辑》期末考试试题(A卷)(请将所有答案写在答题纸上，不用抄题，但注意写清题号)《中山大学授予学士学位工作细则》第六条：”考试作弊不授予学士学位。”年级：2008级班级：A,B,C,E班专业：计科、信息安全任课教师：刘咏梅、周晓聪一、填空题(共20分，每空2分)1.设A是含命题变量p,q,r的矛盾式，则公式A∧((p↔q)→r)的类型是矛盾式。2.设公式A含变量p,q,r，且其主合取范式是M0∧M2∧M3∧M5，则其主析取范式是m1∨m4∨m6∨m7。3.设F(x)表示“x是实数”，G(x)表示“x是有理数”，则命题“实数不都是有理数”符号化为¬∀x(F(x)→G(x))。4.公式∀xF(x)→∀yG(x,y)的前束范式是∃x∀y(F(x)→G(z,y))。5.公式(p∧q)∨r的主析取范式是m1∨m3∨m5∨m6∨m7。6.设F(x)表示“x是无理数”，G(x)表示“x能表示成分数”，则命题“不存在能表示成分数的无理数”符号化为¬∃x(F(x)∧G(x))。7.设p,r为真命题，q,s为假命题，则复合命题(p→q)↔(¬r→s)的真值为0。8.求与公式F=∀x(A(x)→B(x,y))→(∀y¬C(y)∨∃zD(y,z))等值的一个前束范式是：∃x∀t∃z((A(x)→B(x,y))→(¬C(t)∨D(y,z))。9.令L(x)表示x是人，E(x)表示x是食物，F(x,y)表示x对y过敏，则句子“某些人对某些食物过敏”可符号化为∃x∃y(L(x)∧E(y)∧F(x,y))。10.公式((∀y¬G(x)∧∀xF(x))∧∃yG(y))→∀xF(x)的类型是永真式。二、求解下面有关一阶逻辑公式语法的题目。(8分)(1)请指出公式∀x(P(x)→∃xQ(x))∨(∀xH(x)→G(x))中各量词的辖域；解答：第一个量词∀x的辖域是(P(x)→(∃x)Q(x))，量词∃x的辖域是Q(x)，第二个量词∀x的辖域是P(x)。(2)请给出公式∀y(A(x,y)→∀xB(x,y))∧∃zC(x,y,z)中每个变量符号的出现身份，即是指导变元、还是自由出现或约束出现。解答：∀y中的y是指导变元，A(x,y)中的y是约束出现，而x是自由出现，∀x中的x是指导变元，而B(x,y)中的x和y都是约束出现，∃z中的z是指导变元，而C(x,y,z)中的z是约束出现，但x和y都是自由出现。(3)请指出变量x和y分别是公式∀x(A(x,y)→B(y,z))→∃y∀xC(x,y,z)的自由变量还是约束变量；解答：x是该公式的约束变量，而y是该公式的自由变量。(4)请使用约束变量改名规则或自由变量替换规则将公式∃x(A(x,y)→∀yB(y,z))→∃yC(x,y,z)变换成语法等价但所有量词的指导变元不同，且没有变量符号既自由出现又约束出现的公式形式。注意，请依次选择个体变量符号x,y,z,u,v,w,r,s,t等等。解答：∃x(A(x,y)→∀uB(u,z))→∃vC(w,v,z)三、求解下面有关一阶逻辑公式语义解释的题目。(16分)1(1)给定解释I为：论域D={2,4}，而P(x)为真当且仅当x是素数，D(x,y)为真当且仅当x可整除y，E(x,y)为真当且仅当x+y=xy。请给出公式∀x∃y((¬P(x)∨D(x,y))→E(x,y))在解释I下的真值。解答：该公式的真值为1.(2)给定解释I，其论域D是整数集，函数符号f的解释是普通加法，谓词E(x,y)的解释是x=y，请给出公式∃x∀yE(f(x,y),y)的直观含义，并根据常识确定其真值。解答：该公式的直观含义是：存在一个整数和任意另一整数的和都等于另一整数，其真值为1，因为对任意的整数x，都有x+0=0。(3)给定论域D={a,b}，请展开∀x∀y(P(x,y)→¬P(y,x))中的量词。解答：∀x∀y(P(x,y)→¬P(y,x))⇔∀y(P(a,y)→¬P(y,a))∧∀y(P(b,y)→¬P(y,b))⇔(P(a,a)→¬P(a,a))∧(P(a,b)→¬P(b,a))∧(P(b,a)→¬P(a,b))∧(P(b,b)→¬P(b,b))(4)利用一阶逻辑的基本等值式证明∀x(¬F(x)∧G(x))⇔¬(∀xG(x)→∃xF(x))；证明¬(∀xG(x)→∃xF(x))⇔¬(¬∀xG(x)∨∃xF(x))//蕴涵等值式⇔∀xG(x)∧¬∃xF(x)//德摩根律⇔∀xG(x)∧∀x¬F(x)//量词否定等值式⇔∀x(¬F(x)∧G(x))//量词分配等值式四、求解下面有关一阶逻辑公式自然推理的题目。注意下列题目中必须写出详细的证明序列，并注明所使用的自然推理规则。(38分)(1)待验证的推理是：∀x(A(x)→B(x))`∃xA(x)→∃xB(x)，请指出下面证明序列中的错误，并改正（即给出正确的证明序列）：(6分)(1)∀x(A(x)→B(x))//前提引入(2)A(a)→B(a)//(1)全称量词消除(3)∃xA(x)//附加前提引入(4)A(a)//(3)存在量词消除(5)B(a)//(2),(4)蕴涵消除(6)∃xB(x)//(5)存在量词引入(7)∃xA(x)→∃xB(x)//(3),(6)附加前提证明法解答：其中第(3)步到第(4)步使用存在量词消除规则错误，常量符号a已经在前面的证明序列出2现过，正确的证明序列如下：(1)∃xA(x)//附加前提引入(2)A(a)//(1)存在量词消除(3)∀x(A(x)→B(x))//前提引入(4)A(a)→B(a)//(3)全称量词消除(5)B(a)//(2),(4)蕴涵消除(6)∃xB(x)//(5)存在量词引入(7)∃xA(x)→∃xB(x)//(3),(6)附加前提证明法(2)在一阶逻辑中验证推理：(10分)∃xP(x)→∀x((P(x)∨Q(x))→R(x)),∃xP(x),∃xQ(x)`∃x∃y(R(x)∧R(y))证明(1)∃xP(x)→∀x((P(x)∨Q(x))→R(x))//前提引入(2)∃xP(x)//前提引入(3)∀x((P(x)∨Q(x))→R(x))//(1),(2)蕴涵消除(4)P(a)//(2)存在量词消除(5)P(a)∨Q(a)//附加律(6)P(a)∨Q(a)→R(a)//(3)全称量词消除(7)R(a)//(5),(6)蕴涵消除(8)∃xQ(x)//前提引入(9)Q(b)//(8)存在量词消除(10)P(b)∨Q(b)//附加律(11)P(b)∨Q(b)→R(b)//(3)全称量词消除(12)R(b)//(10),(11)蕴涵消除(13)R(a)∧R(b)//(7),(12)合取引入(14)∃y(R(a)∧R(y))//(13)存在量词引入(15)∃x∃y(R(x)∧R(y))//(14)存在量词引入(3)在一阶逻辑中验证推理：∀x(C(x)→¬D(x)),∀x(B(x)∨C(x))`∀x(D(x)→B(x))(10分)3证明(1)∀x(C(x)→¬D(x))//前提引入(2)C(y)→¬D(y)//(1)全称量词消除(3)∀x(B(x)∨C(x))//前提引入(4)B(y)∨C(y)//(3)全称量词消除(5)D(y)//附加前提引入(6)¬C(y)//(2),(5)拒取式(7)B(y)//(4),(6)析取三段论(8)D(y)→B(y)//(5),(7)附加前提证明法(9)∀x(D(x)→B(x))//(8)全称量词引入(4)符号化下面的推理，并在一阶逻辑中验证其正确性：每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除，并不是所有的自然数都能被2整除，因此有的自然数是奇数。（提示：令个体域是自然数集合，Q(x)表示x是奇数，P(x)表示x是偶数，R(x)表示x能被2整除）(12分)证明首先将前提和结论进行符号化，得到要验证的推理是：∀x(Q(x)∨P(x)),∀x(P(x)↔R(x)),¬∀xR(x)`∃Q(x)而验证该推理的证明序列如下：(1)¬∀xR(x)//前提引入(2)∃x¬R(x)//(1)量词否定等值式(3)¬R(c)//(2)存在量词消除(4)∀x(P(x)↔R(x))//前提引入(5)P(c)↔R(c)//(4)全称量词消除(6)P(c)→R(c)//(5)等价消除(7)¬P(c)//(3),(6)拒取式(8)∀x(Q(x)∨P(x))//前提引入(9)Q(c)∨P(c)//(8)全称量词消除(10)Q(c)//(7),(9)析取三段论(11)∃xQ(x)//(10)存在量词引入五、求解下面与命题逻辑有关的题目(18分)(1)在命题逻辑中证明等值式：(10分)(p∨q)∧(q∨r)∧(r∨p)⇔(p∧q)∨(q∧r)∨(r∧p)4我们通过求左边公式的主合取范式，以及右边公式的主析取范式，再进行比较而证明：(p∨q)∧(q∨r)∧(r∨p)//极大项扩展⇔(p∨q∨r)∧(p∨q¬r)∧(¬p∨q∨r)∧(p∨¬q∨r)//极大项编码⇔M0∧M1∧M4∧M2(p∧q)∨(q∧r)∨(r∧p)//极小项扩展⇔(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧r)//极小项编码⇔m7∨m6∨m3∨m5由主析取范式和主合取范式之间的关系有M0∧M1∧M2∧M4⇔m3∨m5∨m6∨m7。（由于各教材的主范式编码稍有不同，因此有必要时可说明主范式的编码及主析取范式和主合取范式之间的关系）(2)在命题逻辑中验证推理（可使用带前提集的证明序列也可使用不带前提集的证明序列）：(8分)¬(p→q)→¬(r∨s),(q→p)∨¬r,r`p↔q证明令Γ=¬(p→q)→¬(r∨s),(q→p)∨¬r,r(1)Γ`r//前提引入(2)Γ`(q→p)∨¬r//前提引入(3)Γ`q→p//(1),(2)析取三段论(4)Γ`r∨s//(1)附加律(5)Γ`¬(p→q)→¬(r∨s)//前提引入(6)Γ`p→q//(4),(5)拒取式(7)Γ`p↔q//(3),(6)等价引入5