Semantics of Propositional Logic
SUMMARY
This class studies the semantics of propositional logic, specifically the assignment of truth values to an expression and how they propagate from one expression to another through logical connectors. The notion of truth tables is introduced, and the truth tables of derived connectors such as negation, disjunction, conjunction, implication, biconditional, and exclusive disjunction are shown. Additionally, the definition of an assignment over a set of atomic expressions is presented, and how it naturally extends over all expressions that can be constructed from that set is explained. Finally, the definitions of valid, satisfiable, and unsatisfiable expressions are established, and examples of tautologies and contradictions are provided. However, it is acknowledged that calculating truth tables for complex expressions can be inefficient, so alternative methods for solving validity or satisfiability problems are mentioned.
LEARNING OBJECTIVES:
By the end of this class, the student will be able to
- Explain the semantics of propositional logic
- Use truth tables to represent the assignments of truth values of expressions in propositional logic
- Model an expression with an assignment in propositional logic
- Apply the semantic rules of propositional logic to determine whether an expression is a tautology, contradiction, or contingency
INDEX
ABOUT TRUTH VALUE ASSIGNMENTS
SEMANTICS OF PROPOSITIONAL LOGIC CONNECTORS
ASSIGNMENTS IN PROPOSITIONAL LOGIC
MODELS IN PROPOSITIONAL LOGIC
AN EFFICIENCY PROBLEM LURKS IN THE SEMANTICS OF PROPOSITIONAL LOGIC
About Truth Value Assignments
We previously reviewed the syntax and deductive systems of propositional logic. While this served us to review how one expression can be derived from another, we have not yet discussed the assignment of truth values. Since we have already said everything there is to say about deduction techniques in propositional logic, we will begin our study on the semantics of propositional logic, where we review how truth value assignments propagate from one expression to another.
Semantics of Propositional Logic Connectors
The semantics of connectors is introduced through truth tables, as they provide a simple and organized way to represent all possible assignments on an expression.
Truth Table of Joint Denial
We will start with the most fundamental connector of all, which is joint denial. Its truth table is as follows:
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
The values “1” and “0” correspond to “True” and “False,” respectively. Each row in the truth table is a possible assignment on the variables (or atomic expressions) that make up the expression (or expressions) to be studied. Similarly, each column where an expression formed by these variables is located has the possible results of those assignments. Thus, the interpretation of this table tells us that \alpha\downarrow\beta is true only when \alpha and \beta are both false at the same time, and false otherwise. For this reason, the connector \downarrow is called joint denial.
Truth Tables of Derived Connectors
From the semantics of joint denial, the semantics of other connectors can be obtained through their definitions. These are:
| Negation: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Inclusive Disjunction: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Conjunction: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implication: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Biconditional: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Exclusive Disjunction: | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
From these definitions, it is possible to calculate the truth tables of the other connectors:
Negation
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
Hence the fact that the negation connector has the property of inverting the truth value of the expression it applies to.
Inclusive Disjunction
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
This is why the inclusive disjunction (or simply “disjunction”) between two expressions is true if at least one of the expressions is true, and false when both expressions are false simultaneously.
Conjunction
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
As a result, the conjunction between two expressions is true only if both expressions are true at the same time, and false otherwise. For this reason, an appropriate name for this connector could also be “joint affirmation.”
Implication
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Thus the truth table of implication summarizes the notion that a true expression can only imply a true expression, but a false one can imply anything.
Biconditional
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The biconditional forms a true expression whenever the two expressions that form it have the same truth values, and false otherwise.
Exclusive Disjunction
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The exclusive disjunction between two expressions is true when one, and only one of the expressions is true, and false otherwise.
Assignments in Propositional Logic
With the above described we have a simple notion of what an assignment is; however, for the developments we will see later, we will need something more precise. If S=\{A_1, A_2, \cdots, A_n\} is a set of atomic expressions and \mathcal{F}(S) is the set of all expressions that can be constructed from the expressions of S, then the following definition holds:
DEFINITION: An assignment over S is a function \mathcal{A}: S \longrightarrow \{0,1\}
In other words, an assignment over S provides a truth value to each atomic expression in S. An assignment \mathcal{A} of S naturally extends over all the elements of \mathcal{F}(S). If we have an expression F\in \mathcal{F}(S), then an assignment \mathcal{A} over S corresponds to a single row in the truth table of F and is said to be the truth value of F in that row.
An assignment \mathcal{A} of S can also be extended to certain expressions that are not in \mathcal{F}(S). If F_0 is an expression that is not in \mathcal{F}(S) and S_0 is the set of atomic subformulas of F_0, then if all extensions of \mathcal{A} to S\cup S_0 have the same value for F_0, then \mathcal{A}(F_0) is defined as that value.
EXAMPLE: If A and B are atomic expressions and \mathcal{A} is an assignment over \{A,B\} defined through \mathcal{A}(A)=1 and \mathcal{A}(B)=0, then:
\mathcal{A}(A\wedge B)=0 and \mathcal{A}(A\vee B)=1
And even though an assignment has not been made over a variable C, it can be said that:
\mathcal{A}(A\wedge (C\vee \neg C))=1 and \mathcal{A}(B\vee (C\wedge \neg C))=0
This happens with the last two expressions because, regardless of the assignment of C, it will always be the case that
\mathcal{A}(C\vee\neg C)=1 and \mathcal{A}(C\wedge\neg C)=0
Which we can quickly check by calculating their truth tables.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ End of Example
Models in Propositional Logic
Consider an assignment \mathcal{A} over a set of expressions S. If F\in S is such that \mathcal{A}(F)=1, then the assignment \mathcal{A} models F, or the expression F is sustained by the assignment \mathcal{A}, and we represent it through the notation
\mathcal{A}\models F.
And from this, the following definitions are established:
DEFINITION: An expression is said to be valid when it is sustained under any assignment. If F is valid, then it is written as \models F . Valid expressions are also called tautologies.
EXAMPLE: The expression (C\vee \neg C), which we have already seen, is a tautology.
■ End of Example
DEFINITION: An expression is said to be satisfiable if it is sustained by some assignment. Satisfiable expressions that are not tautologies are called contingencies.
DEFINITION: An expression is said to be unsatisfiable if it is not sustained by any assignment. Unsatisfiable expressions are called contradictions. If F is a contradiction, then it is written as \not\models F .
EXAMPLE: The expression (C\wedge \neg C), which we have already seen, is a contradiction..
■ End of Example
Examples of Tautologies and Contradictions
Suppose we want to see if an expression is valid or not. This question is a decision problem within the Semantics of Propositional Logic. A decision problem is any problem that, given certain input, results in a “yes” or “no.” If we are given an expression F and we ask whether it is valid or not, then we are facing a decision problem that we call a validity problem. Similarly, if we ask whether it is satisfiable or not, we are facing a satisfiability problem. In propositional logic, truth tables offer a systematic approach to solving these decision problems: if all possible truth values of F are “1,” then F is valid; if only some are “1,” then it is satisfiable; and finally, if all are “0,” then it is unsatisfiable.
EXAMPLE: Consider the expression ((A\wedge (A \rightarrow B)) \rightarrow B). To determine whether this expression is valid, satisfiable, or contradictory, we create its truth table.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
With this, we see that ((A\wedge(A\rightarrow B))\rightarrow B) has a truth value of “1” for all possible assignments, so the expression turns out to be a tautology.
■ End of Example
EXAMPLE: Now consider the expression (((A\rightarrow B)\rightarrow A)\wedge \neg A). The calculation of the truth table yields the following:
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
So the result is a contradiction.
■ End of Example
An Efficiency Problem Lurks in the Semantics of Propositional Logic
In theory, we can determine whether an expression is valid, contingent, or unsatisfiable simply by calculating its truth table, which is not particularly difficult; unfortunately, the ease of execution comes at the cost of efficiency. If we have an expression F composed of n atomic expressions, then we will have to calculate a truth table with 2^n rows; so, for example, if F is composed of 23 atomic expressions, then its truth table will have 8,388,608 rows that need to be calculated. Proceeding in this way, although mechanical and easy to perform, the calculation quickly becomes infeasible as the complexity of the expressions increases. For this reason, one of our future goals will be to find a way to solve validity or satisfiability problems without the need to calculate truth tables. The search for such methods is one of the central problems of any logic.