Question

Find formulas in DNF equivalent to each of the following formulas: (a) \(\neg(p \wedge T)\) (b) \(((p \rightarrow q) \rightarrow r) \rightarrow F\) (c) \(((p \rightarrow q) \rightarrow r) \rightarrow T\) (d) \((p \leftrightarrow q) \leftrightarrow r\) (e) \(\neg(p \leftrightarrow q) \leftrightarrow r\) (f) \(((p \vee q) \rightarrow r) \wedge(r \rightarrow \neg(p \vee q))\) (g) \((\neg r) \rightarrow(((p \vee q) \rightarrow r) \rightarrow \neg q)\)

Short answer

DNF for each part: (a) \(\neg p\), (b) \((p \land \neg q \land \neg r)\), (c) \(T\), (d) an expanded DNF formula, (e) an expanded DNF formula, (f) an expanded DNF formula, (g) \((r) \lor (p \land \neg r \land q)\).

Step-by-step solution

Understand the Concept of DNF

Disjunctive Normal Form (DNF) is a way of structuring logical formulas. A formula is said to be in DNF if it is a disjunction (OR) of conjunctions (ANDs) of literals. For a formula to be in DNF, it should look like \((A_1 \land A_2 \land \ldots \land A_n) \lor \ldots \lor (B_1 \land B_2 \land \ldots \land B_m)\). We will convert each given expression to this form.

Solve Part (a) \(\neg(p \wedge T)\)

Apply De Morgan's laws: \(eg(p \wedge T)\) becomes \(eg p \lor eg T\). Since \(T\) is always true, \(eg T\) is false, leading to \(eg p \lor F\), which simplifies to \(eg p\). This is already in DNF since it is a single literal.

Solve Part (b) \(((p \rightarrow q) \rightarrow r) \rightarrow F\)

The expression \(Y \rightarrow F\) is equivalent to \(eg Y\). Therefore, transform the formula to \(eg((p \rightarrow q) \rightarrow r)\). Rewrite \(p \rightarrow q\) as \(eg p \lor q\), then \((eg p \lor q) \rightarrow r\) becomes \((eg p \lor q \lor r)\). Hence, the negation is \((p \land eg q \land eg r)\) in DNF.

Solve Part (c) \(((p \rightarrow q) \rightarrow r) \rightarrow T\)

Since anything implied by \(T\) results in \(T\) (tautology), the formula is trivially \(T\), which can be \((p \land eg p)\) in DNF for completeness.

Solve Part (d) \((p \leftrightarrow q) \leftrightarrow r\)

Express equivalence \(\leftrightarrow\) as \(eg (A \oplus B)\) which can be translated as \((A \land B) \lor (eg A \land eg B)\). Therefore, \((p \leftrightarrow q) \leftrightarrow r\) converts to \(((p \land q) \lor (eg p \land eg q)) \leftrightarrow r\). Further transforms yield \(((p \land q \land r) \lor (eg p \land eg q \land r)) \lor ((p \land eg q \land eg r) \lor (eg p \land q \land eg r))\) in DNF.

Solve Part (e) \(\neg(p \leftrightarrow q) \leftrightarrow r\)

Start by transforming \(eg(p \leftrightarrow q)\) to \((p \land eg q) \lor (eg p \land q)\). Then apply to the \(\leftrightarrow r\) operator which results in a formula \(((p \land eg q \land r) \lor (eg p \land q \land r)) \lor ((p \land q \land eg r) \lor (eg p \land eg q \land eg r))\) in DNF.

Solve Part (f) \(((p \vee q) \rightarrow r) \wedge(r \rightarrow \neg(p \vee q))\)

First rewrite both parts: \((p \vee q) \rightarrow r\) becomes \(eg(p \vee q) \lor r\); \(r \rightarrow eg(p \vee q)\) becomes \(eg r \lor eg(p \vee q)\). Using distribution laws, consolidate to \(((eg p \land \ q) \lor r) \land (eg r \lor (eg p \land eg q))\) and simplify each component into conjunctions to fit the DNF requirements.

Solve Part (g) \((\neg r) \rightarrow(((p \vee q) \rightarrow r) \rightarrow \neg q)\)

The expression \(X \rightarrow Y\) is the same as \(eg X \lor Y\). Rewrite the expression step by step: \((eg r) \rightarrow (eg((p \vee q) \rightarrow r) \lor eg q)\) becomes \(r \lor (p \land eg r \land q)\). Hence, in DNF it is \((r) \lor (p \land eg r \land q)\).

Key concepts

De Morgan's Laws

De Morgan's Laws are crucial tools in propositional logic, especially when dealing with logical equivalences and transformations. These laws provide rules for transforming logical expressions, particularly involving negations of conjunctions and disjunctions.

According to De Morgan's Laws:

• The negation of a conjunction (\(eg(p \land q)\)) is logically equivalent to the disjunction of the negations (\(eg p \lor eg q\)).
• Similarly, the negation of a disjunction (\(eg(p \lor q)\)) is equivalent to the conjunction of the negations (\(eg p \land eg q\)).

In application, you can observe these transformations in the provided solutions. For example, in step 2 of the exercise, De Morgan's Law is applied to \(eg(p \land T)\) to translate it to \(eg p \lor eg T\), which simplifies to \(eg p\) since the negation of True (\(eg T\)) is False.

Logical Equivalences

Logical equivalences are fundamental in propositional logic, as they help simplify complex expressions into more manageable forms. They are like rules that allow us to transform one logical statement into another without changing its truth value.

Some key logical equivalences used in transforming expressions to DNF include:

• The Implication Law, which states that \(p \rightarrow q\) is equivalent to \(eg p \lor q\).
• The Double Negation Law, allowing \(eg(eg p)\) to be simplified to \(p\).
• Distribution, where expressions like \(p \land (q \lor r)\) can be rewritten as \((p \land q) \lor (p \land r)\).

In the exercise, logical equivalences are frequently employed. For instance, in step 3, the implication transformation is used to convert \((p \rightarrow q)\) into \(eg p \lor q\) and further manipulate it into DNF. Understanding these equivalences is crucial for success in logical transformations.

Propositional Logic

Propositional logic is a branch of logic that deals with propositions and their relationships using logical connectives. It serves as the foundation of logical reasoning and analysis, focusing on the way propositions can be combined and transformed.

Within propositional logic, you encounter several important concepts:

• Propositions: Statements that are either true or false.
• Logical Connectives: Operations like AND (\(\land\)), OR (\(\lor\)), NOT (\(eg\)), IMPLICATION (\(\rightarrow\)), and EQUIVALENCE (\(\leftrightarrow\)).
• Truth Values: Each proposition has a truth value of either true (T) or false (F).

In converting expressions to DNF, these logical connectives and their properties are utilized to structure propositional logic expressions into a form that's easier to analyze and understand.

Conjunctions and Disjunctions

Conjunctions and disjunctions are two of the basic operations in propositional logic, defining how propositions can be combined.

• Conjunction (\(\land\)): Represents the "AND" operation. It takes two or more propositions and yields true if all propositions are true. For example, in \((p \land q)\), the conjunction is true only when both \(p\) and \(q\) are true.
• Disjunction (\(\lor\)): Represents the "OR" operation. In this case, the result is true if at least one of the involved propositions is true. In \((p \lor q)\), the expression is true if either \(p\), \(q\), or both are true.

Understanding these operations is crucial when working with DNF, as DNF aims to structure logical expressions primarily around these two connectives. This structuring helps in analyzing logical statements and making them easier to interpret, as seen in the step-by-step conversion of expressions in the exercise.