Creating truth tables for propositional logic formulas?

Question

I wanted to create a program that, given a logic formula by the user, for example ((¬A ∧ B) ∨ C) ∧ A, calculates its truth table. In this case the formula would be true if A=1, B=0, C=1, or if A=1, B=1, C=1, and it would be false in any other case.

But, I don't know how to create a method that can read the expression given, and then calculate all the possible outcomes.

The [shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm) might be a start. — Andy Turner, Nov 10 '21 at 11:43
Parsing such an expression from the command line would be the hardest part. Why don't you use an existing library to do it ? — Arthur Klezovich, Nov 10 '21 at 12:12
@ArthurKlezovich I kinda want to challenge myself, I'd like to make something a bit complex from scratch. — Simone Tarenzi, Nov 10 '21 at 12:53

Arthur Klezovich · Accepted Answer · 2021-11-10T14:23:25.000

I don't know how to create a method that can read the expression given, and then calculate all the possible outcomes.

OK, so let's start with the task breakdown into subtasks. Here's what you need to do ...

Parse the string you get as input into some internal data structures used by your program. This is a hard task. Make sure to cover relevant methods by unit tests.
Calculate the truth tables. This is easier. You just need to iterate over all possible sets of inputs. These will be binary numbers from 0 to 2^n-1 where n is the number of boolean inputs.

Let's see what resources you can use ...

For the parse part you can adapt this
To generate all possible inputs you can use this

Also, please, make sure to cover your methods by unit tests. Its easy to make a mistake in complicated logic like this, which will take hours to debug. Therefore, unit tests will save you loads of time.

Does this solve your problem ? Tell me in the comments.

@SimoneTarenzi If this answer has helped you, please mark it as accepted and upvote. This will help others find it and reuse it. — Arthur Klezovich, Nov 10 '21 at 15:46

score 0 · Answer 2 · 2021-11-10T20:31:18.113

Try this.

interface Bool {
    boolean get();
    default Bool and(Bool r) { return () -> get() ? r.get() : false; }
    default Bool or(Bool r) { return () -> get() ? true : r.get(); }
    default Bool not() { return () -> !get(); }
}

static class TruthTable {
    String formula;
    int index, ch;
    List<Character> variables;
    Map<Character, Boolean> map;
    Bool bool;

    int get() {
        return ch = index < formula.length() ? formula.charAt(index++) : -1;
    }

    boolean match(int expect) {
        if (ch == expect) {
            get();
            return true;
        }
        return false;
    }

    Bool element() {
        Bool b;
        if (match('(')) {
            b = expression();
            if (!match(')'))
                throw new RuntimeException("')' expected");
        } else if (Character.isAlphabetic(ch)) {
            char v = (char) ch;
            get();
            if (!variables.contains(v))
                variables.add(v);
            b = () -> map.get(v);
        } else
            throw new RuntimeException("unknown char: " + (char) ch);
        return b;
    }

    Bool factor() {
        if (match('￢'))
            return element().not();
        return element();
    }

    Bool term() {
        Bool b = factor();
        while (match('∧'))
            b = b.and(factor());
        return b;
    }

    Bool expression() {
        Bool b = term();
        while (match('∨'))
            b = b.or(term());
        return b;
    }

    String str(boolean b) {
        return b ? "T" : "F";
    }

    void print() {
        for (char v : variables)
            System.out.print(str(map.get(v)) + " ");
        System.out.println(str(bool.get()));
    }

    void test(int i) {
        if (i >= variables.size())
            print();
        else {
            char c = variables.get(i);
            map.put(c, true);
            test(i + 1);
            map.put(c, false);
            test(i + 1);
        }
    }

    public void make(String formula) {
        this.formula = formula.replaceAll("\\s", "");
        index = 0;
        variables = new ArrayList<>();
        map = new HashMap<>();
        get();
        bool = expression();
        if (ch != -1)
            throw new RuntimeException(
                "extra string '" + formula.substring(index - 1) + "'");
        for (char v : variables)
            System.out.print(v + " ");
        System.out.println(formula);
        test(0);
        System.out.println();
    }
}

And

public static void main(String[] args) {
    new TruthTable().make("￢A");
    new TruthTable().make("￢A ∧ B");
    new TruthTable().make("(￢A ∧ B) ∨ C");
    new TruthTable().make("((￢A ∧ B) ∨ C) ∧ A");
}

output:

A ￢A
T F
F T

A B ￢A ∧ B
T T F
T F F
F T T
F F F

A B C (￢A ∧ B) ∨ C
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F F

A B C ((￢A ∧ B) ∨ C) ∧ A
T T T T
T T F F
T F T T
T F F F
F T T F
F T F F
F F T F
F F F F

Creating truth tables for propositional logic formulas?

2 Answers2