(PvQ)  ==>   P+Q-PQ

(P^Q)  ==>   PQ

~P     ==>   1-P


(~PvQ)  ==>   (1-P)+Q - (1-P)Q == 1-P+Q -Q + PQ  = 1-P+PQ


~Q  ==>  1-Q


((~PvQ)^~Q) ==>  (1-P+PQ)(1-Q) = 1-P+PQ -Q +PQ - PQ  = 1-P-Q + PQ



And the propositions with the negation of the conclusion:


(((~PvQ)^~Q)^P) ==> (1-P-Q+PQ)(P) = P-P-PQ+PQ = 0

Therefore the propositions necessarily entail the conclusion.



NAND gate

P  Q    NAND
1  1     0
1  0     1
0  1     1
0  0     1


The function in a neural node can't evaluate P and Q separately.  The function takes only input, which is the weighted sum of the inputs to the node.

Each input is multiplied by a constant including the hidden input (which is always 1) and the sum of these products is the input to the node.

So if the weights on P and Q are both 1, and the weight of the hidden input is -1.  1-max(S,0)    S = 1*P + 1*Q - 1*1

Building NOT from NAND


x NAND x =  NOT X


x split and each input of the NAND gate is a copy of x.

x AND y = NOT (x NAND y)

Make x and y the inputs to the NAND gate, split the output and connect them to the inputs of another NAND gate, and that output will be x AND y


x OR y  = NOT (NOT x AND NOT Y) = NOT x   NAND NOT y

Connect x and y to NOT gates, built from NAND gates as above.  Connect the outputs to another NAND gate, and the output will be X OR Y.