当前位置：文档之家 › 命题逻辑1

命题逻辑1

  • 格式：ppt
  • 大小：1.13 MB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

第一章 命题逻辑

第一章 命题逻辑
定义 5 ：设 P, Q 是两个命题，复合命题 “ P 当且 仅当 Q ”称为 P 与 Q 的等价式，记为 P↔Q。符号 ↔称为双条件联结词。
规定： P↔Q 为真当且仅当 P 与 Q 同时为真或同时 为假。
注：P↔Q 可理解为“Q与P互为充分必要条件”； 它与(P→Q)∧(Q→P)的逻辑关系完全一致。
例 符号化：（1）张伟不是三好学生; 解：记 P：张伟是三好学生。 则: (1) ┐P ； (2) ┐Q . （2） 2 不是有理数 。 Q： 2 是有理数。
第一章
命题逻辑
1.2 联结词
定义2 ：设 P , Q 为两个命题。复合命题“ P 与Q” 即“P 并 且Q” 称为 P 与 Q 的合取式，记为 P ∧ Q。符号∧称为合取联 结词。 规定： P ∧ Q为真当且仅当 P 与Q 同时为真。 注：自然语言中 “与”, “和”, “且”, “既.…又…”, “不仅…而 且…”, “虽然…但是…”, “一面…一面…”等联结词都可以符号 化为∧； 但并不是所有的“与”、“和”等都能用联结词∧替代。
例2 考虑来人是华佗，他能治疗关羽的箭伤这 样一个历史事件。 显然，来人如果是华佗为前提，他（=来 人）能治疗关羽的箭伤是结论。 抽象来看：当前提为真时，可以推出结论为真 上述两个看似不相关的实例说明了一个共 同的问题：推理问题，这就是我们要研究的。 抽象成数理逻辑语言表达方式： 如果A 蕴涵 B，现又有A，则可以推导出B。
(5) 是原子命题,符号化为T: 张辉和王丽是同学。
第一章
命题逻辑
1.2 联结词
定义3 ：设 P , Q 为两个命题 , 复合命题 “ P 或 Q ” 称 为 P 与 Q 的析取式, 记为 P∨Q。符号∨称为析取联结词。 规定： P∨Q 为假当且仅当 P 与 Q 同时为假。 注: 自然语言中的 “或” 联结的两个命题可以具有相容性， 也可以具有排斥性。

逻辑一

逻辑一

A.陈蕃救助过赵欣 C.王玥救助过陈蕃 E.王玥没救助过李佳
B.王玥救助过李佳 D.陈蕃救助过李佳
10
2.排序
甘蓝比菠菜更有营养，但是，因为绿芥兰比莴 苣更有营养，所以甘蓝比莴苣更有营养。 以下各项，作为新的前提分别加入到题干的前 提中，都能是题干的推理成立，除了: A.甘蓝与绿芥兰同样有营养。 B.菠菜比莴苣更有营养。 C.菠菜比绿芥兰更有营养。 D.菠菜与绿芥兰同样有营养。 E.绿芥兰比甘蓝更有营养。
41
7.一个产品要畅销，产品的质量和经销商的诚 信缺一不可。以下各项都符合题干的断定，除 了： A.一个产品滞销说明它或者质量不好，或者经 销商缺乏诚信。 B.一个产品只有质量高并且诚信经销才能畅销。 C.一个产品畅销说明它质量高并有诚信的经销 商。 D.一个产品除非有高的质量和诚信的经销商， 否则不能畅销。 E.一个质量好并且由诚信者经销的产品不一定 畅销。
A .只有I和II D.只有II B.只有I C.只有I和III E. I. II和III
6
2.矛盾（负命题）
1.并非张三看了所有的比赛。 2.并非有同学看了所有的比赛。 3.并非在所有的季节所有的城市都会下雪。 4.并非不到长城的人都不是好汉。
5.并非不来的同学都是懒惰的。
7
3.真假话推理 例：甲、乙、丙、丁是某辅导班的同学。 甲说：“我班同学都通过了MBA联考。” 乙说：“丁没通过MBA联考。” 丙说：“我班有人没通过MBA联考。” 丁说：“乙也没通过MBA联考。” 已知只有一个人说假话，则可推出以下哪项断定 是真的？ A.说假话的是甲，乙没通过联考。 B.说假话的是乙，丙没通过联考。 C.说假话的是丙，丁没通过联考。 D.说假话的是丁，乙没通过联考。 E.说假话的是甲，丙没通过联考。

