Skip to main content

Truth of Formulas

In propositional logic, the truth or falsity of a complex formula depends on two things:

  1. The truth of falsity of each atomic proposition that appears in the formula; and
  2. The rules for assigning:
    • truth or falsity to conjunctions given the truth or falsity of the conjuncts;
    • truth or falsity to disjunctions given the truth or falsity of the disjuncts;
    • truth or falsity to negations given the truth or falsity of the negated formula; and
    • truth or falsity to conditionals given the truth or falsity of the antecedent and consequent.

For instance, suppose you want to determine whether P∧(Q∨R)P\wedge (Q\vee R) is true or false. The main connective is ∧\wedge, so the formula is a conjunction. The left conjunct is PP and the right conjunct Q∨RQ\vee R. The right conjunct is a disjunction, where QQ is the left disjunct QQ and RR is the right disjunct RR. So, to determine the truth or falsity of P∧(Q∨R)P\wedge (Q\vee R) we need answers to the following questions:

  1. Is PP true or false? Is QQ true or false? Is RR true or false?
  2. What is the rule to determine whether a disjunction is true or false given the truth or falsity of the disjuncts?
  3. What is the rule to determine whether a conjunction is true or false given the truth or falsity of the conjuncts?

We start by introducing notation to represent truth and falsity.

Truth Values

The symbols "T\mathsf{T}" (true) and "F\mathsf{F}" (false) are called truth values. When a formula XX is true, we write "XX is T\mathsf{T}" and say "the truth value assigned to XX is T\mathsf{T}" (or more simply "XX is true"). When a formula XX is false, we write "XX is F\mathsf{F}" and say "the truth value assigned to XX is F\mathsf{F}" (or more simply "XX is false").

Note that some texts use other symbols for the truth values:

  • Instead of T\mathsf{T}, some texts use 11 or ⊤\top for true.
  • Instead of F\mathsf{F}, some texts use 00 or ⊥\bot for false.
note

The letters "TT" and "FF" may be used as atomic propositions. We differentiate these letters from truth values by the font. E.g., "TT" is an atomic proposition and "T\mathsf{T}" is the truth value "true", and "FF" is an atomic propositions and "F\mathsf{F}" is the truth value "false". In general, to avoid confusion we will try to avoid using "TT" and "FF" in formulas.

An assignment of truth values to the atomic propositions is called a truth value function.

Truth Value Function

A truth value function, also called a truth value assignment, for a collection of atomic propositions is an assignment of truth values to each atomic proposition in the collection.

Describing Truth Assignments

There are two ways to describe a truth value function for a collection of atomic propositions. The first is to list the truth values assigned to each atomic proposition. For example, a truth value assignment for the atomic propositions P,QP, Q and RR is:

PP is T\mathsf{T}, QQ is F\mathsf{F} and RR is T\mathsf{T}.

The second way to describe a truth value function is to list all the atomic propositions and write the truth values underneath each atomic proposition:

PPQQRR
T\mathsf{T}F\mathsf{F}T\mathsf{T}

So, a truth value assignment is a table where each column consists of an atomic proposition in the first row (the header) and the assigned truth value in the second row below the atomic proposition.

Different truth value functions represent different situations or possibilities. For instance, suppose that there are three piles of cards and each pile contains exactly two cards:

  1. Pile 1 contains two cards that are gray on one side and blue on the other side. On the blue side, one of the cards has an "AA" on it and the other is blank.
  2. Pile 2 contains two cards that are gray on one side and red on the other side. On the red side, one of the cards has an "KK" on it and the other is blank.
  3. Pile 3 contains two cards that are gray on one side and green on the other side. On the green side, one of the cards has an "QQ" on it and the other is blank.

Suppose that a dealer selects three cards, one from each pile, and places them face down on the table. The dealer can distribute the cards in different ways. Each way of dealing the cards is a different situation. The key observation is that each situation is completely described by specifying which of the following atomic propositions are true and which ones are false:

  • AA: the card from pile 1 has an AA on it.
  • KK: the card from pile 2 has a KK on it.
  • QQ: the card from pile 3 has a QQ on it.

How many situations can be created by dealing the cards?

In this example, we identified three atomic propositions (AA, KK and QQ) that are used to describe a deal of the cards. Of course, there are many other aspects about the scenario that we are ignoring: E.g., Did the dealer look at the cards before selecting them, or was the choice of cards random? Are the cards on the table or is someone holding them? What color shirt is the dealer wearing? Are the lights on in the room? If any of these are relevant to evaluate the truth of a proposition, then we must include an atomic proposition describing that aspect of the scenario.

Truth Tables for the Connectives#

The truth value of a complex formula is determined by its main connective.

Conjunction#

