Well-formed Formula - Propositional Calculus

Propositional Calculus

The formulas of propositional calculus, also called propositional formulas, are expressions such as . Their definition begins with the arbitrary choice of a set V of propositional variables. The alphabet consists of the letters in V along with the symbols for the propositional connectives and parentheses "(" and ")", all of which are assumed to not be in V. The formulas will be certain expressions (that is, strings of symbols) over this alphabet.

The formulas are inductively defined as follows:

• Each propositional variable is, on its own, a formula.
• If φ is a formula, then φ is a formula.
• If φ and ψ are formulas, and • is any binary connective, then ( φ • ψ) is a formula. Here • could be (but is not limited to) the usual operators ∨, ∧, →, or ↔.

This definition can also be written as a formal grammar in Backus–Naur form, provided the set of variables is finite:

::= p | q | r | s | t | u | ... (the arbitrary finite set of propositional variables)

::= | | () | () | () | ()

Using this grammar, the sequence of symbols

(((p q) (r s)) (q s))

is a formula, because it is grammatically correct. The sequence of symbols

((p q)(qq))p))

is not a formula, because it does not conform to the grammar.

A complex formula may be difficult to read, owing to, for example, the proliferation of parentheses. To alleviate this last phenomenon, precedence rules (akin to the standard mathematical order of operations) are assumed among the operators, making some operators more binding than others. For example, assuming the precedence (from most binding to least binding) 1. 2. 3. 4. . Then the formula

(((p q) (r s)) (q s))

may be abbreviated as

p q r s q s

This is, however, only a convention used to simplify the written representation of a formula. If the precedence was assumed, for example, to be left-right associative, in following order: 1. 2. 3. 4., then the same formula above (without parentheses) would be rewritten as

(p (q r)) (s ((q) (s)))