Semantics

Introduction

So far, we have learned the formal syntax of the language of sentential logic, but as yet, we have talked only informally about how to interpret and evaluate the formulae of sentential logic. In this chapter, we learn the SEMANTICS of sentential logic, which will provide us with the tools, techniques, and vocabulary we need to interpret and evaluate not only individual formulae, but also inferences as they are represented in sentential logic.

GOALS FOR THIS CHAPTER:

Truth Assignments and Truth Tables

Introduction

As we have already mentioned, our primary interest in sentential logic has to do with the TRUTH-VALUES of the formulae of sentential logic. We have already learned how the basic expressions of sentential logic combine, in accordance with the syntactic rules, to form compound formulae. The syntactic rules thus allow us to determine, for any particular expression, whether or not that expression constitutes a grammatical formula of sentential logic. Similarly, the semantic rules for sentential logic will allow us to determine the truth-value of any formula, given that we know the truth-values of all the atomic formulae involved.

Great, but what if we don't know the truth-values of all the atomic formulae? Well, we can still determine what the truth-value of the formula will be for any possible assignment of truth-values to atomic formulae. Such an assignment of truth-values to atomic formulae is, appropriately enough, known as a TRUTH-VALUE ASSIGNMENT.

Definition:

A TRUTH-VALUE ASSIGNMENT consists of an assignment of a truth-value (either true or false) to every atomic sentence of sentential logic, not just those atomic formulae that appear in some particular formula.

Okay, so this means that we can determine the truth-value of any formula of sentential logic, relative to a given truth-value assignment. Obviously, if our formula is an atomic sentence, all we need to do is to see what truth-value it has been assigned in order to determine what its truth-value is on that assignment. What about compound formulae? You may recall that we've mentioned that the logical connectives are all TRUTH-FUNCTIONAL.

Definition:

This means that the truth-value of a compound formula is a FUNCTION of the truth-values of its components.

In order to see how this works, we should go on to take a look at the semantics of the connectives.

Truth Tables for the Connectives

We have already discussed, though informally, the truth-functions we take to correspond to our logical connectives. So far, we have relied only on an intuitive understanding of the truth-functions our connectives represent, but it is now time to make explicit the truth-functions at work, as well as to provide a formal means, known as TRUTH-TABLES, for representing them.

Recall our first example of a conjunction from the previous chapter:

Now, this sentence would be considered to be true just in case it was true both that John ran, and that Mary laughed. If John didn't run, the conjunction would be false, and similarly if Mary didn't laugh. This intuitive and informal understanding of the TRUTH-CONDITIONS of the conjunction, that a conjunction is true just in case both of its conjuncts are true, and false otherwise, is precisely what we want to capture formally. We can do this in a tabular form, by specifying the truth-value of a conjunction for each possible combination of truth-values that the two conjuncts can take on. Here's the truth-table for this particular conjunction:

J M J & M
TTT
TFF
FTF
FFF

After looking only briefly at the above truth-table, it should be pretty clear what is going on, but it can't hurt to go through it explicitly in any case.

In our truth-table, we have three columns: One for the conjunction itself, plus one for each of the two atomic formulae appearing in the conjunction. As for rows, this truth-table has four (not including the header row, where we specify the atomic formulae and the compound formula), just enough to include every possible combination of the truth-values T (for true) and F (for false) that the two atomic formulae can have. The entries in the conjunction's column specify the truth-value of the conjunction given that the conjuncts have the truth-values indicated in the same row.

Each of the rows in the truth-table thus represents a set of truth-value assignments—the set of truth-value assignments where the atomic formulae listed in the truth-table are assigned the truth-values specified on that row. The first row of the truth-table thus represents all truth-value assignments where the atomic formulae J and M are both assigned the truth-value T. This includes the truth-value assignment where J, M, and, say, R are all assigned the truth-value T as well as the truth-value assignment where J and M are assigned T, but R is assigned F, and so on for every atomic formula not mentioned in the truth-table.

Now, in the truth-table above, we listed some specific atomic formulae. The truth-table thus tells us what the truth-value of the conjunction of those two particular atomic formulae will be on any truth-value assignment. We would like, however, to have a way to represent the relationship between the truth-value of a conjunction and the truth-values of its conjuncts in a general way, rather than just specific instances of the relationship, like in the example above. We can do this with a truth-table by using variables in place of specific formulae for the conjuncts, as follows:

P Q P & Q
TTT
TFF
FTF
FFF

This truth-table, since it doesn't mention any specific formulae, we call the CHARACTERISTIC truth-table for conjunction.

So far, we have only seen the characteristic truth-table for conjunction. We should go on and take a look at the truth-tables for the other connectives, then we will be able to see how to construct a truth-table for any formula of sentential logic.

Here's the truth-table for disjunction:

P Q P v Q
TTT
TFT
FTT
FFF

The truth-table specifies that a disjunction is true on any truth-value assignment where either one or both of the disjuncts is true, and false just in case both of the disjuncts are false. Recall our example disjunction from the last chapter:

