离散数学ch1[2讲义]命题演算

第一章命题演算及其形式系统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. 投影函数：投影函数的输出是其输入之一。

第9章树[离散数学离散数学(第四版)清华出版社]第二章一阶逻辑（Predicate Logic）1、一阶逻辑基本概念2、一阶逻辑公式及解释3、一阶逻辑等值式1、一阶逻辑基本概念前两节介绍的命题与命题演算是命题逻辑的内容，其基本组成单位是原子命题。

一般地，原子命题作为具有真假意义的句子至少由主语和谓语两部分组成。

例如，电子商务是计算机技术的一个应用系统，这里“电子商务”是主语，而“是……”是谓语。

当主语改变为“电子政务”时就得到新的原子命题：电子政务是计算机技术的一个应用系统。

由此可知，主语是独立存在的个体，而谓语用来描述该个体的性质或个体间的关系，这里我们称其为谓词。

用P表示谓词“是……”。

则P（电子商务）或P（电子政务）分别等值于前述两个命题的表达。

将个体用变量（称为个体变量）x推广，则P(x)表示：x是计算机技术的一个新的应用系统。

这时该语句就不是一个命题，而是一个命题函数。

DEFINITION 1.一个谓词P连同相关的n(n≥0)个个体变量组成的表达式称为n元谓词(n-predicate)，记P(x1, x2, …, x n)，其中n是该表达式中不同个体变量的数目。

EXAMPLE 1设P(x)表示语句“x > 3.”，则P(4)和P(2)的真值是多少?P(4) = 1P(2) = 0EXAMPLE 2设Q(x, y)表示语句“x = y + 3.”，则Q(1, 2) 和Q(3, 0)的真值是多少?Q(1,2) = 0Q(3,0) = 1EXAMPLE 3设R(x, y, z) 表示语句“x+y=z.”，则R(1, 2, 3) 和R(0, 0, 1) 的真值是多少?R(1, 2, 3)= 1R(0, 0, 1)= 0当n>1时，通常P给出了xi(i=1,2,…,n)之间的关系。

例如，P(x,y,z)表示x位于y与z之间，是一个三元谓词。

当x,y,z分别用赤道、南半球、北半球代入时，得到命题：赤道位于南半球与北半球之间，其真值为1。