当前位置：文档之家 › 离散数学第一章

离散数学第一章

  • 格式：ppt
  • 大小：2.70 MB
  • 文档页数：209

下载文档原格式

  / 209

合集下载

离散数学第一章 命题逻辑

离散数学第一章 命题逻辑

令Q表示：张亮是跳远运动员。
于是命题，张亮可能是跳高或跳远运动员就可以用P∨Q来表示，因为这里的或是可 兼或。 逻辑联结词析取也是个二元运算符。
1.1 命题和联结词
逻辑联结词单条件—“→”
设P是一个命题，Q是一个命题，由联结词→把P、Q连接成P→Q，称P→Q为P、 Q的条件式复合命题，把P和Q分别称为P→Q的前件和后件，或者前提和结论。 P→Q读作“如果P则Q”或“如果P那么Q”。其中P被称为前件，Q被称为为后件。 很多时候联结词→也被称为蕴涵。 P→Q的真值是这样定义的，当且仅当P→Q的前件P的真值为T，后件Q的真值为F
1.1 命题和联结词
逻辑联结词否定—“┓”
设P是一个命题，则联结词┓和命题P构成┓P，┓P为命题P的否定式复合 命题，读作“非P”。联结词┓是自然语言中的“非”、“不”和“没有” 等的逻辑抽象。 其真值是这样定义的，若P的真值是T，那么┓P的真值是F；若P的真值 是F，则┓P的真值是T。命题P与其否定┓P的如表1.1所示。
1.2 合式公式与真值表
例1.4 令P表示：小明现在正在睡觉。
令Q表示：小明现在正在打球。 于是命题，小明现在正在睡觉或者正在打球不能用P∨Q来表示。因为这里自然语言陈述的或是 排斥或，这种意义的或我们用另一个逻辑联结词“异或”“”来表示，后面我们将给出它的 定义。
1.1 命题和联结词
逻辑联结词析取——“∨”
例1.5 将句子“他昨晚做了20或者30道作业题”表示为复合命题。 在此例中，该句子不能被表示成复合命题，因为这里的“或”表示的是近似或者猜 测的意思。 例1.6 令P表示：张亮是跳高运动员。
P F F T T Q F T F T P∧Q F F F T P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1

离散数学第1章 命题逻辑

离散数学第1章 命题逻辑
P Q 原命题 P Q （P Q） 利用联结词组合起来
TT F
T
TF T
F
F P、Q真值相同时为F，否则为T
T 原命题与 (P Q)真值相同
FT T
F
T
(P Q)
FF F
T
F
总结：命题公式翻译的原则（即本质的东西）：
• 列出在各种指派下的原命题的取值。
• 翻译出来的公式如果与原命题的值一致，则翻译正确，否则， 翻译的公式则是错误的。
(4) 只有有限次地应用（1）、（2）、（3）所得的结果才是公式。
其中（1）为基础，（2），（3）为归纳，（4）为界限，这是一 个递归的定义。
例如：判别下列式子是否是公式？
(P Q) (PQ (P (P Q)) (P Q) (((P Q) R) (P Q)) (PQ R) (P Q)R)
(1)以离散量为研究对象，以讨论离散量的结构和相互之间的关 系为主要目标，这些对象一般是有限个或可数个元素，充分描述了 计算机科学离散性的特点，与我们以前学过的连续数学如高等数学、 数学分析、函数论形成了鲜明对比。
(2)它是数学中的一个分支，因而它有数学的味道，比如用一 些符号、引进一些 定义、运用定理推导等等。因而学习离散数学， 对提高我们的抽象能力，归纳能力、逻辑推理能力将有很大帮助。
（5）：我正在说谎。 若它是命题，则应有确定的真值。 若为T，则我确定说谎，我讲的是真话，与说谎矛盾。 若为F，则我不在说谎，我说的是真话，原命题成立，则“我 确实是在说谎” ，与“不在说谎”矛盾。 所以它不是命题，不能确定真假，是悖论。
1-1 命题及其表示法
（6）：X=3 不是命题 不能判断真假。
应用
Image segmentation

离散数学第一章数理逻辑

