2.1 Language

In this chapter, I'll present a suitable formal language for propositional logic. Its alphabet consists of

• statement letters/elementary proposition symbols: capital letters from the English language (\(A\), \(B\), \(C\), ...), Greek letters (\(\alpha\), \(\beta\), \(\gamma\), ...) and those kinds of letters with subscripts (\(A_1\), \(\alpha_1\), \(\varphi_{42}\), ...)
• logical connective symbols: \(\neg\), \(\land\), \(\lor\), \(\oplus\), \(\rightarrow\), \(\leftrightarrow\), \(\leftarrow\), \(\uparrow\), \(\downarrow\), \(\not\rightarrow\), \(\not\leftrightarrow\) and \(\not\leftarrow\)
• parenthesis: ( and )

This language has no terms and wffs are only one of the following:

• statement letters, or
• the open parenthesis symbol ( followed by the \(\neg\) symbol followed by a wff followed by the close parenthesis symbol ), or
• the open parenthesis symbol ( followed by a wff followed by a logical connective symbol other than "\(\neg\)" followed by a wff followed by the close parenthesis symbol )

Any wff containing at least one logical connective symbol is called a compound statement/proposition and the statement/s the connective applies to is/are called its substatement/s.

Remarks:

• Normally, I should put the symbols inside quotation marks or in italic to specify that they are elements of the object language, but to simplify the writing I'm assuming you are aware what symbols I'm talking about
• From here on, to simplify the writing I'll omit the word "symbol/s" from "elementary proposition symbol/s" and "logical connective symbol/s" when referring to them
• "\(\neg\)" is called a unary connective and all the other connectives of this language are called binary
• To aleviate the reading, I may use other types of parenthesis, as [ and ], or I may write them with different sizes. To convert to a proper wff, simply replace such open parenthesis by ( and close parenthesis by )
• Variables are placeholders/abbreviations for mathematical objects. In the context of Mathematical Logic, metavariables are metalinguistical variables that are placeholders for wffs from the formal language. As an abuse of notation, I may use elementary proposition symbols for metavariables instead, so whenever that happens, it shall be specified beforehand

Parenthesis

In order to render notation less cumbersome, we are going to agree on some metalinguistical conventions to eliminate parenthesis when referring to wffs. First, we may omit the outer pair of parentheses of a wff that isn't a statement letter. Second, we define an order of precedence for the connectives (from highest to lowest):

1. \(\neg\)
2. \(\land\)
3. \(\lor\)
4. \(\oplus\), \(\uparrow\), \(\downarrow\)
5. \(\rightarrow\), \(\leftarrow\), \(\leftrightarrow\), \(\not\rightarrow\), \(\not\leftarrow\), \(\not\leftrightarrow\)

Now, letting \(A\) and \(B\) be metavariables, here's a step-by-step process to restore parenthesis given this order of precedence:

1. Find the leftmost occurrence of the strongest connective that has not yet been processed (i.e. the strongest connective whose compound wff isn't yet surrounded by paranthesis)
2. If its wff is of the form \(\neg A\), convert it to \((\neg A)\)
3. If \(A \circ B\) is of the form \(\varphi_1 \circ...\circ \varphi_{n-1} \circ \varphi_n\), where the same logical connective \(\circ\) appears \(n\) times (at least once) in sequence and in the variables \(\varphi_k\), \(k\) ranges from 1 to \(n+1\), from right to left convert \(\varphi_k \circ \varphi_{k+1}\) to \((\varphi_k \circ \varphi_{k+1})\) for all \(k\) between 1 and \(n-1\)

Remarks:

• This order of precedence is purely conventional/arbitrary. We could agree on any order of precedence as long as we are in possession of an algorithm to rediscover the original wff from the abbreviated one
• This comment is for those who are not familiar with algebra or with the practice of using letters as variables to denote numbers (for those familiar with the existence of various number systems, here by numbers, I specifically mean natural numbers): here we used the letters \(n\) and \(k\) to denote numbers, \(n+1\) for the number that comes after \(n\) and \(n-1\) for the number that comes before \(n\), as is common practice in the mathematical litterature. Any other letters could have been used instead of \(n\) and \(k\) and it should always be clear from the context (blame the author otherwise) when letters are used to denote numbers

Another thing I could have done, this time to completely eliminate parenthesis from our language, would be to define wffs otherwise, through the use of Polish notation. In Polish notation, a wff would be

• a statement letter, or
• \(\neg\) followed by a wff, or
• a binary connective followed by two wffs

Polish notation may be harder for us humans to read, but it is much more compact. Thus, it would be a more suitable notation to define the length of wffs, if we were to study it.

Sigma notation

Sigma notation is another metalinguistical notation that we'll use to abbreviate the writing of wffs.

Let \(\circ\) denote a binary logical connective. Whenever one has expressions of the form \(\neg\neg...\neg A\) or \(A_1 \circ A_2 \circ...\circ A_n\), where the same connective appears \(n\) times (at least once) in sequence in a wff and in the variables \(A_i\), \(i\) ranges from 1 to \(n+1\) in that order, one may instead respectively write \(\mathop{\huge\neg}\limits_{i=1}^nA\) or \(\bigcomp\limits_{i=1}^{n+1}A_i\).