逻辑学：命题逻辑

逻辑学：命题逻辑
2018年8月17日星期五 7
第二章 命题逻辑
第二节 复合命题及其推理
负命题
负命题由否定联结词(如“并非”)联结支命题而形成的复合命 题。例如： (1)并非选修逻辑的学生都是文科生。 (2)这个班的学生不都学英语。 (3)如果它是三角形，则内角和等于180°，这个观点不对。 注：负命题的支命题可以是简单命题，也可以是复合命题。
20语句
任何命题都是通过语句来表达的，但语句和命题并非一一对应：
首先，有的语句不能直接表达命题，如： •（1）西南大学在重庆吗? •（2）请把门关上！ 一般来讲：陈述句与反诘句可以直接表达命题。 其次，同一命题可以用不同的语句来表达，如： “所有的鸟都会飞”与“没有鸟不会飞”表达了相同的命题。 此外，同一命题可用不同的民族语言的语句来表达。 再次，同一语句，可以表达不同的命题，如： 小张将书还给小王，因为他要回家了。
真值表的作用
•p •T •F •¬p F T
根据这个真值表，也可以给f(p)=p这个一元真值函数作如下定义： p为真当且仅当p为假； p为假当且仅当p为真。
2018年8月17日星期五
10
负命题
根据负命题的逻辑性质，可对¬p再否定得到¬¬p，其真值与 p相同，真值表如下：
•p •T •F •¬p •F •T •¬¬p •T •F
2018年8月17日星期五 4
命题的分类
简单命题
非模态命题 命 题
模态命题 复合命题
2018年8月17日星期五
5
命题分析的层次
将联结词所联结的命题作为一个完整的单位来看待
•
•
——研究关于联结词的推理(命题逻辑)
——研究关于量项和联项的推理(传统词项逻辑)

第1章 命题逻辑要点

第1章 命题逻辑要点

第1章 命题逻辑1、会判断一个语句是否为命题（如P31-习题1.1题） 练习：判断下列语句是否为命题。

(1).3+8=13； (2).离散数学是计算机系的一门必修课； (3).太阳系以外的星球上有生物；(4).你打算考硕士研究生吗？ (5).9+5≤12 ；(6). 天上有三个月亮。

(7).x+5 > 6；(8).一定要努力学习！ (9).2是素数； (10).x+5 > 6； (11).我正在说谎；(12).x=13. (13).这朵花多好看呀！(14).7能被2整除. (15).我用的计算机CPU 主频是1G 吗？(16).蓝色和黄色可以调成绿色；(17). 雪是黑色的. (18). 明天会下雨吗？； (19).我能进来吗？ (20).这个男孩真勇敢呀！ (21).蓝色和黄色可以调成绿色； (22).x ≤3； (23)地球饶着太阳转.(24)青年人多么朝气蓬发呀！ (25).5能被2整除.(26).嫦娥一号太棒了！ (27).台湾是中国的一部分； (29) 你下午有会吗？若无会，请到我这儿来！(30).请不要讲话！ (31) 5是奇数； (32).032>+x2、注意五个命题联结词的使用，会将命题进行符号化（如P32-1.3，1.4，1.5题的题型）或在判断体现逻辑联结词的逻辑有关系等。

练习：将以下命题符号化(1)如果你不去逛街，那么我也不去逛街。

(2)小李边吃饭边看电视。

(3)林芳学过英语或日语。

(4)张辉与王丽都是三好生. (5)小王住在101室或102室。

(6).2+2≠4当且仅当王红没努力学习离散数学。

(7)4或6是素数.(8).王晓聪明，但是他不用功.(9)如果今天是1号，则明天是5号。

(10).小潘不能既跳舞又唱歌。

(11)如果你来了，他就唱歌而且陪你跳舞。

(12).或者雪是黑色的，或者太阳从东方升起。

(13).王晓既用功又聪明。

(14)2 + 2 ≠ 4 当且仅当美国位于非洲。

第 1 章 命题逻辑

第 1 章 命题逻辑

