Express all 16 boolean functions with the less than operator

15

3

There are 16 distinct boolean functions for two binary variables, A and B:

A B | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15
-----------------------------------------------------------------------------------------
0 0 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1  | 1   | 1   | 1   | 1   | 1   | 1  
0 1 | 0  | 0  | 0  | 0  | 1  | 1  | 1  | 1  | 0  | 0  | 0   | 0   | 1   | 1   | 1   | 1  
1 0 | 0  | 0  | 1  | 1  | 0  | 0  | 1  | 1  | 0  | 0  | 1   | 1   | 0   | 0   | 1   | 1  
1 1 | 0  | 1  | 0  | 1  | 0  | 1  | 0  | 1  | 0  | 1  | 0   | 1   | 0   | 1   | 0   | 1   

The less than operator <, which normally isn't thought of as a logic operator like NOT, AND, or OR, is in fact one of these functions (F4) when applied to boolean values:

A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0

Interestingly, we can simulate any of the 15 other functions using expressions that only contain the symbols ()<AB10. These expressions are read and evaluated just as they would be in many standard programming languages, e.g. parentheses must match and < must have arguments on either side of it.

Specifically, these expressions must comply with the following grammar (given in Backus-Naur form):

element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)

This means that useless paretheses and expressions of the form A<B<1 are not allowed.

So the expression A<B matches the function F4, and A<B<1 must be changed to (A<B)<1 or A<(B<1).

To prove that all of the 15 other functions can be turned into expressions, it suffices to form a set of expressions that is functionally complete, because then, by definition, they can be composed into expressions for any function.

One such set of expressions is x<1 (where x is A or B), which is ¬x, and (((B<A)<1)<A)<1, which is A → B. Negation (¬) and implication () are known to be functionally complete.

Challenge

Using the characters ()<AB10, write 16 expressions in the form described above that are equivalent to each of the 16 distinct boolean functions.

The goal is to make each of the expressions as short as possible. Your score is the sum of the number of characters in each of your 16 expressions. The lowest score wins. Tiebreaker goes to the earliest answer (provided they didn't edit their answer later with shorter expressions taken from someone else).

You do not technically need to write any real code for this contest but if you did write any programs to help you generate the expressions, you are highly encouraged to post them.

You can use this Stack Snippet to check if your expressions do what's expected:

function check() {
  var input = document.getElementById('input').value.split('\n'), output = ''
  if (input.length == 1 && input[0].length == 0)
    input = []
  
  for (var i = 0; i < 16; i++) {
    var expected = [(i & 8) >> 3, (i & 4) >> 2, (i & 2) >> 1, i & 1]
    
    output += 'F' + i.toString() + '\nA B | expected | actual\n-----------------------\n'
    for (var j = 0; j < 4; j++) {
      var A = (j & 2) >> 1, B = j & 1, actual = '?'
      if (i < input.length) {
        try {
          actual = eval(input[i]) ? 1 : 0
        } catch (e) {}
      }
      
      output += A.toString() + ' ' + B.toString() +
        ' | ' + expected[j] + '        | ' + actual.toString() + '     '
      if (expected[j] != actual)
        output += ' <- MISMATCH'
      if (j != 3)
        output += '\n'
    }
    if (i != 15)
      output += '\n\n'
  }
  document.getElementById('output').value = output
}
<textarea id='input' rows='16' cols='64' placeholder='put all 16 expressions here in order, one per line...'></textarea><br><br>
<button type='button' onclick='check()'>Check</button><br><br>
<textarea id='output' rows='16' cols='64' placeholder='results...'></textarea><br>
"?" means there was some sort of error

Calvin's Hobbies

Posted 2015-03-26T07:55:46.487

Reputation: 84 000

8-1, problem is too simple. – isaacg – 2015-03-26T08:28:48.413

2

Well I guess there's no point posting another answer, so here's my attempt.

– Sp3000 – 2015-03-26T08:31:53.303

7@isaacg You're right. I'd say it's far from the simplest PPCG contest ever but the fact that optimal answers will be almost exactly identical makes it kind of boring as a competition. However, I do think it serves perfectly fine as a personal exercise, especially for people who aren't experts in logic. I'm sure at least half the people on PPCG are here for fun, not just to win, or else no one would ever answer a question with a non-winning submission. – Calvin's Hobbies – 2015-03-26T08:48:38.540

I'd probably compare this to the controversial golf practice. This was a fun and interesting question, if a bit easy.

– Sp3000 – 2015-03-26T09:08:06.893

2

If anyone's interested, here's 3 variables. The longest expressions correspond to (0, 0, 0, 1, 0, 1, 1, 0) and (0, 1, 1, 0, 1, 0, 0, 0).

– Sp3000 – 2015-03-26T09:22:49.913

I'm not even sure this is metagolf, since this doesn't really ask for a program that golfs the results. It's more like a normal code golf which is so specific that someone could use a program to do the work for them (which in theory is possible for any code golf, although very hard in practice). – Martin Ender – 2015-03-26T10:18:49.667

@MartinBüttner Yeah, I wasn't quite sure what to tag it. – Calvin's Hobbies – 2015-03-26T10:22:25.953

Forgive my pedantry, but I fixed the BNF into actual BNF, including the restriction that A<B<0 is not allowed. This should make it easier for people to make language generators as well. – orlp – 2015-03-26T13:16:52.450

Just an observation: As is evident from the posted entries, the material implication "If A then B" may be achieved by a shorter phrase than the one you gave. Actually by a sub-phrase of the one you gave--therefore I'm guessing that you knew this form but deliberately obfuscated/lengthened it for the purpose of the challenge. – mathmandan – 2015-03-26T19:41:09.253

Answers

5

100 characters

0
(A<1)<B
B<A
A
A<B
B
((B<A)<((A<B)<1))<1
(A<(B<1))<1
A<(B<1)
(B<A)<((A<B)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1

jimmy23013

Posted 2015-03-26T07:55:46.487

Reputation: 34 042

9

There are a few options for some of these, so this 100-char set isn't identical to the previously posted ones.

0
(B<A)<A
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<A)<A)<1
1

