Question

Find a CNF for each of the following formulas, and prove that each formula is a tautology. (a) \((p \wedge p) \leftrightarrow p\) (b) \((p \wedge(p \rightarrow q)) \rightarrow q\) (c) \((p \rightarrow(r \rightarrow q)) \leftrightarrow((p \wedge r) \rightarrow q)\) (d) \((p \rightarrow r) \leftrightarrow(\neg r \rightarrow \neg p)\)

Short answer

(a) \((\neg p \vee p) \wedge (p \vee \neg p)\); (b) \(\neg p \vee q\); (c) \(\neg p \vee \neg r \vee q\); (d) \((\neg p \vee r) \wedge (p \vee \neg r)\). All are tautologies.

Step-by-step solution

Simplify the Formula (a)

The formula given is \((p \wedge p) \leftrightarrow p\). We can simplify \(p \wedge p\) to just \(p\) because \(p \wedge p\) is equivalent to \(p\). Thus, the formula simplifies to \(p \leftrightarrow p\), which is always true, hence it's a tautology.

Convert to CNF Form (a)

For a formula in a conjunctive normal form (CNF), we use the fact that a tautology such as \(p \leftrightarrow p\) can be expressed as \((eg p \vee p) \wedge (p \vee eg p)\). This is an example of the principle of excluded middle, and holds as a CNF.

Simplify the Formula (b)

The formula \((p \wedge (p \rightarrow q)) \rightarrow q\) can be rewritten using the implication transformation rule as \(eg (p \wedge (eg p \vee q)) \vee q\). Simplifying, we get \((eg p \vee q) \vee q\), which further simplifies to \(eg p \vee q\). Since any time \(p\) is false or if \(q\) is true, the formula will be true, it's a tautology.

Convert to CNF Form (b)

The simplified tautology \(eg p \vee q\) is already in the correct form for CNF, which is a disjunction of literals.

Simplify the Formula (c)

Rewriting \((p \rightarrow (r \rightarrow q)) \leftrightarrow ((p \wedge r) \rightarrow q)\) in terms of basic operators, we have \(eg p \vee eg r \vee q\) \(\leftrightarrow eg(p \wedge r) \vee q\). Simplification shows both sides are logically equivalent, making the entire expression a tautology.

Convert to CNF Form (c)

The formula \(eg p \vee eg r \vee q\) is already in CNF, as it is a disjunction of literals.

Simplify the Formula (d)

The expression \((p \rightarrow r) \leftrightarrow (eg r \rightarrow eg p)\) can be rewritten using logic transformations: \((eg p \vee r) \leftrightarrow (r \vee eg p)\). As both expressions are equivalent, the result is a tautology.

Convert to CNF Form (d)

The CNF form of \((eg p \vee r) \wedge (p \vee eg r)\) effectively captures the tautology expressed by this equivalence.

Key concepts

Tautology

A tautology is a statement or formula in logic that is always true, no matter the truth values of its components. This means that for every possible situation, the formula evaluates to true. Tautologies are important in logic because they act as foundational truths that need no external proof.
For example, consider the formula \[(p \wedge p) \leftrightarrow p\]This simplifies to \[p \leftrightarrow p\]This statement is always true because we know that "p if and only if p" holds under all circumstances.

Tautologies help verify logical equivalences and are often used in proving more complex theorems in logic.

Logic Simplification

Logic simplification involves reducing a complex logical formula into a simpler but equivalent form. This simplification is crucial for both understanding the logical structure and for converting formulas into specific forms like Conjunctive Normal Form (CNF).
Take a look at the formula \[(p \wedge (p \rightarrow q)) \rightarrow q\]Simplifying using logical rules, we can rewrite it as:\[eg p \vee q\]This step helps in identifying tautologies and streamlines the process of creating CNF. During simplification, equivalent expressions like \(p \wedge p\) are reduced to \(p\), since they carry the same meaning. Logic simplification is a tool to make problem-solving more efficient in discrete mathematics.

Implication Transformation

Implication transformation is the process of converting logical implications into equivalent expressions using other logical operators. This is useful when working with complex formulas and aids in simplification.
An implication \(p \rightarrow q\) can be rewritten as \(eg p \vee q\). For example, in the formula\[(p \rightarrow (r \rightarrow q)) \leftrightarrow ((p \wedge r) \rightarrow q)\]we transform implications to get:\[eg p \vee eg r \vee q\]This transformation is beneficial for both understanding simpler forms of the formula and identifying logical equivalences. By breaking down implications through transformations, we can better manipulate and evaluate logical statements, an essential skill in discrete mathematics.

Discrete Mathematics

Discrete Mathematics is the branch of mathematics that deals with discrete objects, often involving counting, graph theory, and logic. In terms of logic, it focuses on topics like set theory, combinatorics, and proofs.
Working with formulas in identifying CNF is a part of discrete mathematics, where understanding logic and tautologies plays a crucial role. Discrete mathematics provides the tools to work with logical statements, allowing one to transform, simplify, and manipulate them.
As shown through exercises with tautologies and logic transformations, discrete mathematics combines logical reasoning with mathematical techniques to solve problems. It forms the foundation of computer science and mathematical proofs, making the understanding of CNF, tautologies, and transformations vital for students and professionals alike.