离散数学数理逻辑的一个题目某电路中有一个灯泡和三个开关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.
2019-05-29
离散数学数理逻辑的一个题目
某电路中有一个灯泡和三个开关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.
优质解答
设扳上用字母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)).]
设扳上用字母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)).]