An easier proof that < is functionally complete would be that A<(B<1) gives NOR.

The code which I used to find this is a heavy simplification of some Boolean optimisation code I've used on earlier challenges, with two small changes:

  1. Make the score of an expression be the length of its string rather than the number of operations.
  2. Make the string avoid unnecessary parentheses, to minimise the length.
import java.util.*;

public class PPCG48193 {

    public static void main(String[] args) {
        Expr[] optimal = new Expr[16];
        int unfound = 16;

        PriorityQueue<Expr> q = new PriorityQueue<Expr>();
        q.offer(new Expr(0, "0"));
        q.offer(new Expr(15, "1"));
        q.offer(new Expr(3, "A"));
        q.offer(new Expr(5, "B"));
        while (unfound > 0) {
            Expr e = q.poll();
            if (optimal[e.val] != null) continue;

            optimal[e.val] = e;
            unfound--;
            for (Expr e2 : optimal) {
                if (e2 != null) {
                    Expr e3 = e.op(e2), e4 = e2.op(e);
                    if (optimal[e3.val] == null) q.offer(e3);
                    if (optimal[e4.val] == null) q.offer(e4);
                }
            }
        }

        for (Expr e : optimal) System.out.println(e.expr);
    }

    private static class Expr implements Comparable<Expr> {
        public final int val;
        public String expr;

        public Expr(int val, String expr) {
            this.val = val;
            this.expr = expr;
        }

        public Expr op(Expr e) {
            String l = expr.contains("<") ? String.format("(%s)", expr) : expr;
            String r = e.expr.contains("<") ? String.format("(%s)", e.expr) : e.expr;
            return new Expr((15 - val) & e.val, String.format("%s<%s", l, r));
        }

        public int compareTo(Expr e) {
            int cmp = expr.length() - e.expr.length();
            if (cmp == 0) cmp = val - e.val;
            return cmp;
        }
    }
}

Peter Taylor

Posted 2015-03-26T07:55:46.487

Reputation: 41 901

What's the total character count? – user253751 – 2015-03-26T21:28:01.010

@immibis, 100 chars, same as the others. – Peter Taylor – 2015-03-26T23:01:02.867

"avoid unnecessary parentheses, to minimise the length" no you don't avoid them so that you would shorten but to comply with the rules. – Erik the Outgolfer – 2017-05-22T11:21:27.137

@EriktheOutgolfer, I'm not 100% sure what you mean, but my best guess is that you're referring to "This means that useless paretheses and expressions of the form A<B<1 are not allowed." If so, check the timestamps: that was an edit made after this answer. – Peter Taylor – 2017-05-22T11:43:48.200

2

100 characters

0
(A<B)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(B<(A<1))<1
B<(A<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<B)<B)<1
1

isaacg

Posted 2015-03-26T07:55:46.487

Reputation: 39 268

1

100 characters

0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
((B<1)<A)<1
(B<1)<A
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1

Hey, it's not exactly the same as the other ones. I spent like 10 minutes on this so it's worth posting anyways, even if this is 2 years old.

nog642

Posted 2015-03-26T07:55:46.487

Reputation: 151

0

100 characters

0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<1)<A)<1
1

Erik the Outgolfer

Posted 2015-03-26T07:55:46.487

Reputation: 38 134