Proposition Parsing

When a proposition is not well-formed, there is some ambiguity when trying to evaluate it. As such, an order of evaluation is required to properly parse it.

How do we parse the statement below?

$$P\wedge \neg Q\to Q\to \neg R\vee S$$

Binding Powers §

Logical connectives have binding power, which defines their order of precedence. A connective that ‘binds’ stronger is one that should be evaluated first. The binding powers are:

$$\neg >\wedge ,\vee ,>\to$$

That is:

1. Negation binds strongest, stronger than disjunction and conjunction
2. Disjunction and conjunction have equal precedence, can be evaluated left-to-right if no parentheses are present
3. They also bind stronger than implication, which binds weakest.

For example, even though the proposition $P\wedge \neg Q$ is not well-formed, because we know negation binds stronger than conjunction, we can ‘add’ our own implicit parentheses:

$$P\wedge \neg Q\equiv P\wedge (\neg Q)$$

A combination of disjunction and conjunction must have parentheses!

Because both connectives have equal precedence/binding power, we cannot evaluate a statement like:

$$P\wedge Q\vee R\wedge S$$

without explicit parentheses!

Properties of Connectives §

• Both conjunction ($\wedge$) and disjunction ($\vee$) are symmetrical, meaning $P\wedge Q\equiv Q\wedge P$

Expression Trees §

Once the binding powers have been accounted for, a visual way to evaluate such compound statements is via an expression tree:

%%🖋 Edit in Excalidraw, and the dark exported image%%

Note that an expression tree behaves in the ‘reverse’ of binding powers, that is, if two connectives are in the same parenthesis layer, the connective with the lower binding power is put higher up the tree.