离散数学-命题演算
- 格式:pptx
- 大小:172.32 KB
- 文档页数:72
第一章命题演算及其形式系统1.1 命题与联结词内容提要1.1.1 命题我们把对确定的对象作出判断的陈述句称作命题(propositions),当判断正确或符合客观实际时,称该命题真(true),否则称该命题假(false)。
“真、假”常被称为命题的真值。
自然语言中“并非、或者、并且、如果…,那么…、当且仅当” 这样的联结词称为逻辑联结词(logical connectives)。
通常把不含有逻辑联结词的命题称为原子命题或原子(atoms),而把由原子命题和逻辑联结词共同组成的命题称为复合命题(compositive propositions)。
1.1.2 联结词否定词(negation)“并非”(not),用符号┐表示。
设p表示一命题,那么┐p表示命题p的否定。
p真时┐p假,而p假时┐p真。
┐p读作“并非p”或“非p”。
合取词(conjunction)“并且”(and),用符号∧表示。
设p,q表示两命题,那么p∧q表示合取p和q所得的命题,即p和q同时为真时p∧q真,否则p∧q为假。
p∧q读作“p并且q”或“p且q”。
析取词(disjunction)“或”(or)用符号∨表示。
设p,q表示两命题,那么p∨q表示p和q的析取,即当p和q有一为真时,p∨q为真,只有当p和q 均假时p∨q为假。
p∨q读作“p或者q”、“p或q”。
蕴涵词(implication)“如果……,那么……”(if…then…),用符号→表示。
设p,q表示两命题,那么p→q表示命题“如果p,那么q”。
当p真而q假时,命题p→q为假,否则均认为p→q为真。
p→q中的p称为蕴涵前件,q称为蕴涵后件。
p→q的读法较多,可读作“如果p则q”,“p蕴涵q”,“p是q的充分条件”,“q是p的必要条件”,“q当p”,“p仅当q”等等。
数学中还常把q→p,┐p→┐q,┐q→┐p分别叫做p→q的逆命题,否命题,逆否命题。
双向蕴涵词(two-way implication)“当且仅当”(if and only if),用符号表示之。
自考离散数学命题演算笔记一、命题演算的基本概念1. 命题:可以明确判断真假的陈述句称为命题。
2. 命题符号:用字母(如p、q、r等)表示的命题称为命题符号。
3. 命题演算:研究命题符号之间关系的数学分支。
二、命题演算的基本运算1. 否定(¬):表示对命题的否定,如¬p表示对p的否定。
2. 合取(∧):表示两个命题的合取,如p∧q表示p和q同时为真。
3. 析取(∨):表示两个命题的析取,如p∨q表示p和q至少有一个为真。
4. 蕴含(→):表示两个命题的蕴含关系,如p→q表示如果p为真,则q必为真。
5. 双条件(↔):表示两个命题的双条件关系,如p↔q表示p和q同时为真或同时为假。
三、命题演算的基本法则1. 双重否定律:¬¬p = p2. 假言三段论:p→q, ¬q→¬p3. 假言换位:p→q ↔ ¬q→¬p4. 交换律:p∧q ↔ q∧p, p∨q ↔ q∨p5. 结合律:p∧(q∧r) ↔ (p∧q)∧r, p∨(q∨r) ↔ (p∨q)∨r6. 分配律:p∧(q∨r) ↔ (p∧q)∨(p∧r), p∨(q∧r) ↔(p∨q)∧(p∨r)7. 吸收律:p∧(p∨q) ↔ p, p∨(p∧q) ↔ p8. 德摩根律:¬(p∧q) ↔ ¬p∨¬q, ¬(p∨q) ↔ ¬p∧¬q9. 互补律:p∨¬p ↔ 1, p∧¬p ↔ 010. 等幂律:p∧p ↔ p, p∨p ↔ p自考离散数学命题演算笔记四、命题逻辑函数命题逻辑函数是指对命题进行运算的函数,它将命题作为输入,输出也是一个命题。
常见的命题逻辑函数包括:1. 常函数:常函数的输出是一个固定的命题,无论输入是什么。
例如,常真函数T的输出始终为真,常假函数F的输出始终为假。
2. 投影函数:投影函数的输出是其输入之一。
自考离散数学命题演算笔记本章的重点是命题概念及其表示、命题公式化简、主范式及其互化、P规则、T规则以及CP规则。
难点是推理理论及应用。
一、命题概念(领会)学习本章首先要深刻理解命题的概念。
理解原子命题与复合命题的关系,在了解复合命题的基础上,理解联结词的定义。
命题:具有唯一真值的陈述句称为命题,又简称语句。
注意,这里有两个条件,首先它是一个陈述句,其次,它具有唯一的一个真值。
真值:就是语句为真或假的性质。
一个语句的真值可以为真也可以为假。
真值不是说该语句的值必为真。
任一命题必有其真值,也称这个命题的值。
既然是命题了,那它必有一个确定的真值,不管这个真值为真还是为假。
当一个陈述句能够分辩其值的真假时(也就是说,总可以肯定是其中的某一个),它就是命题,即使我们不知道它是真还是假。
另外要理解命题常量、命题变元及指派的含义。
复合命题就是一些原子命题经过一些联结词复合而成的命题。
常用的联结词有:(1)否定、(2)合取、(3)析取、(4)条件、(5)双条件复合命题与联系词是密切相关的,不包含联结词的命题就是原子命题,至少包含一个联结词的命题才是复合命题。
复合命题的真值只取决于构成它们的各原子命题的真值,而与它们的内容含义无关。
对联结词所联结的两原子命题之间有无关系无关。
(这一条很重要,因为一个命题用自然语言表达时,我们往往会受到自然逻辑的影响,比如"我如果不上班,那么天下雨"这种命题,在自然的逻辑里,是不成立的,一个人不上班怎么会导致天下雨呢? 但是在这里,这个复合命题的值实际上是由两个原子命题的真值决定的,与它的含义无关,这个复合命题是|P->Q ,前一个原子命题的真值为假,后一命题值为真,根据条件的定义,这个复合命题值为真)∧、∨、←→具有对称性,|、→无对称性,(教材提示,也可用iff表示双向箭头←→,由于字符集的限制,本网页在表示否定关联词时用"|",请在书写时注意规范写法。
第一章命题演算及其形式系统1.1 命题与联结词内容提要1.1.1 命题我们把对确定的对象作出判断的陈述句称作命题(propositions),当判断正确或符合客观实际时,称该命题真(true),否则称该命题假(false)。
“真、假”常被称为命题的真值。
自然语言中“并非、或者、并且、如果…,那么…、当且仅当” 这样的联结词称为逻辑联结词(logical connectives)。
通常把不含有逻辑联结词的命题称为原子命题或原子(atoms),而把由原子命题和逻辑联结词共同组成的命题称为复合命题(compositive propositions)。
1.1.2 联结词否定词(negation)“并非”(not),用符号┐表示。
设p表示一命题,那么┐p表示命题p 的否定。
p真时┐p假,而p假时┐p真。
┐p读作“并非p”或“非p”。
合取词(conjunction)“并且”(and),用符号∧表示。
设p,q表示两命题,那么p∧q表示合取p和q所得的命题,即p和q同时为真时p∧q真,否则p∧q为假。
p∧q读作“p 并且q”或“p且q”。
析取词(disjunction)“或”(or)用符号∨表示。
设p,q表示两命题,那么p∨q表示p 和q的析取,即当p和q有一为真时,p∨q为真,只有当p和q均假时p∨q为假。
p∨q 读作“p或者q”、“p或q”。
蕴涵词(implication)“如果……,那么……”(if…then…),用符号→表示。
设p,q表示两命题,那么p→q表示命题“如果p,那么q”。
当p真而q假时,命题p→q为假,否则均认为p→q为真。
p→q中的p称为蕴涵前件,q称为蕴涵后件。
p→q的读法较多,可读作“如果p则q”,“p蕴涵q”,“p是q的充分条件”,“q是p的必要条件”,“q当p”,“p仅当q”等等。
数学中还常把q→p,┐p→┐q,┐q→┐p分别叫做p→q的逆命题,否命题,逆否命题。
双向蕴涵词(two-way implication)“当且仅当”(if and only if),用符号↔表示之。