离散数学作业7答案数理逻辑部分最新Word下载.docx

离散数学作业7答案数理逻辑部分最新Word下载.docx

《离散数学作业7答案数理逻辑部分最新Word下载.docx》由会员分享，可在线阅读，更多相关《离散数学作业7答案数理逻辑部分最新Word下载.docx（6页珍藏版）》请在冰点文库上搜索。

将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题

1．命题公式

的真值是　1　．

2．设P：

他生病了，Q：

他出差了．R：

我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为P∨Q→R

．

3．含有三个命题变项P，Q，R的命题公式PQ的主析取范式是（PQ┐R）∨（PQR）

4．设P（x）：

x是人，Q（x）：

x去上课，则命题“有人去上课．”可符号化为

∃x（P（x）∧Q（x））．

5．设个体域D＝{a,b},那么谓词公式

消去量词后的等值式为（A（a）∨A（b））∨（B（a）∧B（b））．

6．设个体域D＝{1,2,3}，A（x）为“x大于3”，则谓词公式（x）A（x）的真值为0．

7．谓词命题公式（x）（（A（x）B（x））C（y））中的自由变元为y．

8．谓词命题公式（x）（P（x）Q（x）R（x，y））中的约束变元为x．

三、公式翻译题

1．请将语句“今天是天晴”翻译成命题公式．

解：

设P：

今天是天晴

则该语句符号化为P

2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．

小王去旅游，Q：

小李也去旅游

则该语句符号化为P∧Q

3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式．

明天天下雪Q：

我就去滑雪

则该语句符号化为P→Q

4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．

他去旅游Q：

他有时间

5．请将语句“有人不去工作”翻译成谓词公式．

设P（x）：

x是人Q（x）：

x不去工作

则谓词公式为（∃x）（P（x）∧Q（x））

6．请将语句“所有人都努力工作．”翻译成谓词公式．

x努力工作

则谓词公式为（∀x）（P（x）→Q（x））

四、判断说明题（判断下列各题，并说明理由．）

1．命题公式PP的真值是1．

不正确，┐P∧P的真值是0，它是一个永假式，命题公式中的否定律就是┐P∧P=F

2．命题公式P（PQ）P为永真式．

正确

可以化简┐P∧（P→┐Q）∨P=┐P∧（┐P∨┐Q）∨P=┐P∨P=1，所以它是永真式

当然方法二是用真值表

3．谓词公式

是永真式．

∀xP（x）→（∃yG（x,y）→∀xP（x））

=∀xP（x）→（┐∃yG（x,y）∨∀xP（x））

=∀xP（x）→（∀y（┐G（x,y））∨∀xP（x））

=┐∀xP（x）∨（∀y（┐G（x,y））∨∀xP（x））

=┐∀xP（x）∨∀y（┐G（x,y））∨∀xP（x）

=┐∀xP（x）∨∀xP（x）∨∀y（┐G（x,y））

=1∨∀y（┐G（x,y））

=1

所以该式是永真式

4．下面的推理是否正确，请给予说明．

（1）（x）A（x）B（x）前提引入

（2）A（y）B（y）US

（1）

不正确，

（1）中（）x的辖域仅是A（x），而不是A（x）B（x）

四．计算题

1．求PQR的析取范式，合取范式、主析取范式，主合取范式．

┐P（Q∨R）=┐PQ∨R

所以合取范式和析取范式都是┐PQ∨R

所以主合取范式就是┐PQ∨R

所以主析取范式就是（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）

2．求命题公式（PQ）（RQ）的主析取范式、主合取范式．

（PQ）（RQ）=（PQ）（RQ）=（PQ）（RQ）

其中（PQ）=（PQ）（RR）=（PQR）（PQR）

其中（RQ）=（RQ）（PP）=（PQR）（PQR）

所以原式=（PQR）（PQR）（PQR）（PQR）

=（PQR）（PQR）（PQR）

=（PQR）（PQR）（PQR）=m2m3m7

这就是主析取范式

所以主合取范式为M0M1M4M5M6

可写为（PQR）（PQR）（PQR）（PQR）（PQR）

3．设谓词公式

．

（1）试写出量词的辖域；

（2）指出该公式的自由变元和约束变元．

（1）量词x的辖域为P（x,y）（z）Q（y,x,z）

量词z的辖域为Q（y,x,z）

量词y的辖域为R（y,x）

（2）P（x,y）中的x是约束变元，y是自由变元

Q（y,x,z）中的x和z是约束变元，y是自由变元

R（y,x）中的x是自由变元，y是约束变元

4．设个体域为D={a1,a2}，求谓词公式yxP（x,y）消去量词后的等值式；

yxP（x,y）=xP（x,a1）xP（x,a2）

=（P（a1,a1）P（a2,a1））（P（a1,a2）P（a1,a2））

五、证明题

1．试证明（P（QR））PQ与（PQ）等价．

证：

（P（QR））PQ（P（QR））PQ

（PQR）PQ

（PPQ）（QPQ）（RPQ）

（PQ）（PQ）（PQR）

PQ（吸收律）

（PQ）（摩根律）

2．试证明（x）（P（x）R（x））（x）P（x）（x）R（x）．

证明：

（1）（x）（P（x）R（x））P

（2）P（a）R（a）ES

（1）

（3）P（a）T

（2）

（4）（x）P（x）EG（3）

（5）R（a）T

（2）

（6）（x）R（x）EG（5）

（7）（x）（P（x）R（x））T（4）（6）