The sentence "Ann and Bob got an A in PHIL 171" is true when both "Ann got an A in PHIL 171" and "Bob got an A in PHIL 171" are true; otherwise the sentence is false. The suggests the following characterization:

Truth of Conjunctions

For any formula XX, if the main connective of XX is ∧\wedge, then XX is true when both conjuncts are true; otherwise XX is false.

Thus, the truth value of P∧QP\wedge Q is determined as follows:

  1. If PP is true and QQ is true, then P∧QP\wedge Q is true.
  2. If PP is true and QQ is false, then P∧QP\wedge Q is false.
  3. If PP is false and QQ is true, then P∧QP\wedge Q is false.
  4. If PP is false and QQ is false, then P∧QP\wedge Q is false.

More generally, truth values are assigned to conjunctions as follows:

Truth Table for Conjunction

Suppose that XX and YY are formulas. The truth value assigned to X∧YX\wedge Y is determined by the following table:

XXYYX∧YX \wedge Y
T\mathsf{T}T\mathsf{T}T\mathsf{T}
T\mathsf{T}F\mathsf{F}F\mathsf{F}
F\mathsf{F}T\mathsf{T}F\mathsf{F}
F\mathsf{F}F\mathsf{F}F\mathsf{F}

Disjunction#

The sentence "Ann or Bob got an A in PHIL 171" is true when either Ann got an A in PHIL 171 or Bob got an A in PHIL 171; otherwise the sentence is false. The suggests the following characterization:

Truth of Disjunctions

For any formula XX, if the main connective of XX is ∨\vee, then XX is true when at least one of the disjuncts is true; otherwise XX is false.

the truth value of P∨QP\vee Q is determined as follows:

  1. If PP is true and QQ is true, then P∨QP\vee Q is true.
  2. If PP is true and QQ is false, then P∨QP\vee Q is true.
  3. If PP is false and QQ is true, then P∨QP\vee Q is true.
  4. If PP is false and QQ is false, then P∨QP\vee Q is false.

More generally, truth values are assigned to disjunctions as follows:

Truth Table for Disjunction

Suppose that XX and YY are formulas. The truth value assigned to X∨YX\vee Y is determined by the following table:

XXYYX∨YX\vee Y
T\mathsf{T}T\mathsf{T}T\mathsf{T}
T\mathsf{T}F\mathsf{F}T\mathsf{T}
F\mathsf{F}T\mathsf{T}T\mathsf{T}
F\mathsf{F}F\mathsf{F}F\mathsf{F}

Negation#

The sentence "Ann did not get an A in PHIL 171" is true when "Ann got an A in PHIL 171" is false; otherwise the sentence is false. The suggests the following characterization:

Truth of Negations

For any formula XX, if the main connective of XX is ¬\neg, then XX is true when the negated formulas is false; otherwise XX is false.

Thus, the truth value of $\neg P$ is determined as follows:
  1. If PP is true, then ¬P\neg P is false.
  2. If PP is false, then ¬P\neg P is true.

More generally, truth values are assigned to disjunctions as follows:

Truth Table for Negation

Suppose that XX is a formula. The truth value assigned to ¬X\neg X is determined by the following table:

XX¬X\neg X
T\mathsf{T}F\mathsf{F}
F\mathsf{F}T\mathsf{T}

Material Conditional#

The truth table for the material conditional is less obvious than the ones for conjunction, disjunction and negation. The main difficulty is that there are well-known mismatches between the meaning of "if...then..." in natural language and the meaning of →\rightarrow according to the following truth table (we will talk about these later in these notes).

Truth Table for the Material Conditional

Suppose that XX and YY are formulas. The truth value assigned to X→YX\rightarrow Y is determined by the following table:

XXYYX→YX\rightarrow Y
T\mathsf{T}T\mathsf{T}T\mathsf{T}
T\mathsf{T}F\mathsf{F}F\mathsf{F}
F\mathsf{F}T\mathsf{T}T\mathsf{T}
F\mathsf{F}F\mathsf{F}T\mathsf{T}

Thus, the truth value of P→QP\rightarrow Q is determined as follows:

  1. If PP is true and QQ is true, then P→QP\rightarrow Q is true.
  2. If PP is true and QQ is false, then P→QP\rightarrow Q is false.
  3. If PP is false and QQ is true, then P→QP\rightarrow Q is true.
  4. If PP is false and QQ is false, then P→QP\rightarrow Q is true.

One thing that is often surprising when first seeing the truth table for the material conditional is that X→YX\rightarrow Y is true when XX is false. That is, conditionals are true when the antecedent is false. To motivate this definition, suppose that Ann and Bob come to the following agreement: "If Ann tutors Bob in logic, then Bob will pay Ann $50." The question is, what are the circumstance in which Ann or Bob violate this agreement? First of all, note that Ann is not under any obligation to tutor Bob in logic according to this agreement. So, she cannot violate this agreement. Consider the following four situations:

  1. Ann tutored Bob in logic, and Bob paid her $50.
  2. Ann tutored Bob in logic, but and Bob didn't pay her $50.
  3. Ann doesn't tutor Bob in logic, but Bob paid Ann $50 anway.
  4. Ann doesn't tutor Bob in logic, and Bob didn't pay her $50.