EXAMPLE:

The truth-table tells us that this sentence will be false only if it is both false that John ran, and false that Mary laughed. If either of the two disjuncts is true (including the case where both disjuncts are true), on the other hand, then the sentence as a whole will be true as well.

Moving on to the last of our binary connectives, here is the truth-table for the conditional:

P Q P → Q
TTT
TFF
FTT
FFT

As you can see, a conditional is false just in case its antecedent is true, and its consequent false. If either the antecedent is false or the consequent true, then the conditional as a whole will be true.

Our final connective is negation. Since negation is a unary connective, we only have one component formula to worry about in the truth-table. The characteristic truth-table for negation will thus have only two rows, since the single formula can be either true or false. Here's the truth-table itself:

P ¬P
TF
FT

Now that we've seen the truth-tables for each of the connectives, we can go on to learn how to use truth-tables to semantically evaluate any formula of sentential logic.

Using Truth Tables

The first thing we need to know with respect to using truth-tables is just how the characteristic truth-tables for the connectives allow us to determine the truth-value of a particular formula on a given truth-value assignment. There's actually a rather handy way to do that using parse trees, which we did promise in the last chapter would have semantic, as well as syntactic applications, after all. Let's take a look and see how:

Now that we know how to use the characteristic truth-tables for the connectives in combination with the parse tree for a formula to determine that formula's truth-value on a given assignment, let's continue on to see how we can construct a truth-table for the formula that specifies its truth-value on any truth-value assignment.

In order to construct a truth-table for an arbitrary formula of sentential logic, the first thing you need to do is to count the number of different sentential letters that occur as subformulae of the formula as a whole. This will tell you how many rows you are going to need in your truth-table. As we have seen, if there's only a single atomic formula, you'll need two rows, and with two atomic formulae, you'll need four rows. See if you can determine how many rows you'd need for larger numbers of atomic formulae, then read on.

Now that you've thought about it, you've likely realised that every additional atomic formula involved is going to double the number of rows you'll need in your truth-table. Thus, for a formula containing three atomic formulae, you need a truth-table with eight rows, for four you'd need sixteen rows, five atomic formulae would require thirty two rows, and so on. Actually, you need 2 to the power of n rows in a truth-table for a formula containing n different atomic formulae as subformulae.

Once you know how many rows you need, you can begin to construct your truth-table by setting out the rows and columns.

EXAMPLE:
(P & Q) → ¬R

Pretty simple, actually. We have now determined the truth-value of our formula (P & Q) → ¬R on every possible truth-value assignment. We just have to find the row where the truth-values assigned to P, Q, and R match the assignment we're interested in, and the above truth-table will tell us whether our formula is true or false on that assignment.

Let's take a look at one more example, just to make sure we have the hang of it all. Consider the following:

That's all there is to it. Now that we know how to construct a truth-table for any formula, why don't we head on to the next section, where we will take a look at the formal version of what we have learned so far about the semantics of sentential logic.

Formal Semantics

So far, we've had a good look at truth-tables and how to use them, but we haven't yet done anything in the way of formally stating the semantics of sentential logic. We should take a moment at this point to present a formal definition of truth with respect to a truth-value assignment, much as we formally stated the syntactic rules in the last chapter.

Without further ado, here it is:

  1. If P is an atomic formula (sentential letter) of sentential logic, then P is true on a truth-value assignment A just in case A assigns the value T to P, and false otherwise.
  2. If P is a formula of the form ¬Q, then P is true on a truth-value assignment A just in case Q is false on A, and false otherwise.
  3. If P is a formula of the form Q & R, then P is true on a truth-value assignment A just in case both Q and R are true on A, and false otherwise.
  4. If P is a formula of the form Q v R, then P is true on a truth-value assignment A just in case either Q is true on A or R is true on A, and false otherwise.
  5. If P is a formula of the form QR, then P is true on a truth-value assignment A just in case either Q is false on A or R is true on A, and false otherwise.

There you have it. You'll note that the truth-conditions specified in the above formal definition match those provided informally by the characteristic truth-tables for the connectives precisely.

Believe it or not, this one little definition gives us everything we need to determine the truth-value of any formula on a given truth-value assignment. We have yet to consider the situation with respect to all truth-value assignments, however, so we really should proceed to the next section in order to do just that.

Properties of Formulae

So far, all the formulae for which we have constructed truth-tables have turned out to be true on some truth-value assignments, and false on others. Such formulae are called CONTINGENT, since their truth-values depend on the particular truth-value assignment under consideration.

Definition:

A CONTINGENT FORMULA is true on some truth-value assignments and false on others.

There are also formulae, however, that turn out to be true on every possible truth-value assignment, and similarly, some that turn out to be false on every possible truth-value assignment. As an example of the former, here's the truth-table for the formula: P v ¬P

P P v ¬P
TTF
FTT

