Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Draw the Parse Tree of a Formula

A parse tree shows how a formula is built: the connective applied last sits at the root, its parts hang below it, and the letters are the leaves. Find the main connective, split, and repeat on each part.

Recognize the task

The question asks for a parse tree, syntax tree or formation tree, for the main connective, or for the order in which a formula is evaluated: ¬P∧Q→R\neg P \land Q \to R, ¬(P∨Q)\neg(P \lor Q), P∧Q∨RP \land Q \lor R. Test: if brackets are missing, the tree decides how the formula is read.
Well-formed formulas and the precedence of connectives are defined in the syntax lesson; syntax trees are explained with the tree builder.

Steps

StepOn ¬P∧Q→R\neg P \land Q \to R
1Restore the brackets. Precedence, tightest first: ¬\neg, ∧\land, ∨\lor, →\to, ↔\leftrightarrow. A ¬\neg applies only to what directly follows it.((¬P)∧Q)→R((\neg P) \land Q) \to R
2Find the main connective. It is the one connective outside all brackets, and it is applied last.main connective: →\to
3Make it the root and hang its parts below. A binary connective gets a left and a right child; ¬\neg gets a single child.root →\to; children ¬P∧Q\neg P \land Q and RR
4Repeat on every part. Split each child at its own main connective until every branch ends in a letter.∧\land with children ¬P\neg P and QQ; ¬\neg with child PP
5Evaluate from the leaves up. For one row, write the letter values at the leaves and compute each node from its children; the root gives the value of the formula.at P=FP = F, Q=TQ = T, R=FR = F: ¬P\neg P is T, ∧\land is T, the root is F

Worked examples

Example 1 · a negated bracket

negation at the root
¬(P∨Q)\neg(P \lor Q): main connective ¬\neg
it negates the whole bracket
root ¬\neg, child ∨\lor, leaves PP and QQ
4 nodes on 3 levels

Example 2 · missing brackets

precedence
P∧Q∨RP \land Q \lor R reads (P∧Q)∨R(P \land Q) \lor R
∧\land binds tighter than ∨\lor
root ∨\lor; children P∧QP \land Q and RR
the main connective comes last
node ∧\land with leaves PP and QQ
5 nodes in all

Example 3 · a biconditional of arrows

9 nodes
(P→Q)↔(¬Q→¬P)(P \to Q) \leftrightarrow (\neg Q \to \neg P): root ↔\leftrightarrow
the only connective outside brackets
left: →\to with leaves PP and QQ
split the left part
right: →\to with children ¬Q\neg Q and ¬P\neg P
split the right part
each ¬\neg has one leaf: 9 nodes, depth 3
count down from the root
Type any formula into the parse tree builder to see its tree and its truth table.

See it happen

The tree is the formula with its grammar made visible. Two strings that look alike, such as ¬P∧Q\neg P \land Q and ¬(P∧Q)\neg(P \land Q), have different roots and so different truth tables. Evaluation always runs from the leaves to the root, the same inside-out order as the columns of a truth table: every inner node of the tree is one column of the table.

Common mistakes

Putting the negation at the root

✗ ¬P∧Q\neg P \land Q: root ¬\neg above P∧QP \land Q
✓ the root is ∧\land; the ¬\neg sits above PP alone

Reading the connectives left to right

✗ P∨Q∧RP \lor Q \land R as (P∨Q)∧R(P \lor Q) \land R
✓ by precedence it is P∨(Q∧R)P \lor (Q \land R), with root ∨\lor
Some calculators give ∧\land and ∨\lor the same level; write the brackets to be safe.

Dropping the brackets in a chain of arrows

✗ write P→(Q→R)P \to (Q \to R) as P→Q→RP \to Q \to R
✓ keep the brackets: at P=FP = F, Q=TQ = T, R=FR = F the two groupings give T and F