(Last modified Tue Jan 22 22:41 2008)
The semantics of PL formulae tells us how to determine the truth-value of any PL formula, with respect to some specific interpretation I. We will describe the semantics by showing how the truth-value of each syntactic kind of formula is determined by its parts, if any. Because we show how to determine the truth value for every way of constructing a PL formula (i.e., for constants, propositional variables, parenthesization of a subformula, negation of a subformula, conjunction of two subformulae, and disjunction of two subformulae — there are no other ways), we have shown how to determine the truth value of every PL formula — the semantics are complete.
α and β are assumed to be syntactically correct PL formulae.
The truth-value of each of the constants is its own value.
The truth-value of a propositional variable is the same as the truth-value of the sentence it refers to. An interpretation gives a truth-value to a sentence; without a specific interpretation, the truth-value of a propositional variable is unknown.
| Parenthesation | ||||||||
|---|---|---|---|---|---|---|---|---|
| α | (α) | |||||||
| true | true | |||||||
| false | false | |||||||
The truth-value of (α) is the same as the truth-value of α itself. The only effect of parentheses is to control the order in which operations are evaluated (or equivalently, to indicate the branching of the abstract syntax tree).
| Negation ("not") | ||||||||
|---|---|---|---|---|---|---|---|---|
| α | ¬α | |||||||
| true | false | |||||||
| false | true | |||||||
The truth-value of ¬α is the opposite of the truth-value of α.
The truth-value of a negated formula is summarized in the truth-table to the right.
| Conjunction ("and") | ||||||||
|---|---|---|---|---|---|---|---|---|
| α | β | α∧β | ||||||
| true | true | true | ||||||
| true | false | false | ||||||
| false | true | false | ||||||
| false | false | false | ||||||
A conjunction is true only if both its subformulae are true.
The truth-value of a conjunction is summarized in the truth-table to the right.
| Disjunction ("or") | ||||||||
|---|---|---|---|---|---|---|---|---|
| α | β | α∨β | ||||||
| true | true | true | ||||||
| true | false | true | ||||||
| false | true | true | ||||||
| false | false | false | ||||||
A disjunction is false only if both its subformulae are false.
The truth-value of a disjunction is summarized in the truth-table to the right.
The semantics above specifies the truth-value for any syntactically correct PL formula. For each formula, the semantics give a rule for determining the truth-value of the formula, usually from the truth-value(s) of its subformula(s).
Let's consider an example: true∧(¬false∨¬true). We will write our results in tabular form, as below. In this table, we will write down the result of each operation whose result we know; for neatness, we will put each result under its operation symbol. For clarity, in this table we have numbered the rows on the left and put an explanation of each row on the right.
| true | ∧ | ( | ¬false | ∨ | ¬true | ) | Explanation | |
|---|---|---|---|---|---|---|---|---|
| 1. | true | false | ¬false is true; ¬true is false | |||||
| 2. | true | true∨false is true | ||||||
| 3. | true | true∧true is true |
We can see the values of true and false immediately, so there is no need to write them down again. The first subformulae we can work out, beyond true and false, are ¬false and ¬true; we write their results beneath them in row 1. Having done that, we can work out ¬false∧¬true, which we now know is the same as true∧false, and we write the result under the ∨. Now we know enough to evaluate the entire formula, and we write the final answer under the ∧.
Once we have learned how to follow this method, we need not number the rows nor explain each row, and we would produce a table such as the one below. While we could write all the results in the same row, this makes it difficult to check our work later, so we continue to use a new row for each step.
| true | ∧ | ( | ¬false | ∨ | ¬true | ) |
|---|---|---|---|---|---|---|
| true | false | |||||
| true | ||||||
| true |
We have seen truth tables for the basic operations so far; but it is certainly possible to write a truth table for any formula, or for other operations. The example in the previous section was written using constants, but can be generalized to use metavariables instead: α∧(¬β∨¬γ).
| α | β | γ | ¬β | ¬γ | ¬β∨¬γ | α∧(¬β∨¬γ) |
|---|---|---|---|---|---|---|
| true | true | true | false | false | false | false |
| true | true | false | false | true | true | true |
| true | false | true | true | false | true | true |
| true | false | false | true | true | true | true |
| false | true | true | false | false | false | false |
| false | true | false | false | true | true | false |
| false | false | true | true | false | true | false |
| false | false | false | true | true | true | false |
There is a straightforward way to write a formula that matches a particular truth table, namely by examining the table, writing a conjunction (∧) for each true row, then joining the conjunctions with ∨. (This is disjunctive normal form.)
The conjunction for a true row will contain each name that is true for that row, and the negation of each name that is false.
If there are no true rows, then the formula is simply false.
For example:
| α | β | ?? | explanation |
|---|---|---|---|
| true | true | false | (this row is false so we ignore it) |
| true | false | true | True row. α is true, and β is false, so α∧¬β |
| false | true | true | True row. α is false, and β is true, so ¬α∧β |
| false | false | false | (this row is false so we ignore it) |
The disjunction of the conjunctions for each true row is (α∧¬β) ∨(¬α∧β). This is a formula that matches the truth table.
This method works for any truth table of any size.
| If ... then | ||||||||
|---|---|---|---|---|---|---|---|---|
| α | β | α→β | ||||||
| true | true | true | ||||||
| true | false | false | ||||||
| false | true | true | ||||||
| false | false | true | ||||||
Material implication is a troublesome operation because it seems to be connected with causality, yet (because propositional logic abstracts everything but truth values and logical structure) causality has no effect on its truth value.
Material implication of β by α is written α→β and pronounced "if alpha, then beta." Unlike the binary logic operations we have already seen, material implication is not commutative and its two operands have separate names: α is called the antecedent and β the consequent. α→β is true unless α is false and β is true.
Material implication is easily confused with the meta-concept of semantic consequence; when material implication is used, semantic consequence is often what is intended. To avoid this confusion, use the logically equivalent ¬α∨β instead of α→β, and if ¬α∨β does not seem right, consider using the meta-operation of semantic consequence instead.
| If and only if | ||||||||
|---|---|---|---|---|---|---|---|---|
| α | β | α↔β | ||||||
| true | true | true | ||||||
| true | false | false | ||||||
| false | true | false | ||||||
| false | false | true | ||||||
Material bi-implication is a troublesome operation because it seems to be connected with causality in both directions, yet (because propositional logic abstracts everything but truth values and logical structure) causality has no effect on its truth value.
Material bi-implication of α and β is written α↔β or α≡β and pronounced "alpha if and only if beta." α↔β is true unless α and β have different truth-values.
Material implication is easily confused with the meta-concept of logical equivalence; when material implication is used, logical equivalence is often what is intended. To avoid this confusion, use the logically equivalent (α∧β)∨(¬α∧¬β) instead of α↔β, and if (α∧β)∨(¬α∧¬β) does not seem right, consider using the meta-operation of logical equivalence instead.
