离散数学 杨圣洪等著 第一章习题二解答.pdf

离散数学 杨圣洪等著 第一章习题二解答.pdf

ID:55057302

大小:203.50 KB

页数:10页

时间:2020-05-08

离散数学 杨圣洪等著 第一章习题二解答.pdf_第1页
离散数学 杨圣洪等著 第一章习题二解答.pdf_第2页
离散数学 杨圣洪等著 第一章习题二解答.pdf_第3页
离散数学 杨圣洪等著 第一章习题二解答.pdf_第4页
离散数学 杨圣洪等著 第一章习题二解答.pdf_第5页
资源描述:

《离散数学 杨圣洪等著 第一章习题二解答.pdf》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、习题二一、分别用等算演算与真值表法,判断下列公式是否存在主析取范式或主合取范式,若有,请写出来。(1)(¬p→q)→(¬q∨p)(2)(¬p→q)→(q∧r)(3)(p∨(q∧r))→(p∨q∨r)(4)¬(q→¬p)∧¬p(5)(p∧q)∨(¬p∨r)(6)(p→(p∨q))∨r(7)(p∧q)∨r(8)(p→q)∧(q→r)(9)(p∧q)→q(10)¬(r↔p)∧p∧q解:(1)pq¬p(¬p→q)¬q(¬q∨p)(¬p→q)→(¬q∨p)0010111011100010011111101011存在主析取范式=成

2、真赋值对应的小项的析取=m00∨m10∨m11=(¬p∧¬q)∨(p∧¬q)∨(p∧q)主析取范式=成假赋值对应的大项的合取=M01=p∨¬q等值演算:(¬p→q)→(¬q∨p)⇔¬(¬¬p∨q)∨(p∨¬q)⇔¬(p∨q)∨(p∨¬q)⇔(¬p∧¬q)∨(p∨¬q)⇔(¬p∨(p∨¬q))∧(¬q∨(p∨¬q))⇔(¬p∨p∨¬q)∧(¬q∨p∨¬q)⇔(1∨¬q)∧(p∨¬q)⇔(p∨¬q)这是大项,故为大项的合取,称为主合取范式(¬p→q)→(¬q∨p)⇔(p∨¬q)⇔(p)∨(¬q)⇔(p∧1)∨(1∧¬q)⇔

3、(p∧(q∨¬q))∨((p∨¬p)∧¬q)⇔(p∧q)∨(p∧¬q)∨(p∧¬q)∨(¬p∧¬q)⇔(p∧q)∨(p∧¬q)∨(¬p∧¬q)因为一个公式的值不是真,就是假,因此当我们得到一个公的取值为真的情况时,剩下的组合是取值为假,因此当得到小项的析取组成的主析取范式后,可以针对剩下的组合写出主合取范式。如当我们得到(¬p→q)→(¬q∨p)的大项之合取(p∨¬q)后,使(p∨¬q)为假时(p,q)的值为(0,1),故其标记为M01,剩余的取值为(0,0),(1,0),(1,1),故小项之析取为m00∨m10∨m1

4、1。反之,若先得到其小项的析取,也可得到其大项的合取。反正这两者将其所有组合瓜分完毕。(2)(¬p→q)→(q∧r)pqr¬p¬p→q(q∧r)结果00010010011001010110001111111000100101010011001001110111主析取范式=m000∨m001∨m011∨m111=(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧q∧r)主合取范式=M010∧M100∧M101∧M110=(p∨¬q∨r)∧(¬p∨q∨r)∧(¬p∨q∨¬r)∧(¬p∨¬q∨r)(3)(p∨

5、(q∧r))→(p∨q∨r)pqr(q∧r)(p∨(q∧r))(p∨q∨r)(p∨(q∧r))→(p∨q∨r)00000010010001010001101100111000111101011111011111111111永真式,所有小项的析取得到其主析取范式=(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)由于没为假的指派,所以没有为假赋值,所对应的大项合取构成的合取,即没有主合取范式。¬(p∨(q∧r))∨(p∨q

6、∨r)=(¬p∧¬(q∧r))∨(p∨q∨r)=((¬p∧¬q)∨(¬p∧¬r))∨(p∨q∨r)=(¬p∧¬q)∨(¬p∧¬r)∨p∨q∨r=¬(p∨q)∨(¬p∧¬r)∨p∨q∨r=1永真(4)¬(q→¬p)∧¬ppq¬p(q→¬p)¬(q→¬p)结果001100011100100100110010没有成真的赋值,从而没有对应的小项,因此没有小项构成的主析取范式永假式即矛盾式,为假指派对应的大项合取=(p∨q)∧(p∨¬q)∧(¬p∨q)∧(¬p∨¬q)原式=¬(¬q∨¬p)∧¬p=(q∧p)∧¬p=0(5)(p∧

7、q)∨(¬p∨r)pqr(p∧q)¬p(¬p∨r)(p∧q)∨(¬p∨r)00001110010111010011101101111000000101001111010011111011主析取范式(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)主合取范式M100=¬p∨q∨r原式=((p∧q)∨¬p)∨r=((p∨¬p)∧(¬p∨q))∨r=(1∧(¬p∨q))∨r=¬p∨q∨r这就是大项也剩下的赋值对应的就是小项(6)(p→(p∨q))

8、∨rpqr(p∨q)(p→(p∨q))(p→(p∨q))∨r000011001011010111011111100111101111110111111111永真式,只有小项组成的主析取范式。没有为假的赋值,所以没有成假赋值对应的大项的合取,即没有主合取范式。原式=(¬p∨(p∨q))∨r=(1∨q)∨r=1(7)(p∧q)∨rpq

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。