2 Formal Language

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.

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’.22 Abbott and Costello’s Who’s on First illustrates the risk of conflating use and mention.

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:

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.

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))\).

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.

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.

Semantics

We will use assignments of truth values to propositional variables in order to interpret the language of propositional logic.

We will declare a sentence of propositional logic to be true or false relative to an assignment of truth values to the propositional variables.

Truth under an Assignment

We define what is for a sentence to be true under an assignment \(A\):

We use truth tables to represent how the truth value of complex sentences depends on the truth values of their simpler sentences. The following truth tables summarize the semantic clauses for negation, conjunction, disjunction, and the material conditional.

Negation

Given a sentence \(\varphi\), the truth value of the negation \(\neg \varphi\) under an assignment is a function of the truth value of \(\varphi\) under the assignment.

⊕Truth table for \(\neg\) \[ \begin{array}{|c|c|} \hline \varphi & \neg \varphi \\ \hline T & F \\ F & T \\ \hline \end{array} \]

Conjunction

Given two sentences \(\varphi\) and \(\psi\), the truth value of the conjunction \((\varphi \wedge \psi)\) under an assignment is a function of the truth values of \(\varphi\) and \(\psi\) under the assignment.

⊕Truth table for \(\wedge\) \[ \begin{array}{|c|c|c|} \hline \varphi & \psi & (\varphi \wedge \psi) \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \\ \hline \end{array} \]

Disjunction

Given two sentences \(\varphi\) and \(\psi\), the truth value of the disjunction \((\varphi \vee \psi)\) under an assignment is a function of the truth values of \(\varphi\) and \(\psi\) under the assignment.

⊕Truth table for \(\vee\) \[ \begin{array}{|c|c|c|} \hline \varphi & \psi & (\varphi \vee \psi) \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{array} \]

Conditional

Given two sentences \(\varphi\) and \(\psi\), the truth value of the material conditional \((\varphi \wedge \psi)\) under an assignment is a function of the truth values of \(\varphi\) and \(\psi\) under the assignment.

⊕Truth table for \(\to\) \[ \begin{array}{|c|c|c|} \hline \varphi & \psi & (\varphi \to \psi) \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \hline \end{array} \]

We may use these rules to calculate the truth values of complex sentences of propositional logic relative to every assignment of truth values to its propositional variables.

⊕How to construct a truth table We want to develop a systematic procedure for constructing a complete truth table for a target sentence. We proceed in three steps:

1. We devote a column for each propositional variable occurring in a sentence followed by a column for each subsentence for the target sentence.

2. The number of propositional variables occurring in a sentence determines the number of rows for the truth table. Given \(n\) propositional variables, there are exactly \(2^n\) types of assignment to consider.44 That means that a truth table for a sentence containing \(3\) propositional variables will require \(8\) rows; one for a sentence containing \(4\) propositional letters will require \(16\) rows; etc. We start with the innermost column devoted to a propositional letter and we alternate occurrences of ‘\(T\)’ and ‘\(F\)’ until we populate the entire column. That is, \(2^0\) occurrences of ‘\(T\)’ followed by \(2^0\) occurrences of ‘\(F\)’. For the next column on the left, we alternate \(2^1\), e.g., \(2\) occurrences of ‘\(T\)’ with \(2^1\), e.g., \(2\) occurrences of ‘\(F\)’. More generally, for the \(n\)th column on the left of the innermost column devoted to a propositional letter, we alternate \(2^n\) occurrences of ‘\(T\)’ with \(2^n\) occurrences of ‘\(F\)’.

3. We populate each subsequent column for a subsetence of the target sentence as a function of the truth values for the relevant subsentences of it.

Tautology

A formula \(\varphi\) is a tautology if, and only if, \(\varphi\) is true under all assignments of truth values to propositional variables.

Contradiction

A formula \(\varphi\) is a contradiction if, and only if, \(\varphi\) is false under all assignments of truth values to propositional variables.

Equivalence

Two formulas \(\varphi\) and \(\psi\) are equivalent if, and only if, they are true under exactly the same assignments of truth values to propositional variables.

Consistency

A set of formulas is consistent if, and only if, there is at least one assignment of truth values to propositional variables under which all of its members are true. Otherwise, the set is inconsistent.

Validity

An argument is valid if, and only if, there is no assignment of truth values to propositional variables under which all of its premises are true while its conclusion is false. Otherwise, the argument is invalid.

⊕The Search for Counterexample Method

The method of truth tables is perfectly general, since it enables one to survey all assignments of truth values to the sentence letters involved in the argument. One issue, however, is that it may require one to draw very complex and cumbersome truth tables in cases in which more than 3 propositional variables are involved in the argument. A truth table for an argument in which 5 propositional variables occur requires \(2^5\), i.e., 32, rows; \(2^6\), i.e., 64 rows, if the argument involves 6 propositional variables, etc.

In those cases, we may proceed differently: we search for a counterexample. That is, we set out to construct an assignment on which the conclusion is false and the premises are true. There are two eventual outcoumes to this procedure. If we succeed, then the argument is invalid; if the construction of the assignment breaks down, then the argument is valid.

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)\)

4. Use the truth table method to determine whether each of the following sentences is a tautology, a contradiction, or neither a tautology or a contradiction.

   1. \(((p \vee q) \to \neg (p \to q))\)

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

   3. \(q \to (q \to p)\)

5. Use the truth table method to determine whether the following pairs of sentences are logically equivalent.

   1. \(p \to q\), \(q \wedge \neg (p \vee q)\)

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

6. Use the truth table method to determine whether the following sets of sentences are consistent.

   1. \(\{ p, q, \neg (p \wedge q)\}\)

   2. \(\{p \vee q, q \to r, \neg (p \wedge r)\}\)

7. Use the truth table method to determine whether the following arguments are valid.

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

   2. \(q \vee (p \wedge r)\)
      \(\neg q\)
      \(r\)

8. Use the search-for-counterexample method to determine whether the following arguments are valid.

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

   2. \((p \to q) \wedge (q \to p)\)
      \(\neg (p \wedge r)\)
      \(\neg (r \to s)\)
      \(s \to q\)