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

离散数学是计算机科学(编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、计算机网络等)、数学、数字电路、人工智能等多学科的共同语言和基础。本学期将讲授数理逻辑与图论个部分。
其中数理逻辑讲授命题逻辑、谓词逻辑两部分,分别由Boole于1847年和Frege于1879年建立。命题逻辑把简单命题作为基本单元进行推理演算;而谓词逻辑对简单命题进一步剖析,并考虑到变量数量的一般与个别。
前言
1
例1:在举重比赛中,有两名副裁判,一名主裁判。当两名以上裁判(必须包括主裁判在内)认为运动员举杠铃合格,按电钮,才裁决合格。试用与非门设计该电路。
解:设主裁判为变元A,副裁判分别为变元B和变元C;按电钮为1,不按为0。表示合格与否的灯为Y,合格为1,否则为0。
(1)根据逻辑要求列出真值表。
关于命题逻辑的两个有趣例子
2
真值表
3
(2)由真值表写出表达式:
(3)化简:
这个小例子涉及到简单命题、复合命题、逻辑联结词的定义、运算优先权、联结词的完备集(例如“与非联结词”构成一个完备集)等等。我们都将介绍到。
4
(4)画出逻辑电路图:
5
例2:设计一个楼上、楼下开关的控制逻辑电路来控制楼梯上的路灯。使之在上楼前,用楼下开关打开电灯,上楼后,用楼上开关关灭电灯;或者在下楼前,用楼上开关打开电灯,下楼后,用楼下开关关灭电灯。
解:
设楼上开关为变元A,楼下开关为变元B,灯泡为变元Y。并设A、B向上时为1,向下时为0;灯亮时Y为1,灯灭时Y为0。
6
本题的解题关键在于:不管开关和灯处于什么状态,灯的状态改变当且仅当只有一个开关的状态发生改变。因此,本题有多解。
(1)若A=0, B=0时Y=0,则相应真值表设计如下
7
相应逻辑表达式为
用异或门实现
8
(2)若A=0, B=0时Y=1,则相应真值表设计如下
相应逻辑表达式为
9
用同或门实现
10