第 1 章命题逻辑数理逻辑是用数学方法研究思维规律和推理过程的科学，而推理的基本要素是命题，因此命题逻辑是数理逻辑最基本的研究内容之一，也是谓词逻辑的基础。

由于数理逻辑使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，一般又称之为符号逻辑。

数理逻辑和电子计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计、逻辑电路、开关理论等计算机应用和理论研究提供了必要的理论基础。

一、命题与命题变量在日常生活中，人们不仅使用语句描述一些客观事物和现象，陈述某些历史和现实事件，而且往往还要对陈述的事实加以判断，从而辨其真假。

语句可以分为疑问句、祈使句、感叹句与陈述句等，其中只有陈述句能分辨真假，其他类型的语句无所谓真假。

在数理逻辑中，我们把每个能分辨真假的陈述句称作为一个命题。

陈述句的这种真或假性质称之为真值或值，这就是说真值包含“真”和“假”。

因而命题有两个基本特征，一是它必须为陈述句：二是它所陈述的事情要么成立(真)，要么不成立(假)，不可能同时既成立又不成立，即它的真值是惟一的。

命题可按其真值分为两类。

若一个命题是真的，则称其真值为真，用1或T表示，称该命题为真命题；若一个命题是假的，则称其真值为假，用0或F表示，称该命题为假命题。

命题还可根据其复杂程度分类。

只是由一个主语和一个谓语构成的最简单的陈述句，称为简单命题或原子命题或原始命题。

简单命题不可能再分解成更简单的命题了，它是基本的，原始的。

当然，也有一些命题并不是最基本的，它们还可以分解成若干个简单命题。

由若干个简单命题通过联结词复合而成的更为复杂的新命题称为复合命题或分子命题。

复合命题仍为陈述句。

任意有限个简单或复合命题，还可用若干不同的联结词复合成极为复杂的复合命题。

简单命题和复合命题的真值是固定不变的，故又可称为命题常量或命题常元，简称为命题。

而有些陈述句尽管不是命题，但可以将其变成命题，它的真值是不固定的、可变的，这种真值可变化的陈述句称为命题变量或命题变元。

《离散数学》命题逻辑

《离散数学》命题逻辑
由原子命题组合而成的命题称为复合 命题（compound proposition）。
例如：
和 e 都是无理数。 6和8至少有一个是合数。 说刘老师讲课不好是不正确的。 不下雨我就去买书。
7
命题与命题联结词
将命题连接起来的方式叫做命题联结词
（ proposition connective ） 或 命 题 运 算 符
3
命题与命题联结词
逻辑
如何表示？ 如何“操作”？
非真即假的陈述句称为命题（proposition）。 一个命题如果是对的或正确的，则称为真命
题，其真值为“真”（true），常用T或1表示； 一个命题如果是错的或不正确的，则称为假
命题，其真值为“假”（false），常用F或0表示。
4
命题与命题联结词
32
命题公式及其分类
为简化公式的形式，作如下规定：
(1) 优先级 , (∧, ∨), (, ) (2) 公式 (~p) 的括号可以省略，写成 ~p (3) 整个公式最外层的括号可以省略
例1
(((p)∧q)(q∨p)) p∧q q∨p
例2
p∧q∨r 不是 命题公式 应写作 (p∧q)∨r 或 p∧(q∨r)
例 判断下列句子哪些是命题，哪些不是
这门课程题为“离散数学”。 这门“离散数学”讲得好吗？ X 这门“离散数学”讲得真好！ X 请学习“离散数学” 。 X 5是素数。 太阳从西方升起。 如果明天晴，而且我有空，我就去踢球。 天王星上没有生命。 x + 3 > 5。 X 5 本命题是假的。X
俞伯牙和钟子期是好朋友。 俞伯牙是好朋友 ∧ 钟子期是好朋友 俞伯牙 ∧ 钟子期是好朋友 Friend (俞伯牙,钟子期)
23

数理逻辑课件 第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同时为假。

第一章 命题逻辑基本概念

