2 Formal Language

The language of propositional logic will allow us to model and study the validity of an important class of argument forms underwritten by the behavior of propositional connectives such as ‘not’, ‘and’ and ‘or’. To describe the language of propositional logic, we will specify:

  • a syntax for the formal language, which will include a vocabulary of symbols used in the language and a set of grammatical rules designed to specify which sequences of symbols are counted as sentences of the language, and

  • a semantics for the formal language, which will explain how to interpret the language and what is for a sentence to be true under such an interpretation.

But first, we need some preliminaries.

Quotation and Metavariables

Notice that in order to describe a language, whether formal or natural, we will have to be able to refer to its expressions. When the target is a natural language such as English, we use quotation marks in order to mention a linguistic expression.

Example 2.1 The expression ‘Los Angeles’ is used in one of the two sentences below, and it is mentioned the other:

Los Angeles is composed of more than eighty cities.

‘Los Angeles’ is composed of two words.

The contrast we seek is between the use of a natural language expression to mean what it means in natural language and the mere mention of that expression to mean the expression itself, not what it means in natural language. In the former example, the name in question is used in the first sentence to mean what it ordinarily means in natural language, i.e., a city in southern California, but the name is merely mentioned in the second sentence to mean the very linguistic expression composed of two different words, e.g., ‘Los’ and ‘Angeles’.2 Abbott and Costello’s Who’s on First illustrates the risk of conflating use and mention.

Example 2.2 The Arabic numeral ‘1’ is used in one of the sentences below and it is mentioned in the other:

‘1’ is an Arabic numeral for the successor of 0.

1 is the remainder of 7 divided by 3.

Quotation marks afford us the means to mention a natural language expression and to discuss its linguistic features, but we sometimes seek to make generalizations over linguistic expressions. We may want to express the fact that whenever something is an English sentence, the concatenation of the expression ‘it is not the case that’ and that sentence form another sentence of English. One way to do this is to use Greek letters as metavariables to range over sentences:

Example 2.3 Greek letters may be used as metavariables over sentences of English in the two sentences below:

If \(\varphi\) is a sentence of English, then the concatenation of the expression ‘it is not the case that’ and \(\varphi\) is another sentence of English.

If we let \(\varphi\) be the sentence ‘water is H2O’ then the expression ‘it is not the case that \(\varphi\)’ is the sentence ‘it is not the case that water is H2O’.3 To ease notation, we may use ‘it is not the case that \(\varphi\)’ as an abbreviation for the concatenation of ‘it is not the case that’ and \(\varphi\).

We will reserve the use of quotation marks for expressions of natural language in order to avoid confusion between use and mention. That means that we will avoid the use quotation marks for expressions of the formal language unless, that is, there is a risk of confusion. On the other hand, we will make frequent use Greek letters as metavariables for expressions of the formal language being introduced.

Syntax

We will now specify the syntax of propositional logic in two stages. We will first specify the vocabulary of the language, and we will then explain how to combine the symbols of the language in order to produce sentences of the language.

Vocabulary The vocabulary of propositional logic contains three types of symbols:

Propositional Variables

These are the lowercase letters \(p\), \(q\), \(r\), \(s\), and \(t\) with or without numerical subscripts: \[ p, q, r, s, t \]

Connectives

These symbols formal counterparts of the natural language connectives ‘not’, ‘or’, ‘and’, and ‘if \(\dots\), then \(\dots\)’: \[ \neg, \vee, \wedge, \to \]

Parentheses

There are two parentheses: \[ ), ( \]

Nothing else is a symbol of the language.

Grammar

The role of grammar for a language is to explain how to combine symbols of the vocabulary into sentences of the language. For propositional logic, we use three main clauses for the characterization of formula. They explain how to generate more complex formulas from simpler formulas with the help of a connective.

Formula

We define what is for an expression to be a formula of propositional logic.

  1. All propositional variables are formulas.
  2. If \(\varphi\) and \(\psi\) are formulas, then each of \[ \neg \varphi, (\varphi \wedge \psi), (\varphi \vee \psi), (\varphi \to \psi) \] is a formula.
  3. Nothing else is a formula.

It will be helpful to look at concrete uses of the characterization in order to justify the fact that certain sequences of symbols are, or not, formulas of propositional logic.

The construction tree for the formula \((p \vee (q \to \neg r))\).

Example 2.4 The expression below is a formula: \[ (p \vee (q \to \neg r)) \] Here is a brief justification:

By rule 2, the expression \((p \vee (q \to \neg r))\) is a formula if both the expression \(p\) and the expression \((q \to \neg r)\) are formulas.
By rule 1, the expression \(p\) is a formula.
By rule 2, the expression \((q \to \neg r)\) is a formula if both the expression \(q\) and the expression \(\neg r\) are formulas.
By rule 1, the expression \(q\) is a formula.
By rule 2, the expression \(\neg r\) is a formula if \(r\) is a formula.
By rule 1, the expression \(r\) is a formula.

Therefore, we conclude that \((p \vee (q \to \neg r))\) is a formula.

The definition may similarly be used to justify the fact that a given string of symbols is not a sentence of propositional logic.

There is no available construction tree.

Example 2.5 The expression below is not a formula of propositional logic: \[ \neg (p \to A) \]

By rule 2, the expression \(\neg (p \to A)\) is a formula if the expression \((p \to A)\) is a formula.
By rule 2, the expression \((p \to A)\) is a formula if both the expression \(p\) and the expression \(A\) are formulas.
By rule 1, the expression \(p\) is a formula.
By rule 3, the expression \(A\) is not a formula, since it is neither a propositional variable nor the outcome of one of the procedures described by rule 2.

Therefore, by rule 3, \(\neg (p \to A)\) is not a formula.

We have explained how to construct complex formulas from simpler ones by means of very strict formation rules. Such sentences may sometimes become difficult to parse and tedious to write. For ease of expression, we will adopt a further notational conventions which will allow us to simplify notation. This is not meant as a revision of the official characterization of formula as it is not part of the official syntax of the language. The point of the rule instead is to allow us to use certain expressions as abbreviations for the official formulas of the language.

Notational Convention

We may remove the outer parentheses from a formula that is not part of another formula.

Example 2.6 We are able to use the expression \[ p \to q \] is an abbreviation for the formula \[ (p \to q) \]

Example 2.7 We are similarly able to remove the outer parentheses of the formula: \[ ((p \vee q) \vee r) \] to obtain: \[ (p \vee q) \vee r. \] as an abbreviation of the first formula.

Exercises

  1. Add quotation marks to the following sentences in order to obtain a true sentence of English. If there is more than one solution, make sure to explain why.

    1. Los Angeles names a city in Southern California.

    2. Los is part of Los Angeles.

    3. Snow is white is a grammatical sentence of English.

    4. What is monosyllabic but whatever is polysyllabic.

  2. Determine whether each of the following expressions is a sentence of propositional logic.

    1. \(\neg \neg A\)

    2. \((p \to (\neg q))\)

    3. \((p)\)

    4. \((q \to (\neg \neg p \vee r))\)

  3. Determine whether each of the following expressions is an abbreviation for a sentence of propositional logic.

    1. \(p \to (q \wedge r)\)

    2. \(p \to q \to r\)

    3. \(p \vee (q \wedge r)\)

    4. \(p \to (q\wedge r \to q)\)