Clearly, in situation 1, Bob satisfies their agreement and in situation 2, Bob broke their agreement. In situations 3 and 4, since Ann didn't tutor Bob in logic, he is under no obligation to pay Ann, though he could pay her $50 for other reasons. So, the only situation in which the agreement is broken is situation 2.

Bi-Conditional#

Recall that the biconditional "↔\leftrightarrow" is intended to mean "...if, and only if,..."). We treat the biconditional as shorthand for a longer formula: "(X↔Y)(X\leftrightarrow Y)" is short for "((X→Y)∧(Y→X))((X\rightarrow Y)\wedge( Y\rightarrow X))".

For example, P↔QP\leftrightarrow Q is shorthand for (P→Q)∧(Q→P)(P\rightarrow Q)\wedge (Q\rightarrow P). So, truth or falsity of P↔QP\leftrightarrow Q is determined as follows:

  1. If PP is true and QQ is true, then P→QP\rightarrow Q is true and Q→PQ\rightarrow P is true; so (P→Q)∧(Q→P)(P\rightarrow Q)\wedge (Q\rightarrow P) is true---that is, P↔QP\leftrightarrow Q is true.
  2. If PP is true and QQ is false, then P→QP\rightarrow Q is false and Q→PQ\rightarrow P is true; so (P→Q)∧(Q→P)(P\rightarrow Q)\wedge (Q\rightarrow P) is false---that is, P↔QP\leftrightarrow Q is false.
  3. If PP is false and QQ is true, then P→QP\rightarrow Q is true and Q→PQ\rightarrow P is false; so (P→Q)∧(Q→P)(P\rightarrow Q)\wedge (Q\rightarrow P) is false---that is, P↔QP\leftrightarrow Q is false.
  4. If PP is false and QQ is false, then P→QP\rightarrow Q is true and Q→PQ\rightarrow P is true; so (P→Q)∧(Q→P)(P\rightarrow Q)\wedge (Q\rightarrow P) is true---that is, P↔QP\leftrightarrow Q is true.

We can summarize this reasoning in the following truth table for the bi-conditional:

XXYYX↔YX\leftrightarrow Y
T\mathsf{T}T\mathsf{T}T\mathsf{T}
T\mathsf{T}F\mathsf{F}F\mathsf{F}
F\mathsf{F}T\mathsf{T}F\mathsf{F}
F\mathsf{F}F\mathsf{F}T\mathsf{T}

Truth of a Formula#

Using the truth tables for the connectives, and given any truth value function, we can assign a truth value to any complex formula XX.

Method to find the truth value for complex formulas: Suppose that XX is a formula and there is a truth value function for all the atomic propositions from XX. The truth value assigned to XX is determined as follows:

  1. Construct the syntax tree for XX
  2. Label the atomic propositions in the syntax tree with the truth values assigned to them by the truth value function.
  3. Chase truth up the tree by labeling the remaining formulas with their truth values determined by identifying the main connective and using the truth table for that connective.
Example

Suppose that PP and QQ have the truth value T\mathsf{T} and RR has the truth value F\mathsf{F}. Then, P∧¬(Q∨R)P\wedge\neg(Q\vee R) has the truth value F\mathsf{F}:

We summarize the assignments of a truth values to the atomic propositions PP, QQ and RR and the formula P∧¬(Q∨R)P\wedge \neg (Q\vee R) in a table with a column for each atomic proposition and the formula:

PPQQRR(P∧¬(Q∨R))(P\wedge \neg (Q\vee R))
T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}

Sometimes we will be interested in tables that include columns for more than one formula. For instance:

PPQQRR(P∧R)(P\wedge R)(¬P∨Q)(\neg P\vee Q)(P→Q)(P\rightarrow Q)
T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}

Practice Questions#

I. Answer the following questions by finding the syntax tree and assigning the appropriate truth value to each formula in the syntax tree.

  1. Suppose that PP has the truth value T\mathsf{T} and QQ has the truth value F\mathsf{F}. What is the truth value assigned to (P∨¬Q)(P\vee \neg Q)?
  1. Suppose that PP has the truth value T\mathsf{T} and QQ has the truth value F\mathsf{F}. What is the truth value assigned to (¬P→Q)(\neg P\rightarrow Q)?
  1. Suppose that PP has the truth value T\mathsf{T} and QQ has the truth value F\mathsf{F}. What is the truth value assigned to ¬(P∧Q)\neg (P\wedge Q)?
  1. Suppose that PP has the truth value T\mathsf{T} and QQ has the truth value F\mathsf{F}. What is the truth value assigned to (¬P∧¬Q)(\neg P\wedge \neg Q)?
  1. Suppose that PP has the truth value T\mathsf{T} and QQ and RR have the truth value F\mathsf{F}. What is the truth value assigned to P∧¬(Q∨R)P\wedge\neg (Q\vee R)?

