命题逻辑的基本概念.ppt

主讲:凌卫新
理学院信息与计算科学系
引言
现代科学技术的各和领域,都提出了大量离散结构的科学问题。例如
计算机科学、程序设计、计算机网络、信息论与编码、通信理论、现代密码学、数字信号处理和形式语言等
它们都与离散数学密切相关。
离散数学
是现代数学的一个重要分支,是计算机科学中基础理论的核心课程。
主要目标——研究离散量的结构和相互之间关系
研究对象——一般是有限个或可数个元素
研究内容——
数理逻辑、集合论、代数学、组合数学、图论、计算理论、复杂网络、网格及网络计算等
《数理逻辑与集合论》的主要内容
第一部分数理逻辑
第1章命题逻辑的基本概念
第2章命题逻辑的等值和推理演算
第4章谓词逻辑的基本概念
第5章谓词逻辑的等值和推理演算
第二部分集合论
第9章集合
第10章关系
第11章函数
第12章实数集合与集合的基数
本课程的要求
授课总学时
32学时:授课周数为16周,每周2学时;
作业
课后布置的作业逢双周星期一交,只有当作业收齐交到讲台上后才开始上课;
成绩评定
平时成绩:20%~30%
期末考成绩:70%~80%
第一部分数理逻辑
先看著名物理学家爱因斯坦出的一道题:
一个商人想招聘一个聪明的助手,有两人前来应聘,商人为了试试哪个更聪明些,就把两个人带进一间漆黑的屋子里,
他打开灯后说:“桌子上有五顶帽子,两顶红色,三顶黑色,现在把灯关掉,并把帽子的位置弄乱,然后我们每人摸一顶帽子戴在自己头上,我再藏起余下的两顶帽子,开灯后,你们要尽快说出自己头上戴的帽子的颜色。”
当开灯后,那两个应试者看到商人头上戴的是一顶红帽子,其中一个人便喊道:“我戴的是黑帽子。”
请问这个人说得对吗?他是怎么推导出来的呢?
第一部分数理逻辑
这需要经历如下过程:
什么是前提?有哪些前提?
结论是什么?
根据什么进行推理?
怎么进行推理?
数理逻辑将回答这些问题,它包括——
命题逻辑
一阶逻辑
数理逻辑(符号逻辑)
是用数学方法来研究推理的形式结构和推理规律的数学学科
它除了研究数学基础课题个,还扩展到了现代科学技术中,如
程序语言、自动机理论、逻辑网络、机器翻译与机器证明等
第1章命题逻辑的基本概念
命题
命题联结词及真值表
合式公式
重言式
命题形式化
波兰表达式
命题
命题的概念
引例就是要对“我戴的是黑帽子”。进行判断。这样的陈述句称为命题。
命题——可判断真假的陈述句。
如:2是素数。
雪是黑色的。
命题的真值——判断的结果
真值的取值——真(1或T)与假(0或F)
真命题: 真值为真的命题(判断正确)
假命题: 真值为假的命题(判断错误)
任何命题的真值都是唯一的。
命题
注意:
感叹句、祈使句、疑问句都不是命题
如:你跑得真快!
全体起立!
又开学了吗?
陈述句中的判断结果不惟一确定以及悖论也不是命题
如:x + 5 > 3
1+1=10
我正在说谎。
 判断给定句子是否为命题的步骤
首先判定它是否为陈述句,
其次判断它是否有唯一的真值。
除地球外的星球有生物。
太阳明天会出来。
命题变项
约定:用大写英文字母(如:P, Q, R, …)来形式化命题,如
用P表示“ 2是素数”。
用Q表示“2 + 5 = 7”。
当P表示任一命题时,P称为命题变项(变元)
命题与命题变项的区别
命题指具体确定真值的陈述句——相当于常量
如:“ 2是素数”。
命题变项的真值不确定,它不是命题,当它用确定命题取代后,它才能确定真值。