又由

P

Q=

(

P=

因此 （P→R）

Q= f(P, P, ==

R)

Q

R))

Q)=

(

Q

P)

f(Q, Q, P).

f(P, P, Q)=

f(Q, Q, f(P, P,

f(Q, Q, f(P, P, f(R,R,R)))

=f(f(Q, Q, f(P, P, f(R,R,R))), f(Q, Q, f(P,

P, f(R,R,R))), f(Q, Q, f(P, P, f(R,R,R))))。

例2.2.12 {，→}是否是联结词的全功能集合？证明你的结论。

在证明此题之前，我们先直观分析一下。考虑两个联结词的特点：当一个命题公式中只含有联结词

和→这和→

时，则当公式中出现的所有命题原子都取真值1时，公式也必然取真值1。这就是说，仅含的命题公式，比如恒假式：A→}不是全功能集。

证明：下面证明{

，→}不是联结词的全功能集。

和→的公式不能表示所有A。因此，联结词集合{

，

对公式中出现的联结词个数使用数学归纳法来证明下面的结论：当一个命题公式中只含有联结词

和→时，则当

公式中出现的所有命题原子都取真值1时，公式也必然取真

值1。

n=0时，即公式中不含任何联结词时，公式为原子，结论显然。

假设n≤k时，命题成立，即，如果一个公式中含有n个联结词

，→，则当公式的所有原子真值取1时，公式也

取真值1。

当n=k+1时，设任一含k+1个联结词的公式为A，则存在公式B和C，使得：

A=B→C或A=B

且B和C中的联结词个数均≤k。

由归纳假设知，当所有原子取真值1时，B和C在该解释下的真值均为1，因此，A在该解释下的真值亦为1。归纳完成。

由该结论知，如果一个命题公式中只含有联结词

和→，

C，

那么至少存在一个解释满足该公式。因此，只含有联结词和→的公式肯定不能表示恒假公式。所以，{，→}不是联结词的全功能集。

2.2.5 综合应用题

综合题主要是先符号化，再使用上面的知识进行联结词的转化、或求主合取式、主析取式、利用基本等价式化简、

或进行逻辑推理来论证或做逻辑判断等。

例2.2.13 一个排队线路，输入为A，B，C，其输出分别为FA, FB, FC。在同一时间只能有一个信号通过。如果同时有两个或两个以上信号通过时，则按A，B，C的顺序输出。例如，A，B，C同时输入时，只能A有输出。写出FA, FB, FC的逻辑表达式，并化成全功能集{

}中的表达式。

解：先将已知事实中的各简单命题符号化，设： P：A输入； Q：B输入； R：C输入。

然后根据已知条件，写出FA, FB, FC的真值表如表2.2.7。 P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 FA 0 0 0 0 1 1 1 1 FB 0 0 1 1 0 0 0 0 FC 0 1 0 0 0 0 0 0 表2.2.7

于是，

FA= (P

QR)

(P

Q

R)

(P

Q

=R））

= = P =P = = =

=(PR)

(P

Q

R)

（（P Q）（

R

R））（P Q）（PQ） （Q

Q）

(PP) (PP) ((P

P)

(PP))

P)

(P

P). FB= (P Q

R)

(

P

=(P

Q) （R R） =P Q =(P

Q) =(P

Q)

=PQ = P(QQ) FC=

PQR

（（P

Q

R)

Q（

R