2.1 Propositional logic and truth tables

Propositional logic is a powerful tool for analyzing arguments and reasoning. It uses symbols to represent statements and logical connectives to combine them, allowing us to evaluate complex propositions and determine their truth values.

Truth tables are key in propositional logic, helping us assess the validity of arguments and identify logical equivalences. By understanding the rules of logical connectives, we can navigate complex reasoning and uncover fundamental truths in logical statements.

Propositional Logic

Propositional logic and syntax

Top images from around the web for Propositional logic and syntax

• 

  Logic AND Gate - Electronics-Lab.com View original

  Is this image relevant?

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Logic AND Gate - Electronics-Lab.com View original

  Is this image relevant?

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 3

Top images from around the web for Propositional logic and syntax

• 

  Logic AND Gate - Electronics-Lab.com View original

  Is this image relevant?

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Logic AND Gate - Electronics-Lab.com View original

  Is this image relevant?

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 3

• Formal system for reasoning about propositions and their relationships using logical connectives
  • Declarative sentences that can be either true or false (propositions)
  • Most basic propositions represented by lowercase letters ($p$, $[q](https://www.fiveableKeyTerm:q)$, $r$)
• Symbols used to combine propositions to form more complex propositions (logical connectives)
  • "not" reverses the truth value of a proposition (negation, $\neg$)
  • "and" true only when both propositions are true (conjunction, $\wedge$)
  • "or" true when at least one proposition is true (disjunction, $\vee$)
  • "if...then" true except when the antecedent is true and the consequent is false (implication, $\rightarrow$)
  • "if and only if" true when both propositions have the same truth value (biconditional, $\leftrightarrow$)
• Propositions constructed according to the syntax rules of propositional logic (well-formed formulas, WFFs)
  • Atomic propositions are WFFs
  • $\neg\phi$ is a WFF if $\phi$ is a WFF
  • $(\phi \wedge \psi)$, $(\phi \vee \psi)$, $(\phi \rightarrow \psi)$, and $(\phi \leftrightarrow \psi)$ are WFFs if $\phi$ and $\psi$ are WFFs

Truth tables for formulas

• Evaluate the truth values of propositional formulas for all possible combinations of truth values of their constituent atomic propositions
  • Each atomic proposition assigned a column, all possible combinations of truth values listed
  • Truth values of complex propositions determined by applying the rules of the logical connectives
• Two propositional formulas logically equivalent if they have the same truth value for all possible combinations of truth values of their atomic propositions
  • Logical equivalence determined by comparing the truth tables of the formulas
  • Formulas logically equivalent if truth tables are identical

Rules of logical connectives

• Negation ($\neg$)
  • $\neg p$ true when $p$ false, false when $p$ true
• Conjunction ($\wedge$)
  • $p \wedge q$ true only when both $p$ and $q$ true
• Disjunction ($\vee$)
  • $p \vee q$ true when at least one of $p$ or $q$ true
• Implication ($\rightarrow$)
  • $p \rightarrow q$ true except when $p$ true and $q$ false
• Biconditional ($\leftrightarrow$)
  • $p \leftrightarrow q$ true when both $p$ and $q$ have the same truth value

Logical Equivalence and Validity

Validity of propositional arguments

• Propositional argument valid if and only if its conclusion true whenever all its premises true
  • To prove validity using truth tables, construct a truth table with columns for premises and conclusion
  • Argument valid if conclusion true in every row where all premises true
• Common logical equivalences
  • De Morgan's laws: $\neg(p \wedge q) \equiv (\neg p \vee \neg q)$ and $\neg(p \vee q) \equiv (\neg p \wedge \neg q)$
  • Double negation: $\neg(\neg p) \equiv p$
  • Conditional equivalence: $(p \rightarrow q) \equiv (\neg p \vee q)$
  • Biconditional equivalence: $(p \leftrightarrow q) \equiv (p \rightarrow q) \wedge (q \rightarrow p)$
• Propositional formula always true, regardless of the truth values of its atomic propositions (tautology)
  • Tautology examples: $p \vee \neg p$, $(p \rightarrow q) \vee (q \rightarrow p)$