[erlang-questions] nand problem

Richard A. O'Keefe ok@REDACTED
Fri Jan 30 06:16:00 CET 2015

On 27/01/2015, at 5:21 am, Roelof Wobben <r.wobben@REDACTED> wrote:

> Hello,
> I now have to make a nand boolean with pattern matching.
> I have found out that nand is true except when its true and true.
> as hint I get to implement nand using and and or.

You can't.  If you think of the Booleans as the lattice
with carrier {false,true} and false < true,
"and" is min and "or" is max, both of which are monotone
non-decreasing.  Any composition of monotone non-decreasing
functions is monotone non-decreasing.  But
nand(false,false) = true > false = nand(true,true),
so nand is NOT monotone non-decreasing and cannot be a
composition of ands and ors.

It's actually the other way around.  Another name for 'nand'
is the "Sheffer stroke", and you can make all the 1 or 2
argument Boolean operators from *it*.

Look, the simplest possible approach is just to write down
the truth table:

  true  nand true  = false
  true  nand false = true
  false nand true  = true
  false nand false = true

and change it to Erlang syntax:

  nand(true,  true)  -> false;
  nand(true,  false) -> true;
  nand(false, true)  -> true;
  nand(false, false) -> true.

Dollars to doughnuts doing it this way was the point of the exercise.

After this,

  not(X) -> nand(X, X).

  and(X, Y) -> not(nand(X, Y)).

  or(X, Y) -> nand(not(X), not(Y)).

Now try material implication, where (X imp Y) is true when Y
is true or X is false.

More information about the erlang-questions mailing list