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\wedge (Q\vee R)$ is true or false. The main connective is $\wedge$, so the formula is a conjunction. The left conjunct is $P$ and the right conjunct $Q\vee R$. The right conjunct is a disjunction, where $Q$ is the left disjunct $Q$ and $R$ is the right disjunct $R$. So, to determine the truth or falsity of $P\wedge (Q\vee R)$ we need answers to the following questions:

1. Is $P$ true or false? Is $Q$ true or false? Is $R$ 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 "$\mathsf{T}$" (true) and "$\mathsf{F}$" (false) are called truth values. When a formula $X$ is true, we write "$X$ is $\mathsf{T}$" and say "the truth value assigned to $X$ is $\mathsf{T}$" (or more simply "$X$ is true"). When a formula $X$ is false, we write "$X$ is $\mathsf{F}$" and say "the truth value assigned to $X$ is $\mathsf{F}$" (or more simply "$X$ is false").

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

• Instead of $\mathsf{T}$, some texts use $1$ or $\top$ for true.
• Instead of $\mathsf{F}$, some texts use $0$ or $\bot$ for false.

note

The letters "$T$" and "$F$" may be used as atomic propositions. We differentiate these letters from truth values by the font. E.g., "$T$" is an atomic proposition and "$\mathsf{T}$" is the truth value "true", and "$F$" is an atomic propositions and "$\mathsf{F}$" is the truth value "false". In general, to avoid confusion we will try to avoid using "$T$" and "$F$" 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, Q$ and $R$ is:

$P$ is $\mathsf{T}$, $Q$ is $\mathsf{F}$ and $R$ is $\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:

$P$	$Q$	$R$
$\mathsf{T}$	$\mathsf{F}$	$\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 "$A$" 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 "$K$" 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 "$Q$" 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:

• $A$: the card from pile 1 has an $A$ on it.
• $K$: the card from pile 2 has a $K$ on it.
• $Q$: the card from pile 3 has a $Q$ on it.

How many situations can be created by dealing the cards?

Lecture

Slides

In this example, we identified three atomic propositions ($A$, $K$ and $Q$) 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 $X$, if the main connective of $X$ is $\wedge$, then $X$ is true when both conjuncts are true; otherwise $X$ is false.

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

1. If $P$ is true and $Q$ is true, then $P\wedge Q$ is true.
2. If $P$ is true and $Q$ is false, then $P\wedge Q$ is false.
3. If $P$ is false and $Q$ is true, then $P\wedge Q$ is false.
4. If $P$ is false and $Q$ is false, then $P\wedge Q$ is false.

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

Truth Table for Conjunction

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

