Question

Find formulas in DNF equivalent to each of the following formulas, and find at least two interpretations that make each formula satisfiable: (a) \(((p \rightarrow q) \rightarrow r) \rightarrow F\) (b) \(\neg(p \leftrightarrow q) \leftrightarrow r\) (c) \((\neg r) \rightarrow(((p \vee q) \rightarrow r) \rightarrow \neg q)\)

Short answer

DNF for (a): \((\neg p \vee q) \wedge \neg r\). DNF for (b): complex. DNF for (c): \((r \wedge q) \vee (p \wedge \neg q)\).

Step-by-step solution

Convert part (a) to DNF

The formula \( ((p \rightarrow q) \rightarrow r) \rightarrow F \) is equivalent to \( eg ((p \rightarrow q) \rightarrow r) \). First, translate \( p \rightarrow q \) to \( eg p \vee q \), then \( (eg p \vee q) \rightarrow r \) to \( eg(eg p \vee q) \vee r \). Simplifying this gives \( (p \wedge eg q) \vee r \). The negation \( eg((p \wedge eg q) \vee r) \) is equivalent to \( eg(p \wedge eg q) \wedge eg r \). Further simplification gives \( (eg p \vee q) \wedge eg r \), which is the DNF.

Interpretations for part (a)

To satisfy \( (eg p \vee q) \wedge eg r \), both conditions must be true:1. \( eg p \) and \( eg r \), with an interpretation like \( (p = F, q = T, r = F) \).2. \( q \) and \( eg r \), with an interpretation such as \( (p = T, q = T, r = F) \).

Convert part (b) to DNF

The formula \( eg(p \leftrightarrow q) \leftrightarrow r \) can be rewritten as \( (p \leftrightarrow q) \oplus r \). First, \( p \leftrightarrow q = (p \wedge q) \vee (eg p \wedge eg q) \). The negation is \( (eg p \wedge q) \vee (p \wedge eg q) \).So, the full expression is \( [((eg p \wedge q) \vee (p \wedge eg q)) \wedge eg r] \vee [((p \wedge q) \vee (eg p \wedge eg q)) \wedge r] \), which is in DNF.

Interpretations for part (b)

To satisfy the DNF, here are two interpretations:1. From \((eg p \wedge q) \wedge eg r\): \( (p = F, q = T, r = F) \).2. From \((p \wedge q) \wedge r\): \( (p = T, q = T, r = T) \).

Convert part (c) to DNF

The formula \( (eg r) \rightarrow (((p \vee q) \rightarrow r) \rightarrow eg q) \) is first converted to \( r \vee (((p \vee q) \rightarrow r) \rightarrow eg q) \). Translate \( (p \vee q) \rightarrow r \) as \( eg(p \vee q) \vee r \) and simplify to \( (eg p \wedge eg q) \vee r \). The full expression becomes \( r \vee [((eg p \wedge eg q) \vee r) \rightarrow eg q] \). Translate this to \( r \vee eg((eg p \wedge eg q) \vee r) \vee q \), which simplifies to \((r \wedge q) \vee (p \wedge eg q)\), which is in DNF.

Interpretations for part (c)

Here are two satisfying interpretations:1. \((r \wedge q)\): \( (p = F, q = T, r = T) \).2. \((p \wedge eg q)\): \( (p = T, q = F, r = F) \).

Key concepts

Logical equivalence

Logical equivalence is an important concept when working with logical formulas. Two formulas are logically equivalent if they show the same truth value in every possible interpretation.
For example, if we have a formula like \( (p \rightarrow q) \rightarrow r \), it is logically equivalent to its transformed version in disjunctive normal form (DNF), which will have the same truth table.
Logical equivalence allows us to replace a formula with another form that might be easier to analyze or solve.

• Logical equivalence helps simplify complex logical expressions.
• Proving equivalency can reveal insights into the logical structure of formulas.

Understanding logical equivalence is crucial for tasks like converting formulas into DNF, as we can ensure the transformation does not change the logical meaning.

Satisfiability

Satisfiability refers to the assignment of truth values to variables in a logical formula that makes the entire formula true. If such an assignment exists, the formula is called satisfiable; otherwise, it is unsatisfiable.
For example, a formula in DNF can easily show satisfiability. The formula \( (p \wedge eg q) \vee (r \wedge q) \) is satisfiable because at least one of its disjunctions can be true.
Furthermore:

• Each clause in a DNF should contain variables that allow at least one interpretation to hold true.
• Analyzing the satisfiability of logical formulas helps in determining their usability in logical operations.

It's a fundamental step to check satisfiability when working with logical formulas, as it determines if there are truth conditions under which the formula holds.

Interpretations

Interpretations are assignments of truth values to the variables in a logical formula. These assignments help determine the truth value of the entire formula.
When discussing interpretations, we are essentially working with the possible states that each variable can take.
For examples from the previous exercises:

• The formula \( (eg p \vee q) \wedge eg r \) satisfies the interpretation \( (p = F, q = T, r = F) \).
• Such interpretations provide concrete examples of how formulas behave under different conditions.

By exploring different interpretations, one can find which combinations of truth assignments yield a true or false outcome for the entire formula. This exploration is key for ensuring the consistency and correctness of logical systems.

Logical formulas

Logical formulas are expressions formed by combining variables and logical operators such as \( \wedge \) (and), \( \vee \) (or), \( eg \) (not), \( \rightarrow \) (implies), and \( \leftrightarrow \) (if and only if).
These formulas are used to represent logical statements mathematically.

• A logical formula like \( eg(p \leftrightarrow q) \leftrightarrow r \) can be broken down and converted into DNF to assess its structure more easily.
• Logical formulas are the building blocks for constructing complex logical statements and exploring logical arguments.

Understanding logical formulas is essential for creating precise propositions and for applying logical reasoning in mathematics and computer science. They serve as the foundation for more advanced topics like logical equivalence and satisfiability.