Abbreviating WFFs

"The word "abbreviation" sure is long for what it means." - Zach Galifianakis

Earlier, we noted that English language has problems with ambiguities. Even if there is no disagreement about the meanings of each word individually, a sentence like

He poked a dog with a stick.

has two different meanings depending on whether we read this as

He used a stick to poke a dog.

or

He poked a dog who had a stick.

The two interpretations are illustrated below in this highly scientific diagram:

Similarly, even if we agreed that \(\land\) means "and", \(\lor\) means "or", \(\to\) means "implies", formulas like

\[ P\land Q\lor R \qquad\qquad P\to Q\to R \qquad\qquad \lnot \,S\lor T \]

leave open the question of whether the first formula should be interpreted as "(\(P\) and \(Q\)) or \(R\)" or "\(P\) and (\(Q\) or \(R\))" and whether the second formula should be interpreted as "(\(P\) implies \(Q\)) implies \(R\)" or "\(P\) implies (\(Q\) implies \(R\))", or whether the third equation means "(not \(S\)) or \(T\)" or "not (\(S\) or \(T\))". The answer matters, because we can use truth tables to verify that the possibilities are not logically equivalent.

Our official definition of Well-Formed Formulas requires parentheses around every conjunction, disjunction, and implication. This solves the problem (for logicians), because the above formulas are simply not considered well-formed. Instead, we are required to write whichever of

\[ ((P\land Q)\lor R) \qquad\qquad (P\land (Q\lor R)) \]

\[ ((P\to Q)\to R) \qquad\qquad (P\to (Q\to R)) \]

\[ (\lnot S \ \lor\ T) \qquad\qquad \lnot (S\lor T) \]

we intended to say. By requiring parentheses, every WFF is either unambiguously a propositional variable (e.g., \(P\)), a propositional constant (e.g., \(\bot\)), a negation, and conjunction, and disjunction, or an implication, and it's unambiguous what subformulas are intended.

Example

• The WFF \(((P\land Q)\lor(R\to S))\) can only be interpreted as the disjunction of \((P\land Q)\) and \((R\to S)\)
• The WFF \(\lnot(P\to Q)\) can only be interpreted as the negation of \(P\to Q\)
• The WFF \((\lnot P\ \to\ (Q\lor R))\) can only be interpreted as saying that \(\lnot P\) implies \(Q\lor R\)

This lack of ambiguity is incredibly convenient for the study of logical systems. However, when we humans are working with large formulas one must admit it is tedious to have to write

\[ (((((P\land Q)\land R)\land S)\land T)\to((U\lor V)\lor W)) \]

instead of just

\[ P\land Q\land R\land S\land T \ \ \to \ \ U\lor V\lor W. \]

Therefore, we will make the following compromise.

1. Officially, all WFFs remain completely parenthesized. Thus, when logicians studying the properties of this logical system want prove something about all WFFs, they can assume they only have to consider unambiguous, fully-parenthesized formulas.
2. However, we allow ourselves to write "abbreviations" for WFFs with fewer parentheses, by defining a set of rules for how ambiguous-looking formulas should be unambiguously interpreted.

Definition

When writing WFFs, we can write abbreviated forms, and use the following rules to figure out which WFF we are referring to:

• Precedence: \(\lnot\) groups most tightly, followed in order by \(\land\), \(\lor\), and \(\to\)
• Associativity: \(\land\) and \(\lor\) are left-associative, but \(\to\) is right-associative
• Other: we allow ourselves to write \(A\leftrightarrow B\) instead of \(((A\to B)\land(B\to A))\) (where \(A\) and \(B\) here represent arbitrary WFFs). The \(\leftrightarrow\) operator has lowest precedence

Example

• \(P\land Q\lor R\) abbreviates \(\ ((P\land Q)\lor R)\) since \(\land\) groups tighter than \(\lor\)
• \(P\to Q\to R\) abbreviates \(\ (P\to (Q\to R))\) since \(\to\) is right-associative.
• \(\lnot \,S\lor T\) abbreviates \(\ (\lnot S\lor T)\) since \(\lnot\) groups tighter than \(\lor\)
• \(P\land Q\leftrightarrow R\) abbreviates the WFF \((((P\land Q)\to R)\land(R\to(P\land Q)))\) since \(\land\) binds tighter than \(\leftrightarrow\).

Previous: 1.4 Entailment

Next: 1.6 English to WFFs