离散数学第一章数理逻辑
故命题可形式化为:(A∧B∧C) ↔ P
34
中北大学离散数学课程组
例3.他既聪明又用功。 例4.他虽聪明但不用功。 例5.除非你努力，否则你将失败。 例6.张三或李四都可以做这件事。
35
中北大学离散数学课程组
作业：
（1）判断下列公式哪些是合式公式，哪些不是合 式公式。
a.(Q→R∧S） b.(P ↔(R →S)) c.((┐P→Q)→(Q→P)) d.(RS→T) e.((P→(Q→R))→((P→Q)→(P→R)) （2）用符号形式写出下列命题。 a.假如上午不下雨，我去看电影，否则就在家里读
书或看报。
36
中北大学离散数学课程组
b.我今天进城，除非下雨。 c.仅当你走我将留下。
37
中北大学离散数学课程组
练习：将下列命题符号化。 1）说逻辑学枯燥无味（P）或毫无意义（Q）是不对的。 2）如果明天有雾（P），则我乘车（Q），不坐飞机（R）。 3）有雨（P）就刮风（Q）。 4）如果小王没来上课（P），一定是他生病了（Q）。 5）如果我上街（P），我就去图书馆看看（Q），除非我很累
2020/6/30
10
中北大学离散数学课程组
结论： 命题一定是陈述句，但并非一切陈述句都是命题。 命题的真值有时可明确给出，有时还需要依靠环境、 条件、实际情况时间才能确定其真值。
2020/6/30
11
中北大学离散数学课程组
二、命题的分类
1.原子命题(简单命题)：不能再分解为更为简单命 题的命题。
游； （5）两个三角形全等当且仅当三角形的三条边全部
相等。 (6) 张辉与王丽是同学。
2020/6/30
24
中北大学离散数学课程组
例 （解）

离散数学课件第一章(第1讲)

离散数学课件第一章(第1讲)

3)区分“可兼或”与“不可兼或（异或，排斥或）” 析取联结词为可兼或 例如： 灯泡有故障或开关有故障。 今天下雨或打雷。 以上例句均为可兼或。
“不可兼或”表示为：▽ (异或),当P和Q均为“T”时， 则P异或Q为“F”。
P
Q
P▽Q
F
F
F
F
T
T
T
F
T
T
T
F
例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。
§1 命题与命题联结词
1 命题
《定义》： 具有唯一值的陈述句叫命题。 讨论定义：
(1)命题的值： 命题值可以是真的，也可以是假的，但不能同时 既为真又为假。
(2)命题的真假值表示： 命题中所有的“真”用“Ｔ ” 或“ 1”表示 命题中所有的“假”用“Ｆ ”或 “0 ”表示。
(3)命题分类： ⅰ)原子命题：一个命题，不能分解成为更简单的命题。
(2) 合取词（“合取”、 “与”运算） 1) 符号 “Λ” 设Ｐ，Ｑ为两个命题，则ＰΛＱ称Ｐ与Ｑ的合取， 读作： “Ｐ与Ｑ” “Ｐ与Ｑ的合取” “Ｐ并且Ｑ”
2) 合取运算真值表
P Q PΛ Q
FF
F
FT
F
TF
F
TT
T
QΛP F F F T
注： ①当且仅当Ｐ和Ｑ的真值均为 Ｔ ，则ＰΛＱ 的真值 为 Ｔ 。否则，其真值为 Ｆ 。
第一篇 数理逻辑
逻辑：通常指人们思考问题，从某些已知条件出发推出合 理的结论的规律。 数理逻辑：用数学方法来研究推理的规律。包括命题逻辑 和谓词逻辑。 数理逻辑研究方法：采用一套数学的符号系统来描述和处 理思维的形式和规律。
第一章 命题逻辑
§1.命题与命题联结词 §2.命题公式与真值表 §3.命题公式的翻译 §4. 等价式与蕴含式 §5.对偶与范 式 §6.命题逻辑的推理理论 §7.其他联结词

离散数学课后习题答案(第一章)

离散数学课后习题答案(第一章)

