Question

Determine conjunctive and disjunctive normal forms for \(\neg(\varphi \leftrightarrow \psi)\), \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi,(\varphi \rightarrow(\varphi \wedge \neg \psi)) \wedge(\psi \rightarrow(\psi \wedge \neg \varphi))\)

Short answer

CNF and DNF: \(\neg(\varphi \leftrightarrow \psi)\) is \((\varphi \land \neg\psi) \lor (\neg\varphi \land \psi)\). For \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi\): \(\top\). For \((\varphi \rightarrow (\varphi \land \neg \psi)) \land (\psi \rightarrow (\psi \land \neg \varphi))\), both forms: \((\neg\varphi \lor \neg\psi) \land (\neg\psi \lor \neg\varphi)\).

Step-by-step solution

Simplifying Negation of Biconditional

Start with the expression \( eg(\varphi \leftrightarrow \psi) \). The biconditional \( \varphi \leftrightarrow \psi \) is equivalent to \((\varphi \land \psi) \lor (eg\varphi \land eg\psi)\). The negation of this expression becomes \((\varphi \land eg\psi) \lor (eg\varphi \land \psi)\). This is the disjunctive normal form (DNF).

Conjunctive Normal Form for \(\neg(\varphi\leftrightarrow\psi)\)

The DNF found in Step 1, \((\varphi \land eg\psi) \lor (eg\varphi \land \psi)\), represents both the simplest DNF and conjunctive normal form (CNF) since it's in both forms inherently.

Simplify and Find CNF for Complex Implication

The expression \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi\) can be rewritten using implications: \((eg\varphi \lor \psi) \rightarrow \psi\) becomes \((egeg\varphi \land eg\psi) \lor \psi)\) which further simplifies to \(\varphi \lor (eg\psi \lor \psi)\). The CNF form simplifies to \(\varphi \lor \top\) which is \(\top\).

DNF of Complex Implication

The DNF of \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi\) is simpler due to its tautological nature in Step 3. It simplifies directly to \(\top\) in both CNF and DNF.

Simplify and Find CNF for Conjunction of Conditionals

The expression \((\varphi \rightarrow (\varphi \land eg \psi)) \land (\psi \rightarrow (\psi \land eg \varphi))\) becomes \((eg\varphi \lor (\varphi \land eg \psi)) \land (eg\psi \lor (\psi \land eg \varphi))\). Applying distribution, this becomes \(((eg\varphi \lor \varphi) \land (eg\varphi \lor eg\psi)) \land ((eg\psi \lor \psi) \land (eg\psi \lor eg\varphi))\) which simplifies directly to \((\top \land (eg\varphi \lor eg\psi)) \land (\top \land (eg\psi \lor eg\varphi))\). The CNF simplifies to \((eg\varphi \lor eg\psi) \land (eg\psi \lor eg\varphi)\).

DNF of Conjunction of Conditionals

The DNF is derived from the constituent CNF \((eg\varphi \lor eg\psi) \land (eg\psi \lor eg\varphi)\), which is inherently in both forms, as it represents a conjunction "or" form.

Key concepts

Conjunctive Normal Form

The Conjunctive Normal Form (CNF) is an essential way to organize logical expressions. It's constructed as an

• AND of ORs
• Each part inside an OR is called a literal

This structure helps us simplify logical expressions for easier manipulation.
For our exercise, consider the expression: \(eg(\varphi \leftrightarrow \psi)\). From Step 2, this expression already achieves its CNF. The beauty of CNF is that if a logical expression inherently holds \(eg(\varphi \leftrightarrow \psi) = (\varphi \land eg\psi) \lor (eg\varphi \land \psi)\), converting it into CNF is straightforward as it's a combination of conjunctions inside disjunctions.
In the example \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi\), simplifying using knowledge of implications and tautologies simplifies directly to \(\top\). With \(\top\), anything ANDed with true maintains a CNF form of itself, confirming the expression is already in conjunctive form.
Thus, CNF greatly aids not only in simplifying expressions but in keeping them easily manageable for further logical deductions.

Disjunctive Normal Form

Disjunctive Normal Form (DNF) is a logical organization where an expression is presented as an

• OR of ANDs
• Composed of conjunctions that are then summed by disjunctions

This form allows for easy recognition and handling of expressions.
In our task, the logical negation \(eg(\varphi \leftrightarrow \psi) = (\varphi \land eg\psi) \lor (eg\varphi \land \psi)\) perfectly demonstrates DNF. The expression is naturally broken into individual ANDed literals which later unify under a disjunction.
When addressing \(((\varphi \rightarrow \psi) \rightarrow \psi) \rightarrow \psi\), our solution simplifies it both in CNF and DNF as \(\top\). This indicates that the expressions are outright tautologies, showing how divergence into simpler forms in DNF applies without additional complexity.
Therefore, breaking expressions into DNF exposes their basic nature, enabling effective logic assessment.

Logical Expressions

Logical expressions are used widely in computer science, mathematics, and day-to-day logical reasoning. They form the backbone of logical computation:

• Composed of variables, connectives, and operators
• Techniques like CNF and DNF help simplify and evaluate these expressions

The operation of turning expressions into CNF or DNF aids not just simplification, but ensures any logical result remains sound and justified.
In our example exercise, dealing with formulas like \(eg(\varphi \leftrightarrow \psi)\) and its transformation enhances computational logic's efficacy. It enables an easy checking of properties such as satisfiability or tautology.
Understanding logical expressions deeply, from interpretations to handling operations, enriches your analytical toolset when breaking down complex concepts into simpler ideas.

Biconditional Negation

Biconditional negation refers to the negation of a biconditional expression \(\varphi \leftrightarrow \psi\). The biconditional itself asserts that both sides are equivalent. Thus, it is true if and only if \(\varphi\) and \(\psi\) share the same truth value.
Negating a biconditional means identifying when the two terms diverge:

• Becomes true when one is false, or vice versa
• Transforms into logical disjunctions and conjunctions

This can be proved by expressing \(eg(\varphi \leftrightarrow \psi)\) as \((\varphi \land eg\psi) \lor (eg\varphi \land \psi)\)\.
Understanding biconditional negation is pivotal to manipulating truth scenarios within logic.
In our solution from Step 1, converting \(eg(\varphi \leftrightarrow \psi)\) into simpler CNF and DNF representations underscores its importance in expressive logic handling.