15
\$\begingroup\$

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

\$\endgroup\$
  • 8
    \$\begingroup\$ -1, problem is too simple. \$\endgroup\$ – isaacg Mar 26 '15 at 8:28
  • 2
    \$\begingroup\$ Well I guess there's no point posting another answer, so here's my attempt. \$\endgroup\$ – Sp3000 Mar 26 '15 at 8:31
  • 7
    \$\begingroup\$ @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. \$\endgroup\$ – Calvin's Hobbies Mar 26 '15 at 8:48
  • \$\begingroup\$ I'd probably compare this to the controversial golf practice. This was a fun and interesting question, if a bit easy. \$\endgroup\$ – Sp3000 Mar 26 '15 at 9:08
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ – Sp3000 Mar 26 '15 at 9:22
5
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

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;
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What's the total character count? \$\endgroup\$ – user253751 Mar 26 '15 at 21:28
  • \$\begingroup\$ @immibis, 100 chars, same as the others. \$\endgroup\$ – Peter Taylor Mar 26 '15 at 23:01
  • \$\begingroup\$ "avoid unnecessary parentheses, to minimise the length" no you don't avoid them so that you would shorten but to comply with the rules. \$\endgroup\$ – Erik the Outgolfer May 22 '17 at 11:21
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor May 22 '17 at 11:43
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.