（2）根据合式公式的定义，说明下列公式是合式公式。 a） ( A → ( A ∨ B )). A 是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。这个过程可以简记为：A；(A∨B)；(A→(A∨B)) 同理可记 b） ((¬A ∧ B) ∧ A). A；┓A ；(┓A∧B) ；((┓A∧B)∧A) c） ((¬A → B) → ( B → A)) A；┓A ；B；(┓A→B) ；(B→A) ；((┓A→B)→(B→A)) d） (( A → B ) ∨ ( B → A)). A；B；(A→B) ；(B→A) ；((A→B)∨(B→A)) （3）对下列公式用指定的公式进行代换。 a） ((( A → B ) → B ) → A), 用 ( A → C ) 代换 A ，用 (( B ∧ C ) → A) 代换 B
P: 你没有给我写信。 R: 信在途中丢失了。 ¬( P ↔ Q)
b) 如果张三和李四都不去，他就去。 P: 张三不去。Q: 李四不去。R: 他就去。 (P∧Q)→R c) 我们不能既划船又跑步。 P: 我们能划船。 Q: 我们能跑步。 ┓(P∧Q) d) 如果你来了，那么他唱不唱歌将看你是否伴奏。 P: 你来了。Q: 他唱歌。R: 你伴奏。 P→(Q↔R) （7）用符号形式写出下列命题。 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。(┓P→Q)∧(P→(R∨S)) b) 我今天进城，除非下雨。 P: 我今天进城。Q:天下雨。┓Q→P c) 仅当你走我将留下。 P: 你走了。 Q:我留下。Q→P 1-4 (7)证明下列等价式。 a) A → ( B → A) ⇔ ¬A → ( A → ¬B ) 证明： A→(B→A)⇔ ┐A∨(┐B∨A) ⇔ A∨(┐A∨┐B) ⇔ A∨(A→┐B) ⇔┐A→(A→┐B)

离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法

离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法

离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。

其它疑问句、祈使句、感叹句、悖论等皆不是。

详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。

特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。

B设出原子命题写出符号化公式。

详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。

详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。

②对每个指派，以二进制数从小到大或从大到小顺序列出。

③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。

详见P8。

6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A⇔B的充要条件是A⇒B且B⇒A。

主要等价式：(1)双否定：⎤⎤A⇔A。

(2)交换律：A∧B⇔B∧A，A∨B⇔B∨A，A↔B⇔B↔A。

3)结合律：(A∧B)∧C⇔A ∧(B∧C)，(A∨B)∨C⇔A∨(B∨C)，(A↔B)↔C⇔A↔(B↔C)。

(4) 分配律：A∧(B∨C)⇔(A∧B)∨(A∧C)，A∨(B∧C)⇔(A∨B)∧(A∨C)。

(5) 德·摩根律：⎤(A∧B)⎤⇔A∨⎤B，⎤(A∨B)⎤⇔A∧⎤B。

(6) 等幂律：A∧A⇔A，A∨A⇔A。

(7) 同一律：A∧T⇔A，A∨F⇔A。

(8) 零律：A∧F⇔F，A∨T⇔T。

(9) 吸收律：A∧(A∨B)⇔A，A∨(A∧B)⇔A。

(10) 互补律：A∧⎤A⇔F，(矛盾律)，A∨⎤A⇔T。

《离散数学》双语教学 第一章 真值表,逻辑和证明

