🤔Mathematical Logic Unit 2 – Truth Tables and Logical Connectives

Key Concepts and Definitions

• Proposition: a declarative sentence that is either true or false, but not both
• Logical connectives: symbols used to connect propositions in a logical formula ($\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\neg$)
  • Conjunction ($\wedge$): represents the logical "AND" operation
  • Disjunction ($\vee$): represents the logical "OR" operation
  • Implication ($\rightarrow$): represents a conditional statement (if-then)
  • Biconditional ($\leftrightarrow$): represents a two-way implication (if and only if)
  • Negation ($\neg$): represents the logical "NOT" operation
• Truth value: the value assigned to a proposition, either true (T) or false (F)
• Tautology: a logical formula that is always true, regardless of the truth values of its propositions
• Contradiction: a logical formula that is always false, regardless of the truth values of its propositions

Logical Connectives Explained

• Conjunction ($\wedge$) combines two propositions and is true only when both propositions are true
  • Example: "The sky is blue $\wedge$ grass is green" is true only if both "The sky is blue" and "grass is green" are true
• Disjunction ($\vee$) combines two propositions and is true when at least one of the propositions is true
  • Inclusive disjunction: allows for both propositions to be true (OR)
  • Exclusive disjunction (XOR): only one proposition can be true, but not both
• Implication ($\rightarrow$) represents a conditional statement, where the truth of the second proposition depends on the truth of the first
  • Example: "If it rains, then the ground is wet" ($rain \rightarrow wet$)
  • The implication is false only when the antecedent (first proposition) is true and the consequent (second proposition) is false
• Biconditional ($\leftrightarrow$) represents a two-way implication, where both propositions imply each other
  • Example: "A number is even if and only if it is divisible by 2" ($even \leftrightarrow divisible\_by\_2$)
• Negation ($\neg$) reverses the truth value of a proposition
  • Example: If "The sky is blue" is true, then "$\neg$(The sky is blue)" is false

Truth Table Basics

• A truth table is a tabular representation of the truth values of a logical formula for all possible combinations of its propositions' truth values
• Each proposition is assigned a column, and the logical connectives are represented in separate columns
• The number of rows in a truth table is determined by $2^n$, where $n$ is the number of unique propositions
  • Example: A truth table with 2 propositions will have $2^2 = 4$ rows
• The truth values of the propositions are listed in a binary counting sequence (00, 01, 10, 11 for 2 propositions)
• The final column of the truth table represents the truth value of the entire logical formula for each combination of proposition truth values

Constructing Truth Tables

• Identify the unique propositions in the logical formula and assign each a column in the truth table
• Determine the number of rows needed based on the number of unique propositions ($2^n$)
• Fill in the truth values for the propositions in a binary counting sequence
• Evaluate the truth values of the logical connectives in the order of their precedence
  • Negation ($\neg$) has the highest precedence
  • Conjunction ($\wedge$) and disjunction ($\vee$) have equal precedence and are evaluated next
  • Implication ($\rightarrow$) and biconditional ($\leftrightarrow$) have the lowest precedence
• Fill in the truth values for the entire logical formula in the final column

Analyzing Complex Statements

• Break down complex logical formulas into smaller, manageable parts
• Use parentheses to group propositions and connectives to ensure the correct order of evaluation
  • Example: $(p \wedge q) \vee (r \rightarrow s)$
• Construct truth tables for each part of the complex statement
• Combine the truth tables using the appropriate logical connectives to determine the truth value of the entire statement
• Identify tautologies, contradictions, and contingencies (formulas that are neither tautologies nor contradictions) in the complex statement

Applications in Logic and Computing

• Logical connectives and truth tables are fundamental concepts in computer science and digital electronics
• Boolean algebra: a branch of algebra that deals with the manipulation of logical expressions
  • Used in the design of digital circuits and computer algorithms
• Propositional logic: a branch of logic that deals with propositions and their relationships using logical connectives
  • Used in artificial intelligence, automated theorem proving, and formal verification of software and hardware systems
• Conditional statements and logical implications are essential for programming languages (if-else, switch-case)
• Truth tables can be used to simplify and optimize logical expressions in digital circuit design (Karnaugh maps, Quine-McCluskey algorithm)

Common Mistakes and How to Avoid Them

• Confusing the order of precedence for logical connectives
  • Remember: negation ($\neg$), conjunction ($\wedge$) and disjunction ($\vee$), implication ($\rightarrow$) and biconditional ($\leftrightarrow$)
  • Use parentheses to group propositions and connectives to ensure the correct order of evaluation
• Misinterpreting the truth values of implications and biconditionals
  • An implication ($p \rightarrow q$) is false only when $p$ is true and $q$ is false
  • A biconditional ($p \leftrightarrow q$) is true when both $p$ and $q$ have the same truth value
• Forgetting to consider all possible combinations of truth values for the propositions
  • Double-check that the number of rows in the truth table is $2^n$, where $n$ is the number of unique propositions
• Misplacing the negation symbol ($\neg$) or misinterpreting its scope
  • The negation symbol applies only to the proposition or group of propositions immediately following it
  • Use parentheses to clearly define the scope of the negation

Practice Problems and Solutions

• Problem 1: Construct a truth table for the logical formula $(p \wedge q) \rightarrow (p \vee \neg q)$
  • Solution: Truth table with 4 rows, showing that the formula is a tautology (always true)
• Problem 2: Simplify the logical expression $\neg(p \vee q) \wedge (p \rightarrow q)$
  • Solution: Apply De Morgan's laws and the definition of implication to simplify the expression to $\neg p \wedge q$
• Problem 3: Determine whether the logical formula $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ is a tautology
  • Solution: Construct a truth table with 8 rows, showing that the formula is indeed a tautology (known as the law of syllogism)
• Problem 4: Express the exclusive disjunction (XOR) operation using only the logical connectives $\wedge$, $\vee$, and $\neg$
  • Solution: The exclusive disjunction of $p$ and $q$ can be expressed as $(p \vee q) \wedge \neg(p \wedge q)$