1-1-5 习 题
1．将下列公式化为析取范式和合取范式： （1） P?(Q?R?S); （3）(P?Q)?R
（2）?(P??Q)?(S?T); （4） (?P?Q)?(P??Q);
（5）(?P??Q)?(P??Q);
（6） (P?(Q?R))?(?P?(?Q??R));
2. 用两种方法将上题中各公式的主合取范式与主析取范式求出来。 3．重言式和矛盾式的主合取范式和主析取范式是什么？ 4．用化为范式的方法判断下列公式是否等价： (1)(P?Q)?P?Q, (?P?Q)?(Q?P); （2）(P?Q)?(P?R), P?Q?R.
5．判断下列公式是重言式还是矛盾式（化为范式）： （1） (A?B?C)?(?A?(?B??C)); （2） A?(A?B?A); （3） (B?A)?(?A?B); （4） (?A??B)?(A??B).
6．从A，B，C，D四个人中派二人出差，要求符合以下条件：若A去为必需C，D中去一人B，C不能同去，若C去为D必须留下，问如何派去。
7．A，B，C，D四个队参加足球比赛，有三个球迷预测比赛结果，第一人认为“A第一，B第二”，第二人认为“C第二，D第四”，第三人认为“A第二，D第四”，结果三人都对了一半，问四个队的名次如何。
§1-1-6 其它逻辑联结词
§1-1-1中已将常用的逻辑联结词的符号意义和作用作了讲叙，并指出了应该注意的地方。本节将对计算机设计，开关理论，电子元件中常用的逻辑联结词和另一些基本的逻辑联结词进行讨论。
定义 1-1-6.1 由命题公式P和Q产生的新命题P?Q称为P和Q的不可
36
兼或，其真值表为
P 1 1 0 0 Q 1 0 1 0 P?Q 0 1 1 1
P 1 1 0 0 Q 1 0 1 0 P?Q 0 1 1 0
不可兼或已在1-1-1中举过实际例子。“”有下列基本等价式： (1) P?Q?Q?P； (2) (P?Q)?R?P?(Q?R)；
(3) P? (Q?R)? (P?Q)?(P?R)； (4) P?Q? (P??Q)?(?P?Q)； (5) P?Q??(P?Q)；
(6) P?P?F , P?F?P , P?T??P 。 以上等价式可以用真值表法加以证明。
定义 1-1-6.2 由命题公式P和Q产生的新命题公式P?Q与P?Q分别称为P和Q的“与非”与“或非”，其真值表分别为
P 1 1 0 0 Q 1 0 1 0 P?Q 0 0 0 1 “?”和“?”有如下等价式，最基本的为：
（1） P?P??(P?P)??P ； （2）(P?Q)?(P?Q)??(P?Q)? P?Q ；
（3）(P?P)?(Q?Q)??P??Q??(?P??Q)? P?Q ； （4） P? P?? (P?P)??P ； （5）(P?Q)?(P?Q)??(P?Q)?P?Q ；
（6）(P?P)?(Q?Q)??P??Q??(?P??Q)?P?Q。 由§1-1-5的对偶概念和定理知“?”与“?”互为对偶。 例1-1-6.1 A=P?(Q??(R? P))，求A* 。 解： A* =P?(Q??(R?P))。
例1-1-6.2 A= (A?B)?(B?B)，求A*
37
解： A* =((A?B)?(B?B))*
=((?A?B)?(B?B))* =(?A?B)?(B?B)。
命题是能判别真假的陈述句，即是说命题的值只有两个：真（1），假（0）。这是二值逻辑。而各种电的机械的器件常常考虑两种可能的状态，如开、关；通过、不通过；传导、不传导；啮合、不啮合；顺时针方向、逆时针方向等等，现在加以推广，即通过的不仅是电，机械物，各种液体，也可以是信息，?。因此将上述开关等术语统一称为“门”，逻辑联结词?，?，?，?，?，? 分别称为非门，与门，或门，异或门，与非门，或非门，涉及到的原子命题变元真值指派称为输入,逻辑连结词产生的公式在真值指派下运算的结果称为输出.在理论和实际设计中为了便于讨论,对上述各种”门”采用下列图示标号:
非门 P ?P
与非门 P P?Q
Q
Q
与门 P P?Q
Q 或门 P P?Q
或非门 ： P P?Q Q
P
异或门 Q P?Q
P
Q
上面的各种门(组件)可以按图示互相连结,恰当地选取就能实现所要求的逻辑表达式(命题公式),经过联结后的“门”图称为逻辑网络(组合网络)。
由于一个命题公式可以有多个等价的表达式，因如形成逻辑网络的方式也就不同，对生产和维护来说，需要考虑设计的技巧，使用单一种类的门常常比使用多种类型的门或使用较少的门比使用较多的门要方便或便宜些，有时也常利用对偶性使一个门即可作与非门有又可作或非门用,这些设计思想在大规模集成电路中已经采用。
例1-1-6.3 某仓库装有一个警报系统,它只在保卫部门的一个人工控制开关关闭时进行工作。当此人工开关关闭时，如果通到设施范围内的禁区的门有盗贼进入，或者保卫人员还没有关闭一个专门开关时，设施的主要出入口就已
38
打开。则报警器鸣响。设计此控制线路。
解: 令 A：警报器鸣响，B：关闭人工控制开关，C：设施的主要出入口打开，D:禁区的门有盗贼进入，E:专门开关关闭。
则 A=B?(D?(?E?C))
故控制线路图
E C D B A 例1-1-6.4 一家航空公司，为了保证安全，用三台计算机同时复核飞行计划是否正确。由计算机所给的答案，根据少数服从多数的原则作出计划是否正确的判断，试画出逻辑网络。
解：设P，Q，R表示3台计算机，C表示判断结果，由题设得真值表如下：
P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 C 1 1 1 0 1 0 0 0
据1-1-5.4定理得
C=(P?Q?R)?(P?Q??R)?(P??Q?R)?(?P?Q?R)
?(P?Q?R)?(P?Q??R)?(P??Q?R)?(P?Q?R)?(P?Q?R)?(?P?Q?R) ?((P?Q)?(R??R))?((P?R)?(Q??Q))?((Q?R)?(P??P)) ?((P?Q)?T)?((P?R)?T)?((Q?R)?T) ?(P?Q)?(P?R)?(Q?R) 故逻辑网络为
P Q
C
R 39
除了上述常用的逻辑联结词：?，?，?，?，?，?，?，?以外，还
?c??”（或记为???，称为条件否定），其真值表为 有逻辑联结词“?P 1 1 0 0 Q 1 0 1 0 P?Q 0 1 0 0 c
????实际是?与?复合而成，故不在作讨论。
1-1-6 习 题
1．用真值表验证“?”的基本等价式。
2.“?”的结合律中括号能否去掉不写？为什么？ 3.“?”和“?”满足结合律吗？
4.将下列各式用?（或?）的等价式表示出来，并尽可能简化。
（1）（P?Q）??P ； （2）?Q??P?（?R??P）； （3）（P?Q??R）??P?Q ； （4）P?（?P?Q）。
5.设计一个盥洗室的照明电路，使分别装在卧室和盥洗室的两个开关都能控制照明。
6.设计十字路口的自动控制线路，要求：传感器中计数器的内容C?5时亮绿灯，C?2 时亮红灯，2?C?5 时亮黄灯。
7.一个小型演播厅共四个门，每道门有一个双态开关，要求设计出线路能在改变一个开关状态时，都能改变演播厅的亮或暗，假若厅里没有人的时候暗，有人时亮，试画出电路图（尽可能简单）。
8.一个二进制译码器是有n条输入线和2n条输出线的装置，且输入与输出合于：对每组输入只有一条输出值为1，其余输出线的输出值为0，对此译码器设计一种极小电路。
§1-1-7 逻辑联结词的功能完备集
§1-1-6与§1-1-1两节我们已经看到了利用真值表定义了九个逻辑联结词，是否还可以定义其他联结词呢？有没有必要再定义呢？这九个联结词是否
40