第一部分 数理逻辑
传统逻辑与数理逻辑： 传统逻辑与数理逻辑： 逻辑一词源于希腊文，意思指： 逻辑一词源于希腊文，意思指：词、思 想、理性、规律等。 理性、规律等。 逻辑学研究的是：判别一个推理过程是 逻辑学研究的是： 否正确的标准。数理逻辑也叫符号逻辑， 否正确的标准。数理逻辑也叫符号逻辑，即 用人工符号来书写逻辑法则， 用人工符号来书写逻辑法则，它是一门涉及 数学、逻辑学、 数学、逻辑学、哲学等几门学科的横向交叉 学科。 学科。
数理逻辑是用数学方法来研究推理的 形式结构和推理规律的数学学科， 形式结构和推理规律的数学学科，它与数 学的其它分支、计算机科学、人工智能、 学的其它分支、计算机科学、人工智能、 语言学等学科均有密切的联系。 语言学等学科均有密切的联系。命题逻辑 一阶谓词逻辑是数理逻辑中最成熟的部 和一阶谓词逻辑是数理逻辑中最成熟的部 在计算机科学中应用最为广泛， 分，在计算机科学中应用最为广泛，其中 命题逻辑是数理逻辑的最基础部分， 命题逻辑是数理逻辑的最基础部分，谓词 逻辑是在它的基础上发展起来的。 逻辑是在它的基础上发展起来的。
将下列命题符号化： 例 将下列命题符号化： 吴颖既用功又聪明。 （1）吴颖既用功又聪明。 吴颖不仅用功而且聪明。 （2）吴颖不仅用功而且聪明。 吴颖虽然聪明，但不用功。 （3）吴颖虽然聪明，但不用功。 张辉与王丽都是三好生。 （4）张辉与王丽都是三好生。 张辉与王丽是同学。 （5）张辉与王丽是同学。 （1）-（3）说明描述合取式的灵活性与多样性 ）（ ） （4）-（5）要求分清联结词“与”联结的复合 ） （ ）要求分清联结词“ 命题与简单命题
一、主要内容
命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理理论
二、学习要求 深刻理解命题、 联结词、 深刻理解命题 、 联结词 、 复合命 命题公式、 等值式、 题 、 命题公式 、 等值式 、 等值演 算、推理及证明等概念 熟练进行等值演算与构造证明

命题逻辑



逻辑形式表示为： 要么p，要么q 非p —————— 所以，q 水涨船高
p⊙q ¬p ——— ∴q

（2）肯定否定式。 肯定否定式不相容选言推理，就是在小前 提中肯定选言命题的一个选言支，在结论 中否定其他的选言支。
第三节 假言命题及其推理

某人的死要么是正常死亡，要么是非正常死亡， 某人的死是正常死亡， ————————————————————— 所以，某人的死不是非正常死亡。 逻辑形式可以表示为：
pⅴq pⅴq
T F
T
T
T F
F
F T
F
T T
F
的问题 1、选言支必须穷尽 如果选言支不穷尽，则可能遗漏惟一为真的事物 情况。而如果选言支穷尽，则事物的一切情况都 包括无遗，其中必有取值为真的选言支，从而保 证整个选言命题为真。 如果需要限定，就一定要有说明，否则，人们就 会以穷尽一切选言支的选言命题来对待。
1）看联结词 2）看复合命题与支命题之间的真假关系（联言命 题必须在所有的支命题都为真时才成立，而相容 选言命题只要有一个支命题为真就可以成立）


有一块矿石，让甲乙丙三位同学辨认。甲说： “这不是铁，也不是铅。”乙说：“这不是铁， 而是铜。”丙说：“这不是铜，而是铁。”已知， 这三位同学中，有一个人都猜对了，有一个人都 猜错了，有一个人只猜对一半。 问：根据这些条件，下列哪词是真的？ A．这块矿石是铁矿。 B．这块矿石是铜矿。 C．这块矿石是铅矿。 D．这块矿石是锡矿。 E．这块矿石是银矿。

2、联言命题的逻辑性质：当且仅当所有支 命题为真，则该联言命题为真。 3、联言命题的基本形式：分解式联言推理； 组合式联言推理

1）分解式联言推理；组合式联言推理 联言推理的分解式就是前提为联言命题， 结论是其支命题的联言推理形式。

第二章 命题逻辑[2010](1)