$X$	$Y$	$X \wedge Y$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{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 $X$, if the main connective of $X$ is $\vee$, then $X$ is true when at least one of the disjuncts is true; otherwise $X$ is false.

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

1. If $P$ is true and $Q$ is true, then $P\vee Q$ is true.
2. If $P$ is true and $Q$ is false, then $P\vee Q$ is true.
3. If $P$ is false and $Q$ is true, then $P\vee Q$ is true.
4. If $P$ is false and $Q$ is false, then $P\vee Q$ is false.

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

Truth Table for Disjunction

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

$X$	$Y$	$X\vee Y$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{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 $X$, if the main connective of $X$ is $\neg$, then $X$ is true when the negated formulas is false; otherwise $X$ is false.

Thus, the truth value of $\neg P$ is determined as follows:

1. If $P$ is true, then $\neg P$ is false.
2. If $P$ is false, then $\neg P$ is true.

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

Truth Table for Negation

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

$X$	$\neg X$
$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\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 $X$ and $Y$ are formulas. The truth value assigned to $X\rightarrow Y$ is determined by the following table:

$X$	$Y$	$X\rightarrow Y$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$

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

1. If $P$ is true and $Q$ is true, then $P\rightarrow Q$ is true.
2. If $P$ is true and $Q$ is false, then $P\rightarrow Q$ is false.
3. If $P$ is false and $Q$ is true, then $P\rightarrow Q$ is true.
4. If $P$ is false and $Q$ is false, then $P\rightarrow Q$ is true.

One thing that is often surprising when first seeing the truth table for the material conditional is that $X\rightarrow Y$ is true when $X$ 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\leftrightarrow Y)$" is short for "$((X\rightarrow Y)\wedge( Y\rightarrow X))$".

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

1. If $P$ is true and $Q$ is true, then $P\rightarrow Q$ is true and $Q\rightarrow P$ is true; so $(P\rightarrow Q)\wedge (Q\rightarrow P)$ is true---that is, $P\leftrightarrow Q$ is true.
2. If $P$ is true and $Q$ is false, then $P\rightarrow Q$ is false and $Q\rightarrow P$ is true; so $(P\rightarrow Q)\wedge (Q\rightarrow P)$ is false---that is, $P\leftrightarrow Q$ is false.
3. If $P$ is false and $Q$ is true, then $P\rightarrow Q$ is true and $Q\rightarrow P$ is false; so $(P\rightarrow Q)\wedge (Q\rightarrow P)$ is false---that is, $P\leftrightarrow Q$ is false.
4. If $P$ is false and $Q$ is false, then $P\rightarrow Q$ is true and $Q\rightarrow P$ is true; so $(P\rightarrow Q)\wedge (Q\rightarrow P)$ is true---that is, $P\leftrightarrow Q$ is true.

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

$X$	$Y$	$X\leftrightarrow Y$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{F}$	$\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 $X$.

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

1. Construct the syntax tree for $X$
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 $P$ and $Q$ have the truth value $\mathsf{T}$ and $R$ has the truth value $\mathsf{F}$. Then, $P\wedge\neg(Q\vee R)$ has the truth value $\mathsf{F}$:

Lecture

Slides

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

$P$	$Q$	$R$	$(P\wedge \neg (Q\vee R))$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$

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

$P$	$Q$	$R$	$(P\wedge R)$	$(\neg P\vee Q)$	$(P\rightarrow Q)$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{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 $P$ has the truth value $\mathsf{T}$ and $Q$ has the truth value $\mathsf{F}$. What is the truth value assigned to $(P\vee \neg Q)$?

2. Suppose that $P$ has the truth value $\mathsf{T}$ and $Q$ has the truth value $\mathsf{F}$. What is the truth value assigned to $(\neg P\rightarrow Q)$?

3. Suppose that $P$ has the truth value $\mathsf{T}$ and $Q$ has the truth value $\mathsf{F}$. What is the truth value assigned to $\neg (P\wedge Q)$?

4. Suppose that $P$ has the truth value $\mathsf{T}$ and $Q$ has the truth value $\mathsf{F}$. What is the truth value assigned to $(\neg P\wedge \neg Q)$?

5. Suppose that $P$ has the truth value $\mathsf{T}$ and $Q$ and $R$ have the truth value $\mathsf{F}$. What is the truth value assigned to $P\wedge\neg (Q\vee R)$?

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

1. $P$	$Q$	$(P\rightarrow \neg Q)$
   $\mathsf{T}$	$\mathsf{F}$

   Correct!

2. $P$	$Q$	$(\neg P\rightarrow Q)$
   $\mathsf{F}$	$\mathsf{F}$

   Correct!

3. $P$	$Q$	$\neg (P\rightarrow \neg Q)$
   $\mathsf{T}$	$\mathsf{F}$

   Correct!

4. $P$	$Q$	$R$	$(P\wedge (Q\vee \neg R))$
   $\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$

   Correct!

5. $P$	$Q$	$(\neg P\wedge \neg Q)$
   $\mathsf{F}$	$\mathsf{T}$

   Correct!

6. $P$	$Q$	$(\neg P\wedge \neg Q)$
   $\mathsf{F}$	$\mathsf{F}$

   Correct!

7. $P$	$Q$	$\neg (P\wedge Q)$
   $\mathsf{T}$	$\mathsf{F}$

   Correct!

8. $P$	$Q$	$(P\leftrightarrow \neg Q)$
   $\mathsf{T}$	$\mathsf{F}$

   Correct!

9. $P$	$Q$	$R$	$((P\vee R)\leftrightarrow \neg Q)$
   $\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$

   Correct!

10. $P$	$Q$	$R$	$(P\rightarrow (R\rightarrow Q))$
    $\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$

    Correct!

11. $P$	$Q$	$R$	$(P\rightarrow (R\rightarrow Q))$
    $\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$

    Correct!

12. $P$	$Q$	$R$	$(P\leftrightarrow (R\rightarrow Q))$
    $\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$

    Correct!

13. $P$	$(P\wedge \neg P)$
    $\mathsf{T}$

    Correct!

14. $P$	$Q$	$\neg (P\vee Q)$
    $\mathsf{T}$	$\mathsf{F}$

    Correct!

15. $P$	$Q$	$(\neg P\wedge \neg Q)$
    $\mathsf{T}$	$\mathsf{F}$

    Correct!

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

1. $P$	$Q$	$(P\rightarrow \neg Q)$
   		$\mathsf{T}$

   Correct! The submitted truth function makes the formula true

2. $P$	$Q$	$(P\rightarrow \neg Q)$
   		$\mathsf{F}$

   Incorrect: The submitted truth function makes the formula true

3. $P$	$Q$	$(P\wedge \neg Q)$
   		$\mathsf{F}$

   Correct! The submitted truth function makes the formula false

4. $P$	$Q$	$\neg (P\wedge \neg Q)$
   		$\mathsf{F}$

   Incorrect: The submitted truth function makes the formula true

5. $P$	$Q$	$\neg (\neg P\wedge \neg Q)$
   		$\mathsf{T}$

   Incorrect: The submitted truth function makes the formula false

6. $P$	$Q$	$\neg (P\leftrightarrow Q)$
   		$\mathsf{F}$

   Correct! The submitted truth function makes the formula false

7. $P$	$Q$	$R$	$(R\rightarrow (P\wedge Q))$
   			$\mathsf{F}$

   Incorrect: The submitted truth function makes the formula true

8. $P$	$Q$	$R$	$(\neg (\neg P\wedge \neg Q)\rightarrow \neg R)$
   			$\mathsf{T}$

   Correct! The submitted truth function makes the formula true

9. $P$	$Q$	$R$	$(P\rightarrow (Q\rightarrow R))$
   			$\mathsf{F}$

   Incorrect: The submitted truth function makes the formula true

10. $P$	$Q$	$R$	$((P\rightarrow Q)\rightarrow R)$
    			$\mathsf{F}$

    Correct! The submitted truth function makes the formula false

11. $P$	$Q$	$(\neg (P\vee Q)\leftrightarrow (\neg P\vee \neg Q))$
    		$\mathsf{F}$

    Incorrect: The submitted truth function makes the formula true

12. $P$	$Q$	$((P\wedge Q)\rightarrow (P\leftrightarrow Q))$
    		$\mathsf{T}$

    Correct! The submitted truth function makes the formula true

13. $P$	$Q$	$((P\leftrightarrow Q)\rightarrow (P\wedge Q))$
    		$\mathsf{F}$

    Correct! The submitted truth function makes the formula false

14. $A$	$B$	$C$	$D$	$((A\rightarrow (B\wedge C))\wedge (\neg D\rightarrow A))$
    				$\mathsf{F}$

    Correct! The submitted truth function makes the formula false

15. $A$	$B$	$C$	$D$	$(((\neg A\wedge B)\wedge \neg C)\wedge D)$
    				$\mathsf{T}$

    Incorrect: The submitted truth function makes the formula false