第四章归结法原理习题与解答1.用归结法证明：(1)(2)(3)(4)(5)(6)解(1)首先将p→q,p→r，?(p→q∧r)化为合取范式。p→q??p∨qp→r??p∨r?(p→q∧r)??(?p∨(q∧r))?p∧(?q∨?r)给出子句集{?p∨q,?p∨r,p,?q∨?r}的反驳如下。⑴?p∨q⑵?p∨r⑶p⑷?q∨?r⑸q由⑴和⑶由⑵和⑶⑹r⑺?r由⑷和⑸⑻□由⑹和⑺因此，p→q,p→r|=p→q∧r(2)首先将p→r，q→r，?(p∨q→r)化为合取范式。p→r??p∨rq→r??q∨r?(p∨q→r)?(p∨q)∧?r给出子句集{?p∨r,?q∨r,p∨q,?r}的反驳如下。⑴?p∨r⑵?q∨r⑶p∨q⑷?r⑸q∨r由⑴和⑶p→q,p→r|=p→q∧rp→r,q→r|=p∨q→rp→q∨r|=(p→q)→(p→r)p∧q→r|=(p→r)∨(q→r)p∨q∨r,p→r|=q∨r(p→q)→(p→r)|=p→(q→r)由⑵和⑸⑹r⑺□由⑷和⑹因此，p→r，q→r|=p∨q→r(3)首先将p→q∨r,?((p→q)∨(p→r))化为合取范式。p→q∨r??p∨q∨r?((p→q)∨(p→r))??((?p∨q)∨(?p∨r))?p∧?q∧?r给出子句集{?p∨q∨r,p,?q,?r}的反驳如下。⑴?p∨q∨r⑵p⑶?q⑷?r⑸q∨r由⑴和⑵⑹r由⑶和⑸⑺□由⑷和⑹因此，p→q∨r|=(p→q)∨(p→r)(4)首先将p∧q→r,?((p→r)∨(q→r))化为合取范式。p∧q→r??(p∧q)∨r??p∨?q∨r?((p→r)∨(q→r))??((?p∨r)∨(?q∨r))?p∧q∧?r给出子句集{?p∨?q∨r,p,q?r}的反驳如下。⑴?p∨?q∨r⑵p⑶q⑷?r⑸?q∨r由⑴和⑵⑹r由⑶和⑸⑺□由⑷和⑹因此，p∧q→r|=(p→r)∨(q→r)(5)首先将p→r，?(q∨r)化为合取范式。p→r??p∨r?(q∨r)??q∧?r给出子句集{p∨q∨r,?p∨r,?q,?r}的反驳如下。⑴p∨q∨r⑵?p∨r⑶?q⑷?r⑸q∨r由⑴和⑵⑹r由⑶和⑸⑺□由⑷和⑹因此，p∨q∨r，p→r|=q∨r(6)首先将(p→q)→(p→r)，?(p→(q→r))化为合取范式。(p→q)→(p→r)??(?p∨q)∨(?p∨r)?(p∧?q)∨(?p∨r)??p∨?q∨r?(p→(q→r))?p∧q∧?r给出子句集{?p∨?q∨r,p,q,?r}的反驳如下：⑴?p∨?q∨r⑵p⑶q⑷?r⑸?q∨r由⑴和⑵⑹r由⑶和⑸⑺□由⑷和⑹因此，(p→q)→(p→r)|=p→(q→r)。2.用归结法判断以下结论是否成立：(1)p∨q→r|=(p→r)∨(q→r)(2)(p→q)∨(p→r)∨(p→s)|=p→q∨r∨s2(3)(p→q)→(q→r)，r→p|=q→p(4)p∧q→r,p∧q→?r|=?p∧?q∧?r解(1)首先将p∨q→r,?((p→r)∨(q→r))化为合取范式。p∨q→r??(p∨q)∨r?(?p∧?q)∨r?(?p∨r)∧(?q∨r)?((p→r)∨(q→r))??((?p∨r)∨(?q∨r))?p∧q∧?r给出子句集{?p∨r,?q∨r,p,q,?r}的反驳如下。⑴?p∨r⑵?q∨r⑶p⑷q⑸?r⑹r由⑴和⑶⑺□由⑹和⑸因此，p∨q→r|=(p→r)∨(q→r)(2)首先将(p→q)∨(p→r)∨(p→s),?(p→q∨r∨s)化为合取范式。(p→q)∨(p→r)∨(p→s)(?p∨q)∨(?p∨r)∨(?p∨s)??p∨q∨r∨s?(p→q∨r∨s)??(?p∨q∨r∨s)?p∧?q∧?r∧?s给出子句集{?p∨q∨r∨s,p,?q,?r,?s}的反驳如下。⑴?p∨q∨r∨s⑵p⑶?q⑷?r⑸?s⑹q∨r∨s由⑴和⑵⑺r∨s由⑶和⑹⑻s由⑷和⑺⑼□由⑸和⑻因此，(p→q)∨(p→r)∨(p→s)|=p→q∨r∨s(3)首先将(p→q)→(q→r),r→p,?(q→p)化为合取范式。(p→q)→(q→r)??(?p∨q)∨(?q∨r)?(p∧?q)∨?q∨r??q∨rr→p?p∨?r?(q→p)??(?q∨p)??p∧q给出子句集{?q∨r,p∨?r,?p,q}的反驳如下。⑴?q∨r⑵p∨?r⑶?p⑷q⑸?r由⑵和⑶⑹r由⑷和⑴⑺□由⑸和⑹因此，(p→q)→(q→r),r→p|=q→p。(4)首先将p∧q→r,p∧q→?r,?(?p∧?q∧?r)化为合取范式。p∧q→r??(p∧q)∨r??p∨?q∨rp∧q→?r??(p∧q)∨?r??p∨?q∨?r?(?p∧?q∧?r)?p∨q∨r为了判断子句集{?p∨?q∨r,?p∨?q∨?r,p∨q∨r}是否可满足，消去命题变元r，用子句?p∨?q∨?r分别与子句p∨q∨r和?p∨?q∨r归结均得到子句?p∨?q∨p∨q，因为子句集{?p∨?q∨p∨q}可满足，所以子句集{?p∨?q∨r,?p∨?q∨?r,p∨q∨r}可满足。因此，p∧q→r,p∧q→?r|=/?p∧?q∧?r。3.求下列公式的斯科伦范式。(1)??x(P(x)→?y(P(y)→P(f(x,y)))∧??y(Q(x,y)→P(y)))(2)?x?y(P(x,y)→Q(y,x))∧(Q(y,x)→R(x,y))(3)?xP(x,y)→(Q(x)→??xR(y,x))(4)?xP(x,y)⊕?yQ(x,y)解(1)??x(P(x)→?y(P(y)→P(f(x,y)))∧??y(Q(x,y)→P(y)))???x(P(x)→?y(P(y)→P(f(x,y)))∧??z(Q(x,z)→P(z)))??x?(P(x)→?y(P(y)→P(f(x,y)))∧??z(Q(x,z)→P(z)))??x(P(x)∧?(?y(P(y)→P(f...
