(Last modified Tue Jan 22 22:41 2008)
Propositional logic considers formulae made from the values "true" and "false" and variables representing those values. These values and variables may be combined using many operations, but we will restrict ourselves to the operations "not", "and", and "or". They are sufficient to express any other operations (such as "if ... then" or "if and only if").
We use the phrase "propositional logic" so frequently that we will abbreviate it as PL.
Figure 1
The various syntactic kinds of PL formulae are shown in Figure 1. They are:
Each of these is discussed in more detail below. Strictly speaking, nothing other than these can be a PL formula (although one sometimes sees other operations).
PL formulae have truth-values, either true or false (or unknown).
We will use metavariables in discussing PL syntax. A metavariable represents a syntactically-correct PL formula. We will write metavariables as α, β, γ, ... , α1, α2, ....
The two constants "true" and "false", which we will write as true and false, are syntactically-correct PL formulae.
The propositional variables, of which there is an unbounded supply and which we will write as A, B, C, ... , Z, A1, A2, ... , Aa, Ab, ... , are syntactically-correct PL formulae.
A propositional variable stands for a formula of the logic whose internal structure is not of importance to us. It represents either "true" or "false" but we may not know which.
If α is a PL formula, then its parenthesization, which we will write as (α) and pronounce "open paren alpha close paren", or whenever possible just "alpha" if no confusion would result, is also a syntactically-correct PL formula.
If α is a PL formula, then its negation, which we will write as ¬α and pronounce "not alpha", is also a syntactically-correct PL formula.
If α and β are PL formulae, then their conjunction, which we will write as α∧β, and pronounce "alpha and beta", is also a syntactically-correct PL formula.
α and β are called the conjuncts of the conjunction α∧β.
A mnemonic for ∧ is that it looks somewhat like the "A" in "And".
If α and β are PL formulae, then their disjunction, which we will write as α∨β, and pronounce "alpha or beta", is also a syntactically-correct PL formula.
α and β are called the disjuncts of the disjunction α∨β.
The symbol ∨ (it was originally just "v") was chosen because the Latin word for "or" is vel.
We use parentheses to show which operations are to be evaluated first, as in algebra. Also as in algebra, we use conventions to reduce the number of parentheses. The most common convention in logic is that anything in parentheses is evaluated first, then negation ¬ (like any unary operator), then conjunction ∧, and finally disjunction ∨.
Examples:
You will sometimes see other operations included as part of propositional logic, especially the material conditional "if ... then" (usually written →) and material equivalence "equivalent to" (usually written ↔ or ≡). We will not use them, primarily because they can cause confusion about cause and effect (which these operations do not expression), and confusion with the meta-relationships implication and equivalence.
It is not necessary to use material implication and equivalence because formulae involving them can be rewritten using ∧, ∨, and ¬. Specifically, for any formulae α and β,
α→β is equivalent to ¬α∨β,
and
α↔β is equivalent to (α∧β)∨(¬α∧¬β)
We will see below that these rewritings are semantically equivalent. Indeed, it can be shown that any truth-function on PL formulae can be written using ∧, ∨, and ¬, or even using just ∧ and ¬, or just ∨ and ¬.
