命题逻辑及命题演算.ppt

《命题逻辑及命题演算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑一、绪言1、离散数学课程简介:--"研究离散结构的数学分科。"《辞海》79年版，P355概述和计算机科学联系和计算机科学联系紧密是计算机科学的支撑学科之一，也是信息科学的数学基础。在计算机理论研究及软硬件开发的各个领域都有广泛的应用。在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题构成了离散数学。学习离散数学的重要性一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我

2、把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”    请问这个人说得对吗？他是怎么推导出来的呢？要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程：(1)什么是前提？有哪些前提？(2)结论是什么

3、？(3)根据什么进行推理？(4)怎么进行推理？二、命题与联结词1引例：4是素数；是无理数；大于；大于吗？；请不要吸烟！定义：命题---具有唯一真值的陈述句。例我正在说假话；2009年的元旦是晴天。真命题---命题的判断结果为真。假命题---命题的判断结果为假。表示方法：命题（），真（1）假（0）。4是素数；是无理数等不能分解成更简单例的陈述句了，称此种命题为简单命题（原子命题）。否则，某命题是由简单命题通过联结词连接在一起的命题，称之为复合命题。例：2是偶数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。解：2是偶数；2

4、是素数；4是素数；3是素数。非；且；或；如果则；当且仅当。p┐pF（0）T（1）T（1）F（0）“见假为真，见真为假”┐p读作“并非p”或“非p”。(1)否定式：（negation）设P为一命题，P的否定是一个新命题，记作“┐P”。若P为T，┐P为F；若P为F，┐P为T。联结词“┐”表示自然语言中的“并非”（not）。三、联结词（2）合取式：（conjunction）两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，其他情况下，P∧Q的真值都是F。合取联结词“∧”表示自然语言中的“并且”。pqp∧qF（0）F（0）T（1）T（1

5、）F（0）T（1）F（0）T（1）F（0）F（0）F（0）T（1）p∧q读作“p并且q”或“p且q”见假为假，全真为真。（3）析取式：两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q为F，其他情况下，P∨Q的真值都是T。析取联结词“∨”表示自然语言中的“或”（or）。pqp∨qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）T（1）T（1）T（1）见真为真，全假为假。p∨q读作“p或者q”、“p或q”。（4）蕴涵式：给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q。当且仅当P的真值为T，Q的真值为F时

6、，P→Q的真值为F，其他情况下，P→Q的真值都是T。条件联结词“→”表示自然语言中的“如果…，那么…”。pqp→qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）T（1）F（0）T（1）p→q中的p称为条件前件，q称为条件后件前真后假为假，其他为真。（5）等价式：给定两个命题P和Q，其复合命题PQ称作双条件命题。当P和Q的真值相同时，PQ的真值为T，否则，PQ的真值都是F。双条件联结词“”表示自然语言中的“当且仅当”。pqpqF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）F（0）F（0）T（1）pq读作

7、“p与q互为条件”，“p当且仅当q”。相同为真，相异为假。1-1.2复合命题的符号化复合命题的符号化的基本步骤1)找出各个原子命题，并逐个符号化；2)找出各个连接词，符号成相应联结词；3)用联结词将原子命题逐个联结起来；1-1.2复合命题的符号化例将下列命题符号化(1)北京不是村庄P:表示“北京是村庄”┐P:北京不是村庄(2)小王是游泳冠军和百米赛跑冠军P：小王是游泳冠军;Q：小王百米赛跑冠军P∧Q:小王是游泳冠军和百米赛跑冠军1-1.2复合命题的符号化例将下列命题符号化(3)小明或者小华能解够出这道题P：小明能够解出这道题;Q：小华能够解出这道题P∨Q(4)小王

8、或者小李中