3. Semantics of Propositional Logic

To use propositional logic in the study of logical arguments, we have to give some meaning to the formulas we introduced in the last lecture. This meaning is called the semantics of the language.

Defining the Connectives

Our goal is to determine how to evaluate the truth value of any formula given some truth assignment to the propositional variables.

The first step in doing so is to determine how our logical connectives are defined.

Negation (not)

The negation operator \(\neg\) flips the truth value of the negated proposition. That is, when \(\phi\) is True, then \(\neg \phi\) is False. And when \(\phi\) is False, then \(\neg \phi\) is True. We can represent this information more concisely with a truth table.

Conjunction (and)

The conjunction operator \(\wedge\) is also defined in the intuitive way: \(\phi \wedge \psi\) is True if and only if \(\phi\) and \(\psi\) are both True. Once again, we can represent this definition with a truth table.

Disjunction (or)

The formula \(\phi \vee \psi\) is True if and only if at least one of the formulas \(\phi\), \(\psi\) is True:

Note that this connective evaluates to True when both \(\phi\) and \(\psi\) is True. This differs from the exclusive-or (or “xor”) connective that evaluates to True if and only if exactly one of \(\phi\) and \(\psi\) is True. In common speech, “or” is sometimes used to mean “exclusive-or”, but in this course we will always use it to mean only the (inclusive) disjunction connective defined in the table above.

Conditional (if-then)

The conditional connective is defined in the following way: the formula \(\phi \to \psi\) is True if and only if it is not the case that \(\phi\) is True and \(\psi\) is False:

The conditional connective is a little bit trickier than the previous ones. So it’s worth pausing a little bit to consider it carefully. Below is a logic puzzle due to Wason. Try to answer it directly, and then see how you can justify (or correct!) your answer using the conditional connective and its truth table above.

We have a set of cards, where each card has a letter on one side and a number on the other.

I claim that if a card has an A on one side, then it has the number 5 on the other side.

The following four cards are on the table:

Which cards do you need to turn over to see if all four cards agree with my claim?

Biconditional (iff)

The biconditional connective is defined by setting \(\phi \leftrightarrow \psi\) to be True whenever \(\phi\) and \(\psi\) both evaluate to the same value:

The name “biconditional” highlights the close connection of the \(\leftrightarrow\) connective with the conditional connective: \(\phi \leftrightarrow \psi\) is True if and only if \(\phi \to \psi\) and \(\psi \to \phi\) are both True. (We will see how to prove that this connection is valid in the next lecture.)

Truth Assignments

A truth assignment to the set \(P\) of propositional variables is a function

where \(T\) and \(F\) represent True and False, respectively.

We can obtain a truth value for each formula from a truth assignment. This truth value is a function \(v^* \colon L^p(\sigma) \to \{T, F\}\) that assigns the value True or False to every formula based on the truth assignment \(v\) to the propositional variables.

The function \(v^*\) is defined recursively as follows:

Definition. For a fixed truth assignment function \(v\) on all the propositional variables, the truth value

\[v^* \colon L^p(\sigma) \to \{T, F\}\]

is defined in the following way:

• If \(\phi = \pi\) for some propositional variable \(\pi\), then \(v^*(\phi) = v(\pi)\);
• If \(\phi = \neg \psi\), then \(v^*(\phi) = \neg v^*(\psi);\)
• If \(\phi = (\psi \wedge \theta)\) then \(v^*(\phi) = v^*(\psi) \wedge v^*(\theta);\)
• If \(\phi = (\psi \vee \theta)\) then \(v^*(\phi) = v^*(\psi) \vee v^*(\theta);\)
• If \(\phi = (\psi \to \theta)\) then \(v^*(\phi) = v^*(\psi) \to v^*(\theta);\) and
• If \(\phi = (\psi \leftrightarrow \theta)\) then \(v^*(\phi) = v^*(\psi) \leftrightarrow v^*(\theta).\)

