湖南大学离散数学教案-命题逻辑.ppt

第一章 命题逻辑 杨圣洪 yangshenghong8@引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分， 但究竟什么是命题？ 如何表示命题？ 如何构造出复杂的命题？ 在本章将讨论这些问题。 1.1 命题及联结词 对错确定的陈述语句称为命题。如： (1)湖南大学是一本学校。 (2)命题逻辑是计算机科学的基础课程。 (3)命题及联结词是命题逻辑的最基础的内容。 (4)4是素数。 (5)湖南大学坐落于湘江以东。 (6)2011年湖南长沙轻轨通车。 其中(1)、(2)、(3) 与事实相符，是对的、正确的，称为真命题，或者称命题的值为“真”，简记为T或数字1。 而(4)、(5)明显与事实不相符，是错的、不正确，称为假命题，或称命题的值为“假”，简记为F或数字0。 陈述句(6)的正确性，到2011年12月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。 1.1 命题及联结词 对错确定的陈述语句称为命题。如： (7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10 (7)的对错不确定的。当x为50、y为50时是对的，当x为51、y为52时是错的。 (8)的对错是不确定的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句不是命题。 (9)岳麓山的红叶真美呀！ (10)动作快点！ (11)你是离散数学老师吗？ 这三个语句不是陈述语句，因此不是命题。 1.1 命题及联结词 对错确定的陈述语句称为命题。如： (12)我在说假话。 (13)我只给自己不能理发的人理发。 (14)派出所说:必须先房子再能上户口 单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 这是一个悖论，其真值不能确定，故不是命题。。 1.1 命题及联结词 对错确定的陈述语句称为命题。如： (13)我既要学程序设计，又要学离散数学。 (14)我们早餐在公寓食堂或外面早点摊上吃。 (15)我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。 其中(13)与(14)可分解为另外二句话的组合， 而(15)是对“我是数学院学生”的否定，这些语句称为“复合命题”，不能再分解的语句称为“简单命题”或“原子命题”，为了便于推理与书写，常用小写字母表示简单命题或原子命题。 1.1 命题及联结词 简单命题组合成复杂命题时所使用的辅助词称为“联结词”。 命题逻辑中的联结词归纳为以下5种。 合取?：C语言中 and 并且 析取?：C语言中 || or 或 否定?：C语言中 ! not 非,不是,否定 条件式?：C语言中 if () 如果…那么 如p则q 双条件式?： 如p则q且如q则p,当且仅当 1.1 命题及联结词 定义1.1合取： 当p、q都对，即取值为真(T或1)时，“p合取q”的值为真. 1.1 命题及联结词 定义1.1合取： 当p、q都对，即取值为真(T或1)时，“p合取q”的值为真，其他情况为假。 1.1 命题及联结词 定义1.2析取： 当p、q都不对，即取值为假(F或0)时，“p析取q”的值为假，其他情况为真。 1.1 命题及联结词 逻辑运算符“析取” 与汉语的“或”几乎一致但有区别： (16)“讲离散数学的老师是杨老师或刘老师”，可以表示为“讲离散数学的老师是杨老师”?“讲离散数学的老师是刘老师”，这两个原子命题有可能都是对的，这种“或”称为“可同时为真的或”，或简称为“可兼或”。 (17)“离散数学的教室是102或302”，不可以表示为“离散数学的教室是102”?“离散数学的教室是302”，因为这两个原子命题不可能都对，只能这二种情况之一，这种“或”称为“不可同时为真的或”，或简称为“不可兼或”、“排斥或”. 这种“或”表示不能简单表示为“析取”，需要联合使用下面将要介绍的“否定”与“析取”符号，才能准确表达。 1.1 命题及联结词 定义1.3否定:当p是1 ，p的否定?p即为0。 1.1 命题及联结词 定义1.4条件:当p是1 ,q是0时,p?q为0,即1