Syntax trees

A formula is built from smaller formulas, one connective at a time. A syntax tree draws that building process, so you can see at a glance what a formula says and how it is put together. If the connectives are new to you, read the basics guide first.

Formulas are built from parts

Every formula starts from sentence letters such as P and Q. Each step then adds one connective. Here is how ¬(P ∧ Q) → R is built:

1. Start with the letters P and Q, and join them with ∧ to get P ∧ Q.
2. Negate that, to get ¬(P ∧ Q). The brackets show that ¬ applies to the whole of P ∧ Q.
3. Join ¬(P ∧ Q) and the letter R with →, to get ¬(P ∧ Q) → R.

Every formula made along the way is a subformula of the final one. The letters count, and so does the whole formula itself.

The tree

A syntax tree draws these steps upside down. The whole formula is at the top, in a node called the root. Below each connective hang the parts it joins: one part for ¬, and two for ∧, ∨, → and ↔, the left part on the left. At the bottom are the sentence letters (and ⊥, if the formula has it). They are the tree’s leaves: nothing hangs below them, because they have no connective.

When the formula has a connective, the root is its main connective: the last connective added when the formula was built. Its scope is the whole formula, and it says what kind of sentence the formula is. A formula whose main connective is → is a conditional, one whose main connective is ¬ is a negation, and so on.

The main connective matters in every tool. A truth table gives the value of the whole formula in the main connective’s column. Tableaux and proofs work on it too: it is the first thing to look at when you choose a rule.

Worked example: finding the main connective

Take ¬(P ∧ Q) → R, which could say “if it is not both cold and wet, we go out”. What is its main connective?

1. Check the outer brackets. If one pair of brackets wraps the whole formula, it can be dropped. Here the brackets close after Q, before the end, so they do not wrap the whole formula.
2. Find the connectives outside all brackets. There are two: the ¬ at the front and the →. The ∧ is inside the brackets, so it belongs to a smaller part.
3. Prefer the two-place connective. A ¬ applies only to the formula right after it, here (P ∧ Q). The → joins everything to its left with everything to its right, so it is the main connective.

So the formula is a conditional. Its antecedent (the part before the arrow) is ¬(P ∧ Q), and its consequent (the part after it) is R.

Drawing the tree

Now repeat the question for each part, until only letters are left:

1. Draw the root. Write → at the top, with two lines down: one to its left part, ¬(P ∧ Q), and one to its right part, R.
2. The right part is done. R is a sentence letter, so it is a leaf.
3. Take the left part apart. In ¬(P ∧ Q), no two-place connective stands outside the brackets, and the formula starts with ¬. So its main connective is that ¬, with one part below it: P ∧ Q.
4. Finish. The main connective of P ∧ Q is ∧, with the leaves P and Q below it. Every path now ends in a letter, so the tree is complete.

Listing the subformulas

Each node of the tree stands for a subformula: the node together with everything below it. So you can list the subformulas by reading the tree from the bottom up. The app lists them in a fixed order: first the left part and everything in it, then the right part and everything in it, and the formula itself last, with the same order inside each part. So every formula comes after its own parts, and the whole formula comes last. For ¬(P ∧ Q) → R that gives the 6 in the figure above: P, Q, P ∧ Q, ¬(P ∧ Q), R and the whole formula. R comes after ¬(P ∧ Q) because it belongs to the right part. A part that occurs more than once, like P in P → P, is listed once.

A second example

Now take ¬P ∧ Q. There are no brackets, and two connectives: ¬ and ∧. The ¬ applies only to the formula right after it, which is just P. So the main connective is ∧, and the formula is a conjunction of ¬P and Q.

Solve and Practice

Type a formula into the tool, or open one of the examples under the input, and the app draws its tree. The toolbar switches between two modes.

In Solve, the default, the main connective is filled in and ringed. Next to the tree (below it on a narrow screen), the app names the main connective, for example “conditional (→)”, lists the sentence letters in alphabetical order, and lists every subformula in the order described above: each part after its own parts, the left part before the right, and the whole formula last. Hover over a node, or focus it, to read its subformula. Click a node to keep its part of the tree highlighted, and click it again to let go. With the keyboard, Tab moves into the tree, the arrow keys move from node to node, and Enter or Space does what a click does.

In Practice, the app draws the same tree but does not say which node is the main connective. Click the node you think it is. If you pick a connective lower down, the app says which part of the formula it is the main connective of. If you pick a sentence letter, it reminds you that a letter is not a connective. Once you find the main connective, the app marks it and names it.