In each of the last five cases, the values of \(\neg v^*(\psi)\) and \(v^*(\psi) \,\square\, v^*(\theta)\) for \(\square \in \{\wedge, \vee, \to, \leftrightarrow\}\) are all computed as per the connective definitions from the last section.

Building Truth Tables

The truth table of a formula gives its truth value under all possible truth assignments to the propositional variables that it includes. (We can also construct even larger truth tables for a formula that include the truth assignments to other propositional variables as well, though those assignments never affect the truth value of the formula.)

In practice, we can construct the truth table for any formula using an iterative approach. As we describe this approach, we also illustrate it with the example formula \((p \wedge q) \leftrightarrow (p \to \neg r))\).

A formula with \(n\) distinct propositional variables will have \(2^n\) rows, one for each of the possible truth assignment combinations to those variables.

The first \(n\) columns of the table contain the truth assignments for each of the propositional variables. We begin by copying these columns under each of the instances of the variables in the formula:

In the next step, whenever we have a subformula \(\neg \phi\) with the value of \(\phi\) already entered in the table, we use the definition of the negation connective above to fill in the column under the \(\neg\) symbol. (This column represents the value of the \(\neg \phi\) formula itself.) Similarly, whenever we have a subformula \((\phi \,\square\, \psi)\) for some binary connective \(\square\) where \(\phi\) and \(\psi\) have already been evaluated, we fill in the truth table for the formula under the connective symbol.

In the example, we see that we can fill in the truth table for the \((p \wedge q)\) and \(\neg r\) subformulas, as such:

(The greying out of entries in the table is not necessary. I am doing it in this example for clarity since the columns that have been used to evaluate a new column will not be needed in future evaluations.)

We then repeat the last step with any connective symbol whose corresponding subformulas have been evaluated in the truth table. In our example, there is one connective that satisfies this condition: the $\to$ symbol.

We can now finally complete the truth table for the formula by filling in the column of the last remaining connective:

This iterative process of filling in the truth table corresponds to computing the truth tables of the formulas in each node in the parse tree for the final formula. As you can verify by examining the parse tree of the example formula we just considered, we start by computing the truth table of the leaves of the tree, then work up the tree layer by layer until we compute the truth table at the root of the tree to obtain our final truth table.

Satisfiability, Tautologies, and Contradictions

A satisfying assignment of a formula \(\phi\) is a truth assignment that causes \(\phi\) to evaluate to True.

A formula is satisfiable if it has at least one satisfying assignment. Or, in other words, if there is at least one row of its truth table that evaluates to True.

Examples:

• \(((p \wedge q) \leftrightarrow (p \to \neg r))\) is satisfiable.

  As seen above, the truth assignment defined by \(v(p,q,r) = (T,T,F)\) is one of the three satisfying assignments of this formula.

• \(((((p_1 \wedge \neg p_2) \wedge \neg p_3) \wedge p_4) \wedge p_5)\) is satisfiable.

  The truth assignment \(T, F, F, T, T\) is the unique satisfying assignment of this formula.

• \((\neg(p \to q) \to p)\) is satisfiable.

  Every truth assignment satisfies this formula.

A tautology is a formula where every truth assignment to its propositional variables is a satisfying assignment. Equivalently, a formula is a tautology when all the rows of its truth table evaluate to True.

Examples:

• \((\neg(p \to q) \to p)\) is a tautology.

  Note that every tautology is satisfiable, but that some satisfiable formulas (such as the first two examples above) are not tautologies.

• \((p \vee \neg p)\) is a tautology.
• \((\neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q))\) is a tautology.

A contradiction is a formula that is not satisfiable. The truth table of a contradiction has False entries on every row.

Examples:

• \(\neg(\neg(p \to q) \to p)\) is a contradiction.

  More generally, whenever \(\phi\) is a tautology, \(\neg \phi\) is a contradiction.

• \((p \wedge \neg p)\) is a contradiction.