I'm going to be talking about propositional logic and how the laws of probability are its necessary, uniquely determined extension to deal with degrees of credence, so let's start by reviewing propositional logic. If you’re already familiar with propositional logic, you should at least skim this series of posts to get synced up on the terminology and notation I’m using.
Propositional logic1 has these main elements:
A language for expressing propositions, whether simple (atomic) propositions or more complex propositions formed by combining simpler ones.
The semantics of this language and the entailment relation ⊨, which defines what it means for a propositional formula A to be the logical consequence of some collection of proposition formulas Γ.
An algorithm for checking whether a sequence of propositional formulas ending with A is a valid proof that Γ ⊨ A.
This part discusses (1), and the remaining parts will discuss item (2). Item (3) is the subject of the propositional calculus.
What is a proposition?
A proposition is a statement (or claim, or assertion) that is objectively either true or false, although we may not know which. Here are some examples of propositions:
2 + 3 = 5.
5 – 7 = 10.
John F. Kennedy died on December 3, 1916.
The Earth’s diameter is less than 10,000 miles.
The Greek philosopher Socrates awoke between 6:22 a.m. and 6:41 a.m. local time in Athens on the morning of May 27, 412 B. C. (Gregorian calendar).
Propositions (2) and (3) are known to be false; propositions (1) and (4) are known to be true; and nobody knows whether proposition (5) is true.
The following, however, are not propositions:
Johnny is a big kid.
You should treat other people the way you would want them to treat you.
Braveheart is the best movie of all time.
Mary gets angry too quickly.
(1) is simply too vague — is 5 feet 8 inches enough to qualify as “big”? Is 170 pounds large enough? (2) and (4) are value statements, and (3) is an aesthetic judgment; all of these are subjective.
The example propositions discussed so far are all atomic propositions, meaning that they cannot be decomposed further into some combination of simpler propositions. Although they may in fact have some internal structure — “3 < 5” comprises the numbers “3” and “5” related by “<” — this internal structure is not accessible in propositional logic.
Logical operators
We can combine propositions to make more complex propositions, using logical operators. In describing these operators we will use the variables 𝐴 and 𝐵 to stand for any two propositions (they may even be the same proposition). Here are descriptions of the standard logical operators:
Not: ¬ 𝐴 is the proposition stating that 𝐴 is false. For example, ¬ (John’s birthday is in December) is the same as the proposition “John’s birthday is not in December.” If 𝐴 is true, then ¬ 𝐴 is false; if 𝐴 is false, then ¬ 𝐴 is true.
And: 𝐴 ∧ 𝐵 is the proposition stating that both 𝐴 and 𝐵 are true. That is, the proposition 𝐴 ∧ 𝐵 is true if both 𝐴 and 𝐵 are true, and is false if 𝐴 is false or 𝐵 is false. Some examples:
(dogs are mammals) ∧ (3 – 6 = 4) is the proposition stating that both “dogs are mammals” and “3 – 6 = 4” are true. This particular proposition is false: although “dogs are mammals” is true, “3 – 6 = 4” is false, and that’s enough to make the combined proposition false.
(triangles have three sides) ∧ (frogs are amphibians) is a proposition that is true, since “triangles have three sides” is true, and “frogs are amphibians” is also true.
Or: 𝐴 ∨ 𝐵 is the proposition stating that 𝐴 is true or 𝐵 is true (possibly both). That is, the proposition 𝐴 ∨ 𝐵 is true if at least one of the propositions 𝐴, 𝐵 are true; it is false only if both of them are false. Some examples:
(3 < 10) ∨ (3 > 0) is true, since both 3 < 10 and 3 > 0 are true.
(the moon is made of green cheese) ∨ (dogs are mammals) is true, since “dogs are mammals” is true.
(Einstein had 3 eyes) ∨ (the Earth is 3 miles across) is false, since Einstein assuredly did not have three eyes, and the Earth is much more than 3 miles across.
If … then (or implies): 𝐴 → 𝐵 is the proposition stating that if 𝐴 is true, then so is 𝐵. That is, 𝐴 → 𝐵 is false only if 𝐴 is true but 𝐵 is not; it is, by definition, true in all other cases. If we think of truth values as being ordered so that false < true, then the → operator is the equivalent of ≤ for truth values: 𝐴 → 𝐵 means “B is at least as true as A.” Some examples:
(3 > 5) → (3 > 4) is true, since 3 > 5 is false.
(5 > 3) → (5 > 2) is true, since 5 > 2 is true.
(5 > 3) → (3 > 4) is false, since 5 > 3 is true but 3 > 4 is false.
If and only if: 𝐴 ↔︎ 𝐵 is the proposition stating that either both 𝐴 and 𝐵 are true, or both 𝐴 and 𝐵 are false; put another way, 𝐴 ↔︎ 𝐵 says that 𝐴 is true if, and only if, 𝐵 is true. It is the equivalent of equality ( = ) for truth values. Some examples:
(𝑥 = 𝑦) ↔︎ (𝑦 = 𝑥) is true for any two numbers 𝑥 and 𝑦.
(dogs are mammals) ↔︎ (cheese is a food) is true, since both “dogs are mammals” and “cheese is a food” are true.
(triangles have four sides) ↔︎ (2 + 2 = 5) is true, since both “triangles have four sides” and 2 + 2 = 5 are false.
(there are 12 inches to a foot) ↔︎ (3 is a letter of the alphabet) is false, since “there are 12 inches to a foot” is true, but “3 is a letter of the alphabet” is false.
To recap, here’s a quick summary of the logical operators:
¬ 𝐴 means “not 𝐴,” or, equivalently, “𝐴 is false.”
𝐴 ∧ 𝐵 means “both 𝐴 and 𝐵 are true.”
𝐴 ∨ 𝐵 means “either 𝐴 or 𝐵 (or both) is true.”
𝐴 → 𝐵 means “A implies B,” or equivalently, “𝐵 is at least as true as 𝐴.”
𝐴 ↔︎ 𝐵 means “𝐴 if and only if 𝐵,” or equivalently, “𝐴 and 𝐵 are equally true.”
Propositional symbols
In formal logic we work with textual representations of propositions. A propositional symbol is one of a countably2 infinite set of symbols Σ that we use to represent atomic propositions. The members of the set Σ may themselves be sequences of characters from some character set not including the parentheses nor any of the logical operators. For example, Σ could be all nonempty sequences of lower-case alphabetic characters:
The set of propositional symbols Σ could even include character sequences such as
or
but beware! — despite their appearance, these strings are just names. As mentioned above, any internal structure of these strings is inaccessible to propositional logic.
Why infinitely many symbols?
Most presentations of propositional logic allow Σ to be finite, yet here I’m requiring it to be infinite. This will be important later on, as it allows a certain open-endedness; no matter how many propositional symbols we have already used, there are always more available for our use. We can endlessly extend our universe of discourse.
Propositional formulas
The most general textual representation of a proposition (in propositional logic) is a propositional formula, which is either
a propositional symbol s,
a text string of the form ¬ 𝐴,
a text string of the form (𝐴 ∧ 𝐵),
a text string of the form (𝐴 ∨ 𝐵),
a text string of the form (𝐴 → 𝐵), or
a text string of the form (𝐴 ↔︎ 𝐵),
where A and B are themselves propositional formulas. Here are some examples, assuming that the propositional symbols include any sequence of alphabetic characters:
When written for human consumption, we may omit some parentheses if this does not create ambiguity. In particular,
We write (𝐴 ∧ 𝐵 ∧ C) for ((𝐴 ∧ 𝐵) ∧ C); we write (𝐴 ∧ 𝐵 ∧ C ∧ D) for (((𝐴 ∧ 𝐵) ∧ C) ∧ D); and so on.
We write (𝐴 ∨ 𝐵 ∨ C) for ((𝐴 ∨ 𝐵) ∨ C); we write (𝐴 ∨ 𝐵 ∨ C ∨ D) for (((𝐴 ∨ 𝐵) ∨ C) ∨ D); and so on.
We write (𝐴 → 𝐵 → C) for (𝐴 → (𝐵 → C)); we write (𝐴 → 𝐵 → C → D) for (𝐴 → (𝐵 → (C → D))); and so on. Note that the operator → associates to the right, not to the left.
We may drop the outermost parentheses.
Typographic conventions
Note that we are using the following typographic conventions:
uppercase italic font (e.g., A) indicates a variable that is to be replaced with a propositional formula;
lowercase italic font (e.g., s) indicates a variable that is to be replaced with a propositional symbol; and
typewriter font indicates the actual, concrete text of a propositional symbol, e.g.
\(\mathtt{aPropositionalSymbol}.\)
Additional notation
When discussing propositional formulas in the abstract, we use the following notational conventions:
If we write A₁ ⋀ … ⋀ Aₙ then when n = 0 this is understood to stand for a tautology such as (a ⋁ ¬a), a propositional formula that is guaranteed to be true.
If we write A₁ ⋁ … ⋁ Aₙ then when n = 0 this is understood to stand for a contradiction such as (a ⋀ ¬a), a propositional formula that is guaranteed to be false.
We may use the alternate notations
\(\begin{eqnarray*} \bigwedge_{i=1}^n A_i &\stackrel{\mathrm{def}}{=} & A_1 \wedge \cdots \wedge A_n \\ \bigvee_{i=1}^n A_i &\stackrel{\mathrm{def}}{=} & A_1 \vee \cdots \vee A_n \end{eqnarray*}\)
More precisely, classical propositional logic; but we won’t be discussing any other sort.
An infinite set is countable if it has the same “size” as the set of all positive integers; that is, if desired, we could list its members one by one so we have a first member, a second member, a third member, and so on, without omitting any set member.