Truth Tables

Truth Tables

Truth tables are a fundamental tool in propositional logic. They help you determine the truth value of logical expressions based on the truth values of their components. Understanding truth tables is essential for analysing logical statements and for various applications in computer science.

Basic Concepts

A proposition is a statement that can either be true (T) or false (F). Logical connectives are used to combine propositions. The main logical connectives are:

• Conjunction (AND): Denoted by ∧. The expression P ∧ Q is true only if both P and Q are true.
• Disjunction (OR): Denoted by ∨. The expression P ∨ Q is true if at least one of P or Q is true.
• Negation (NOT): Denoted by ¬. The expression ¬P is true if P is false, and vice versa.
• Implication (IF...THEN): Denoted by →. The expression P → Q is false only if P is true and Q is false.
• Biconditional (IF AND ONLY IF): Denoted by ↔. The expression P ↔ Q is true if P and Q are both true or both false.

Constructing Truth Tables

To construct a truth table, follow these steps:

1. Identify the propositions involved.
2. Determine the number of rows needed, which is 2^n, where n is the number of distinct propositions.
3. List all possible combinations of truth values for the propositions.
4. Evaluate the expression for each combination.

Example 1: Simple Truth Table

Let’s consider the propositions P and Q. We will create a truth table for the expression P ∧ Q.

Step 1: Identify propositions: P, Q

Step 2: Number of rows: 2^2 = 4

Step 3: List combinations:

Row 1: P = T, Q = T

Row 2: P = T, Q = F

Row 3: P = F, Q = T

Row 4: P = F, Q = F

Step 4: Evaluate P ∧ Q:

Row 1: T ∧ T = T

Row 2: T ∧ F = F

Row 3: F ∧ T = F

Row 4: F ∧ F = F

The completed truth table is:

P	Q	P ∧ Q
T	T	T
T	F	F
F	T	F
F	F	F

Example 2: Truth Table with Multiple Connectives

Now, let’s create a truth table for the expression (P ∨ Q) → ¬R. We will use three propositions: P, Q, and R.

Step 1: Identify propositions: P, Q, R

Step 2: Number of rows: 2^3 = 8

Step 3: List combinations:

Row 1: P = T, Q = T, R = T

Row 2: P = T, Q = T, R = F

Row 3: P = T, Q = F, R = T

Row 4: P = T, Q = F, R = F

Row 5: P = F, Q = T, R = T

Row 6: P = F, Q = T, R = F

Row 7: P = F, Q = F, R = T

Row 8: P = F, Q = F, R = F

Step 4: Evaluate (P ∨ Q) → ¬R:

Row 1: (T ∨ T) → ¬T = T → F = F

Row 2: (T ∨ T) → ¬F = T → T = T

Row 3: (T ∨ F) → ¬T = T → F = F

Row 4: (T ∨ F) → ¬F = T → T = T

Row 5: (F ∨ T) → ¬T = T → F = F

Row 6: (F ∨ T) → ¬F = T → T = T

Row 7: (F ∨ F) → ¬T = F → F = T

Row 8: (F ∨ F) → ¬F = F → T = T

The completed truth table is:

P	Q	R	(P ∨ Q) → ¬R
T	T	T	F
T	T	F	T
T	F	T	F
T	F	F	T
F	T	T	F
F	T	F	T
F	F	T	T
F	F	F	T

Using Truth Tables for Logical Equivalence

Truth tables can also be used to determine if two logical expressions are equivalent. Two expressions are equivalent if they have the same truth values for all combinations of their variables.

Example 3: Checking Logical Equivalence

Let’s check if the expressions P → Q and ¬P ∨ Q are equivalent.

Step 1: Identify propositions: P, Q

Step 2: Number of rows: 2^2 = 4

Step 3: List combinations:

Row 1: P = T, Q = T

Row 2: P = T, Q = F

Row 3: P = F, Q = T

Row 4: P = F, Q = F

Step 4: Evaluate P → Q and ¬P ∨ Q:

Row 1: T → T = T; ¬T ∨ T = F ∨ T = T

Row 2: T → F = F; ¬T ∨ F = F ∨ F = F

Row 3: F → T = T; ¬F ∨ T = T ∨ T = T

Row 4: F → F = T; ¬F ∨ F = T ∨ F = T

The completed truth table is:

P	Q	P → Q	¬P ∨ Q
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

Since both expressions have the same truth values for all combinations of P and Q, they are logically equivalent.

Summary

• Truth tables show the truth values of propositions and their combinations.
• Construct a truth table by identifying propositions, determining the number of rows, listing combinations, and evaluating expressions.
• Use truth tables to check for logical equivalence between expressions.

Check your understanding

1. Construct a truth table for the expression P ∨ (Q ∧ R).
2. Determine if the expressions (P ∧ Q) → R and ¬R ∨ (P ∧ Q) are logically equivalent using a truth table.
3. Explain how the truth value of ¬(P ∧ Q) relates to the truth values of P and Q.
4. What is the truth value of the expression P → (Q ∨ R) when P is false, Q is true, and R is false?