Operational Semantics in prolog

Question

My question is quite simple and iI understand what I have to do, but it seems like I can't represent my understanding. How to write predicates to define gates such as XOR or NOR in terms of a NAND gate rules?

for example :

nand(t,t,f).
nand(t,f,t).
nand(f,t,t).
nand(f,f,t).

Above is a truth table for nand gate. Now if I want to define XOR gate using the above terms in Prolog, for example I need to ask Prolog about XOR(X,Y,Z) , it would give me three possible answers, how should I build a predicate to define it?

Thank You

See the answer @CapelliC gave on this. You just need to first use boolean logic to write out (or "wire up") the desired operation in terms of the given operations. He showed how to get XOR from NAND inputs. If you want NOR, you would use boolean logic again. NAND is NOT(A AND B). NOR is NOT(A OR B). Use logical rules such as NOT(A OR B) is equivalent to (NOT A) AND (NOT B). How do you get NOT A from NAND? Easy: NOT A = NAND(A, A). Do a little work from there to figure out nor(A, B, C). — lurker
To be clear, I wasn't writing Prolog statements in my prior comment. They are just logical statements. But the information should be sufficient for you to solve your problem if you give it some thought. — lurker

CapelliC CapelliC · Accepted Answer · 2017-03-22T06:54:03

The difficult part is to devise the expression in terms of a nand gate. Let's say we trust this question: a solution then could be

xor(A,B,C) :-
    nand(A,B,O1),
     nand(A,O1,O21),
     nand(B,O1,O22),
      nand(O21,O22,C).

test:

?- setof(X/Y/Z,xor(X,Y,Z),L).
L = [f/f/f, f/t/t, t/f/t, t/t/f].

Operational Semantics in prolog

1 Answers