离散数学第一章命题逻辑-1-4节.ppt
《离散数学第一章命题逻辑-1-4节.ppt》由会员分享,可在线阅读,更多相关《离散数学第一章命题逻辑-1-4节.ppt(68页珍藏版)》请在三一办公上搜索。
1、1,离 散 数 学,河南工业大学,信息科学与工程学院,第一章 命题逻辑,2,第一篇 数理逻辑,什么是逻辑(学)?研究人类思维的科学。研究思维形式及思维过程。公元前四世纪亚里斯多德工具论奠定了逻辑学的理论基础。中国最早的一部逻辑专著墨经也创造了一个比较完整的逻辑体系。,辩证逻辑,形式逻辑,3,什么是数理逻辑?,数理逻辑是用数学的方法研究逻辑。所谓“数学方法”:就是引进一套符号体系的方法。用数学理论、手段和技巧找出研究对象内在联系的数学表达式及其规范的方法,包括使用符号和公式,已有的数学成果和方法,特别是使用形式的公理方法。数理逻辑即引进一套符号体系的方法来研究概念、判断和推理,即对符号进行判断和
2、推理。所以数理逻辑也称为“符号逻辑”。数理逻辑属于形式逻辑。,它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。,数理逻辑的主要内容,数理逻辑内容丰富,但其主要包括“两个演算”加“四论”,即:逻辑演算。包括命题演算和谓词演算证明论。主要研究数学理论系统的相容性(即不矛盾、协调性)的证明。递归论(能行性理论)。自从电子计算机发明后,迫切需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论,它为能行可计算的函数找出各种理论上精确化的严密类比物。模型论。主要是对各种数学理论系统建立模型,并研究各模型之间的关系以及模型与系统之间的关系。公理集合论。主要研究在消除已知集合论
3、悖论的情况下,用公理方法把有关集合的理论充分发展下去。,5,1、“甲在河南工业大学上学”,2、“甲在郑州上大学”,如果“甲在河南工业大学上学”真的,则显然“甲在郑州上大学”也是真的。,推理形式“如果甲在河南工业大学上学,则 甲在郑州上大学”;甲在河南工业大学上学;则可推出甲在郑州上大学。,符号化为:P表示“甲在河南工业大学上学”;Q表示“甲在郑州上大学”;P Q表示“如果甲在河南工业大学上学,则 甲在郑州上大学”。,推理形式可以表示为P Q为真;P为真;则可推出Q为真。可以抽象地写成(P Q)P Q,3、“如果甲在河南工业大学上学,则甲在郑州上大学”是成立的,例:,请根据下面事实,找出凶手:1
4、.清洁工或者秘书谋害了经理。2.如果清洁工谋害了经理,则谋害不会发生在午夜前。3.如果秘书的证词是正确的,则谋害发生在午夜前。4.如果秘书的证词不正确,则午夜时屋里灯光未灭。5.午夜时屋里灯灭了。问:谁是凶手?,秘书谋害了经理。,第一篇 数理逻辑,主要研究内容,第一章 命题逻辑研究的内容,命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系。,1-1 命题与命题的真值1-2 联结词1-3 命题公式及翻译1-4 真值表与等价公式1-5 重言式与蕴含式1-6 其它联结词()1-7 对偶与范式1-8 命题推理理论,第一章 命题逻辑 学习要求,10,1-1.命题与命题的真值,本
5、节主要讨论四个问题:命题的概念命题的真值原子命题与复合命题命题的表示,11,一、命题的概念,陈述句:陈述一个事实或一个说话人的看法,句末用句号。祈使句:要求或者希望别人做什么事或者不做什么事时用的句子,句末用句号或感叹号。疑问句:提出问题的句子,句末用问号。感叹句:带有浓厚感情的句子,句末用感叹号。,请看下面给出的两个陈述句:,(1)2是个素数。(2)雪是黑色的。这两个陈述句都表示对事件性质的判断。第一句话表示的判断是正确的,第二句话表示的判断是错误的。像(1),(2)这样能够唯一确定所表达的判断是正确的还是错误的陈述句称为命题。,13,一、命题的概念,命题是一个能判断是真的或是假的陈述句。命
6、题一定是陈述句,但并非一切陈述句都是命题。真值:一个命题的值叫真值。一个命题的真值有两个:“真”或“假”真值为真:一个命题所作的判断与客观一致,则称该命题的真值为真,记作T(True),真命题。真值为假:一个命题所作的判断与客观不一致,则称该命题的真值为假,记作F(False),假命题。命题是具有唯一真值 的陈述句。命题可以是真的,或者是假的,但不能同时为真又为假。,例子,例1-1.1,(1)中华人民共和国的首都是北京。(2)大于4的偶数均可分解为两个质数的和(哥德巴赫猜想)。(3)所有质数都是奇数。(4)雪是黑色的。,真命题,真命题,假命题,假命题,判断语句是否为命题要注意的问题:,1、目前
7、无法确定真值,但从本质而言,真值存在的语句是命题。例:(1)别的星球上有生物。(2)2046年世界杯在中国举行。2、真值因时因地而异的判断性陈述句是命题。例:(1)2011年的元旦是晴天。(2)今天下雨。3、含有未确定内容的代词,不能判断真假的语句不是命题。例:(1)1+101=110。当1和101是二进制数,语句为真,为十进制数,语句为假。(2)x+y10。4、悖论不是命题。语句既为真,同时又包含假的不是命题,这样的句子称为“悖论”。例:我正在说慌。,如何判断一个句子是否为真命题?,1、是否为陈述句?2、其真值是否唯一?3、其真值是否为真。,命题,分子命题,原子命题,二、原子命题与复合命题,
8、简单命题(原子命题):由最简单的陈述句构成的命题(该句再不能分解成更简单的句子了)。如:我是一位学生。复合命题(分子命题):由若干个原子命题使用适当的联结词所组成的新命题。我是一位学生。他是一位教师。我是一位学生和他是一位教师,这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,18,三、命题的表示,大写的带或不带下标的英文字母,如:A,A3,P例如:P:今天下雨。Q:张三在唱歌。表示命题的符号。表示确定命题的命题标识符。命题常量真值确定,是命题。可表示任意一个(原子或复合)命题的命题标识符,就称为命题变元。命题标识
9、符只表示任意命题的位置标志。注意:命题变元可以表示任意的命题,所以真值不确定,命题变元不是命题。当命题变元P用一个特定命题去取代或者是直接赋给命题变元真值“T”或“F”时,才能确定P的真值,该过程称对P进行指派。例:若P是命题变元,P:北京是中国的首都。(指派P为命题北京是中国的首都),命题标识符:,表示方法:,对命题变元作指派(给命题变元一个解释):,命题常量:,命题变元:,19,1-2 联结词,复合命题的构成:是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词,定义了六个逻辑联结词,分别是:(1)否定“”(2)合取“”(3)析取“”(4)异或“”(5)条件“”(6)双条件“”,
10、20,一、否定“”一元运算,符号,读作:“非”,“否定”。设P为命题,在P的前面加否定词,变为P,P读作:“非P”或“P的否定”。P为一新的命题,定义:用真值表表示。P是P的否定式。例1-2.1 P:2是素数。(T)P:2不是素数。(F)P:上海是一个大城市。(T)P:上海不是一个大城市。或:上海是个不大的城市。(严格讲不建议)。,21,一、否定“”一元运算,P:咱班每个同学都大于18岁。P?咱班每个同学不都大于18岁咱班每个同学都不大于18岁。用真值表来判断。,P P,T F,F T,P:咱班每个同学不都大于18岁。不是每个同学不大于18岁。至少有一个同学不大于18岁。,对量化命题的否定,需
11、要同时对动词和量化词要加以否定。,二、合取“”二元运算,符号:设P,Q为两个命题,PQ 称为P与Q的合取,读作:“P合取Q”,“P与(并且)Q”,“P与Q的合取”等。P和Q的合取为一个复合命题。定义:由真值表给出。PQ的真值为真,当且仅当P和Q的真值均为真。,P和Q是互为独立的,地位是相等,P和Q的位置可以互换而不会影响PQ 的结果。,23,二、合取“”二元运算,相应的日常用语:“并且”、“既又”,“不但(仅)而且”,“虽然但是”,“尽管还”,例1-2.2 P:今天下雨。Q:明天下雨。PQ:今天下雨而且明天下雨(或者:今天与明天都下雨,或者:这两天都下雨)。P:我们去食堂吃饭。Q:教室里有三块
12、黑板。PQ:我们去食堂吃饭并且教室里有三块黑板。注:复合命题中的原子命题之间无需有一般逻辑意义上的关联。,下列语句不是合取联结词组成的命题,1)张丽和王芳是好朋友。2)他打开箱子然后(而后)拿出一件衣服来。,三、析取“”、异或“”二元运算1.析取“”,符号:设P,Q为两个命题,P Q 称为P与Q的析取,读作:“P或者Q”、“P析取Q”等。P和Q的析取为一个复合命题。定义:见真值表PQ的真值为F,当且仅当P与Q均为F。,区分“可兼或”与“不可兼或”,例1-2.3灯泡有故障或者线路有故障。今晚写字或看书。今天下雨或打雷。以上例子为可兼或。析取为可兼或。,2.异或“”,P Q的真值为F,当且仅当P与
13、Q的真值相同。例1-2.4他通过电视看足球比赛或到体育馆看体育比赛。他乘火车去郑州或乘汽车去郑州。以上例子为不可兼或。,四、双条件“”,符号:设P,Q为两个命题,P Q 读作:“P当且仅当Q”、“P是Q的充分必要条件”等。P和Q的双条件为一个复合命题。定义:见真值表PQ的真值为真,当且仅当P与Q的真值相同。例1-2.4:P:ABC是等边三角形。Q:ABC是等角三角形。PQ:ABC是等边三角形当且仅当它是等角三角形。,例:下面均为双条件联结词,平面上二直线平行,当且仅当这二直线不相交。春天来了,燕子飞回来了。(春天来了当且仅当燕子飞回来了)2+2=4当且仅当雪是白的。,P Q中,P和Q的地位是平
14、等的,P、Q交换位置不会改变真值表的值。,30,五、条件“”,符号:设P,Q为两个命题,P Q 读作:“P蕴含Q”、“如果P则Q”、“P条件Q”、“P是Q的充分条件”、“Q是P的必要条件”、“P仅当Q”、“Q当且P”等。P Q为一个复合命题。P:称为前件、条件、前提、假设,Q:称为后件、结论。定义:见真值表。,PQ的真值,PQ的真值为假,当且仅当P为真,Q为假。注意:当前件P为假时,PQ为T。,结论:P Q中,P和Q的地位是不平等的,P、Q交换位置将会改变真值表的值。,前件为假,PQ为真。后件为真,PQ为真。,一位父亲对儿子说:“如果星期天天气好,就一定带你去动物园。”问:在什么情况下父亲食言
15、?父亲的可能情况有如下四种:(1)星期天天气好,带儿子去了动物园;(2)星期天天气好,却没带儿子去动物园;(3)星期天天气不好,却带儿子去了动物园;(4)星期天天气不好,也没带儿子去动物园。,示例,没有食言,没有食言,没有食言,食言,33,书例:,前提与结论有联系的:如果某动物为哺乳动物,则它必胎生。如果我得到这本小说,那么我今夜就读完它。前提与结论可以没有联系的:如果雪是黑的,那么太阳从西方出来。,举例:,令:P:天气好。Q:我去公园。,1.如果天气好,我就去公园。,PQ,2.只要天气好,我就去公园。,PQ,3.天气好,我就去公园。,PQ,4.只有天气好,我才去公园。,Q P,5.仅当天气好
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第一章 命题逻辑
链接地址:https://www.31ppt.com/p-6326532.html