命题逻辑基本概念1
- 格式：ppt
- 大小：988.06 KB
- 文档页数：48
下载文档原格式
合集下载
第2章 命题逻辑(1)
析取
符号
读作“析取”
定义2.3：设p，q为两命题，复合命题“p或q” 称为p与q的析取式，
记作p Ú q ，符号 称为析取联结词。并规定p q为假当且仅当p与q
同时为假。
真值表：
PQ 00
P Q
0
例子 小李是学数学或者计算
01
1
10
1
11
1
机科学pq p：小李是学数学 q：小李是学计算机 科学
2.1.1 命题与联结词
例3：判断下列命题是否为复合命题
（1）5能被2整除。
原子命题
（2）2是素数当且仅当三角形有三条边。 复合命题
（3）4是2的倍数或是3的倍数。
复合命题
（4）李明与王华是同学。
原子命题
（5）蓝色和黄色可以调配成绿色。
原子命题
（6）3不是偶数。
复合命题
（7）林芳学过英语或日语。
复合命题
合取
例：将下列命题符号化。
（1）吴颖既用功又聪明。
p q
（2）吴颖不仅用功而且聪明。
p q
（3）吴颖虽然聪明，但不用功。
p q
（4）张辉与王丽都是三好学生。
r s
（5）张辉与王丽是同学。
t
p:吴颖用功。
q:吴颖聪明。
r:张辉是三好学生。
s:王丽是三好学生。
t:张辉与王丽是同学。
注意：若“和”、“与”连接的是主语成分，则该陈述句为简单命题。
FT
T
F
F
补充：翻译语句
因为语言（包括一切人类语言）常有二义性，把 句子译成逻辑表达式可以消除歧义
把语言翻译成由命题变量和逻辑联接词组成的表 达式
第2章_1节-命题逻辑基本概念
定义2.4 设p，q为两个 命题“如果p，则q” 称作p与q的蕴涵式， 记作 pq，并称p是 蕴涵式的前件，q为蕴 涵式的后件，称蕴 涵联接词.其真值表为 ： p q pq 0 0 1 0 1 1 1 0 0 1 1 1
pq也可表示为： （1）只要p，就q； （2）因为p，所以q （3）p仅当q； （4）只有q，才p； （5）除非q，才平； （6）除q，否则非p； （7）假如没有q，就没有p.
离散数学
主讲教师：易静
1
2.1 命题逻辑基本概念
关键知识点： • 命题与真值 •联结词(¬ , , , , , ) •命题公式(重言式,矛盾式,可满足式) •重要等值式 •重要推理规则 •个体,个体域与谓词 •全称量词与存在量词
2
命题与真值
命题:所表达的判断是真（正确）或假（错误）但不能可 真可假的陈述句。通常用p,q,r等表示（即命题符号化） 命题的真值:作为命题所表达的判断只有两个结果：正确 和错误，此结果称为命题的真值。 命题是正确的，称此命题的真值为真；命题是错误 的，称此命题的真值为假。 在数理逻辑中，命题的真值的真和假，有时分别用 1和0来表达，也有时分别用T(True)和F(False)来表 达。本书用1和0来表达。（即真值的符号化） 真命题:真值为真的命题 假命题:真值为假的命题 例如, p:2+2=4, q:3是偶数 它们都是命题, p是真命题, q是假命题.
定义2.2 设p，q为二 命题，复合命题“p并 且q”（或“p与q”） 称为p与q的合取式， 记作pq，称作合取 联接词. 其真值表为：
p 0 0 1 1 q 0 1 0 1 pq 0 0 0 1
也可表示联接词： “既......,又.......”， “不但......而 且......”, “虽然......但 是.......”, “一面......一 面.......”等
命题逻辑的基本概念
命题逻辑的基本概念命题逻辑（propositional logic），又称命题演算，是数理逻辑的一个分支，它研究命题与命题之间的逻辑关系。
在命题逻辑中，命题是语句或陈述，可以判断为真或假。
命题逻辑的基础概念包括命题、联结词和复合命题等。
一、命题在命题逻辑中，命题是用来陈述某种事实或陈述的语句，可以判断为真或假。
命题通常用字母表示，如p、q、r等。
下面是一些例子：1. p：今天是晴天。
2. q：明天会下雨。
3. r：1+1=2。
二、联结词联结词是用来连接命题的词语，它们可以表示不同的逻辑关系。
常见的联结词有否定、合取、析取、条件、双条件等。
1. 否定（¬）：表示命题的否定，将命题的真值取反。
例如，¬p表示命题p的否定。
2. 合取（∧）：表示逻辑与的关系，表示两个命题都为真时，结果命题才为真。
例如，p∧q表示命题p和命题q都为真。
3. 析取（∨）：表示逻辑或的关系，表示两个命题中至少一个为真时，结果命题为真。
例如，p∨q表示命题p或命题q至少一个为真。
4. 条件（→）：表示逻辑蕴含的关系，表示命题p成立时，命题q也必定成立。
例如，p→q表示命题p蕴含命题q。
5. 双条件（↔）：表示逻辑等价的关系，表示命题p和命题q有相同的真值。
即当p和q同时为真或同时为假时，结果命题为真。
例如，p↔q表示命题p和命题q等价。
三、复合命题复合命题是由多个命题通过联结词构成的新命题。
复合命题的真假取决于其组成命题的真假以及联结词的逻辑关系。
例如：1. (p∧q)→r：表示命题p和命题q的合取蕴含命题r。
2. ¬(p∨q)：表示命题p和命题q的析取的否定。
3. p↔q∧r：表示命题p和命题q等价，并且命题r为真。
在命题逻辑中，通过运用联结词的组合和推理规则，可以进行逻辑推理和推断。
命题逻辑为我们提供了分析和解决复杂问题的思维工具。
总结：命题逻辑是数理逻辑的一个重要分支，研究命题与命题之间的逻辑关系。
1命题逻辑基本概念
6
东南大学
Introduction
Assume a very fast PC:
1 flop = 1 nanosecond = 10-9 sec. = 1,000,000,000 ops/sec = 1 GHz.
7
东南大学
Introduction
If n=8, T(n) = 7•8! = 282,240 flops < 1/3 sec. If n=50, T(n) = 49•50! = 1.48 1066 = 1.49 1057 seconds = 2.48 1055 minutes = 4.13 1053 hours = 1.72 1052 days = 2.46 1051 weeks = 4.73 1049 years.
定义1.1 设原子命题为p，则复合命题“p的否定” 或“非p”称为p的否定式。记做¬p，符号 ¬称 作否定联结词。规定¬p为真当且仅当p为假。
15
东南大学
1.1 命题与联结词
（２）严格由真值表定义 （３）举例： 北京是一座城市。 p 北京不是一座城市。 ¬p 每一种生物均是动物。 q 有一些生物不是动物。 ¬q 不是每一种生物均是动物。¬q 每一种生物均不是动物。 p ¬p T F F T
circuit design many other CS problems n cities c1, c2, . . . , cn distance between city i and j, dij
Given:
Find the shortest tour.
5
东南大学
Introduction
A tour requires n-1 additions. How many different tours?
东南大学
Introduction
Assume a very fast PC:
1 flop = 1 nanosecond = 10-9 sec. = 1,000,000,000 ops/sec = 1 GHz.
7
东南大学
Introduction
If n=8, T(n) = 7•8! = 282,240 flops < 1/3 sec. If n=50, T(n) = 49•50! = 1.48 1066 = 1.49 1057 seconds = 2.48 1055 minutes = 4.13 1053 hours = 1.72 1052 days = 2.46 1051 weeks = 4.73 1049 years.
定义1.1 设原子命题为p，则复合命题“p的否定” 或“非p”称为p的否定式。记做¬p，符号 ¬称 作否定联结词。规定¬p为真当且仅当p为假。
15
东南大学
1.1 命题与联结词
（２）严格由真值表定义 （３）举例： 北京是一座城市。 p 北京不是一座城市。 ¬p 每一种生物均是动物。 q 有一些生物不是动物。 ¬q 不是每一种生物均是动物。¬q 每一种生物均不是动物。 p ¬p T F F T
circuit design many other CS problems n cities c1, c2, . . . , cn distance between city i and j, dij
Given:
Find the shortest tour.
5
东南大学
Introduction
A tour requires n-1 additions. How many different tours?
命题的基本概念
指派
当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派。
本章小结
只有陈述句才有可能是命题，但并不是所有的陈述句都能成为命题。 本小节的思维形式注记图：
• 意味着P表示“今天下雨”这个命题的名。 • 也可用数字表示此命题 例如：[12]：今天下雨 表示命题的符号称为命题标识符，P和[12]就是命题标识符。
1.1.3 命题标识符
命题常元
一个命题标识符如果表示确定的简单命题，就称为命题常元。
命题变元
如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元。 因为命题变元可以表示任意简单命题，所以它不能确定真值，故命题变元不是命题。
命题
判断给定的句子是否为命题的基本步骤
首先应是陈述句； 其次要有唯一的真值。
68%
80%
Sed ut perspiciatis unde omnis.
Sed ut perspiciatis unde omnis.
180
175
案例
1）该吃早饭了！ 祈使句，不是命题。
2）多漂亮的花呀！ 感叹句，不是命题。
我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题。
5） x-y ＞2。
Sed ut perspiciatis
Sed ut perspiciatis
unde omnis.
unde omnis.
不是命题。因为x, y的值不确定，某些x, y使x−y＞2为真，某些x, y使x−y＞2为假，即
复合命题的基本性质是：其真值可以由其原子命题的真值以及它们复合成该复合
命题的联结方式确定。
1.1.3 命题标识符
命题标识符
• 为了能用数学的方法来研究命题之间的逻辑关系和推理，需要将命题符号化。 • 通常使用大写字母P, Q, R…或用带下标的大写字母或用数字，如Pi，[12]等表
当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派。
本章小结
只有陈述句才有可能是命题，但并不是所有的陈述句都能成为命题。 本小节的思维形式注记图：
• 意味着P表示“今天下雨”这个命题的名。 • 也可用数字表示此命题 例如：[12]：今天下雨 表示命题的符号称为命题标识符，P和[12]就是命题标识符。
1.1.3 命题标识符
命题常元
一个命题标识符如果表示确定的简单命题，就称为命题常元。
命题变元
如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元。 因为命题变元可以表示任意简单命题，所以它不能确定真值，故命题变元不是命题。
命题
判断给定的句子是否为命题的基本步骤
首先应是陈述句； 其次要有唯一的真值。
68%
80%
Sed ut perspiciatis unde omnis.
Sed ut perspiciatis unde omnis.
180
175
案例
1）该吃早饭了！ 祈使句，不是命题。
2）多漂亮的花呀！ 感叹句，不是命题。
我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题。
5） x-y ＞2。
Sed ut perspiciatis
Sed ut perspiciatis
unde omnis.
unde omnis.
不是命题。因为x, y的值不确定，某些x, y使x−y＞2为真，某些x, y使x−y＞2为假，即
复合命题的基本性质是：其真值可以由其原子命题的真值以及它们复合成该复合
命题的联结方式确定。
1.1.3 命题标识符
命题标识符
• 为了能用数学的方法来研究命题之间的逻辑关系和推理，需要将命题符号化。 • 通常使用大写字母P, Q, R…或用带下标的大写字母或用数字，如Pi，[12]等表
01命题基本概念及联接词
解：这9个句子中，（7）～（9）都不是陈述句， 因而都不是命题。 （1）是真命题，（2）是假命题。 （3）的真值虽然现在还不能判断，到2100年就能 判断了，因而是命题。 （4）在十进制中为假，在二进制中为真，当确定 了进位制时其真值就确定了，因而是命题。 （5）是命题，真值视具体情况惟一确定（不是真 就是假）。 （6）是陈述句，但无法给出真假值。这种自相矛 盾的判断称为悖论，以后再讲。
1.2.2 合取联结词∧
定义1.2.2 设P,Q为二命题，复合命题“P并且Q”（或 “ P 与 Q” ）称为 P 与 Q 的合取式，记作 P∧Q ，符号 “∧” 称为合取联结词 . P属于二元 ∧Q为真当且仅当 P和Q同时为真 . 说明：1、“∧” (binary)运算符 . 2、联结词“∧”的定义真值表如下：
从上述例子可以看出，原命题与逆否命题意思相同, 即等价：
P Q Q P
逆命题与反命题意思相同。 这一点非常重要，在推理过程中，有时按原命题进 行推导比较困难，而用逆否命题却可收到事半功倍 的效果。
1.2.5 双条件联结词（等价联结词）
定义1.2.5 设P,Q为二命题，复合命题“P当且仅当Q” 称为P与Q的双条件命题，记作P iff Q或PQ，符号 称为双条件（等价）联结词。PQ为真当且仅当
Q:今天天下雨。
定义1-3 如果一个命题标识符代表任意未知命题，则 称该命题标识符为命题变元（命题变项）.如果一 个命题标识符代表一个确定的命题，则称之为命 题常元。
命题变元类似代数中的变量，命题常元类似
常量，但两者有着本质的区别。命题变元或常元
代表的是命题元素，而变量和常量代表的是一个
数值。
例如，x+y≥ 5 这是一个代数表达式，其中x和y是 变量，不是命题变元，但该表达式也可以作为一 个命题变元。假设代表该表达式的命题变元为z， 当变量x和y的值确定后，表达式成为一个命题常 元，命题变元z被该命题常元所取代成为命题，且 命题的真值随变量x和y不同取值而变化。 当用确定的命题代入命题变元时称为对命题 变元的代入。
数理逻辑课件 第1节 命题逻辑的基本概念
符号化： p: 凡是偶数都能被2整除。 q: 6是偶数。 r: 6都能被2整除。 (pq)r 是永真式吗？
•35/49
练习1
1. 将下列命题符号化。 (1) 豆沙包是由面粉和红小豆做成的。 (2) 苹果树和梨树都是落叶乔木。 (3) 王小红或李大明是物理组成员。 (4) 王小红或李大明中的一人是物理组成员。 (5) 由于交通阻塞，他迟到了。 (6) 如果交通不阻塞，他就不会迟到。 (7) 他没迟到，所以交通没阻塞。 (8) 除非交通阻塞，否则他不会迟到。 (9) 他迟到当且仅当交通阻塞。
(5) 在自然语言中，“如果p，则q”，p, q具有某
种
内在联系；但在数理逻辑中， p, q可以无任•13/49
蕴涵联结词
(3) 当 p 为假时，pq恒为真，称为空证明 证明：空集是任意集合的子集。
•14/49
联结词的实例
例4 设 p:天冷，q:小王穿羽绒服，将下列命题符号化。
(1) 只要天冷，小王就穿羽绒服。
pq (5) p: 张辉与王丽是同学
(1)—(3) 说明描述合取式的灵活性与多样性 (既/又、不但/而且、虽然/但是、一面/一面等)
(4)—(5) 要求分清 “与” 所联结的成分 •9/49
联结词的实例
例3 将下列命题符号化。 (1) 2 或 4 是素数。 (2) 2 或 3 是素数。 (3) 4 或 6 是素数。 (4) 小元元只能拿一个苹果或一个梨。 (5) 王小红生于 1975 年或 1976 年。
定义2 设p,q为两个命题，复合命题“p并且q”(或 “p与 q”)称为p与q的合取式，记作p∧q，∧称作 合取联结词。 规定: p∧q为真当且仅当p与q同时为真。
定义3 设p, q为两个命题，复合命题“p或q”称作 p与q的析取式，记作p∨q，∨称作析取联结词。 规定: p∨q为假当且仅当p与q同时为假。
•35/49
练习1
1. 将下列命题符号化。 (1) 豆沙包是由面粉和红小豆做成的。 (2) 苹果树和梨树都是落叶乔木。 (3) 王小红或李大明是物理组成员。 (4) 王小红或李大明中的一人是物理组成员。 (5) 由于交通阻塞，他迟到了。 (6) 如果交通不阻塞，他就不会迟到。 (7) 他没迟到，所以交通没阻塞。 (8) 除非交通阻塞，否则他不会迟到。 (9) 他迟到当且仅当交通阻塞。
(5) 在自然语言中，“如果p，则q”，p, q具有某
种
内在联系；但在数理逻辑中， p, q可以无任•13/49
蕴涵联结词
(3) 当 p 为假时，pq恒为真，称为空证明 证明：空集是任意集合的子集。
•14/49
联结词的实例
例4 设 p:天冷，q:小王穿羽绒服，将下列命题符号化。
(1) 只要天冷，小王就穿羽绒服。
pq (5) p: 张辉与王丽是同学
(1)—(3) 说明描述合取式的灵活性与多样性 (既/又、不但/而且、虽然/但是、一面/一面等)
(4)—(5) 要求分清 “与” 所联结的成分 •9/49
联结词的实例
例3 将下列命题符号化。 (1) 2 或 4 是素数。 (2) 2 或 3 是素数。 (3) 4 或 6 是素数。 (4) 小元元只能拿一个苹果或一个梨。 (5) 王小红生于 1975 年或 1976 年。
定义2 设p,q为两个命题，复合命题“p并且q”(或 “p与 q”)称为p与q的合取式，记作p∧q，∧称作 合取联结词。 规定: p∧q为真当且仅当p与q同时为真。
定义3 设p, q为两个命题，复合命题“p或q”称作 p与q的析取式，记作p∨q，∨称作析取联结词。 规定: p∨q为假当且仅当p与q同时为假。
逻辑与命题的基本概念与性质知识点总结
逻辑与命题的基本概念与性质知识点总结逻辑与命题是逻辑学的两个重要概念。
逻辑是研究思维、推理和判断的科学，而命题是逻辑讨论的基本单位。
在本文中，我们将对逻辑与命题的基本概念与性质进行总结。
一、逻辑的基本概念逻辑是一门研究思维规律和正确推理的学科。
它研究了推理的形式和结构，以及推理过程中的误区和常见的谬误。
逻辑分为形式逻辑和实质逻辑两个方面。
形式逻辑研究命题和推理的结构，而实质逻辑则关注具体领域中的思维与推理。
逻辑学中的基本概念包括命题、命题联结词、真值表、逻辑等值式、推理形式等。
其中，命题是逻辑讨论的基本单位。
二、命题的基本概念与性质命题是陈述语句，可以判断为真或假的陈述。
命题的基本性质如下：1. 真值性：命题必然具有确定的真值，即真或假。
2. 独立性：命题的真值与其他命题的真值相互独立，互不影响。
3. 完整性：命题必然具有确定的真值，不存在不确定或模棱两可的情况。
4. 互斥性：命题的真值只能是真或假，不能同时为真和假。
5. 排中律：任何一个命题，必然为真或假中的一个，不存在中间值。
通过命题联结词，我们可以对多个命题进行组合，形成复合命题。
常见的命题联结词有“与”、“或”、“非”等。
三、逻辑运算与真值表逻辑运算是通过对命题进行合理的组合，形成复合命题并进行推理的过程。
根据不同的逻辑运算，可以得到命题之间的真值关系。
1. 与运算：当且仅当所有参与运算的命题都为真时，结果命题才为真。
用符号“∧”表示。
2. 或运算：当至少有一个参与运算的命题为真时，结果命题就为真。
用符号“∨”表示。
3. 非运算：对一个命题取反，真命题变为假，假命题变为真。
用符号“¬”表示。
4. 异或运算：当参与运算的命题真值不同的时候，结果命题为真；否则为假。
用符号“⊕”表示。
5. 条件运算：若p为真，q为假，则条件运算“若p，则q”为假；否则为真。
用符号“→”表示。
通过构建真值表，我们可以清楚地展示不同命题组合运算的结果。
1第一章 命题逻辑基本概念
如何将语句符号化, 以及如何理解符号化了的语句。 语句符号化要注意:
1. 要善于确定简单命题, 不要把一个概念硬拆成几个 概念。 例如“我和他是同学”是一个简单命题。 2. 要善于识别自然语言中的联结词 (有时它们被省略)。 例 1.11 狗急跳墙。
解 应理解为: p: 狗急了, q: 狗才跳墙
解 令 p: odd是奇数, q: odd2是奇数，
上述语句可表示为 p q。 6. 异或(exclusive or)连结词“” 【定义】 对于“排斥或”, 在数理逻辑中用联结词 “”表示, 称作“异或”。 当且仅当命题p和q的真值相异时, p q便取值为 真。
p q的真值表如表1.1.6所示。
1. 否定(negation)词“” 【定义 1.1】 设p是一个命题, 复合命题“非P‖(P的否 定)称为命题p的否定式, 记作“P‖, (读作“非p‖)。 命题p取值为真, 当且仅当命题P取值为假。 p的真值表如表1.1.1所示。 表.1.1 P 0 1 P 1 0
例 1.3 P：地球是圆的。 P：地球不是圆的。
p
0 0 1 1
表 1.6 q 0 1 0 1
pq 0 1 1 0
从定义可知联结词“”有以下性质： (1) p q = q p (2) (p q) r = p (q r) (3) p∧(q r) = (p∧q) (p∧r) (4) p q (p∧q)∨(p∧q) (5) p q (p q) (6) p p 0，p F P, p T P。
但不完全等同。
p∧q的真值表如表1.1.2所示。
表 1.2 p q 0 0 0 1 1 0 1 1
逻辑与命题的基本概念
逻辑与命题的基本概念逻辑是一门研究人类思维和推理方式的学科，它涉及到判断、推理、论证和推断等方面。
而命题则是逻辑研究的基本单位，是陈述句或者陈述式，可以判断真假的表达式。
本文将介绍逻辑与命题的基本概念，帮助读者了解逻辑思维的基本原理和命题的构成。
一、逻辑的基本概念逻辑是一种用以推理和论证的工具或方法。
它研究了人类思维的规律和逻辑推理的原则。
在逻辑学中，我们可以通过推理推导出新的结论，分析事物之间的关系，并判断有效的论证方式。
逻辑的基本概念包括：1. 真值：在逻辑中，我们用真（T）和假（F）来表示陈述句的真假。
真值是命题的核心特征，它描述了陈述句是否符合事实。
2. 推理：逻辑通过推理来从已知的命题中得出新的结论。
推理是一种从一组前提中推导出结论的方式，可以是演绎推理或归纳推理。
3. 命题：命题是陈述式，可以判断为真或假的陈述句。
命题可以是简单命题或复合命题，根据其结构和含义的不同，可以进行逻辑运算。
二、命题的基本概念命题是逻辑研究的基本单位，它可以判断为真或假，并且具有确定的真值。
命题的构成包括：1. 简单命题：也称为原子命题，它是不能再分解的陈述句，它可以是真或假。
例如：“今天是星期一”和“2加2等于4”。
2. 复合命题：由多个简单命题通过逻辑运算符（如与、或、非）组合而成的陈述句。
例如：“如果明天下雨，我就带伞；或者今天是晴天”。
3. 逻辑运算符：逻辑运算符用来连接或改变命题的真值。
常见的逻辑运算符有“与”（∧）、“或”（∨）和“非”（¬）等。
例如，命题“A∧B”表示A和B的交集。
三、逻辑与命题的关系逻辑与命题是密切相关的概念，逻辑是研究命题之间的关系和推理方式的学科。
逻辑通过命题和逻辑运算符的组合，分析命题之间的关联性，判断推理是否有效。
命题是逻辑的基本单位，是逻辑研究的对象。
在逻辑中，我们可以通过推理来判断命题的真假，从而得出结论。
通过运用逻辑思维，我们可以进行正确的论证和推理。
离散数学结构第1章命题逻辑基本概念
离散数学结构第1章命题逻辑基本概念第1章命题逻辑基本概念主要内容1. 命题与真值（或真假值）。
2. 简单命题与复合命题。
3. 联结词：否定联结词┐，合取联结词∧，析取联结词∨，蕴涵联结词→，等价联结词。
4. 命题公式（简称公式）。
5. 命题公式的层次和公式的赋值。
6. 真值表。
7. 公式的类型（重⾔式（或永真式），⽭盾式（或永假式），可满⾜式）。
学习要求1. 在5种联结词中，要特别注意蕴涵联结的应⽤，要弄清三个问题：① p→q的逻辑关系② p→q的真值③ p→q的灵活的叙述⽅法2. 写真值表要特别仔细认真，否则会出错误。
3. 深刻理解各联结词的逻辑含义。
4. 熟练地将复合命题符号化。
6. 会⽤真值表求公式的成真赋值和成假赋值。
1.1 命题与联结词 (2)⼀、命题的概念 (2)⼆、复合命题与联结词 (2)三、复合命题真假值 (5)1.2 命题公式及其赋值 (6)⼀、命题公式的定义 (6)⼆、公式的层次 (6)三、公式的赋值 (6)四、真值表 (7)五、公式的真假值分类 (8)1.1 命题与联结词⼀、命题的概念引⾔中的例⼦就是要对“我戴的是⿊帽⼦”进⾏判断。
这样的陈述句称为命题。
作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
真命题表达的判断正确，假命题表达的判断错误。
任何命题的真值都是唯⼀的。
判断给定句⼦是否为命题，应该分两步：⾸先判定它是否为陈述句，其次判断它是否有唯⼀的真值。
例1.1 判断下列句⼦是否为命题。
(1) 4是素数。
(2) 是⽆理数。
(3) x⼤于y。
(4) ⽉球上有冰。
(5) 2100年元旦是晴天。
(6) π⼤于吗？(7) 请不要吸烟！(8) 这朵花真美丽啊！(9) 我正在说假话。
解:本题的(9)个句⼦中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因⽽这3个句⼦都不是命题。
剩下的6个句⼦都是陈述句，但(3)⽆确定的真值，根据x,y的不同取值情况它可真可假，即⽆唯⼀的真值，因⽽不是命题。
离散数学 第1章 命题逻辑的基本概念
4. 蕴涵式与蕴涵联结词“→” 定义 1.4 设 p, q 为二命题，复合命题“如果 p, 则 q”称作 p 与 q 的 蕴涵式，记作 p→q，并称 p 是蕴涵式的前件，q 为蕴涵式的后件， →称作蕴涵联结词，并规定，p→q 为假当且仅当 p 为真 q 为假. 说明： （1）p→q 的逻辑关系：q 为 p 的必要条件 （2） “如果 p, 则 q 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或除非 q，否则非 p，…． （3）当 p 为假时，p→q 为真，可称为空证明 （4) 常出现的错误：不分充分与必要条件
3. 析取式与析取联结词“∨” 定义 1.3 设 p, q 为二命题，复合命题“p 或 q”称作 p 与 q 的析 取式，记作 p∨q，∨称作析取联结词，并规定 p∨q 为假当且仅 当 p 与 q 同时为假. 例 将下列命题符号化 （1）2 或 4 是素数. （2）2 或 3 是素数. （3）4 或 6 是素数. （4）小元元只能拿一个苹果或一个梨. （5）王小红生于 1975 年或 1976 年. （1）—（3）为相容或 （4）—（5）为排斥或 在符号化时（5）可有两种形式，而（4）则不能
离散数学
高等教育出版社
课程简介
• 离散数学是现代科学的一个重要分支。 离散数学是现代科学的一个重要分支。 • 离散数学的研究对象是离散量，一切以 离散数学的研究对象是离散量， 离散现象作为其研究对象或对象之一的数 学均称为离散数学， 学均称为离散数学，其研究各种各样的离 散量的结构及之间的关系。 散量的结构及之间的关系。 • 离散数学不仅在基础数学研究中具有极 其重要的地位，在其它如计算机科学、 其重要的地位，在其它如计算机科学、编 码和密码学、物理、化学、生物等学科中 码和密码学、物理、化学、 均有重要应用。 均有重要应用。
命题逻辑的基本概念
命题逻辑的基本概念第一节命题一、什么是命题命题是一个非真即假（不可兼）的陈述句。
有两层意思，首先命题是一个陈述句，而命令句、疑问句和感叹句都不是命题。
其次是说这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。
凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句。
这就是说，一个命题具有两种可能的取值（又称真值）为真或为假，又只能取其一。
通常用大写字母T表示真值为真，用F表示真值为假，有时也可分别用1和0表示它们。
因为只有两种取值，所以这样的命题逻辑称为二值逻辑。
我们把以这种非真必假的命题作为研究对象的逻辑称为古典逻辑，但也有人反对关于命题的这种观点，认为存在既不真也不假的命题，例如：直觉主义逻辑、多值逻辑等。
举例举例说明命题概念：1. "雪是白的"。
是一个陈述句，可决定真值，显然其真值为真，或说为T，所以是一个命题。
2. "雪是黑的"。
是一个陈述句，可决定真值，显然其真值为假，或说为F，所以是一个命题。
3. "好大的雪啊！"不是陈述句，不是命题。
4. "一个偶数可表示成两个素数之和"（哥德巴赫猜想）。
是命题，或为真或为假，只不过当今尚不知其是真命题还是假命题。
5. "1+101=110"。
这是一个数学表达式，相当于一个陈述句，可以叙述为"1加101等110"，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真。
可见这个命题的真值还与所讨论问题的范围有关。
举例举例：下列句子都是命题（1）8小于12。
（2）8大于12。
（3）21世纪末，人类将住在月球。
（4）任何一个大于5的偶数可表成两个素数的和。
（1）显然为命题，它陈述了一个事实。
（2）表示了一个错误的判断，故为假，又是一个陈述句，故为命题。
（3）也是命题，虽然现在还不知道真假，但到21世纪末，就能知其真假，故它是不为真必为假的一个陈述句，即为命题。
第1章 命题逻辑的基本概念
第1章
例题3
例3、一位父亲对儿子说：“如果我去书店，就 一 定给你买本《儿童画报》。”问：什么情况 下父亲食言？ 解：可能有四种情况： (1)父亲去了书店，给儿子买了《儿童画报》。 (2)父亲去了书店，却没给儿子买《儿童画报》。 (3)父亲没去书店，却给儿子买了《儿童画报》。 (4)父亲没去书店，也没给儿子买《儿童画报》。
第1章
等价
5、等价 由p、q和等价符号↔组成的式子(p↔q)称为p和q 的等价式。 p↔q为真当且仅当p、q真值相同。 真值表描述如下： 例：p：两圆面积相等 p↔q p q
0 0 1 1 0 1 0 1 1 0 0 1
q：两圆半径相等 两圆的面积相等当且仅当它 们的半径相当。 (p↔q)
第1章
第1章
例题4
例4、p：天下雨 q：我骑车上班 (1) 如果天不下雨，我就骑车上班。 ┐p→q (2)只要天不下雨，我就骑车上班。 ┐p→q (3)只有天不下雨，我才骑车上班。 q→┐p 或 p→┐q (4)除非天下雨，否则我就骑车上班。 ┐p→q (5)如果天下雨，我就不骑车上班。 p→┐q
第1章
0 0 1 1 0 1 0 1 0 1 1 1
q：小明学过法语 则小明学过英语或法语 表示为： (p∨q)
第1章
相容性或与排斥或
例、小明学过英语或法语 p：小明学过英语 q：小明学过法语 相容性或 表示为：p∨q 例、小明只能挑选计算机专业或物联网工程专业 p：小明选计算机专业 q：小明选物联网专业 排斥或 表示为：(p∧┐q)∨(┐p∧q) 例、小明是安徽人或河南人 p：小明是安徽人 q：小明是河南人 排斥或 表示为：(p∧┐q)∨(┐p∧q) p∨q
例5
例5、p：2＋2＝4 q：3是奇数 (1) 2+2=4当且仅当3是奇数。p↔q (2) 2+2=4当且仅当3不是奇数。p↔┐q (3) 2+2≠4当且仅当3是奇数。┐p↔q (4) 2+2≠4当且仅当3不是奇数。┐p↔┐q
逻辑与命题的基本概念
逻辑与命题的基本概念逻辑和命题是我们日常思维和语言表达中经常使用的概念。
了解它们的基本概念对于推理和论证的正确性至关重要。
本文将介绍逻辑和命题的基本概念，并探讨它们在我们日常生活中的运用。
一、逻辑的基本概念逻辑是研究人类思维和推理的学科。
它关注以合理性为目标的推理方式和论证过程。
逻辑主要研究推理规则、论证形式以及命题之间的关系。
在逻辑中，我们常常使用命题和论证来推导出结论。
二、命题的基本概念命题是陈述句或陈述句等价的表达方式，它可以被证明为真或假。
命题可以分为简单命题和复合命题。
1. 简单命题简单命题是不能再分解的命题，它只有两种可能的真值：真或假。
比如：“今天是星期天。
”这个陈述可以是真或假，取决于当天的实际情况。
2. 复合命题复合命题是由简单命题通过逻辑运算符（如“与”、“或”、“非”）组合而成的命题。
常见的逻辑运算符包括合取、析取和否定。
- 合取是指两个命题同时为真，整个复合命题才为真。
用符号“∧”表示。
例如，“今天是星期天∧明天是休息日。
”只有当这两个简单命题同时为真时，整个复合命题才为真。
- 析取是指两个命题中至少一个为真，整个复合命题就为真。
用符号“∨”表示。
例如，“今天是星期六∨明天是休息日。
”只要这两个简单命题中有一个为真，整个复合命题就为真。
- 否定是指命题的反面，其真值与原命题相反。
用符号“¬”表示。
例如，“今天不是星期六。
”这个命题的真值与“今天是星期六”的真值相反。
通过将不同的简单命题进行逻辑运算，我们可以形成各种复杂的命题，进而进行复杂的推理和论证。
三、逻辑与命题在日常生活中的运用1. 科学推理逻辑和命题在科学领域中发挥着重要的作用。
科学家们通过观察和实验，根据逻辑和命题的关系提出假设，然后通过推理和证据来验证这些假设。
逻辑的正确运用能够帮助科学家们建立准确、严谨的科学理论。
2. 法律推理逻辑和命题在法律领域也有广泛的应用。
在法庭上，律师通过逻辑和命题来构建合理的论证，为自己的观点辩护。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
p：4是素数。
q： x大于y。
P,q成了所表示命题的代表，其中p的值是0，q为命题变项。
例1.2
将下面这段陈述中所出现的原子命题符号化，并指出它 们的真值，然后再写出这段陈述。
2是有理数是不对的；2是偶素数；2或4是素数；如果2
是素数，则3也是素数；2是素数当且仅当3也是素数。
p： 2 是有理数 0
联结词
主要的五个联结词： 1. 否定联结词 2. 合取联结词 3. 析取联结词 4. 蕴涵联结词 5. 等价联结词
定义1.1 否定(negation)
设p为命题，复合命题“非p”(或“p 的否定”)称为p的否定式,记作┐p， 符号┐称作否定联结词，并规定┐p 为真当且仅当p为假。
p ┐p 10 01
例如：p： 哈尔滨是一个大城市。 ┐p：哈尔滨是一个不大城市。 ┐p：哈尔滨不是一个大城市。
定义1.2 合取(conjunction)
设p,q为二命题，复合命题“p
p
q
p∧q
并且q”(或“p与q”)称为p与q
1
1
1
的合取式，记作p∧q，∧称作
1
0
0
合取联结词，并规定p∧q为真
0
1
0
当且仅当p与q同时为真。
而定。 (6)不是，疑问句 (7)不是，祈使句 (8分为:
原子命题和复合命题
不能被分解成更简单的陈述句，称这 样的命题为简单命题或原子命题。
由简单陈述句通过联结词而成的陈述 句，称这样的命题为复合命题。
简单命题和真值的符号化
简单命题用小写英文字母p,q,r…,pi ,qi ,ri …表示命题 用“1”表示真，用“0”表示假
0
0
0
使用合取联结词时要注意的两点：
1) 描述合取式的灵活性与多样性。 自然语言中的“既……又……”、“不但……而且……”、 “虽然……但是……”、“一面……一面……”等联结词都 可以符号化为∧。
2) 分清简单命题与复合命题。 不要见到“与”或“和”就使用联结词∧。
例1.3 将下列命题符号化
(1)吴颖既用功又聪明。 (2)吴颖不仅用功而且聪明。 (3)吴颖虽然聪明，但不用功。 (4)张辉与王丽都是三好学生。 (5)张辉与王丽是同学。
说 明
在数理逻辑中，关心的只是复合命题与构成复合
命题的各原子命题之间的真值关系，即抽象的逻
辑关系，并不关心各语句的具体内容。
定义1.3 析取(disjunction)
设p，q为二命题，复合命题“p 或q”称作p与q的析取式，记作
p∨q，∨称作析取联结词，并
p 1
q
p∨q
1
1
规定p∨q为假当且仅当p与q同
q：2是素数；
1
r：2是偶数
1
s：3是素数；
1
t：4是素数
0
非p； q并且(与)r； q或t； 如果q，则s；
q当且仅当s。
例1.2的讨论
半形式化形式 数理逻辑研究方法的主要特征是将论述或推
理中的各种要素都符号化。即构造各种符号 语言来代替自然语言。 形式化语言：完全由符号所构成的语言。 将联结词（connective）符号化，消除其二义 性，对其进行严格定义。
1
0
1
0
1
1
时为假。
0
0
0
自然语言中的“或”具有二义性，用它联结的命 说 题有时具有相容性，有时具有排斥性，对应的联 明 结词分别称为相容或和排斥或(排异或)。
析取式p∨q 表示的是一种相容或
例1.4 将下列命题符号化
(1)张晓静爱唱歌或爱听音乐。 (2)张晓静只能挑选202或203房间。 (3)张晓静是江西人或安徽人。
1.1 命题符号化与联结词
称能判断真假的陈述句为命题 （proposition）。
作为命题的陈述句所表达得的判断结果称为命题的真值。 真值只取两个：真与假。 真值为真的命题称为真命题。 真值为假的命题称为假命题。
说 感叹句、疑问句、祈使句都不能称为命题。 明 判断结果不唯一确定的陈述句不是命题。
简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以 也称简单命题为命题常项或命题常元。
称真值可以变化的陈述句为命题变项或命题变元 。也用p,q,r,… 表示命题变项。
当p,q,r,…表示命题变项时，它们就成了取值0或1的变项，因而 命题变项已不是命题。
这样一来，p,q,r,…既可以表示命题常项，也可以表示命题变项 。在使用中，需要由上下文确定它们表示的是常项还是变项。
定义1.4 蕴涵(implication)
设p，q为二命题，复合命题“如果p，
p
则q”称作p与q的蕴涵式，记作p→q，
1
并称p是蕴涵式的前件，q为蕴涵式的
陈述句中的悖论不是命题。
例1.1 判断下列句子是否为命题。
(1)2是素数。
(2) 5是无理数
(3)x大于y。
(4)充分大的偶数等于两个 素数之和。
(5)明年10月1日是晴天。
(6)π大于 2吗？
(7)请不要吸烟！
(8)这朵花真美丽啊！
(9)我正在说假话。
(1)是，真命题 (2)是，真命题 (3)不是，无确定的真值 (4)是，真值客观存在 (5)是，真值根据具体情况
离散数学
第1章 命题逻辑
本章说明
本章的主要内容
– 命题、联结词 – 命题公式、命题公式的分类 – 等值演算 – 连接词全功能集 – 对偶与范式 – 推理理论 – 题例分析
1.1 命题符号化与联结词
数理逻辑研究的中心问题是推理。 推理的前提和结论都是表达判断的陈述句。 表达判断的陈述句构成了推理的基本单位。
(1)设 p：张晓静爱唱歌，q：张晓静爱听音乐。 相容或，符号化为 p∨q
(2)设t：张晓静挑选202房间， u：张晓静挑选203房间。 排斥或，符号化为：(t∧┐u)∨(┐t∧u)
(3)设r：张晓静是江西人， s：张晓静是安徽人。 排斥或，符号化为：r∨s。
(排斥或联结的两个命题事实上不可能同时为真) 或符号化为：(r∧┐s)∨(┐r∧s)
p: 吴颖用功。 q: 吴颖聪明。 r: 张辉是三好学生。 s: 王丽是三好学生。 t: 张辉与王丽是同学。
解题要点： 正确理解命题含义。 找出原子命题并符号化。 选择恰当的联结词。
(1)p∧q (2)p∧q (3)q∧┐p (4)r∧s (5)t
合取举例
p：我们去看电影。 q：房间里有十张桌子。 p∧q：我们去看电影并且房间里有十张桌子。