Formal Logic/Sentential Logic/Formal Syntax

From Wikibooks, open books for an open world
< Formal Logic‎ | Sentential Logic
Jump to: navigation, search
← The Sentential Language ↑ Sentential Logic Informal Conventions →



Formal Syntax[edit]

In The Sentential Language, we informally described our sentential language. Here we give its formal syntax or grammar. We will call our language \mathcal{L_S}\,\!.

Vocabulary[edit]

  • Sentence letters: Capital letters 'A' – 'Z', each with (1) a superscript '0' and (2) a natural number subscript. (The natural numbers are the set of positive integers and zero.) Thus the sentence letters are:
\mathrm{A^0_0},\ \mathrm{A^0_1},\ ...,\ \mathrm{B^0_0},\ \mathrm{B^0_1},\ ...,\ ...,\ \mathrm{Z^0_0},\ \mathrm{Z^0_1},\ ...\,\!
  • Sentential connectives:
\land,\ \lor,\ \lnot,\ \rightarrow,\ \leftrightarrow\,\!
  • Grouping symbols:
(,\ )\,\!

The superscripts on sentence letters are not important until we get to the predicate logic, so we won't really worry about those here. The subscripts on sentence letters are to ensure an infinite supply of sentence letters. On the next page, we will abbreviate away most superscripts and subscripts.

Expressions[edit]

Any string of characters from the \mathcal{L_S}\,\! vocabulary is an expression of \mathcal{L_S}\,\!. Some expressions are grammatically correct. Some are as incorrect in \mathcal{L_S}\,\! as 'Over talks David Mary the' is in English. Still other expressions are as hopelessly ill-formed in \mathcal{L_S}\,\! as 'jmr.ovn asgj as;lnre' is in English.

We call a grammatically correct expression of \mathcal{L_S}\,\! a well-formed formula. When we get to Predicate Logic, we will find that only some well formed formulae are sentences. For now though, we consider every well formed formula to be a sentence.

Formation rules[edit]

An expression of \mathcal{L_S}\,\! is a well-formed formula of \mathcal{L_S}\,\! if and only if it is constructed according to the following rules.

i. A sentence letter is a well-formed formula.
ii. If \varphi\,\! and \psi\,\! are well-formed formulae, then so are each of:
\mbox{ii-a.}\ \ \lnot \varphi\,\!
\mbox{ii-b.}\ \ (\varphi \land \psi)\,\!
\mbox{ii-c.}\ \ (\varphi \lor \psi)\,\!
\mbox{ii-d.}\ \ (\varphi \rightarrow \psi)\,\!
\mbox{ii-e.}\ \ (\varphi \leftrightarrow \psi)\,\!

In general, we will use 'formula' as shorthand for 'well-formed formula'. Since all formulae in \mathcal{L_S}\,\! are sentences, we will use 'formula' and 'sentence' interchangeably.

Quoting convention[edit]

We will take expressions of \mathcal{L_S}\,\! to be self-quoting and so regard

(\mathrm{P^0_0} \rightarrow \mathrm{Q^0_0})\,\!

to include implicit quotation marks. However, something like

(1) \quad (\varphi \rightarrow \psi)\,\!

requires special consideration. It is not itself an expression of \mathcal{L_S}\,\! since \varphi\,\! and \psi\,\! are not in the vocabulary of \mathcal{L_S}\,\!. Rather they are used as variables in English which range over expressions of \mathcal{L_S}\,\!. Such a variable is called a metavariable, and an expression using a mix of vocabulary from \mathcal{L_S}\,\! and metavariables is called a metalogical expression. Suppose we let \varphi\,\! be \mathrm{P^0_0}\,\! and \psi\,\! be (\mathrm{Q^0_0} \lor \mathrm{R^0_0})\ .\,\! Then (1) becomes

(\,\!'\mathrm{P^0_0}\,\!' \rightarrow (\,\!'\mathrm{Q^0_0}\,\!' \lor\,\!'\mathrm{R^0_0}\,\!'))\,\!

which is not what we want. Instead we take (1) to mean (using explicit quotes):

the expression consisting of '(\,\!' followed by \varphi\,\! followed by '\rightarrow\,\!' followed by \psi\,\! followed by ')\,\!' .

