离散数学及其应用数理逻辑部分课后习题答案(3)

⑨s?q ⑩t?q

11q ○

⑧化简 ⑥⑨假言三段论

②⑩假言推理

前提引入

11○12假言推理 ○12○13合取 ○

12q?p ○13p ○

⑨p?q

15、在自然推理系统P中用附加前提法证明下面推理： （1）前提：p?(q?r),s?p,q

结论：s?r 证明： ①s

附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理

②s?p ③p

④p?(q?r) ⑤q?r ⑥q ⑦r

16、在自然推理系统P中用归谬法证明下面推理： （1）前提：p?q,p?r,q?s

结论：r?s 证明： ①?(r?s) ②?r??s ③?s ④?r

结论否定引入 ①置换 ②化简 ②化简 前提引入 前提引入 ④⑤拒取式 ③⑥拒取式 ⑦⑧合取 ⑨置换 前提引入

⑤p?r ⑥q?s ⑦?p ⑧?q

⑨?p??q ⑩?(p?q)

11p?q ○

11矛盾。 ⑩○

17：在自然推理系统P中构造下面推理的证明：

只要A曾到过受害者房间并且11点以前没有离开，A就是谋杀嫌疑犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见过他。看门人没有看见他。所以，A是谋杀嫌疑犯。 解答：

（1） 命题符号化：p:A曾到过受害者房间；q:A在11点以前离开；

r: A就是谋杀嫌疑犯；s:看门人会看见过A；

（2） 推理的形式结构：

前提：(p??q)?r;p;q?s;?s 结论：r （3） 证明

①?s

前提引入 前提引入 ①②拒取式 前提引入 ③④合取 前提引入 ⑤⑥假言推理。

②q?s ③?q ④p

⑤p??q

⑥(p??q)?r ⑦r

P63:习题四

5、在一阶逻辑中讲下列命题符号化。 （3）不存在比所有火车都快的汽车。 （4）凡是汽车就比火车慢是不对的。

解答：F(x):x为火车；G(y)：y为汽车；H(x,y)：y比x快。

（3）?(?y?x(G(y)?F(x)?H(x,y))) （4）??y?x(G(y)?F(x)?H(y,x))

6、将下列命题符号化，个体域为实数集合R，并指出各命题的真值。 （1）对所有的x，都存在y使得x?y?0。 （3）对所有的x，都存在y使得y?x?1。 解答：F(x,y):x?y?0;G(x,y):y?x?1 （1）?x?yF(x,y)，真值为1； （3）?x?yG(x,y)，真值为1；

9、给定解释I如下。 （a）个体域为实数集合R。 （b）特定元素a?0。

（c）函数f(x,y)?x?y,x,y?R

（d）谓词F(x,y):x?y,G(x,y):x?y,x,y?R。 给出下列公式在I下的解释，并指出它们的真值。 （1）?x?y(G(x,y)??F(x,y)) （3）?x?y(G(x,y)??F(f(x,y),a))

解答：（1）对任意的x和y，如果x?y,那么x?y。真值为1；

11、判断下列各式的类型。

（2）?x(F(x)?F(x))??y(G(y)??G(y)) （4）?x?yF(x,y)??y?xF(x,y)

解答：（2）?x(F(x)?F(x))真值为1；?y(G(y)??G(y))真值为0；

所以?x(F(x)?F(x))??y(G(y)??G(y))真值为0，所以为永假式。 （4）?x?yF(x,y)与?y?xF(x,y)真值相同，所以为永真式。

13、给出下列各公式的一个成真解释和一个成假解释。 （1）?x(F(x)?G(x)) （2）?x(F(x)?G(x)?H(x)) （3）?x(F(x)??y(G(y)?H(x,y)) 解答：

（1）成真解释：F(x):x为偶数；G(x):x为奇数

成假解释：F(x):x为偶数；G(x):x为素数

（3）对任意的x和y，如果x?y,那么x?y?0。真值为1；

（2）成真解释：F(x):x能被2整除；G(x):x能被3整除；H(x):x能被5整除。

成假解释：F(x):x为偶数；G(x):x为奇数，H(x):x为素数

（3）成真解释：F(x):x为正数；G(x):x负数；H(x，y):x?y。

成假解释：F(x):x为正数；G(x):x负数；H(x，y):x?y。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学及其应用数理逻辑部分课后习题答案(3)在线全文阅读。