Building Compound Propositions

From Symbols to Truth: The Role of Truth Tables

In the last lesson, we built expressions like $(P\wedge Q)\to R$. The truth of this entire statement depends entirely on the truth of its atomic parts: P, Q, and R. A truth table is simply a way to exhaustively list every possible combination of truth values for these atomic parts and see what the result is for the whole expression. Since you're familiar with boolean logic from programming, you can think of a truth table as a systematic way to test a complex boolean expression against all possible inputs.

Let's begin by defining the five connectives we learned about in terms of their truth tables. We'll start with the most straightforward ones.

The Tricky Connectives: Implication and Biconditional

The truth tables for negation, conjunction, and disjunction are quite intuitive. The tables for implication ($\to$) and biconditional ($\leftrightarrow$) can be a little less obvious, especially the implication. Understanding these is key to mastering logic. The most confusing part is that an implication is considered true whenever its premise (the "if" part) is false.

Let's watch an explanation that tackles this head-on.

To summarize, here are the complete truth tables for all five connectives. In this image, A and B are used as propositional variables (like our P and Q), and the values 1 and 0 correspond to True and False, respectively—a convention you'll recognize from your computer science background.

Memorizing these five tables is essential, as they are the building blocks for everything that follows.

Building Tables for Complex Propositions

Now that we know the rules for each individual connective, we can combine them to find the truth value of any compound proposition. The process is methodical and analogous to calculating the value of a complex arithmetic expression by handling the innermost parentheses first.

The Process:

1. Count the Rows: If you have $n$ distinct atomic propositions, you will need $2^n$ rows to cover all possible combinations of their truth values.
2. Set Up Columns: Create a column for each atomic proposition on the left. Then, create columns for the sub-expressions, gradually building up to the final proposition.
3. Fill Systematically: Fill in the initial columns for the atomic propositions. A common, error-proof method is to alternate T/F values, doubling the period for each column as you move left. For 3 variables (P, Q, R), the R column would be T, F, T, F...; the Q column T, T, F, F,...; and the P column T, T, T, T, F, F, F, F.
4. Evaluate Sub-expressions: Fill in the columns for the sub-expressions by applying the rules from the characteristic truth tables to the values in the columns you've already completed.

The following reading provides a clear, step-by-step guide to this process.

Let's Build One Together

Let's apply this process to an example: $(P\vee \neg Q)\to P$.

1. Rows: We have two atomic propositions, P and Q. So, we need $2^2=4$ rows.
2. Columns: We need columns for P, Q, $\neg Q$, $(P\vee \neg Q)$, and finally the full expression $(P\vee \neg Q)\to P$.

Step-by-step evaluation:

• Column 3 ($\neg Q$): The opposite of column 2.
• Column 4 ($P\vee \neg Q$): Apply the OR rule to column 1 and column 3. It's only false when both are false (which never happens here).
• Column 5 ($(P\vee \neg Q)\to P$): Apply the implication rule. The antecedent is column 4, and the consequent is column 1. The only time an implication is false is when T → F. This happens only in the last row, where $(P\vee \neg Q)$ is True and $P$ is False.

This methodical approach guarantees you can find the truth conditions for any well-formed logical expression, no matter how complex.

Conclusion

In this lesson, you've moved from writing logical expressions to truly understanding their meaning. By defining the logical connectives with their characteristic truth tables, we've established a rigorous method for evaluating any compound proposition.

Key Takeaways:

• A truth table systematically determines the truth value of a compound proposition for all possible truth values of its atomic components.
• The five logical connectives ($\neg ,\wedge ,\vee ,\to ,\leftrightarrow$) each have a unique characteristic truth table that defines their logical function.
• The implication $P\to Q$ is only false when $P$ is true and $Q$ is false. It is true in all other cases.
• We can construct truth tables for complex expressions by breaking them down into sub-expressions and evaluating them column by column, from the inside out.

In our next lesson, we will put these truth tables to a very powerful use: determining logical equivalence. We will learn how to use truth tables to prove that two completely different-looking expressions are, in fact, identical in their logical meaning. This is a fundamental concept for simplifying logical formulas, optimizing database queries, and refining code.