As you can see, this formula turns out to be true on every possible truth-value assignment, i.e., on every row of its truth-table.

Definition:

Formulae that are true on all truth-value assignments are called TAUTOLOGIES.

You've probably already realised that the negation of any tautology is going to be false on every truth-value assignment, but here's the truth-table for the negation of our tautology P v ¬P to demonstrate this:

P ¬ ( P v ¬P
TFTF
FFTT

Definition:

Formulae that are false on every truth-value assignment are known as CONTRADICTORIES.

Of course, not all contradictories are negations of tautologies, as the following example demonstrates:

P P & ¬P
TFF
FFT

The negation of this formula, on the other hand, is a tautology, since it will be true on every possible truth-value assignment.

Now that we've learned how to semantically classify individual formulae of sentential logic, and how to use truth-tables to determine the classification of a particular formula, it's time to move ahead and take a look at inference from a semantic perspective.

Arguments and Validity

As you will recall from the introduction, we consider an inference to be a good argument just in case its premises are all true, and those premises furthermore support the conclusion. The kind of support we are most interested in is, of course, deductive validity, which we can now characterise in terms of truth-value assignments to the inferences involved.

Definition:

An inference is DEDUCTIVELY VALID (or SOUND) just in case any truth-value assignment that makes all the premises of the argument true also makes the conclusion true. An inference will thus be INVALID just in case it is not valid, i.e., if there is some truth-value assignment that makes the premises of the argument true, but the conclusion false.

Now that we know how to use truth-tables to determine the truth-value of a formula on any truth-value assignment, we can apply this technique to the premises and conclusion of an argument, symbolised as formulae of sentential logic, in order to determine with certainty whether or not an argument is valid. We just need to be careful to ensure that we take into consideration all the right truth-value assignments.

Consider the following conversation:

EXAMPLE:
HilbertHilbert: It's raining outside.
GodelGodel: If it's raining outside, then Kant won't stop at the grocery store to buy ice cream.
SocratesSocrates: If Kant doesn't stop at the grocery store to buy ice cream, then we will have to settle for cookies for dessert.
HilbertHilbert: Alas, we will thus have to settle for cookies for dessert.

Interpreting this as an argument, we can symbolise it as follows:

R
R → ¬K
¬K → S

S

We can make a truth-table for all the premises plus the conclusion by first noting the atomic formulae that occur as subformulae of any premise or of the conclusion, then setting up the truth-table for all such atomic formulae. We include a column for each of the premises and also the conclusion. Here's what the resulting table looks like:

R K S R ( R ¬K ) ( ¬K S ) S
TTTTFFFTT
TTFTFFFTF
TFTTTTTTT
TFFTTTTFF
FTTFTFFTT
FTFFTFFTF
FFTFTTTTT
FFFFTTTFF

In order to determine whether the argument is valid or not, we now look for any rows in this truth-table where all the premises are true. In this case, there is only one such row—the third one—and the conclusion is true on this row, so the argument is shown to be valid.

Counterexamples

Put text here

Exercises

Exercise: 3.1

Construct truth-tables for each of the following formulae:

  1. P & (Q v ¬P)
  2. ¬P → Q
  3. Q v ¬(P & Q)
  4. P → ¬(P & Q)
  5. P → (P v Q)
  6. Q → (P → Q)
  7. P & ¬P
  8. (Q v P) & ¬P

Exercise: 3.2

Construct truth-tables for each of the following formulae:

  1. P → (Q & R)
  2. P v (R → ¬Q)
  3. (Q & R) v (¬Q v ¬R)
  4. P → (Q → ¬R)
  5. (P → Q) & (R → Q)
  6. (P v ¬P) & (¬Q & R)
  7. Q → (R → (¬Q & P))
  8. R & ((P → ¬R) & (¬P → ¬R))

Exercise: 3.3

Construct truth-tables for each of the following formulae:

  1. (S → R) v (Q & ¬P)
  2. (P → Q) → (R → S)
  3. ¬(P & S) → (Q v R)
  4. (P & (Q v ¬P)) → (R v S)

Exercise: 3.4

For each of the above formulae, indicate whether it is a tautology, contigent, or contradictory.

Exercise: 3.5

Determine whether each of the following arguments is valid or invalid. If it is invalid, specify a truth-value assignment that provides a counterexample:

i
P & Q
¬P v R

Q & R
ii
D → (C & ¬E)
A & D

¬E & A
iii
J → K
¬J

¬K
iv
H & (B v C)
B → ¬C

H → C
v
A v C
A → T

T & C
vi
F & ¬(B v C)
G → B

F & ¬G
vii
A v (B v C)
A → P
B → P

P & C
viii
D v E
¬D v (E → C)

C
ix
J & ¬N
K → ¬J

N → ¬K
x
A → B
B → A

(A & B) v (¬A & ¬B)
xi
P → (Q & R)
Q → T
R → S

P → (S & T)
xii
P v ¬R
R v ¬Q

Q → ¬P

Exam