Explicit quotes following this convention are called Quine quotes or corner quotes. Our corner quotes will be implicit.

Additional terminology[edit]

We introduce (or, in some cases, repeat) some useful syntactic terminology.

  • We distinguish between an expression (or a formula) and an occurrence of an expression (or formula). The formula
((\mathrm{P^0_0} \land \mathrm{P^0_0}) \land \lnot \mathrm{P^0_0})\,\!

is the same formula no matter how many times it is written. However, it contains three occurrences of the sentence letter \mathrm{P^0_0}\,\! and two occurrences of the sentential connective \land\,\!.

  • \psi\,\! is a subformula of \varphi\,\! if and only if \varphi\,\! and \psi\,\! are both formulae and \varphi\,\! contains an occurrence of \psi\,\!. \psi\,\! is a proper subformula of \varphi\,\! if and only if (i) \psi\,\! is a subformula of \varphi\,\! and (ii) \psi\,\! is not the same formula as \varphi\,\!.
  • An atomic formula or atomic sentence is one consisting solely of a sentence letter. Or put the other way around, it is a formula with no sentential connectives. A molecular formula or molecular sentence is one which contains at least one occurrence sentential connective.
  • The main connective of a molecular formula is the last occurrence of a connective added when the formula was constructed according to the rules above.
  • A negation is a formula of the form \lnot \varphi\,\! where \varphi\,\! is a formula.
  • A conjunction is a formula of the form (\varphi \land \psi)\,\! where \varphi\,\! and \psi\,\! are both formulae. In this case, \varphi\,\! and \psi\,\! are both conjuncts.
  • A disjunction is a formula of the form (\varphi \lor \psi)\,\! where \varphi\,\! and \psi\,\! are both formulae. In this case, \varphi\,\! and \psi\,\! are both disjuncts.
  • A conditional is a formula of the form (\varphi \rightarrow \psi)\,\! where \varphi\,\! and \psi\,\! are both formulae. In this case, \varphi\,\! is the antecedent, and \psi\,\! is the consequent. The converse of (\varphi \rightarrow \psi)\,\! is (\psi \rightarrow \varphi)\,\!. The contrapositive of (\varphi \rightarrow \psi)\,\! is (\lnot\psi \rightarrow \lnot\varphi)\,\!.
  • A biconditional is a formula of the form (\varphi \leftrightarrow \psi)\,\! where \varphi\,\! and \psi\,\! are both formulae.

Examples[edit]

(1) \quad (\lnot(\mathrm{P^0_0} \lor \mathrm{Q^0_0}) \rightarrow (\mathrm{R^0_0} \land \lnot \mathrm{Q^0_0}))\,\!

By rule (i), all sentence letters, including

\mathrm{P^0_0},\ \mathrm{Q^0_0},\ \mbox{and}\ \mathrm{R^0_0}\ ,\,\!

are formulae. By rule (ii-a), then, the negation

\lnot \mathrm{Q^0_0}\,\!

is also a formula. Then by rules (ii-c) and (ii-b), we get the disjunction and conjunction

(\mathrm{P^0_0} \lor \mathrm{Q^0_0}),\ \mbox{and}\ (\mathrm{R^0_0} \land \lnot \mathrm{Q^0_0})\,\!

as formulae. Applying rule (ii-a) again, we get the negation

\lnot(\mathrm{P^0_0} \lor \mathrm{Q^0_0})\,\!

as a formula. Finally, rule (ii-c) generates the conditional of (1), so it too is a formula.


(2) \quad ((\mathrm{P^0_0} \lnot \land \mathrm{Q^0_0}) \lor \mathrm{S^0_0})\,\!

This appears to be generated by rule (ii-c) from

(\mathrm{P^0_0} \lnot \land \mathrm{Q^0_0}),\ \mbox{and}\ \mathrm{S^0_0}\ .\,\!

The second of these is a formula by rule (i). But what about the first? It would have to be generated by rule (ii-b) from

\mathrm{P^0_0}\lnot\ \mbox{and}\ \mathrm{Q^0_0}\ .\,\!

But

\mathrm{P^0_0}\lnot\,\!

cannot be generated by rule (ii-a). So (2) is not a formula.


← The Sentential Language ↑ Sentential Logic Informal Conventions →