离散数学 数理逻辑
假命题:凡与事实不相符的命题,其真值为假。符号化:用“0”或 “F”表示。 真命题:凡与事实相符的命题,其真值为真。符号化:用“1”或 “T”表示。
2020/10/13
8
第一篇数理逻辑第一章命题逻辑
1.1命题及表示法
例:判断下列语句是否为命题 (1)三角形的三个内角和为180度。
(2)4为素数。
(3)1+101=110
定义:设P和Q为两个命题,由P与Q用二元联结词 “” 成复合命题,记为“PQ”。读作“P且Q”
2020/10/13
11
第一篇数理逻辑第一章命题逻辑
1.2命题联结词
例1:P43;11=100”,Q:“熊猫为稀有动物” PQ:
注:内容上无联系的两个命题也可以组成具有确定真值的命题。
例2:雪是黑的,仅当太阳从西方出来。 等价于 如果雪是黑的,则太阳从西方出来。 5、等价词(双条件)“” 定义:设P和Q为两个命题,由P与Q用二元联结词 “”组成复 合题命,称为等价复合命题记为“PQ”。读作“P当且仅当Q”,当且 仅 P和Q的真值相同时,PQ为真。否则为假。 例:将下列命题符号化,并讨论它们的真值 1) if:3+3=6,则雪是白的。 2) if:3+3不等于6,则雪是白的。 3) if:3+3=6,则雪不是白的。 4) if:3+3不等于6,则雪不是白的。 5) 3为有理数当且仅当美国在亚洲。
离散数学教程
上海电力学院
2020/10/13
1
前言
一、为什么要学习离散数学?
1、专业的需要: 2、对本身素质的训练 二、连续数学与离散数学 1、连续数学:微积分,微分方程,复变函数等. 2、离散数学:是许多数学分支的总称.主要括:
数理逻辑,集合论,代数系统,图论. 三.教学方法
1)引路 2)预习 3)作业 4)章后总结
例1:有位父亲对儿子说:“如果我去书店,我一给你买光盘。” 试问:在何种情况下,这位父亲算失信? 解:P:父亲去书店,Q:给儿子买光盘
1) P=1,Q=1 2) P=1,Q=0
3) P=0,Q=1 4) P=0,Q=0
注:善意的推论。
2020/10/13
13
第一篇数理逻辑第一章命题逻辑
1.2命题联结词
2020/10/13
10
第一篇数理逻辑第一章命题逻辑
1.2命题联结词
定义:简单命题(原子命题)不能再分解为更简单的命题。
定义:复合命题 若干个简单命题通过命题联结词而构成的新命题。 1、否定词“” 定义:设P为一个命题,利用“”与P组成复合命题称为P的否命 题记,为“ P”。读作“非P”,其真值表见表1-1 注: “”为一元运算,否定全部而非部分。 2、合取词“”
3:析取词“” 定义:设P和Q为两个命题,由P与Q用二元联结词 “”组 成 复合命题,记为“PQ”。读作“P或Q”
例1:P:“开关坏了”,Q:“灯炮坏了”:PQ: 注: “”表示可兼或。不可兼或不能用“”表示。
2020/10/13
12
第一篇数理逻辑第一章命题逻辑
1.2命题联结词
例2:小李下午去打蓝球或在宿舍玩电脑。 4、条件“” 定义:设P和Q为两个命题,由P与Q用二元联结词 “”组成复 合题命,记为“P Q”。读作“如果P,则Q”,其中P为前件,Q为后 件 只。有当前件为真,后件为假时, PQ为假。
形式逻辑。计算机的硬件,软件,算法及语言都具有数理逻辑 的性质。 我们在此仅讲授数理逻辑的基础部分——逻辑演算部分。它包 括命题演算和(一阶)谓词演算两部分。
2020/10/13
5
第一篇数理逻辑第一章命题逻辑
第1章命题逻辑
1.1 命题及表示法 1.2 联结词 1.3 命题公式与翻译 1.4~1.5 命题逻辑的等值演算 1.6 其它联结词及联结词完备集 1.7 对偶与析取范式和合取范式(范式) 1.8 命题逻辑推理理论
第一篇集合论(集合基本概念、关系、无限集) 第二篇代数结构(代数系统、群、环、域、格)
第三篇图论(图的基本概念以及不同类型的图) 第四篇数理逻辑(命题逻辑和谓词逻辑)
2020/10/13
4
第一篇数理逻辑第一章命题逻辑
第1章命题逻辑
数理逻辑是计算机科学的基础理论之一。可分为五大部分: 逻辑演算、集合论、证明论、模型论、递归论。数理逻辑既是 数学又是逻辑学:它研究数学中的逻辑问题,用数学方法研究
(4)你喜欢离散数学吗? (5)这朵花真美啊! (6)x>y (7)我正在说谎。
2020/10/13
9
第一篇数理逻辑第一章命题逻辑
1.1命题及表示
命题符号化:一般用大写字母A,B,…,P,Q,…或带下标的大 写字母或数字表示。 例:(1)P:“雪是黑的”
(2)Q2:“上海是个美丽的城市” (3):“X+2>8” 命题常元与命题变元 命题常元:表示具体确定内容的命题。 命题变元:表示任意的,没有赋予具体内容的抽象命题。 注1:命题变元与命题常元的区别 注2:命题变元与命题常元在逻辑演算中处理原则相同。
2020/10/13
2
前言
四、参考书
1)《离散数学》耿素云等编著,高教出版社 2)《离散数学》何自强等编著,科学出版社 如何使用参考书? 每章每节后看参考书,然后总结,压缩即:薄厚薄 五、作业
2020/10/13
3
前言
基础课离之散一数。学本是课现程代以数学集的合一论个、重代要数分结支构,、是学数习理计逻算辑机、科图学论与的术的重要 四大部分为主干教学内容,并辅以组合论、数论基础、形式语言与 自动机初步等内容。本教案选取课程的主干内容进行组织,包括:
2020/10/13
6
第一篇数理逻辑第二章谓词逻辑
第2章谓词逻辑
2.1谓词的概念与表示 2.2命题函数与量词 2.3~2. 4一阶谓词公式 2.5一阶谓词演算的等价式与蕴含式 2.6 一阶谓词前束范式 2.7一阶逻辑的推理理论
2020/10/13
7
第一篇数理逻辑第一章命题逻辑
1.1命题及表示法
命题逻辑研究的中心问题是推理,即研究推理中的前题和结论之 间的形式关系,而不涉及前题和结论的具体内容。推理的基本单 位为命题。 定义1:命题是能判断真假的陈述句。 注1:上命题必须是陈述句。而疑问句、祈使句和感叹句等不是命 题。 注2:命题的真值是唯一的,但与我们是否知道它的真值无关。 定义2:真值是陈述句为真或假的这种性质。