离散数学习题选讲.pdfVIP

离散数学习题选讲 第 1 页 共 7 页 第一章 命题逻辑 1、将下列命题符号化，并讨论其真值。 （1）如果今天是 1 号，则明天是 2 号。 解：p →r ，其中：p ：今天是 1 号，r ：明天为2 号。 在这里，当p 为真时，r 一定为真，p →r 一定为真，且p 为假时，r 也为假，因而p →r 中不会出现前件为真，后件为假的情况，于是解：p →r 为真。 （2 ）如果今天是 1 号，则明天是 3 号。 解：p →r ，其中：p ：今天是 1 号，r ：明天为 3 号。 在这里，当p 为真时，r 一定为假，p →r 一定为假，当p 为假时，无论r 为真还是假，p →r 为真。 2 、一个排队线路，输入为 A ，B ，C，其输出分别为F ,F ,F 。在同一时间内只能有一个 A B C 信号通过，如果同时有两个或两个以上信号通过时，则按 A ，B ，C 的顺序输出。例如，A ， B ，C 同时输入时，只能A 有输出。写出F ,F ,F 的逻辑表达式，并化成全功能集{ ↓}中 A B C 的表达式。 解：设：p ：A 输入，q ：B 输入，r ：C 输入。 由题给的条件，容易写出F ,F ,F 的真值表，见下表所示。由真值表分别写出它们的主析 A B C 取范式，而后，将它们都化成与之等值的{ ↓}中的公式即可。 p q r FA FB FC 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 FA ⇔(p ∧¬q ∧¬r) ∨(p ∧¬q ∧r) ∨(p ∧q ∧¬r) ∨(p ∧q ∧r) ⇔(p ∧¬q) ∧(¬r ∨r) ∨(p ∧q) ∧(¬r ∨r) ⇔(p ∧¬q) ∨( p ∧q) ⇔p ∧(¬q ∨q) ⇔p ⇔¬¬(p ∨p ) ⇔¬(p ↓p ) ⇔(p ↓p ) ↓(p ↓p ) FB ⇔(¬p ∧q ∧¬r ) ∨(¬p ∧q ∧r) 离散数学习题选讲 第 2 页 共 7 页 ⇔(¬p ∧q) ∧(¬r ∨r) ( p q ) ⇔ ¬ ∧ ( ) ⇔¬¬¬ ∧ p q ⇔ ↓¬ p q p (q q) ⇔ ↓ ↓ FC ⇔(¬p ∧¬q ∧r) ⇔¬ ∨ ∧ (p q ) r ⇔ ↓ ∧ (p q ) r ⇔¬¬ ↓ ∧ ((p q ) r) ⇔¬¬ ↓ ∨¬ ( (p q ) r) ⇔¬ ↓ ↓¬ (p q ) r