2.3 Truth Tables: Construction and Interpretation

Truth tables are powerful tools for analyzing logical statements. They help us determine the truth values of complex propositions by systematically evaluating all possible combinations of atomic propositions.

By constructing and interpreting truth tables, we can identify tautologies, contradictions, and contingencies. We can also use them to prove logical equivalence between different formulas, providing a foundation for more advanced logical reasoning.

Truth Tables

Truth tables for propositional formulas

Top images from around the web for Truth tables for propositional formulas

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  TruthTable | Wolfram Function Repository View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  TruthTable | Wolfram Function Repository View original

  Is this image relevant?

1 of 3

Top images from around the web for Truth tables for propositional formulas

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  TruthTable | Wolfram Function Repository View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  TruthTable | Wolfram Function Repository View original

  Is this image relevant?

1 of 3

• Identify the atomic propositions (variables) in the formula (p, q, r)
• Determine the number of rows needed in the truth table
  • The number of rows is $2^n$, where $n$ is the number of atomic propositions ($2^3 = 8$ rows for 3 variables)
• List all possible combinations of truth values (T, F) for the atomic propositions
  • Use a systematic method, such as binary counting, to ensure all combinations are included (000, 001, 010, 011, 100, 101, 110, 111)
• Evaluate the truth value of the formula for each row
  • Apply the rules for each connective used in the formula
    • Negation ($\neg$): If $p$ is true, then $\neg p$ is false, and vice versa (NOT gate in digital logic)
    • Conjunction ($\land$): $p \land q$ is true only when both $p$ and $q$ are true (AND gate in digital logic)
    • Disjunction ($\lor$): $p \lor q$ is true when at least one of $p$ or $q$ is true (OR gate in digital logic)
    • Implication ($\rightarrow$): $p \rightarrow q$ is false only when $p$ is true and $q$ is false (if-then statement in programming)
    • Biconditional ($\leftrightarrow$): $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth value (XNOR gate in digital logic)
• Complete the truth table by filling in the truth values (T, F) for the formula in each row

Truth values of compound statements

• Identify the connectives used in the compound statement ($\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$)
• Break down the compound statement into its component propositions (simpler statements connected by connectives)
• Assign truth values to the component propositions (T, F)
• Apply the rules for each connective to determine the truth value of the compound statement
  1. Work from the innermost parentheses outward (order of operations)
  2. Use the truth values of the component propositions to evaluate each connective (refer to the rules for each connective)

Interpretation of truth tables

• Tautology: A formula that is always true, regardless of the truth values of its atomic propositions
  • In the truth table, the formula column contains only true (T) values (e.g., $p \lor \neg p$)
• Contradiction: A formula that is always false, regardless of the truth values of its atomic propositions
  • In the truth table, the formula column contains only false (F) values (e.g., $p \land \neg p$)
• Contingency: A formula that is neither a tautology nor a contradiction
  • In the truth table, the formula column contains both true (T) and false (F) values (e.g., $p \land q$)
• Satisfiability: A formula is satisfiable if there exists at least one assignment of truth values to its atomic propositions that makes the formula true
  • In the truth table, the formula column contains at least one true (T) value (e.g., $p \lor q$)

Logical equivalence through truth tables

• Construct truth tables for the formulas being compared (e.g., $p \rightarrow q$ and $\neg p \lor q$)
• Ensure that the atomic propositions are listed in the same order for both truth tables (p, q)
• Compare the formula columns of the truth tables
  • If the formula columns are identical, the formulas are logically equivalent (e.g., $p \rightarrow q \equiv \neg p \lor q$)
  • If the formula columns differ in at least one row, the formulas are not logically equivalent (e.g., $p \land q \not\equiv p \lor q$)
• Common logical equivalences:
  • De Morgan's Laws: $\neg (p \land q) \equiv \neg p \lor \neg q$ and $\neg (p \lor q) \equiv \neg p \land \neg q$
  • Double Negation: $\neg (\neg p) \equiv p$
  • Implication: $p \rightarrow q \equiv \neg p \lor q$
  • Biconditional: $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$