选言支可以同时为真 2. 简单推理： 简单推理： • • • 否定肯定式 添加式 无效式
（二）不相容选言命题
• 不相容选言命题是断定两种事物情况中有且只 有一种情况成立的选言命题。 有一种情况成立的选言命题。 • 或为玉碎，或为瓦全。 或为玉碎，或为瓦全。 • 今天不是星期一，就是星期二。 今天不是星期一，就是星期二。 • 任一个自然数或者是偶数，或者是奇数。 任一个自然数或者是偶数，或者是奇数。
• • • • • • •
并非：并不是，…不成立，…是假的，…不符 并不是， 不成立， 是假的， 并不是 合事实，等等。 合事实，等等。 并且：和；然后；不但，而且；虽然，但是； 和 然后；不但，而且；虽然，但是； 不仅， 等等。 不仅，还；等等。 或者：要么，要么；二者必居其一；等。 要么，要么；二者必居其一； 要么 要么：或者；要么，要么；二者必居其一；等。 或者；要么，要么；二者必居其一； 或者 如果，则：假如，就；倘若，便；只要，就； 假如， 假如 倘若， 只要， 哪怕， 就算， 哪怕，也；就算，也；当…时；等。 只有，才：除非，才；除非，不；不，就不； 除非， 除非 除非， 就不； 仅当， 等等。 仅当，才；等等。 当且仅当：如果…则…并且只有…才…，如 如果… 如果 并且只有… 并且如果非…则非… 等等。 果…则…并且如果非…则非…，等等。
约定： 约定：
• 整个公式外面的括号可以省略； 整个公式外面的括号可以省略； • 各联结词的结合力依下列次序递减： 各联结词的结合力依下列次序递减：
¬；∧；∨；→；↔
• 连续的“→”从后向前结合。 连续的“→”从后向前结合。 从后向前结合
（一）逻辑性质
• 联言命题是判定几种事物同时存在的复合命题 • 只有他的各个联言支都是真的，它本身才是真的 只有他的各个联言支都是真的， 如果由一个支命题为假，则联言命题为假。 ；如果由一个支命题为假，则联言命题为假。 • p∧q
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3. 命题公式
命题公式是由0、1、命题常元、命题变元以及命题 联结词、括号等组成的符号串。 定义 （命题公式的递归定义）
（1） 0，1，命题常元是命题公式； （2） 命题变元是命题公式； （3） 如果A是命题公式，则¬ A是命题公式； （4） 如果A和B是命题公式，则（A∨B）， （A∧B）,(A→B）,(A↔ B）也是命题公式； 有限次地利用上述（1）—（4）而产生的符号串是命题公式， 又称为合式公式，简称公式。
命题逻辑
命题符号化 命题公式的赋值 公式的等值
命题逻辑推理理论
公式的标准形式
1.1 命题符号化
命题相关概念 联结词 命题符号化
1.1 命题符号化
一、 命题(statement)的概念
命题：是能判断真假的陈述句。 命题的真值：作为命题的陈述句所表达的判断结果。 真值只取两个值：真(1)或假(0) 真命题：真值为真的命题。 假命题：真值为假的命题。 判断给定句子是否为命题分两步： 1、判定它是否为陈述句 2、判断它是否有唯一的真值
要学好这门课程，首先必须充分认识到这门课程的 上述特点，需要做到以下几点： 1、注重课堂效率，熟读教材。准确理解各个概念和定理 的含义（结合多个例子来理解），必要的推理过程要看懂、 理解（它可以帮助你熟悉和深刻理解定理的含义）。 2、独立思考，做好习题。仅靠熟读教材并不能将书上的 知识变成你自己的知识，在熟读教材的基础上，必须通 过大量练习，独立思考来真正获取知识。 3、注重抽象思维能力的训练。数学与其他学科相比较具 有较高的抽象性，而离散数学的抽象性特点更为显著，它 有着大量抽象的概念和抽象的推理，要学好这门课程必须 具有较好的抽象思维能力，才能深入地掌握课程内容。
p 0 0 1 1 q 0 1 0 1 p∧q 0 0 0 1
说明：
1、“既……又……”、“不但……而且……”、“虽 然……但是……”、“一面……一面……”等联结而成 的复合命题一般符号化为合取式。 2、命题中出现“与”、“和”不一定就用∧联结词。
பைடு நூலகம்
合取联结词
例 将下列命题符号化 李平既聪明又用功 李平虽然聪明但不用功 李平不但聪明而且用功 李平不是不聪明而是不用功 李文和李武是兄弟 王芳和陈兰都是好学生 兰色和黄色可以调成绿色 兰色和黄色都是常用颜色 小李一边吃苹果一边看电视 p∧q p ∧ ┐q p∧q ┐ ┐ p ∧ ┐q r p∧q s p∧q p∧q
例
用符号形式表示下列命题
（1）我们不能既划船又跑步。 （2）如果你来了，那么他唱不唱歌将看你是否伴奏而定。 （3）假如上午不下雨，我去看电影，下雨就在家里看书。
（4）如果晚上做完了作业并且没有其它的事，他就会 看电视或听音乐。
解 （1） ¬ (p∧q） （2） p→（q↔r） （3）（¬p → q）∧（p→r） （4）（p∧¬ q）→（r∨s）
0 0 1 1 0 1 0 1 1 1 0 1
说明：
1、自然语言里 ，“只要p, 就q”, “因为p, 所以q”, “p仅当q”,
“只有q才p”, “除非q才p”, “除非q, 否则非p” 等叙述方式都应 符号化为p→q 。 2、在数理逻辑中, p与q可以无任何内在联系 。
蕴涵联结词
例 将下列命题符号化 只要不下雨，我就骑车上班。 只有不下雨，我才骑车上班。 如果3+3＝6, 则雪是白的。 因为下雨了，所以我不骑车上班。 除非下雨，否则我骑车上班。 4是偶数仅当5是奇数。 只有4是偶数，5才是奇数。 除非 4是偶数，否则5不是奇数。 ┐p → q q → ┐p p→q p → ┐q ┐p → q 或 ┐q → p p→q q → p或 ┐ p → ┐q
定义 设p为命题, 复合命题“非p”(或“p的否定”) 称为p的否定式,记作┐p, 符号┐称作否定联结词
P 1
0
¬ P 0
1
例 设p：上海是一个城市；
q：每个自然数都是偶数。
则 ¬ p：上海不是一个城市; ¬ q：并非每个自然数都是偶数。
合取联结词(conjunction)
定义 设p,q为二命题, 复合命题“p并且q”(或 “p与q”)称为p与q的合取式, 记作p∧q, ∧ 称作合取联结词。
三、命题符号化
利用联结词可以把许多日常语句符号化，基本 步骤如下： 1、从语句中分析出各原子命题，将它们符号化； 2、使用合适的命题联结词，把原子命题逐个联结起 来，组成复合命题的符号化表示。
例
（1） （2） （3） （4） 用符号形式表示下列命题 如果明天早上下雨或下雪，那么我不去学校。 如果明天早上不下雨且不下雪，那么我去学校。 如果明天早上不是雨夹雪，那么我去学校。 只有当明天早上不下雨且不下雪时，我才去学校。
命题联结词
以上定义了五种最基本、最常用、也是 最重要的联结词┐, ∧, ∨, →, ↔ , 将它们组 成一个集合{┐, ∧, ∨, →, ↔}, 称为一个联 结词集。其中┐为一元联结词, 其余的都是 二元联结词。 联结词可以嵌套使用, 在嵌套使用时, 规 定如下优先顺序： ( ), ┐, ∧, ∨, →, ↔, 对 于同一优先级的联结词, 先出现者先运算。
张晓静爱唱歌或爱听音乐
张静只能挑选202或203房间 王平要么选修法语要么选修德语 小米是湖南人或湖北人 解： p∨q (t∧┐u)∨(┐t∧u) (p∧┐q)∨(┐p∧q) p∨q 或(p∧┐q)∨(┐p∧q)
蕴涵联结词(implication)
定义 设p, q为二命题,复合命题“如果p, 则q” 称作p与q的蕴涵式, 记作p→q, →称作蕴涵 联结词。称p是蕴涵式的前件，称q是蕴涵 式的后件。 p q p→q
第一部分
数理逻辑
数理逻辑是用数学方法研究思维规律的一门学科。 所谓数学方法是指:用一套数学的符号系统来描述和处理 思维的形式与规律。因此, 数理逻辑又称为符号逻辑。数 理逻辑和计算机的发展有着密切的联系，为机器证明、 自动程序设计、逻辑电路等计算机应用和理论研究提供 了必要的理论基础。 德国的哲学家和数学家莱布尼茨被认为是数理逻辑 的创始人，他提出表意的符号语言和思维演算的思想。 从17世纪70年代莱布尼茨数理逻辑思想的提出，一 直到19世纪末20世纪初，由于德国的弗雷德、英国的罗 素等人的工作，逻辑演算得以建立，这是数理逻辑的基 础，也就是离散数学中要介绍的命题逻辑和谓词逻辑。
例 判断下列语句是否是命题 （1）空气是人生存所必需的。 （2）请把门关上。 （3）南京是中国的首都。 （4）你吃饭了吗？ （5）x=3。 （6）啊，真美呀！ （7）明年春节是个大晴天。 （8）这句话是假话。
著名的理发师悖论——理发师给不给自己刮胡子
“我只给那些不给自己刮胡子的人刮胡子！”
二、逻辑联结词(logical connectives)
析取联结词(disjunction)
定义 设p,q为二命题, 复合命题“p或q”称为p 与q的析取式, 记作p∨ q, ∨称作析取联结词。
p 0 0 1 1 q 0 1 0 1 p∨q 0 1 1 1
说明：
自然语言中的“或”具有二义性，用它联结的 命题在符号化时要区分相容或和排斥或。
析取联结词
例 将下列命题符号化
二、离散数学课程的特点
离散数学课程是应计算机科学和技术发 展的需要，综合了现代数学的多个分支而形 成的。其特点是以离散量为研究对象，内容 丰富，涉及面较宽。因此概念多、定理多、 推理多并且内容较为抽象。但由于它是为学 生后继专业知识的学习做必要的数学准备， 因此它研究的内容均比较基础。
三、如何学好离散数学
3. 《离散数学》 孙吉贵等编 高等教育出版社
4. 《离散数学学习指导与习题解答》孙吉贵等 育出版社 5. 《离散数学学练考》王海艳 清华大学出版社 高等教
6. 《离散数学——习题与解析》胡新启等 版社
清华大学出
7. 《离散数学》 姜泽渠等编 重庆大学出版社
六
教学要求
1. 准备好课堂笔记本，记录课堂进度，做好课堂 练习。 2. 作业使用统一的单页纸书写，于下次课前由学 委收齐后交上来。 3. 上课迟到以旷课论, 缺勤达到一定次数不得参 加期末考试。 4. 作业未按时交或非独立完成，一次扣除平时成 绩5分。
离散数学
distinct mathematics
主讲教师
姚 敏
E-mail:371698479@
课 程 说 明
一、离散数学课程的地位和作用
离散数学是现代数学的重要分支，是研究离散 量的结构及相互关系的学科，在计算机理论研究及 软、硬件开发的各个领域都有着广泛的应用，是计 算机科学与技术专业的一门核心基础课程。
1、离散数学为计算机专业的后继课程如数据结构、操作系 统、数据库原理、编译原理、网络和算法设计、人工智能等 课程提供必要的数学基础。 2、通过该课程的学习可以提高学生的抽象思维、严格的逻 辑推理以及综合归纳分析能力。 3、为学生今后从事计算机科学和技术理论研究，软、硬件 开发和应用提供有力的工具，增强学生使用离散数学知识分 析问题与解决实际问题的能力。
等价联结词(equivalence)
定义 设p, q为二命题,复合命题“p当且仅当q” 称作p与q的等价式, 记作p ↔ q, 称作等价 联结词。
p 0 0 1 1 q 0 1 0 1 p↔q 1 0 0 1
命题符号化练习：
1、经一事长一智，不经一事不长一智。 2、黄山比喜马拉雅山高，当且仅当3是素数。
例
(┐p∧q)→r, (┐(p→┐q))∧((r∨s) ↔ ┐p)分别为3层和4层公式
二、公式的赋值
简单命题(原子命题)：简单的陈述句。 观察下面例子： 1、李力既是三好学生又是足球队员。 2、张平或者正在钓鱼或者正在睡觉。 3、如果明天天气晴朗，那么我们举行运动会。 4、12不是素数。 复合命题(compound statement)：由一个或几 个原子命题通过联结词联结而成的命题。