Question

离散数学数理逻辑的一个题目

某电路中有一个灯泡和三个开关A,B,C。已知在且仅在下述四种情况下灯亮：
（1）C的扳键向上，A,B的扳键向下。
（2）A的扳键向上，B,C的扳键向下。
（3）B,C的扳键向上，A的扳键向下。
（4）A,B的扳键向上，C的扳键向下。
设F为1表示灯亮，p,q,r分别表示A,B,C的扳键向上。
（a）求F的主析取范式。
（b）在联结词完备集{┐,∧}上构造F.
（c）在联结词完备集{┐,→, }上构造F.

Answer 1

设扳上用字母ABC表示，扳下用否定表示。
(a)(┐A∧┐B∧C)∨(A∧┐B∧┐C)∨(┐A∧B∧C)∨(A∧B∧┐C)

(b)
记(┐A∧┐B∧C)=P，
(A∧┐B∧┐C)=Q，
(┐A∧B∧C)=R，
(A∧B∧┐C)=S，

由于P∨Q=┐(┐P∧┐Q)，所以
P∨Q∨R∨S
=┐(┐P∧┐Q)∨R∨S
=┐(┐(┐(┐P∧┐Q))∧┐R)∨S
=┐((┐P∧┐Q)∧┐R)∨S
=┐(┐(┐((┐P∧┐Q)∧┐R))∧┐S)
=┐(((┐P∧┐Q)∧┐R)∧┐S)
=┐(┐P∧┐Q∧┐R∧┐S)。

(c)由于P∧Q=┐(P→┐Q)，
所以┐(┐P∧┐Q∧┐R∧┐S)
=┐(┐P∧┐Q∧┐R∧┐S)
=┐(┐(┐P→Q)∧┐R∧┐S)
=┐(┐(┐(┐P→Q)→R)∧┐S)
=┐(┐(┐(┐(┐P→Q)→R)→S))
其中，
P=(┐A∧┐B∧C)=(┐(┐(┐A→┐B)→┐C))，
Q=(A∧┐B∧┐C)=(┐(┐(A→┐B)→C))，
R=(┐A∧B∧C)=(┐(┐(┐A→┐B)→┐C))，
S=(A∧B∧┐C)=(┐(┐(A→┐B)→C))。
[这都是因为(P∧Q∧R)=(┐(P→┐Q)∧R)=(┐(┐(P→┐Q)→┐R))。]

Answer 2

主析取范式和主合取范式的概念应该知道吧？
等值演算：(¬p→q)→(¬q∨p)
=(p∨q)→(¬q∨p)=¬(p∨q)∨(¬q∨p)；（条件式转化为析取式）
=(¬p∧¬q)∨(¬q∨p)；（否定转移到到单个逻辑变量）
求主范式和将公式简化的过程正好相反，它要求每个子式都包含所有逻辑变量。这通常就需要用到具有“扩展”功能的运算律：
X=X∧1=X∧(Y∨¬Y)=(X∧Y)∨(X∧¬Y)；——主析取范式；
X=X∨0=X∨(Y∧¬Y)=(X∨Y)∧(X∨¬Y)；——主合取范式；
主合取范式：(¬p∧¬q)∨(¬q∨p)

=(¬p∨¬q∨p)∧(¬q∨¬q∨p)；（析取对合取的分配律）
=1∧(¬q∨p)=p∨¬q；——该主合取范式只包含一项；
主析取范式：(¬p∧¬q)∨(¬q∨p)
=(¬p∧¬q)∨(p∧¬q)∨(¬p∧¬q)∨(p∧q)∨(p∧¬q)；（扩展后面两个变量）
=(p∧q)∨(p∧¬q)∨(¬p∧¬q)；
至于成真赋值或成假赋值法，需要对各种逻辑联结词的真值表熟记于心：
(¬p→q)→(¬q∨p)
观察这个表达式，整体是一个条件式；条件式成真的赋值有3种，成假的赋值有1种；以成假赋值为例：原式的成【假】赋值要求：(¬p→q)真、(¬q∨p)假；
第一项(¬p→q)还是条件式，成真赋值有3：¬p真q真，¬p假q真，¬p假q假；即：
【p假q真】【p真q真】【p真q假】；

第二项(¬q∨p)是析取式，成假赋值有1：¬q假p假；即：【p假q真】；
将两项的要求组合，发现只有【p假q真】能同时满足两项，即：当且仅当【p假q真】时，原式结果为【假】。
对于二元逻辑式，只有4种赋值，排除这唯一的成假赋值，剩下的3种就是成真赋值。
主析取范式，就是成真赋值的析取；

主合取范式，就是成假赋值——取反——的合取，即【p真或q假】；（因为只有一组成假赋值，也就是主合取范式中只包含一项析取式，也就不用再作合取运算了。）