OLI - 2. Syntax and symbolization

All and only the following are _____:

1. The capital letters we use to symbolize atomic sentences, called atomic formulae or occasionally sentential letters: A, B, C, and so on (possibly with numeric subscripts).

2. The symbols for the logical connectives: &, ∨, →, and ¬.

3. The parentheses used to disambiguate the scope of the connectives: ( and ).

Any finite sequence or string of basic symbols.

1. Every atomic formula φ is a formula of sentential logic.

2. If φ is a formula of sentential logic, then so is ¬φ.

3. If φ and ψ are formulae of sentential logic, then so are each of the following:

   1. (φ&ψ)

   2. (φ∨ψ)

   3. (φ→ψ)

4. An expression φ of sentential logic is a formula only if it can be constructed by finitely many applications of the first three rules.

A formula ψ is a subformula of a formula φ if and only if ψ appears (as a node) in the parse tree of φ.

1. First, insert parentheses around every occurrence of & and its two conjuncts, starting with the rightmost & and ending with the leftmost,

2. Next, insert parentheses in the same fashion for each ∨ and its two disjuncts, from rightmost occurrence first, to the leftmost occurrence last,

3. Finally, insert parentheses for each →, and its antecedent and consequent, from rightmost occurrence first, to the leftmost occurrence last,

As you follow this procedure, keep in mind that parentheses are never inserted around negations, and that a single parenthesis should never be inserted within another set, i.e., do not break up any existing pairs of parentheses with ones you insert.