II. In each of the following questions, select the appropriate truth value for the formula.

  1. PPQQ(P→¬Q)(P\rightarrow \neg Q)
    T\mathsf{T}F\mathsf{F}
  2. PPQQ(¬P→Q)(\neg P\rightarrow Q)
    F\mathsf{F}F\mathsf{F}
  3. PPQQ¬(P→¬Q)\neg (P\rightarrow \neg Q)
    T\mathsf{T}F\mathsf{F}
  4. PPQQRR(P∧(Q∨¬R))(P\wedge (Q\vee \neg R))
    T\mathsf{T}F\mathsf{F}T\mathsf{T}
  5. PPQQ(¬P∧¬Q)(\neg P\wedge \neg Q)
    F\mathsf{F}T\mathsf{T}
  6. PPQQ(¬P∧¬Q)(\neg P\wedge \neg Q)
    F\mathsf{F}F\mathsf{F}
  7. PPQQ¬(P∧Q)\neg (P\wedge Q)
    T\mathsf{T}F\mathsf{F}
  8. PPQQ(P↔¬Q)(P\leftrightarrow \neg Q)
    T\mathsf{T}F\mathsf{F}
  9. PPQQRR((P∨R)↔¬Q)((P\vee R)\leftrightarrow \neg Q)
    T\mathsf{T}F\mathsf{F}T\mathsf{T}
  10. PPQQRR(P→(R→Q))(P\rightarrow (R\rightarrow Q))
    T\mathsf{T}F\mathsf{F}T\mathsf{T}
  11. PPQQRR(P→(R→Q))(P\rightarrow (R\rightarrow Q))
    T\mathsf{T}T\mathsf{T}F\mathsf{F}
  12. PPQQRR(P↔(R→Q))(P\leftrightarrow (R\rightarrow Q))
    T\mathsf{T}T\mathsf{T}F\mathsf{F}
  13. PP(P∧¬P)(P\wedge \neg P)
    T\mathsf{T}
  14. PPQQ¬(P∨Q)\neg (P\vee Q)
    T\mathsf{T}F\mathsf{F}
  15. PPQQ(¬P∧¬Q)(\neg P\wedge \neg Q)
    T\mathsf{T}F\mathsf{F}

III. In each of the following questions, find a truth value function that assigns the give truth value to the formula.

  1. PPQQ(P→¬Q)(P\rightarrow \neg Q)
    T\mathsf{T}
  2. PPQQ(P→¬Q)(P\rightarrow \neg Q)
    F\mathsf{F}
  3. PPQQ(P∧¬Q)(P\wedge \neg Q)
    F\mathsf{F}
  4. PPQQ¬(P∧¬Q)\neg (P\wedge \neg Q)
    F\mathsf{F}
  5. PPQQ¬(¬P∧¬Q)\neg (\neg P\wedge \neg Q)
    T\mathsf{T}
  6. PPQQ¬(P↔Q)\neg (P\leftrightarrow Q)
    F\mathsf{F}
  7. PPQQRR(R→(P∧Q))(R\rightarrow (P\wedge Q))
    F\mathsf{F}
  8. PPQQRR(¬(¬P∧¬Q)→¬R)(\neg (\neg P\wedge \neg Q)\rightarrow \neg R)
    T\mathsf{T}
  9. PPQQRR(P→(Q→R))(P\rightarrow (Q\rightarrow R))
    F\mathsf{F}
  10. PPQQRR((P→Q)→R)((P\rightarrow Q)\rightarrow R)
    F\mathsf{F}
  11. PPQQ(¬(P∨Q)↔(¬P∨¬Q))(\neg (P\vee Q)\leftrightarrow (\neg P\vee \neg Q))
    F\mathsf{F}
  12. PPQQ((P∧Q)→(P↔Q))((P\wedge Q)\rightarrow (P\leftrightarrow Q))
    T\mathsf{T}
  13. PPQQ((P↔Q)→(P∧Q))((P\leftrightarrow Q)\rightarrow (P\wedge Q))
    F\mathsf{F}
  14. AABBCCDD((A→(B∧C))∧(¬D→A))((A\rightarrow (B\wedge C))\wedge (\neg D\rightarrow A))
    F\mathsf{F}
  15. AABBCCDD(((¬A∧B)∧¬C)∧D)(((\neg A\wedge B)\wedge \neg C)\wedge D)
    T\mathsf{T}