例5.11证明子句集{P∨一Q,一P,Q}是不 可满足的。 证 (1)P∨一Q (2)-P (3)Q (4)-Q 由(1),(2) (5)□ 由(3),(4)潼
例5.11 证明子句集{ P∨﹁Q,﹁P,Q }是不 可满足的。 证 (1)P∨﹁Q (2)﹁P (3)Q (4)﹁Q 由(1),(2) (5)□ 由(3),(4)
例5.12用归结原理证明R是 P,(P∧Q)→R,(S∨U)→Q,U 的逻辑结果。 证由所给条件得到子句集 S={P,→P∨QVR,=S∨Q,=U∨Q,U,=R 然后对该子句集施行归结,归结过程用下面的归结演绎 树表示(见图5-1)。由于最后推出了空子句,所以子 句集S不可满足,即命题公式 P∧(-P∨Q∨R)∧(→S∨Q)∧(-UVQ)∧U∧一R 不可满足,从而R是题设前提的逻辑结果
例5.12 用归结原理证明R是 P,(P∧Q)→R,(S∨U)→Q,U 的逻辑结果。 证 由所给条件得到子句集 S=｛P,﹁ P∨﹁ Q∨R,﹁ S∨Q,﹁ U∨Q,U,﹁ R｝ 然后对该子句集施行归结，归结过程用下面的归结演绎 树表示（见图5―1）。由于最后推出了空子句，所以子 句集S不可满足，即命题公式 P∧(﹁ P∨﹁ Q∨R)∧(﹁ S∨Q)∧(﹁ U∨Q)∧U∧﹁ R 不可满足，从而R是题设前提的逻辑结果
PV7QVRR8大学 BRe8m47PV-08 P595R9 西电大学出版 Q U八Q 资电子将大学出版要电子 版 画安电子故学出版高要电子啊 图5—1例5.12归结演绎树
图5―1 例5.12归结演绎树
5.2.3替换与合 C1=P(x)∨Q(x) C2=-P(a)VR(y)潼 用a替换C1中的x,则得到 Cl′=P(a)∨Q(a) C2′=-P(a)VR(y)
5.2.3 替换与合一 例： C1=P(x)∨Q(x) C2=﹁P(a)∨R(y) 用a替换C1中的x，则得到 C1′=P(a)∨Q(a) C2′=﹁P(a)∨R(y)
定义6一个替换( Substitution)是形如 t1/x1,t2x2…,tn/xn}的有限集合,其中t,t2,,tn是 项,称为替换的分子;x1,x2,Xn是互不相同的个 体变元,称为替换的分母;t不同于x,x;也不循 环地出现在1(i=1,2,…,m)中;tx表示用t替换x 若1,t2,,n都是不含变元的项(称为基项)时,该 替换称为基替换;没有元素的替换称为空替换, 记作E,它表示不作替换
定义6 一个替换(Substitution)是形如 ｛t1 /x1 ,t2 /x2 ,…,tn /xn｝的有限集合，其中t1 ,t2 ,…,tn是 项，称为替换的分子；x1 ,x2 ,…,xn是互不相同的个 体变元，称为替换的分母；ti不同于xi，xi也不循 环地出现在tj(i,j=1,2,…,n)中；ti/xi表示用ti替换xi。 若t1 ,t2 ,…,tn都是不含变元的项（称为基项）时，该 替换称为基替换；没有元素的替换称为空替换， 记作ε，它表示不作替换