This module delves into the construction of a formal logical system from the ground up. We will build a complete propositional calculus, exploring its primitive symbols, formation rules, axioms, and the proofs of its most fundamental properties.
1. Object Language and Metalanguage
This study unit follows the construction of a formal system, or logical calculus, designed to handle arguments based on how sentences are truth-functionally compounded. Unlike natural languages like English, which evolve organically, a formal language must be deliberately constructed.
When we build this formal language, we need a way to talk about it. This creates a crucial distinction:
- The Object Language is the formal language we are constructing and studying. Initially, its symbols and formulas are just meaningless marks.
- The Metalanguage is the language we use to describe and give meaning to the object language. In this module, our metalanguage will be English.
It's important to note that these terms are relative. We can use English (a metalanguage) to study the grammar of Japanese (an object language), or we could use Japanese to study the grammar of English.
The Liar's Paradox and Language Levels
Consider the famous, syntactically correct sentence:
This sentence is false.(1)
This leads to a contradiction: if (1) is true, then what it says is the case, so it must be false. But if (1) is false, then it is false that it is false, which makes it true.
The contradiction arises because the sentence is trying to be part of the object language (a statement) and the metalanguage (a statement about a statement) at the same time. By strictly separating these levels, the paradox dissolves. The object language contains statements, while the metalanguage contains statements like "'Sentence X' is false."
The primary reason for distinguishing between an object language and a metalanguage in formal logic is to:
2. Primitive Symbols and Well-Formed Formulae (WFFs)
A logistic system begins with a set of basic units, or primitive symbols. Our system starts with just four operator symbols, which are initially meaningless marks that we will later interpret.
~ (the "tilde")Represents "not." For example, if A stands for "It is raining," then ~A will represent "It is not raining."
• (the "dot")Represents "and." If A is "It is raining" and B is "It is cold," then A•B will represent "It is raining and it is cold."
( and )Parentheses are used to group expressions and avoid ambiguity, just like in mathematics. For example, ~ (A•B) ("It is not the case that both A and B are true") is different from (~A)•B ("A is false and B is true").
In addition to operators, our system requires two kinds of symbols:
- Operator Symbols: The four symbols defined above:
~•() - Propositional Symbols: We require an infinite supply. We will use the first four capital letters of the Roman alphabet in bold, with or without subscripts:
A, A₁, A₂, A₃, ...B, B₁, B₂, B₃, ...C, C₁, C₂, C₃, ...D, D₁, D₂, D₃, ...
A 'formula' is any sequence of these symbols, such as B₁~((A)• or C₃)))((. However, we are only interested in sequences that are grammatically correct, which we call Well-Formed Formulae (WFFs).
Recursive Definition of a WFF
Since there are infinitely many WFFs, we cannot list them all. Instead, we provide a recursive definition—a set of rules that can be repeatedly applied to generate all possible WFFs.
- Any propositional symbol is a WFF.
- If any formula
Pis a WFF, then~(P)is a WFF. - If any formulae
PandQare both WFFs, then(P)•(Q)is a WFF.
(No formula of the object language is a WFF unless it can be derived from the above rules.)
This definition provides an effective procedure for checking if any formula is a WFF. Let's analyze an example:
Is
~((A)•(~(B)))a WFF?
- The entire formula,
~((A)•(~(B))), is a WFF by rule (b) if((A)•(~(B)))is a WFF. ((A)•(~(B)))is a WFF by rule (c) ifAand~(B)are both WFFs.Ais a WFF by rule (a).~(B)is a WFF by rule (b) ifBis a WFF.Bis a WFF by rule (a).
Since we have successfully broken the formula down into its basic components using only the allowed rules, we can conclude: Yes, it is a WFF.
According to the recursive definition of a WFF, which of the following is NOT a well-formed formula?
3. Interpretation and Notational Conventions
Now we begin to interpret our system, which we'll call R.S. (for 'Rosser's System', after the logician J. Barkley Rosser). We intend for ~(P) to stand for negation and (P)•(Q) for conjunction. With just these two operators, we want our system to be functionally complete—that is, able to express every possible truth-functional compound statement.
To make the system easier to use, we introduce abbreviations in our metalanguage (Syntax Language). These abbreviations do not exist in the object language itself.
- Disjunction (v):
P v Qis an abbreviation for~((~(P))•(~(Q))). In natural language, this is the inclusive "or". "P or Q" means P is true, or Q is true, or both are true. - Conditional (⊃):
P ⊃ Qis an abbreviation for~((P)•(~(Q))). This represents the "if... then..." statement. "If P, then Q." (For a refresher, see our module on truth-functional connectives.) - Equivalence (≡):
P ≡ Qis an abbreviation for(P ⊃ Q)•(Q ⊃ P). This is the "if and only if" connective, meaning P and Q have the same truth value. It's a mutual conditional: P implies Q, and Q implies P.
Notational Conventions
To reduce clutter, we adopt two conventions:
- Parentheses can be replaced by square brackets
[]or curly bracesfor readability. - An order of precedence is established for operators, reducing the need for parentheses. The operator with the widest scope (highest precedence) is on the left:≡ ⊃ v • ~;
For example, P ⊃ Q v R•S is unambiguous. The ⊃ has the widest scope, followed by v, then •. It is interpreted as: P ⊃ [Q v (R•S)].
When an expression contains multiple instances of the same connective, we use the convention of association to the left. This means the rightmost occurrence has the widest scope. For example, P ⊃ Q ⊃ R is interpreted as [ (P ⊃ Q) ⊃ R ].
Example: "Undoing" an Abbreviation
Let's rewrite P v ~P in terms of only primitive symbols.
- P v ~P
- ~((~(P)) • (~(~P))) (by definition of 'v')
This final form uses only the primitive symbols ~, •, and parentheses, along with the propositional variable P.
4. Functional Completeness
We have shown that R.S. can express several truth functions (negation, conjunction, disjunction, etc.). But to be functionally complete, it must be able to express all possible truth functions.
A truth function's value is completely determined by the truth values of its arguments. We can define any truth function with a truth table. For a single argument P, there are exactly four possible truth functions (unary functions):
| P | f1(P) |
|---|---|
| T | F |
| F | T |
| P | f2(P) |
|---|---|
| T | T |
| F | F |
| P | f3(P) |
|---|---|
| T | F |
| F | F |
| P | f4(P) |
|---|---|
| T | T |
| F | T |
R.S. can express all of these:
f1(P)is expressible as~P. (Negation)f2(P)is expressible asP. (Affirmation)f3(P)(always false) is expressible asP•~P. (Contradiction)f4(P)(always true) is expressible as~(~(P•~P)). (Tautology)
Similarly, there are 16 possible truth functions for two arguments (binary functions), and 256 for three arguments. It can be proven that R.S. can express every single one. This proof shows that for any truth table, no matter how many variables it has, we can construct an equivalent WFF in R.S. using only ~ and •. This leads to our first major theorem about the system:
Metatheorem I: R.S. is functionally complete.
What does it mean for a set of logical operators to be 'functionally complete'?
5. Axioms and Demonstrations
To build a deductive system, we need starting points (axioms) and rules for moving from one point to another (rules of inference). To simplify proofs, we can assume infinitely many WFFs as axioms, as long as they fit specific patterns.
The Axioms of R.S.
P ⊃ (P•P)Natural Language Meaning: "If P is true, then 'P and P' is true." This is a version of the Law of Tautology, establishing a basic property of conjunction.
(P•Q) ⊃ PNatural Language Meaning: "If 'P and Q' are true, then P is true." This is the fundamental principle of Simplification.
(P ⊃ Q) ⊃ [~(Q•R) ⊃ ~(R•P)]Natural Language Meaning: This axiom is a complex version of Transposition (or Modus Tollens). It essentially states that if P implies Q, then if Q and R cannot both be true, then R and P cannot both be true.
These are axiom schemata; any WFF that has one of these forms is an axiom. For example, (A•B) ⊃ A and ((C⊃D)•~F) ⊃ (C⊃D) are both instances of Axiom 2.
The Rule of Inference
R.S. has only one rule of inference:
- Rule 1 (R1): From
PandP ⊃ Q, inferQ. (Modus Ponens)
A demonstration of an argument's validity is a sequence of WFFs where each line is either a premise, an axiom, or follows from two preceding lines by R1. A theorem is the conclusion of a demonstration that uses only axioms as premises. We use the symbol ⊢ (turnstile) to indicate a theorem, e.g., ⊢ Q.
This setup creates a "symbolic machine" that generates theorems. A key question is whether this machine is consistent and sound. A system is analytic if all of its theorems are tautologies.
Metatheorem II: R.S. is analytic.
This is proven by showing that the axioms are all tautologies and that the rule of inference (Modus Ponens) preserves tautologousness (i.e., if you apply it to tautologies, you get another tautology).
Corollary: R.S. is consistent.
Since R.S. is analytic, it can only prove tautologies. The formula P•~P ("P and not-P") is a contradiction, not a tautology, so it cannot be proven as a theorem. A system that contains a formula it cannot prove is consistent. For example, it's impossible for our system to prove "It is raining and it is not raining."
6. Independence of the Axioms
An important property of an axiom set is independence, which means that no axiom can be derived as a theorem from the others. To prove an axiom is independent, we need to find a characteristic such that:
- The axiom in question lacks the characteristic.
- All other axioms have the characteristic.
- The characteristic is hereditary with respect to the rules of inference (i.e., the rules can't produce a formula without the characteristic from formulas that have it).
We can't use "being a tautology" because all our axioms have that characteristic. Instead, we can use a three-valued logic model with values 2. We can think of 0 as our "designated" or "true-like" value.
By carefully defining truth tables for ~ and • in this three-valued system, we can show that Axioms 2 and 3 will always evaluate to 0 (they have the characteristic), but for certain inputs, Axiom 1 evaluates to 1 (it lacks the characteristic). This proves Axiom 1 is independent. The process can be repeated with different three-valued models to prove the independence of Axioms 2 and 3 as well.
7. Development and Deductive Completeness
From our three axioms and one rule of inference, we can now derive a vast number of theorems and new, valid rules of inference (Derived Rules). This is the process of developing the calculus. We start by proving foundational theorems like ⊢ ~(~P•P) and ⊢ ~~P ⊃ P (Double Negation).
Crucially, we can prove a metatheorem that greatly simplifies this process:
Metatheorem III: The Deduction Theorem
If we can demonstrate Q from a set of premises including P, then we can demonstrate P ⊃ Q from the other premises alone. This theorem justifies the method of Conditional Proof. For example, if you assume "it is raining" (P) and from that prove "the ground is wet" (Q), the Deduction Theorem allows you to conclude "If it is raining, then the ground is wet" (P ⊃ Q).
With the Deduction Theorem and other derived rules, we can eventually prove all 19 of the standard Rules of Inference and Replacement used in introductory logic. This shows that our minimal system is surprisingly powerful.
The final question is whether our system is powerful enough. A system is deductively complete if all its tautologies are provable as theorems.
Metatheorem X: R.S. is deductively complete.
This is the converse of Metatheorem II. Together, they establish that the set of theorems in R.S. is exactly the same as the set of all tautologies.
Conclusion
By establishing that R.S. is analytic (Metatheorem II) and deductively complete (Metatheorem X), we have created a solution to the decision problem for propositional calculus. The method of truth tables provides an effective procedure for deciding whether any WFF is a tautology, and since the tautologies are precisely the theorems, truth tables can decide whether any WFF is a theorem of the system. We have successfully built a consistent, complete, and sound system for propositional logic from first principles.