《离散数学》双语教学第一章真值表，逻辑和证明《离散数学》双语教学第一章真值表，逻辑和证明CHAPTER 1TRUTH TABLES, LOGIC, AND PROOFSGlossarystatement, proposition:命题 logical connective:命题联结词compound statement:复合命题 propositional variable:命题变元negation:否定(式)truth table:真值表conjunction:合取 disjunction:析取 propositional function:命题公式fallacy: 谬误syllogism:三段论universal quantification:全称量词化 existential quantification:存在量词化 hypothesis(premise): 假设～前提～前件 conditional statement, implication:条件式～蕴涵式 consequent, conclusion:结论～后件 converse:逆命题contrapositive:逆否命题biconditional, equivalence:双条件式～等价(逻辑)等价的 logically equivalent:contingency:可满足式tautology:永真式(重言式)contradiction, absurdity:永假(矛盾)式 logically follow:是…的逻辑结论 argument:论证axioms:公理第 1 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明 postulate:公设rules of reference:推理规则modus ponens:肯定律 modus tollens:否定律reductio ad absurdum:归谬律proof by contradiction:反证法counterexample:反例 minterm:极小项disjunctive normal form:主析取范式maxterm:极大项conjunctive normal form:主合取范式第 2 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明本章内容及教学要点:1.1 Statements and Connectives教学内容:statements(propositions)～compound statement～connectives:negation～conjunction～disjunction～truth tables 1.2 Conditional Statements教学内容:implications(conditional statements)～biconditional～equivalent～and quantifications1.3 Equivalent Statements教学内容:logical equivalence～converse～inverse～contrapositive～tautology～contradiction(absurdity)～contingency～properties of logical connectives1.4 Axiomatic Systems: Arguments and Proofs教学内容:rules of reference～augument～valid argument～hypotheses～premises～law of detachment(modus ponens)～syllogism～modus tollens～addition～proof by contradiction 1.5 Normal Forms教学内容:minterm～disjunctive normal form～maxterm～conjunctive normal form定理证明及例题解答第 3 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明Logic, developed by Aristotle, has been used through the centuries in the development of many areas of learning including theology, philosophy, and mathematics. It is the foundation on which the whole structure of mathematics is built. Basically it is the science of reasoning, which may allow us to determine statements about mathematics whether are true or false based on a set of basic assumptions called axioms. Logic is also used in computer science to construct computer programs and to show that programs do what they are designed to do.逻辑学是研究人的思维形式的科学. 而数理逻辑是逻辑学的一个重要分支～是用数学形式化的方法研究思维规律的一门学科. 由于它使用了一套符号来简洁地表达出各种推理的逻辑关系～故它又称符号逻辑.数理逻辑用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系. 数理逻辑的主要内容:逻辑演算(L和L)、公理化集合论、模型论、S p构造主义与证明论. 数理逻辑在电子线路、机器证明、自动化系统、编译理论、算法设计方法方面有广泛的应用.The rules of logic specify the meaning of mathematicalstatements. Logic is the basis of all mathematical reasoning, and it has practical applications to the design of computing machines, to system specifications, to artificial intelligence(AI), to computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study.第 4 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明1.1 Statements and Connectivess(命题和联结词)命题逻辑研究的对象是命题及命题之间的逻辑关系.Propositions are the basic building blocks of logic. Many mathematical statements are constructed by combining one or more propositions.定义1.1.1 A proposition is a statement or declarative sentence that is either true or false, but not both,命题是一个非真即假的陈述句,.因此不能判断真假的陈述句、疑问句、祈使句和感叹句都不是命题.,1, The true or false value assigned to a statement is called its truth value; (一个命题的真或假称为命题的真值. 真用T或1表示～假用F或0表示),2, 一个陈述句有真值与是否知道它的真假是两回事.例1.1.1 判断下列语句是不是命题,若是～给出命题的真值: (1) 陕西师大不是一座工厂.(2) 你喜欢唱歌吗,(3) 给我一块钱吧:(4) 我不是陕西师大的学生.(5) 我正在说谎.Logical connectives(命题联结词)数理逻辑的特点是并不关心具体某个命题的真假～而是将逻辑推理变成类似数学演算的形式化过程, 关心的是命题之间的关联性. 因此需要进行命题符号化.命题联结词的作用是为了将简单命题组合成复合命题.We will now introduce the logical connectives that are used to form new propositions from existing propositions. And once truth values have been assigned to simple propositions, we can progress to more complicated compound statements.A statement that contains no connectives is called a simple第 5 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明statement. We will use p,q,r…to represent simple statements(简单命题就是简单陈述句～用字母p,q,r…(或带下标)表示),Sometimes, the letters p,q,r,s,…are used to denote propositional variables that can be replacedby statements(命题变元:可以用命题代替的变元).A statement that contains logical connectives(命题联结词) is called compound statements(复合命题). In general, a compound statement may have many component parts, each of which is itself a statement, represented by some propositional variable. The truth of a compound proposition is determined by the truth or falsity of the component parts.propositional constant(命题常元):T(1)或F(0)～或者表示一个确定的命题,propositional variable(命题变元):可用一个特定的命题取代。

东南大学离散数学第一章

– 王华的成绩很好并且品德很好 pq • p：王华的成绩很好 • q：王华的品德很好
计算机科学与工程学院
p q
F F F T T F T T
pq
F F F T
21
1.1 命题与联接词
析取联接词
– 符号,读作“析取”
定义：命题 p，q – p与q的析取式：复合命题“p或q” – 符号：pq(符号称作析取联结词) – pq为假当且仅当p和q同时为假 例子
数理逻辑提供了计算机科学与技术研究中的 重要工具与方法
计算机科学与工程学院
12
第一部分 数理逻辑
■ 主要内容 命题逻辑基本概念
命题逻辑等值演算
命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理
计算机科学与工程学院
13
第1章 命题逻辑基本概念 Propositional Logic
• 离散数学与数据库理论
数据库理论中的关系演算与关系模型需要用到谓词逻辑 关系数据库是行和列组成的二维表，表间的连接操作由笛卡尔积 理论支持 表的操作（查询、删除、修改）与关系代数和数理逻辑密切相关
计算机科学与工程学院
6
绪论：离散数学与计算机科学(续)
• 离散数学与人工智能
计算机智能化（推理）的前提——自然语言的符号化 语言符号化是数理逻辑研究的基本内容
– 自然数、整数，真假值，有限节点等
研究方法：推理、运算及实验等
计算机科学与工程学院
2
绪论：为什么要学习离散数学
计算机技术的支撑科学：计算机只能处理离散的或
离散化了的数量关系
培养离散思维与抽象思维能力 计算机专业课程学习的重要基础
培养理论研究和应用开发的离散建模能力

