Formula

A formula is a sequence of symbols that borrow from a set of symbols (known as its vocabulary). Hence (usually in linguistics), formulae are sometimes called sentences and vocabulary is sometimes referred to as alphabet. Formulas can be well-formed if they follow the rules of a formal language.

Here, words like sentences, alphabet, etc. are mathematical terms, and not their traditional meanings.

A formula can be thought of as a string, which here is an array of symbols.

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

Definition §

Formula (Logic) ^definition

A formula, $f$, is defined as a sequence of symbols from some set of symbols, $\Sigma$ (known as its vocabulary). More specifically, a formula is an element of the set of all finite-length formulae, ${\Sigma }^{\ast }$ that can be defined from its corresponding vocabulary:

$$\begin{array}{rlrlr}\Sigma =\{\text{Symbols}\}& & & & {\Sigma }^{\ast }=\{\text{Formulas constructed from Σ}\}\end{array}$$

$$f\in {\Sigma }^{\ast }$$

Well-formed Formula (WFF) §

Well-formed Formula ^definition-wff

A formula, $f$, is well-formed if belongs to some formal language, $L$:

$$f\in L\subseteq {\Sigma }^{\ast }$$

Examples §

Example: Natural Alphabet §

We can take the vocabulary/alphabet to be our natural, English lowercase alphabet. Then $\Sigma =\{a,b\dots z\}$. Any permutation of the symbols is a valid formula, even ones that seem to ‘make no sense’:

• $\text{xauaadckjbcz}$ is just as much of a formula as $\text{chatter}$

Our set of all finite-length words would start off as:

$${\Sigma }^{\ast }=\{ϵ,a,b\dots z\}$$

Then we begin by looking at all words/formulae of length 2:

$${\Sigma }^{\ast }=\{ϵ,a,b\dots z\}\cup \{aa,ab,\dots az,ba,bb,\dots zz\}$$

(where $ϵ$ means the empty formula, consisting of no symbols)

And continue this process for all finite words of length $k$.

Example: Binary §

In binary, we have a much smaller vocabulary. $\Sigma =\{0,1\}$. Valid formulas include:

• $1$
• $0$
• $1010$
• $11111111$

${\Sigma }^{\ast }$ would be the set of all finite-length binary strings.