Question

Check by the truth table method which of the following propositions are tautologies (a) \((\neg \varphi \vee \psi) \leftrightarrow(\psi \rightarrow \varphi)\) (b) \(\varphi \rightarrow((\psi \rightarrow \sigma) \rightarrow((\varphi \rightarrow \psi) \rightarrow(\varphi \rightarrow \sigma)))\) (c) \((\varphi \rightarrow \neg \varphi) \leftrightarrow \neg \varphi\) (d) \(\neg(\varphi \rightarrow \neg \varphi)\) (e) \((\varphi \rightarrow(\psi \rightarrow \sigma)) \leftrightarrow((\varphi \wedge \psi) \rightarrow \sigma)\) (f) \(\varphi \vee \neg \varphi\) (principle of the excluded third) (g) \(\perp \leftrightarrow(\varphi \wedge \neg \varphi)\) (h) \(\perp \rightarrow \varphi\) (ex falso sequitur quodlibet)

Short answer

Tautologies are (b), (e), (f), and (h).

Step-by-step solution

Understanding the Propositions

Each proposition needs to be evaluated to determine if it is a tautology. A tautology is a formula which is true in every possible interpretation. We will use truth tables to evaluate this.

Constructing the Truth Table for (a)

For the proposition \((eg \varphi \vee \psi) \leftrightarrow(\psi \rightarrow \varphi)\), construct a truth table. Determine whether this logical equivalence holds for all combinations of truth values of \(\varphi\) and \(\psi\).

Evaluating (a) through Truth Table

The truth table for \(eg \varphi \vee \psi\) and \(\psi \rightarrow \varphi\) must match in all rows for the proposition to be a tautology. Check if \((eg \varphi \vee \psi) \leftrightarrow (\psi \rightarrow \varphi)\) results in "true" for all possible truth values of \(\varphi\) and \(\psi\).

Constructing the Truth Table for (b)

For the proposition \(\varphi \rightarrow((\psi \rightarrow \sigma) \rightarrow((\varphi \rightarrow \psi) \rightarrow(\varphi \rightarrow \sigma)))\), construct a truth table. Evaluate every possible outcome by assigning all combinations of truth values to \(\varphi\), \(\psi\), and \(\sigma\).

Evaluating (b) through Truth Table

The expression \((\psi \rightarrow \sigma) \rightarrow((\varphi \rightarrow \psi) \rightarrow(\varphi \rightarrow \sigma))\) always yields true, making \(\varphi \rightarrow ...\) also true if \(\varphi\) is false or if the inner expression is true for all entries.

Constructing Truth Table for (c)

For \((\varphi \rightarrow eg \varphi) \leftrightarrow eg \varphi\), build a truth table considering all combinations for \(\varphi\). Evaluate \((\varphi \rightarrow eg \varphi)\) and compare it to \(eg \varphi\).

Evaluating (c) through Truth Table

The proposition will not be a tautology if there exists even one comparison in the truth table that results in false. Check if both sides of the equivalence are always equal.

Constructing Truth Table for Each Proposition (d - h)

Use truth tables to evaluate each of the remaining propositions \(d\) through \(h\): (d) \(eg(\varphi \rightarrow eg \varphi)\) (e) \((\varphi \rightarrow(\psi \rightarrow \sigma)) \leftrightarrow((\varphi \wedge \psi) \rightarrow \sigma)\) (f) \(\varphi \vee eg \varphi\) (g) \(\perp \leftrightarrow(\varphi \wedge eg \varphi)\) (h) \(\perp \rightarrow \varphi\)

Evaluating Each From (d-h)

Verify with truth tables:- (d) Is false when \(\varphi\) is true.- (e) Is true for all values because it represents Curry-Howard correspondence for implications.- (f) Is always true, known as the law of excluded middle.- (g) Is always false.- (h) Is always true, because from falsehood anything follows (ex falso quodlibet).

Conclusion from Truth Table Results

Summarize which propositions from (a) to (h) are tautologies based on all truth table evaluations: - Tautologies: (b), (e), (f), (h) - Non-tautologies: (a), (c), (d), (g)

Key concepts

truth table

A truth table is a mathematical table used to determine the truth value of logical expressions based on all possible combinations of truth values for the variables involved. In this context, truth tables are crucial for evaluating whether a proposition is a tautology—a statement that is always true, regardless of the truth values of its components.

To construct a truth table, you must first list all variables and their possible truth values. For example, if a proposition includes variables \(\varphi\) and \(\psi\), you would list all combinations of "True" and "False" for \(\varphi\) and \(\psi\). Each row of the table represents a different combination of these truth values.

A truth table allows you to systematically evaluate logical expressions by breaking them down into simpler parts. This process helps reveal the overall truth value of a compound statement for each possible combination of its components. If the end result is "True" for every row, the statement is a tautology. Conversely, a single "False" outcome means it's not a tautology.

propositional logic

Propositional logic is a branch of logic that deals with propositions, which are statements that can be either true or false. The foundational elements of propositional logic are simple statements, and their truth values as they are combined using logical connectives such as "and" (\(\wedge\)), "or" (\(\vee\)), "not" (\(eg\)), "implies" (\(\rightarrow\)), and "if and only if" (\(\leftrightarrow\)).

In propositional logic, more complex statements (propositions) are built from simpler ones using these connectives. Each compound proposition can be analyzed through truth tables to determine its validity under different circumstances.

Propositional logic serves as the base for more complex forms of logic. It allows you to create expressions with multiple propositions and understand how altering any individual part affects the whole. This logic finds applications in computer science, mathematics, and philosophy, as it provides the tools for formal reasoning and problem-solving.

logical equivalence

Logical equivalence occurs when two logical expressions always yield the same truth value for all possible combinations of truth values of their variables. In simpler terms, two propositions are logically equivalent if their truth tables are identical.

Logical equivalence is a key concept in evaluating tautologies, as demonstrated in the original exercise. For instance, the proposition \((eg \varphi \vee \psi) \leftrightarrow (\psi \rightarrow \varphi)\) is evaluated for logical equivalence between its two parts to determine if it's universally true. If both yield identical truth tables, they are logically equivalent, thereby confirming the expression as a tautology.

Understanding logical equivalence allows us to simplify logical expressions, making them easier to analyze or apply in different contexts. Recognizing equivalent expressions helps reduce complexity in computations and proofs, an aspect fundamental not only in theoretical exercises but also in practical applications like digital circuit design and automated reasoning.

law of excluded middle

The law of excluded middle is a principle in classical logic stating that for any proposition \(\varphi\), either \(\varphi\) is true, or its negation \(eg \varphi\) is true. In essence, this principle asserts that there is no middle ground between being true or false—no third option exists.

This law is reflected in the proposition \(\varphi \vee eg \varphi\), which is a tautology. The truth table for this expression shows that every possible combination of truth values for \(\varphi\) results in "True."

The law of excluded middle plays a crucial role in classical reasoning, including mathematical proofs and logical argumentation. It simplifies reasoning by allowing assumptions that either a statement or its negation holds, making it one of the cornerstones of classical logic applied in mathematics, philosophy, and computer science.