离散数学第一章知识点总结

离散数学第一章知识点总结离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等领域都有着广泛的应用。

第一章通常是对离散数学的基础概念和预备知识进行介绍，为后续的学习打下坚实的基础。

以下是对离散数学第一章知识点的详细总结。

一、集合的基本概念集合是由一些确定的、不同的对象所组成的整体。

集合中的对象称为元素。

我们通常用大写字母来表示集合，用小写字母表示元素。

如果一个元素 a 属于集合 A，记作 a ∈ A；如果一个元素 b 不属于集合 A，记作 b ∉ A。

集合有两种常见的表示方法：列举法和描述法。

列举法是将集合中的元素一一列举出来，例如 A ＝｛1, 2, 3, 4, 5}。

描述法是通过描述元素的共同特征来表示集合，例如 B ＝｛x ｜ x 是大于 0 小于 10 的整数}。

集合之间的关系包括子集、真子集和相等。

如果集合 A 中的所有元素都属于集合 B，那么 A 是 B 的子集，记作 A ⊆ B。

如果 A 是 B 的子集，且 B 中存在元素不属于 A，那么 A 是 B 的真子集，记作 A ⊂ B。

如果 A 和 B 包含相同的元素，那么 A 和 B 相等，记作 A ＝ B。

二、集合的运算集合的基本运算有并集、交集和差集。

集合 A 和集合 B 的并集，记作 A ∪ B，是由属于 A 或者属于 B 的所有元素组成的集合。

集合 A 和集合 B 的交集，记作A ∩ B，是由同时属于 A 和 B 的所有元素组成的集合。

集合 A 与集合 B 的差集，记作 A B，是由属于 A 但不属于 B 的所有元素组成的集合。

此外，还有补集的概念。

如果给定一个全集 U，集合 A 的补集记作A，是由属于 U 但不属于 A 的所有元素组成的集合。

集合运算满足一些重要的定律，如交换律、结合律、分配律等。

例如，A ∪ B ＝ B ∪ A（并集的交换律），A ∩ B ＝B ∩ A（交集的交换律），（A ∪ B) ∪ C ＝ A ∪（B ∪ C)（并集的结合律），（A ∩B) ∩ C ＝A ∩ （B ∩ C)（交集的结合律）等。

离散数学(同济大学)


读作“p与q”或“p合取q”。
是自然语言中的“并且”、
p
“既又”、“不但
F
而且”、“虽然但是”
F
、“一面一面”等的逻辑抽象。 T
T
q
pq
F
F
T
F
F
F
T
T
p：王化的成绩很好。
q：王化的品德很好。
p∧q： 王化不但成绩好而且品德好。
1.1 命题和命题联结词
3).析取词 命题p、q和 组成的复合命题记作p q,读作“p或q”。
p→q的逻辑关系为q是p的必要条件或p是q的充分条件。
1.1 命题和命题联结词
5).等价词 由命题p、q和 组成的复合命题记作p q,读作“p当且仅当q”。 是自然语言中的“充要条件”，“当且仅当”的逻辑抽象。
p q的逻辑关系为p与q互为充要条件
p
q
pq
例：1.3是有理数当且仅当加拿大位于亚洲。
,
p2
,,
p
的命题公式，
n
给p1 , p2 ,, pn一组确定的取值，称为对A的一组赋值或解释。 若指定的一组值使A的真值为1，则称其为A的成真赋值，否则
称为成假赋值。
1.2 命题公式及其赋值
定义4.将公式A在其全部赋值下的真值情况列成表， 称为A的真值表。
真值表的构造步骤： （1）若公式F共有（ n n 1)个变元，则真值表第一行写出
1.2 命题公式及其赋值
例（1）p q q r (2)r q p q p
(3) p q)
(4)r p (5) p r
同时约定：（1）最外层的括号可以省去。 （2）不影响运算次序的括号也可以省去。
1.2 命题公式及其赋值
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。