Question

Show that the following formulas from Table 2.5 are tautologies: (a) \((p \wedge p) \leftrightarrow p\) (b) \((p \wedge(p \rightarrow q)) \rightarrow q\) (c) \((p \rightarrow r) \leftrightarrow(\neg r \rightarrow \neg p)\)

Short answer

All three formulas are tautologies because they are true for any truth values of the variables.

Step-by-step solution

Define a Tautology

A formula is called a tautology if it is true for all possible truth values of its variables. This means, regardless of how you assign values to the variables within the formula (true or false), the outcome will always be true.

Analyze Formula (a)

Formula (a) is \((p \wedge p) \leftrightarrow p\). We start by examining the term \(p \wedge p\), which simplifies to \(p\) since \(p \wedge p\) is true if and only if \(p\) is true. So, the formula becomes \(p \leftrightarrow p\), and this expression is always true because any statement is always equivalent to itself.

Examine Formula (b)

Consider \((p \wedge(p \rightarrow q)) \rightarrow q\). First, \(p \rightarrow q\) is true unless \(p\) is true and \(q\) is false. Thus \(p \wedge(p \rightarrow q)\) means \(p\) is true, and \(p \rightarrow q\) is also true, implying \(q\) must be true. Then the implication \((...) \rightarrow q\) is always true because if the premise is true, so must be \(q\). If the premise is false, the implication is automatically true by definition.

Explore Formula (c)

Consider \((p \rightarrow r) \leftrightarrow (eg r \rightarrow eg p)\). By using the contra-positive law, \(p \rightarrow r\) is logically equivalent to \(eg r \rightarrow eg p\). Hence, the formula \((p \rightarrow r) \leftrightarrow (eg r \rightarrow eg p)\) is always true as it expresses a logical equivalence.

Conclude

After evaluating each formula, we see that they hold true for all possible truth values of \(p\), \(q\), and \(r\). Therefore, each formula is a tautology, by definition.

Key concepts

Logical Equivalence

Logical equivalence is a fundamental concept in propositional logic. It occurs when two statements or propositions have the same truth value in every possible scenario. When we say that two formulas are logically equivalent, we mean that no matter how you assign truth values to their variables, the truth values of the entire expressions will always match in every case. For example, consider this formula: - \( (p \rightarrow r) \leftrightarrow (eg r \rightarrow eg p) \). Using the rule of contraposition, we know that - \( p \rightarrow r \) is equivalent to - \( eg r \rightarrow eg p \). Thus, the expression is always true, highlighting logical equivalence. Logical equivalence is vital for understanding tautologies because tautologies often arise from logically equivalent expressions.

Propositional Logic

Propositional logic is a branch of logic that deals with propositions, which are declarative sentences that can either be true or false. This field of logic uses symbols to represent logical forms, which allows us to analyze statements systematically. The use of operators such as "and" (\(\wedge\)), "or" (\(\vee\)), and "implies" (\(\rightarrow\)) are key in building complex expressions. In propositional logic, we often look at formulas and determine their truthfulness based on different combinations of truth values for the variables involved. This ability to apply rules and derive new statements from existing ones makes propositional logic a powerful tool for reasoning and problem solving. In exercises like this, understanding propositional logic helps classify formulas as tautologies, contradictions, or contingencies, guiding us in logical reasoning.

Truth Tables

Truth tables are an essential tool in propositional logic, providing a clear way to visualize how the truth values of variables affect the outcome of logical expressions. Truth tables list all possible combinations of truth values for their input variables, and then calculate the resulting truth value for the expression. This process helps us confirm whether a formula is always true, sometimes true, or never true. For instance, when examining a formula to verify it as a tautology, a truth table allows us to - systematically check that the formula holds true across all possible truth value assignments. This method ensures that there are no exceptions where the formula becomes false, confirming it as a tautology. By using truth tables, anyone can become more adept at understanding and verifying logical expressions systematically.