上海交通大学：《离散数学》课程教学资源（PPT课件）第二章 命题逻辑的等值和推理演算

第二章 命题逻辑的等值和推理演算

第二章 命题逻辑的等值和推理演算

关于命题逻辑的两个有趣例子 例1：在举重比赛中，有俩名副裁判，一名 主裁判。当两名以上裁判（必须包括主裁判 在内)认为运动员举杠铃合格，按电钮，才 裁决合格。试用与非门设计该电路。 解：设主裁判为变元A,副裁判分别为变元B 和变元C;按电钮为1，不按为0。表示合格 与否的灯为Y,合格为1，否则为0。 (1)根据逻辑要求列出真值表

例1：在举重比赛中，有俩名副裁判，一名 主裁判。当两名以上裁判（必须包括主裁判 在内）认为运动员举杠铃合格，按电钮，才 裁决合格。试用与非门设计该电路。 解：设主裁判为变元A，副裁判分别为变元B 和变元C；按电钮为1，不按为0。表示合格 与否的灯为Y，合格为1，否则为0。 （1）根据逻辑要求列出真值表。 关于命题逻辑的两个有趣例子

真值表 A B C Y AB C Y 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 011 0 111 1

A B C Y A B C Y 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 真 值 表

(2)由真值表写出表达式： Y=(AAB∧C)V(A∧B∧一C)V(A∧B∧C) (3)化简： Y=(A∧B)V(A∧C) =((AΛB)∧(AΛC) 这个小例子涉及到简单命题、复合命题、逻辑联结词 的定义、运算优先权、联结词的完备集（例如“与非联 结词”构成一个完备集)等等。我们都将介绍到

（2）由真值表写出表达式： Y  (A B C) (A B  C) (A B C) （3）化简： Y  (A B) (AC)  ((A B)(AC)) 这个小例子涉及到简单命题、复合命题、逻辑联结词 的定义、运算优先权、联结词的完备集(例如“与非联 结词”构成一个完备集)等等。我们都将介绍到

(4)画出逻辑电路图： A & B & Ao & C

（4）画出逻辑电路图： A B A C Y & & &

例2：设计一个楼上、楼下开关的控制逻辑电 路来控制楼梯上的路灯。使之在上楼前，用楼 下开关打开电灯，上楼后，用楼上开关关灭电 灯；或者在下楼前，用楼上开关打开电灯，下 楼后，用楼下开关关灭电灯。 解： 设楼上开关为变元A,楼下开关为变元B,灯 泡为变元Y。并设A、B向上时为1，向下时为0 ;灯亮时Y为1，灯灭时Y为0

例2：设计一个楼上、楼下开关的控制逻辑电 路来控制楼梯上的路灯。使之在上楼前，用楼 下开关打开电灯，上楼后，用楼上开关关灭电 灯；或者在下楼前，用楼上开关打开电灯，下 楼后，用楼下开关关灭电灯。 解： 设楼上开关为变元A，楼下开关为变元B，灯 泡为变元Y。并设A、B向上时为1，向下时为0 ；灯亮时Y为1，灯灭时Y为0

本题的解题关键在于：不管开关和灯处 于什么状态，灯的状态改变当且仅当只 有一个开关的状态发生改变。因此，本 题有多解。 (1)若A=0,B=O时Y=0,则相应真值表设计如下 B 0 1 1 0 1 0

本题的解题关键在于：不管开关和灯处 于什么状态，灯的状态改变当且仅当只 有一个开关的状态发生改变。因此，本 题有多解。 （1）若A=0, B=0时Y=0，则相应真值表设计如下

相应逻辑表达式为 Y=(A∧B)V(A∧B) 用异或门实现 A =1 B

相应逻辑表达式为 Y  (A B) (A B) A B =1 Y 用异或门实现

第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基 本内容 推理过程是从前提出发，根据所规定的规 则来推导出结论的过程 重言式是重要的逻辑规律，正确的推理形 式，等值式都是重言式

第二章 命题逻辑的等值和推理演算 n 推理形式和推理演算是数理逻辑研究的基 本内容 n 推理过程是从前提出发，根据所规定的规 则来推导出结论的过程 n 重言式是重要的逻辑规律，正确的推理形 式，等值式都是重言式

本章对命题等值和推理演算进行讨论，是 以语义的观点进行的非形式的描述，不仅 直观且容易理解，也便于实际问题的逻辑 描述和推理 严格的形式化的讨论见第三章所建立的公 理系统

n 本章对命题等值和推理演算进行讨论，是 以语义的观点进行的非形式的描述，不仅 直观且容易理解，也便于实际问题的逻辑 描述和推理。 n 严格的形式化的讨论见第三章所建立的公 理系统