Expression tree generator
Type a logic expression and see the tree its connectives form: which one is applied last, and what each one works on. Pick a row to fill in every node's value, from the letters at the bottom up to the answer at the top.
¬ ~ ! not, ∧ & ^ and, ∨ | v or, ⊕ xor, → -> if-then, ↔ <-> iff if and only if. Here ^ means AND. For circuit notation such as ab + c', use the truth table generator.
With p = T, q = T, r = T the whole expression is false. It is true in 1 of 8 rows.
4 connectives, 4 leaves, 4 levels. The ringed node at the top is applied last, so its value is the answer.
Pick a row
| p | q | r | (p → q) ∧ ¬(q ∨ r) |
|---|---|---|---|
| T | T | T | F |
| T | T | F | F |
| T | F | T | F |
| T | F | F | F |
| F | T | T | F |
| F | T | F | F |
| F | F | T | F |
| F | F | F | T |
What an expression tree is
An expression tree shows how an expression is built. Each connective is a node, and its branches lead to the parts it joins. The letters and constants are the leaves, at the ends of the branches. The node at the top, the root, is the connective applied last: it decides what kind of statement the whole thing is. A root of → makes the whole expression a conditional; a root of ∧, a conjunction.
It is also called a parse tree or a syntax tree, since it is what a parser builds when it reads the text. Brackets do not appear in it. They only tell the parser how to group, and the shape of the tree already records that.
How precedence decides the shape
Without brackets, ¬ binds tightest, then ∧, ⊕, ∨, → and finally ↔. So in ¬p ∨ q → r the ¬ takes only p, and → is applied last. Put brackets around p ∨ q and the ¬ moves up the tree to take all of it:
Both have → at the root, but the left one negates p alone and the right one negates the whole of p ∨ q. They disagree in 2 of 8 rows: with p = T, q = T, r = F, for instance, the left is false and the right is true. Without brackets, a connective that binds more tightly always sits lower in the tree, because it is applied first.
Evaluating from the bottom up
To find the value of an expression for one row, start at the leaves with the values of the letters, then work upwards: each node applies its connective to the values just below it. Here is (p ∨ q) ∧ ¬r with p false, q true and r false:
This is exactly what the working columns of a truth table do. Each connective in the tree is one column, filled in the same order, innermost first:
| p | q | r | p ∨ q | ¬r | (p ∨ q) ∧ ¬r |
|---|---|---|---|---|---|
| F | T | F | T | T | T |
The last column is the root, T. A full truth table repeats this for every row: the truth table calculator for logic statements shows those columns for any statement.
Trees and circuits
Read a tree upside down and it is a logic circuit: the leaves are inputs, each connective is a gate, and each branch is a wire carrying one gate's output to the next. The root is the output. A tree is the special kind of circuit where no gate's output is used twice.
Real circuits often share. In (p ∧ q) ∨ ¬(p ∧ q) ∧ r the part p ∧ q appears twice, so the tree has two identical p ∧ q branches, with 3 ∧ nodes and 5 leaves in all:
A circuit can build p ∧ q once and wire its output to both places, and the letters become input wires shared by every gate that reads them. The circuit diagram generator draws an expression as gates, and the boolean algebra calculator simplifies it so the circuit needs fewer of them.
Chains of the same connective
A connective joins two things, so p ∧ q ∧ r is read as (p ∧ q) ∧ r and drawn with two ∧ nodes. Since ∧ and ∨ give the same answer however a chain is grouped, the chain can also be drawn as one node with three branches, the way a three-input AND gate would be:
Questions
Is an expression tree the same as a parse tree or a syntax tree?
Nearly. Strictly, a parse tree (or concrete syntax tree) has a node for every rule of the grammar, brackets included, while an abstract syntax tree keeps only the connectives and what they join. The brackets are not needed once the shape records the grouping. What courses call an expression tree is the abstract syntax tree, and that is what this page draws.
How do I type the symbols?
NOT: ¬, ~, ! or not. AND: ∧, &, ^ or and. OR: ∨, |, + or or, and a lone v between two letters works too. XOR: ⊕. IF-THEN: →, -> or =>. IF AND ONLY IF: ↔, <-> or iff. Each letter is a single letter such as p or q, and ⊤ and ⊥ (or 1 and 0) are constants. Note that ^ means AND here, as in logic classes. For circuit notation, where ab means a AND b and ^ is XOR, use the truth table generator, which draws the tree too.
Why does p → q → r branch to the right?
Because → groups to the right by convention: p → q → r means p → (q → r). The other connectives group to the left, so p ∧ q ∧ r means (p ∧ q) ∧ r and its tree leans left. For ∧ and ∨ the grouping makes no difference to the value; for → it does, which is why the convention matters.
Why are there two ∧ nodes for p ∧ q ∧ r?
Because each connective joins two things, and the parser reads the chain as (p ∧ q) ∧ r. Since ∧ and ∨ are associative, the grouping never changes the answer, so choosing "merged" for chains draws one ∧ node with three children instead. Chains of → are never merged, since → is not associative.
How do I read an expression back out of a tree?
Visit each node after its children, from left to right, and write down what you meet. That is a post-order traversal, and it gives the expression in reverse Polish notation: p ∧ q → r becomes p q ∧ r →. Evaluating that list with a stack is the same bottom-up evaluation the tree shows.
How big can the expression be?
Up to 6 different letters, which is 64 rows to pick from. A letter can appear as many times as you like; each appearance is its own leaf. Wide trees scroll sideways inside their box.