The app always draws the tree for you. To practise drawing one, sketch it on paper first, then compare it with the app’s tree.

Common mistakes

Stretching the scope of ¬. A ¬ applies only to the formula right after it. In ¬P ∧ Q that is just P, so the formula is a conjunction. To deny the whole conjunction, write ¬(P ∧ Q), which is a negation. Compare its tree with the one for ¬P ∧ Q above.

• Leaving out brackets you need. P ∧ Q ∨ R means (P ∧ Q) ∨ R, a disjunction, because ∧ binds more tightly than ∨. If you mean a conjunction whose second part is Q ∨ R, you must write P ∧ (Q ∨ R).
• Taking the first connective. The main connective is not simply the first or the last symbol: in ¬(P ∧ Q) → R the formula starts with ¬, but it is a conditional.

The recursive definition

Logicians define formulas (also called well-formed formulas) by a recursive definition: a few clauses that build new formulas from ones already built.

1. Every sentence letter is a formula, and so is ⊥.
2. If A is a formula, so is ¬A.
3. If A and B are formulas, so are (A ∧ B), (A ∨ B), (A → B) and (A ↔ B).
4. Nothing else is a formula.

Here A and B stand for any formulas. A syntax tree records how a formula meets this definition: its leaves come from clause 1, and each connective node is one use of clause 2 or 3.

The definition has an important consequence, called unique readability: a formula can be built in only one way. Unless it is a letter or ⊥, it has exactly one main connective and exactly one way to split into parts, so it has exactly one tree. The brackets make this work. In a formula written with every bracket, the main connective of (A ∧ B) is the only two-place connective that sits inside just one pair of brackets; every other one sits deeper.

Subformulas and complexity

The subformulas can be defined in the same recursive way. A letter, or ⊥, has only itself. The subformulas of ¬A are ¬A and those of A. The subformulas of A ∧ B are A ∧ B and those of A and of B, and likewise for the other two-place connectives. These are exactly the formulas at the nodes of the tree.

A formula’s complexity can be measured in two common ways. One is the number of connectives it contains: ¬(P ∧ Q) → R has 3, and ¬P ∧ Q has 2. The other is the depth of its tree: the number of steps on the longest path from the root down to a leaf. ¬(P ∧ Q) → R has depth 3 (from → to ¬ to ∧ to P), and ¬P ∧ Q has depth 2. A single letter, such as P, scores 0 on both.

Many facts about formulas are proved by induction on complexity: show that the fact holds for the letters and ⊥, then that it survives each step that adds a connective. Since every formula is built by finitely many such steps, the fact holds for all formulas.

Brackets and the app’s conventions

Without brackets, a string of symbols can have two trees. P ∧ Q ∨ R could be read as (P ∧ Q) ∨ R, a disjunction, or as P ∧ (Q ∨ R), a conjunction, and these two formulas are not equivalent. The strict definition above avoids this by bracketing every two-place connective.

The app lets you leave out brackets, and settles every reading with a fixed order of strength: ¬ binds most tightly, then ∧, ∨, → and, least tightly, ↔. So among the connectives outside all brackets, the main connective is the one that binds least tightly: P ∧ Q ∨ R is a disjunction. If only ¬ stands outside the brackets, the formula is a negation, and its first ¬ is the main connective. A chain of ∧, or of ∨, groups from the left, so its last connective is the main one. A chain of →, or of ↔, has no agreed grouping, so the app refuses P → Q → R and says: “→” can't be chained. Add brackets, as in (P → Q) → R.

The app also prints formulas with the fewest brackets these rules allow, as the basics guide explains. When a printed formula is hard to read, its tree shows exactly how the app reads it.

Trees and truth tables

A truth table works through the tree from the leaves up. Its first columns are the letters, the leaves. Each connective gets a column, worked out from the columns of the parts below it, and the root’s column, the main connective’s, gives the value of the whole formula. So the columns match the nodes of the tree: one for each connective, and one for each sentence letter. A letter that occurs twice is two leaves of the tree but has only one column.

Unique readability is what makes this possible: since each formula has one tree, each row gives it exactly one truth value. The truth tables guide shows how the app lays these columns out.

Further reading

forall x: Calgary, the free textbook whose proof rules the app uses, gives the recursive definition in its chapter on the sentences of TFL, its name for propositional logic, together with the main connective and scope, and it also explains its own conventions for leaving out brackets. It says “sentence” where this guide says formula, and “main logical operator” for the main connective. The proofs guide shows how a proof’s rules follow the main connective.