编译原理数据结构、操作系统、数据库系统、算法的分析与设计PPT课件

用异或门实现
A
=1
Y
B
2020年9月28日
8
（2）若A=0, B=0时Y=1，则相应真值表设计如下
AB
Y
00
1
01
0
10
0
11
1
相应逻辑表达式为
2020年9月28日
Y ( A B ) (A B )
9
用同或门实现
A
=1
Y
B
2020年9月28日
10
第1章 命题逻辑的基本概念
内容：命题逻辑研究的是命题的推理演 算．这一章介绍命题逻辑的基本概念，包括 引入命题联结词，讨论合式公式、重言式以 及自然语句的形式化等内容．
2020年9月28日
1
关于命题逻辑的两个有趣例子
例1：在举重比赛中，有两名副裁判，一名 主裁判。当两名以上裁判（必须包括主裁判 在内）认为运动员举杠铃合格，按电钮，才 裁决合格。试用与非门设计该电路。
解：设主裁判为变元A，副裁判分别为变元B 和变元C；按电钮为1，不按为0。表示合格 与否的灯为Y，合格为1，否则为0。
命题逻辑与谓词逻辑区别：命题逻辑中将简单命 题作为一个不可分的整体来看待．在谓词逻辑里， 才对命题中的主谓结构进行深入分析．
2020年9月28日
15
复合命题定义：把一个或几个简单命题用 联结词(如与、或、非)联结所构成的新的 命题称为复合命题．
复合命题真值判断：复合命题自然也是陈 述句，其真值依赖于构成该复合命题的各 简单命题的真值以及联结词，如“张三学 英语和李四学日语”就是一个复合命题，
否定词的运算规则真值表：
2020年9月28日
19
P P TF
FT
真值表描述了命题 之间的真值关系， 很直观。
2020年9月28日
6
本题的解题关键在于：不管开关和灯处 于什么状态，灯的状态改变当且仅当只 有一个开关的状态发生改变。因此，本 题有多解。
（1）若A=0, B=0时Y=0，则相应真值表设计如下
AB
Y
00
0
01
1
10
1
2020年9月28日
11
0
7
相应逻辑表达式为
Y ( A B ) (A B )
2020年9月28日
14
简单命题和复合命题
简单命题定义：简单命题又称原子命题，它是不 包含任何的与、或、非一类联结词的命题．如 1．1．1中例子．这样的命题不可再分割，如再 分割就不是命题了．而像命题“雪是白的而且l+l ＝2”，就不是简单命题，它可以分割为“雪是白 的”以及“1十1＝2”两个简单命题，联结词是 “而且”．
2020年9月28日
13
命题变项
命题变项定义：约定用大写字母表示命题， 如以P表示“雪是白的”，Q表示“北京是中国 的首都”等．当P表示任一命题时，P就称为命题 变项(变元)．
命题与命题变项区别：命题与命题变项含义 是不同的，命题指具体的陈述句，是有确定的真 值，而命题变项的真值不定，只当将某个具体命 题代入命题变项时，命题变项化为命题，方可确 定其真值，命题与命题变项像数学中常量与变量 的关系一样．在不混淆的情况下，逻辑演算中不 再区分它们了。
2020年9月28日
17
命题联结词及真值表
联结词可将命题联结起来构成复杂的命题， 从而使命题逻辑的内容变得丰富起来。
值得注意的是逻辑联结词与日常自然用语 中的有关联结词的共同点和不同点．
2020年9月28日
18
常用的逻辑联结词
1. 否定词
称谓、读法、记号：否定词“ ”是个 一元联结词，亦称否定符号，读作非。 一个命题P加上否定词就形成了一个新的 命题，记作 P。
(1)“雪是白的”是命题，真值为真 (2)“雪是黑的”是命题．真值为假 (3)“好大的雪啊”不是陈述句，不是命题． (4)“一个偶数可表示成两个素数之和” ．是命题，
不知真值． (5)“1+101＝110”．是命题，这个句子所表达的内
容在十进制范围中真值为假，而在二进制范围中 真值为真．可见，这个命题的真值与所讨论问题 的范围(论域)有关．
2020年9月28日
11
命题逻辑的基本概念
命题定义：命题是一个非真即假(不可兼)的陈 述句．有两层意思，首先命题是一个陈述句， 其次真假不可兼．
命题的取值称为真值 ． 通常用T表示真值为真，用F表示真值为假．因
为只有两种取值，所以这样的命题逻辑称为二 值逻辑．
2020年9月28日
12
举例说明
5
例2：设计一个楼上、楼下开关的控制逻辑电 路来控制楼梯上的路灯。使之在上楼前，Байду номын сангаас楼 下开关打开电灯，上楼后，用楼上开关关灭电 灯；或者在下楼前，用楼上开关打开电灯，下 楼后，用楼下开关关灭电灯。
解：
设楼上开关为变元A，楼下开关为变元B，灯 泡为变元Y。并设A、B向上时为1，向下时为0 ；灯亮时Y为1，灯灭时Y为0。
由简单命题“张三学英语” “李四学日
语”经联结词“和”联结而成，这两个简
单命题真值均为真时，该复合命题方为
真．
2020年9月28日
16
数理逻辑关心什么？不关心内容：这些具 体的陈述句的真值究竟为什么是真还是假。 关心形式：关心的仅是命题可以被赋予真 或假这样的可能性，以及规定了真值后怎 样与其他命题发生联系．
前言
离散数学是计算机科学(编译原理、数据结构、操 作系统、数据库系统、算法的分析与设计、计算 机网络等 )、数学、数字电路、人工智能等多学 科的共同语言和基础。本学期将讲授数理逻辑与图论个部分。
其中数理逻辑讲授命题逻辑、谓词逻辑两部分， 分别由Boole于1847年和Frege于1879年建立。命 题逻辑把简单命题作为基本单元进行推理演算； 而谓词逻辑对简单命题进一步剖析，并考虑到变 量数量的一般与个别。
（1）根据逻辑要求列出真值表。
2020年9月28日
2
真 值表
ABC Y ABC Y
000 0 100 0
001 0 101 1
010 0 110 1
011 0 111 1
2020年9月28日
3
（2）由真值表写出表达式：
Y ( A B C ) ( A B C ) ( A B C )
（3）化简：
Y(A B ) (A C ) ( (A B ) (A C ))
这个小例子涉及到简单命题、复合命题、逻辑联结词 的定义、运算优先权、联结词的完备集(例如“与非联 结词”构成一个完备集)等等。我们都将介绍到。
2020年9月28日
4
（4）画出逻辑电路图：
A
&
B
&
Y
A &
C
2020年9月28日