Definition:Abbreviation of WFFs of Propositional Logic
Definition
The WFFs of propositional logic can be made more readable by allowing them to be abbreviated. The resulting strings are not actually WFFs as such, but can be translated back uniquely into full WFFs.
Rules for Abbreviation of WFFs
- $(2): \quad$ Brackets can be removed around parts of nested WFFs if the inner WFF has a higher binding priority than the outer one.
- $(3): \quad$ In the case of repeated $\land$ or $\lor$ connectives, we can replace:
- $\paren {\paren {\mathbf A \land \mathbf B} \land \mathbf C}$ with $\paren {\mathbf A \land \mathbf B \land \mathbf C}$
- but not:
- $\paren {\mathbf A \land \paren {\mathbf B \land \mathbf C} }$ with $\paren {\mathbf A \land \mathbf B \land \mathbf C}$
- (there is a reason for this).
- but not:
Any string obtained from a WFF $\mathbf A$ by applying any of the above rules is called an abbreviation of $\mathbf A$.
Standard Abbreviation
The string obtained by applying as many of the rules for abbreviation of WFFs to a WFF $\mathbf A$ as possible is known as the standard abbreviation of $\mathbf A$.
Examples
- $\left({\mathbf A * \mathbf B}\right)$ can be written $\mathbf A * \mathbf B$.
- $\left({\left({\mathbf A \land \mathbf B}\right) \implies \mathbf C}\right)$ can be written $\left({\mathbf A \land \mathbf B \implies \mathbf C}\right)$
Combining the above rules, we can write the latter as $\mathbf A \land \mathbf B \implies \mathbf C$.
When writing a conjunction or disjunction of a finite number of WFFs, e.g.
- $\mathbf A_1 \land \mathbf A_2 \land \mathbf A_3 \land \cdots \land \mathbf A_n$
the ability to abbreviate is particularly convenient.
Notes
Adding brackets
The standard abbreviation is usually easier to read than the WFF it came from, but it is sometimes convenient to clarify a particularly complicated WFF by adding brackets.
Hence, for example, in order to emphasise that the negation sign has a higher binding priority than a binary connective, we might wish to write $\left({\neg \mathbf A}\right) \land \mathbf B$ instead of $\neg \mathbf A \land \mathbf B$.
This would also be termed an abbreviation, even though it is not actually any shorter.
Origin of abbreviations
The abbreviation of WFFs of propositional logic stems from their semantics. It is only because we "know how binary connectives work" that we are able to allow these abbreviation rules to be defined.
In particular, note that the ability to remove brackets from around repeated $\land$ and $\lor$ connectives stems from the Rule of Association which (at the stage of construction of the formal system that is PropLog) has not even been suggested, let alone proved.
As $\implies$ is not associative, of course, the same rule can not be applied to that connective.
The question also needs to be answered: why can't we replace $\left({\mathbf A \land \left({\mathbf B \land \mathbf C}\right)}\right)$ with $\left({\mathbf A \land \mathbf B \land \mathbf C}\right)$? Isn't that essentially what the Rule of Association states? Either way, the statement is only true if all three are true.
This is indeed the case, but if $\left({\mathbf A \land \mathbf B \land \mathbf C}\right)$ were allowed to be an abbreviation for $\left({\mathbf A \land \left({\mathbf B \land \mathbf C}\right)}\right)$, then there would be two different WFFs: $\left({\mathbf A \land \left({\mathbf B \land \mathbf C}\right)}\right)$ and $\left({\left({\mathbf A \land \mathbf B}\right) \land \mathbf C}\right)$, which would have the same abbreviation.
This is something that we wish (at this stage at least) to avoid.
Sources
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): $\S 1.4$: Main Connective