第4章习题解答.pdf

第四章第四章 归结法原理归结法原理 1 用归结法证明 1 qp rp rqp 2 rp rq rqp 3 rqp rpqp 4 rqp rqrp 5 rqp rp rq 6 rpqp rqp 解解 1 首先将qp rp rqp 化为合取范式 qp qp rp rp rqp rqprqp 给出子句集 rqprpqp 的反驳如下 qp rp p rq q 由和 r 由 和 r 由 和 由 和 因此 qp rp rqp 2 首先将rp rq rqp 化为合取范式 rp rp rq rq rqp rqp 给出子句集 rp rq qp r 的反驳如下 rp rq qp r rq 由 和 r 由 和 由 和 因此 rp rq rqp 3 首先将rqp rpqp 化为合取范式 rqp rqp rpqp rqprpqp 给出子句集 rqp p q r 的反驳如下 rqp p q r rq 由 和 r 由 和 由 和 因此 rqp rpqp 4 首先将rqp rqrp 化为合取范式 rqp rqp rqp rqrp rqprqrp 给出子句集 rqp p q r 的反驳如下 rqp p q r rq 由 和 r 由 和 由 和 因此 rqp rqrp 5 首先将rp rq 化为合取范式 rp rp rqrq 给出子句集 rqp rp q r 的反驳如下 rqp rp q r rq 由 和 r 由 和 由 和 因此 rqp rp rq 6 首先将 rpqp rqp 化为合取范式 rpqp rpqp rpqp rqp rqprqp 给出子句集 rqprqp 的反驳如下 rqp p q r rq 由 和 r 由 和 由 和 因此 rpqp rqp 2 用归结法判断以下结论是否成立 1 rqp rqrp 2 sprpqp srqp 3 rqqp pr pq 4 rqp rqp rqp 解解 1 首先将rqp rqrp 化为合取范式 rqp rqrprqprqp rqrp rqprqrp 给出子句集 rp rq p q r 的反驳如下 rp rq p q r r 由 和 由 和 因此 rqp rqrp 2 首先将 sprpqp srqp 化为合取范式 sprpqp srqpsprpqp srqp srqpsrqp 给出子句集 srqp p q r s 的反驳如下 srqp p q r s srq 由 和 sr 由 和 s 由 和 由 和 因此 sprpqp srqp 3 首先将 rqqp pr pq 化为合取范式 rqqp rqrqqprqqp pr rp pq qppq 给出子句集 rq rp p q 的反驳如下 rq rp p q r 由 和 r 由 和 由 和 因此 rqqp pr pq 4 首先将rqp rqp rqp 化为合取范式 rqp rqp rqp rqp rqp rqp rqp rqp 为了判断子句集 rqp rqp rqp 是否可满足 消去命题变元r 用子句 rqp 分别与子句rqp 和rqp 归结均得到子句qpqp 因为子句集 qpqp 可满足 所以子句集 rqp rqp rqp 可满足 因此 rqp rqp rqp 3 求下列公式的斯科伦范式 1 yPyxQyyxfPyPyxPx 2 yxRxyQxyQyxPyx 3 xyxRxQyxxP 4 yxyQyxxP 解解 1 yPyxQyyxfPyPyxPx zPzxQzyxfPyPyxPx zPzxQzyxfPyPyxPx zPzxQzyxfPyPyxPx zPzxQzyxfPyPyxPx zPzxQzyxfPyPyxPx zPzxQyxfPyPxPzyx yPyxQyyxfPyPyxPx 的斯科伦范式是 zPzaQbafPbPaPz 2 yxRxyQxyQyxPyx yxRxyQzuQuzPuz yxRxyQzuQuzPuz yxRxyQxyQyxPyx 的斯科伦范式是 yxRxyQzfuQzfzPz 3 xyxRxQyxxP uyuRxQyzzP uyRuxQyzzP uyRxQyzPuz xyxRxQyxxP 的斯科伦范式是 uyRxQyaPu 4 yxyQyxxP yxyQyxxPyxyQyxxP wxwQyvvPuxuQyzzP wxwQyvPvuxQuyzzP wxQyvPwvuxQyzPuz wxQyvPuxQyzPuzwv yxyQyxxP 的斯科伦范式是 bxQyaPuxQyzPuz 4 证明 前束范式A是永假式当且仅当A的无 前束范式是永假式 证明证明 设 A 是前束范式A的无 前束范式 设A可满足 即有解释I和I中赋值v使得1 vAI 我们证明 A 可满足 对A中 的出现次数进行归纳 若A中不出现 则 A 与A相同 A 可满足 设A中 的出现次数为1 m 若A为yB A 为 y a B 因为1 vAI 故有 I Dd 使得1 dyvBI 令解释 I 与I的区 别仅在于daI 则 1 dyvBIvaIyvBIvBI y a y a B可满足 由归纳假设知 y a B可满足 即 A 可满足 若A为yBxx n 1 A 为 1 1 y xxf n n Bxx 定义 I D上的n元运算g如下 对于任意 In Daa 1 令 1n aag 为集合 1 11 byaxaxvBIb nn 中的一个元素 这 个集合是非空的 因为1 11 nn axaxvyBI 令解释 I 与I的区别仅在于gf I 对 于任意 In Daa 1 11 1 nn y xxf axaxvBI n 11111nnnnn axaxvxxfIyaxaxvBI 1 111 nnn aagyaxaxvBI 所 以 1 1 1 vBxxI y xxf n n y xxf n n Bxx 1 1 可 满 足 由 归 纳 假 设 知 1 1 y xxf n n Bxx 可满足 即 A 可满足 我们证明AA 由谓词逻辑公理系统的可靠性定理知 只需证明AA 对A中 的出现次数进行归纳 若A中不出现 则 A 与A相同 AA 设A中 的出现次数为1 m 若A为yB A 为 y a B 由第三章习题 9 1 知 yBB y a 故yBBy a 由归纳假设知 y a B y a B 因此 y a ByB 若A为yBxx n 1 A 为 1 1 y xxf n n Bxx 由归纳假设知 1 1 y xxf n n Bxx y xxf n n Bxx 1 1 由第三章习题 9 1 知 yBB y xxf n 1 再 次 应 用 例3 8得 到 y xxf n n Bxx 1 1 yBxx n 1 所 以 1 1 y xxf n n Bxx yBxx n 1 即AA AA 若 A 可满足 有解释I和I中 赋值v满足 A 则I和v满足A A可满足 5 前束范式A的无 前束范式 A 定义如下 1 若A中不出现 则 A 是A 2 若A是yB 则 A 是 y a B 其中a是在B中不出现的常元 3 若A是yBxx n 1 其中n是正整数 则 A 为 1 1 y xxf n n yBxx 其中f是在B中不出 现的n元函数符号 证明 A是永真式当且仅当 A 是永真式 6 证明 若I是赫布兰德解释 则对每个基项t ttI 证明证明 对t进行归纳 1 若t是常元a 则aaaI I 2 若t是 1 n ttf 由归纳假设知 11 ttI nn ttI 1111nn I n I n ttfttftItIfttfI 7 证明 若语句集 可满足 则有赫布兰德解释满足 8 用归结法证明以下子句构成的集合不可满足 1 bxfxP zQzyfxPyQxQ aQ bQ 2 xRaQ xRxQ aPxR xP 3 yyfPayP yfyPayP ayPyxP yyfPyxP yfyPyxP 4 xfxSxVxE xfCxVxE aP aE yPyaS xVxP xCxP 5 wzuPwvxPvzyPuyxP yxyxgP yyxhxP xfxxfP 解解 1 给出该子句集的一个反驳如下 bxfxP zQzyfxPyQxQ aQ bQ zQzafaP 由 ayax和 bQ 由 ax和 bz 由 和 所以该子句集不可满足 2 给出该子句集的一个反驳如下 xRaQ xRxQ aPxR xP aR 由 ax和 ax aP 由 ax和 由 ax和 所以该子句集不可满足 3 给出该子句集的一个反驳如下 yyfPayP yfyPayP ayPyxP yyfPyxP yfyPyxP aaPaafP 由 afyax和 ay aafP 由 ay和 ayax aaP 由 和 由 ayax和 所以该子句集不可满足 4 给出该子句集的一个反驳如下 xfxSxVxE xfCxVxE aP aE yPyaS xVxP xCxP afPaVaE 由 ax和 afy afPaV 由 和 aVafC 由 和 afx aVaE 由 ax和 aV 由 和 aP 由 ax和 由 和 所以该子句集不可满足 5 给出该子句集的一个反驳如下 wzuPwvxPvzyPuyxP yxyxgP yyxhxP xfxxfP uzuPxzxP 由 uwxvxyuxgx和 uy uxxhuP 由 xxhz和 xy 由 xxhfu和 xxhx 所以该子句集不可满足 9 用归结法证明 1 yQyPy zxRzQzyxRyPyx 2 yxRyQyyPyxSyx xxQ yPyxSyx 3 yCyxSyxRxQx yPyxSyxQxPx xRxPx xCxPx 4 xQxPx xxQxxP 5 yxyPx yxxPy 解解 1 由语句 yQyPy 得到子句 yQyP 由语句 zxRzQzyxRyPyx 得到子句 bP baR以及 zxRzQ 构造子句集 yQyP bP baR zxRzQ 的一个反驳如下 yQyP bP baR zxRzQ bQ 由 和 bQ 由 和 由 和 因此 yQyPy zxRzQzyxRyPyx 2 由语句 yxRyQyyPyxSyx 得到子句 xfQyPyxS 和 xfxRyPyxS 由 语 句 xxQ 得 到 子 句 xQ 由 语 句 yPyxSyx 得到子句 baS和 bP 构造子句集 xfQyPyxS xfxRyPyxS xQ baS bP 的一个反驳如下 xfQyPyxS xfxRyPyxS xQ baS bP yPyxS 由 和 bP 由 和 由 和 因此 yxRyQyyPyxSyx xxQ yPyxSyx 3 由 语 句 yCyxSyxRxQx 得 到 子 句 xfxSxRxQ 和 xfCxRxQ 由语句 yPyxSyxQxPx 得到子句 aP aQ yPyaS 由 语 句 xRxPx 得 到 子 句 xRxP 由 语 句 xCxPx 得到子句 xCxP 构造子句集 xfxSxRxQ xfCxRxQ aP aQ yPyaS xRxP xCxP 的一个反驳如下 xfxSxRxQ xfCxRxQ aP aQ yPyaS xRxP xCxP afPaRaQ 由 和 aR 由 和 afPaR 由 和 afP 由 和 afCaR 由 和 afC 由 和 afP 由 和 由 和 因此 yCyxSyxRxQx yPyxSyxQxPx xRxPx xCxPx 4 由 语 句 xQxPx 得 到 子 句 xQxP 由 语 句 xQxPx 得 到 子 句 xQxP 显 然 这 两 个 子 句 的 归 结 子 句 是 永 真 子 句 因 此 xQxPx xxQxxP 5 由语句 yxyPx 得到子句 xfxP 由语句 yxxPy 得到子句 yygP 我们证明 这两个子句没有归结子句 若有代换 1 tx和代换 2 ty使 21 tgt 21 ttf 可 得 出 11 tfgt 这 是 不 可 能 的 因 为 这 里 的 表 示 作 为 符 号 串 的 相 同 因 此 yxyPx yxxPy 10 每个一年级学生至少有一个高年级学生作他的辅导员 凡理科学生的辅导员皆是理科学生 小王是理 科一年级学生 因此 至少有一个理科高年级学生 解解 首先将前提和结论符号化 取个体域为学生的集合 xxF 是一年级学生 xxH 是高年级学生 xxL 是理科学生 xxW 是文 科学生 xyxG 是y的辅导员 a小王 每个一年级学生至少有一个高年级学生作他的辅导员 符号化为 xyGyHyxFx 凡理科学生的辅导员皆是理科学生 符号化为 yLxyGyxLx 小王是理科一年级学生 符号化为 aFaL 至少有一个理科高年级学生 符号化为 xHxLx 将 xyGyHyxFx 化为斯科伦范式 xxfGxFxfHxFx 得出子句 xfHxF 和 xxfGxF 将 yLxyGyxLx 化为斯科伦范式 yLxyGxLyx 得出子句 yLxyGxL aFaL 本身即为斯科伦范式 得出子句 aL和 aF 将 xHxLx 化为斯科伦范式 xHxLx 得出子句 xHxL 构造子句集 xfHxF xxfGxF yLxyGxL aL aF xHxL 的一个反驳如下 xfHxF xxfGxF yLxyGxL aL aF xHxL afH 由 和 aafG 由 和 yLayG 由 和 afL 由 和 afL 由 和 由 和 11 任何喜欢步行的人都不喜欢乘汽车 每个人或者喜欢乘汽车或者喜欢骑自行车 有的人不喜欢骑自行 车 因此 有的人不喜欢步行 解解 首先将前提和结论符号化 取个体域为人的集合 xxW 喜欢步行 xxC 喜欢乘汽车 xxB 喜欢骑自