Question

Find formulas in CNF 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

Transform to CNF by simplifying, using equivalences, and distributing terms.

Step-by-step solution

Simplify the Formula

For each formula, begin by simplifying any constants if possible. For instance, for part (a): \[eg(p \wedge T) \Rightarrow eg p\] Since any proposition and `True` results in the proposition itself. Use similar simplification for other parts.

Apply Equivalence Rules

Now let's apply logical equivalences to further simplify or transform the expressions, aiming towards Conjunctive Normal Form (CNF). Here are examples:- For part (b):\[((p \rightarrow q) \rightarrow r) \rightarrow F \equiv (eg(p \rightarrow q) \vee r) \vee eg F\] which simplifies to \[(p \wedge eg q) \vee eg r\] and then to \[(eg p \vee eg r) \wedge (eg q \vee eg r)\] as it moves to CNF.- For part (c) the transformation results in:\[(eg(p \rightarrow q) \vee r) \vee T \equiv T\] because anything OR `True` is `True`.

Standardize the Formula

For each logical expression, ensure all uses of implication or equivalency are removed:- Use: \[p \rightarrow q \equiv eg p \vee q\]- Use: \[p \leftrightarrow q \equiv (p \wedge q) \vee (eg p \wedge eg q)\] Transform to get expressions in basic disjunctions.

Apply Distributive Law

For some expressions, use the distributive law to further adjust to CNF, which is a conjunction of disjunctions. Look at expressions with nested or complex disjunctions/conjunctions: - For part (f): \[((p \vee q) \rightarrow r) \equiv eg(p \vee q) \vee r \rightarrow eg p \wedge eg q \vee r\] Then the full CNF transformation results as terms extend.

Conclude with CNF Verification

Check that each expression is in CNF form, i.e., it should look like a conjunction of disjunctions: - Each clause is a disjunction (or) of literals (a variable or its negation), and the overall expression is a conjunction (and) of these disjunctions.

Key concepts

Logical Equivalence

Logical equivalence is central to many logic problems, including transforming logical expressions into conjunctive normal form (CNF). Two statements are logically equivalent if they have the same truth value in every possible scenario. In logical equivalence:

• We can replace subexpressions with logically equivalent ones to simplify complex formulas.
• It involves using known equivalences such as De Morgan's Laws or identities to transform expressions.

In this particular exercise, logical equivalence plays a role when, for example, simplifying a formula such as \(((p \rightarrow q) \rightarrow r) \rightarrow F\), which can then be handled in a way that takes it closer to CNF. Ensuring that we understand these equivalences is vital in streamlining logical expressions.

Implication Removal

One of the preliminary steps in transforming any logical expression into conjunctive normal form (CNF) is removing implications. In logic:

• An implication \(p \rightarrow q\) can be replaced by \(eg p \vee q\), to eliminate the arrow in favor of simpler operations like AND, OR, and NOT.

In the exercise, such as in formula \(((p \vee q) \rightarrow r)\) in part (f), we transform it to \(eg(p \vee q) \vee r\). This modification is crucial because CNF only uses conjunctions of disjunctions, which do not include implications or biconditionals. By removing implications, the structure becomes more amenable to further transformations.

Distributive Law

The distributive law in logic is crucial for converting expressions into conjunctive normal form (CNF). The law allows us to distribute conjunctions over disjunctions and vice versa. It is expressed as:

• \(a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)\)
• \(a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)\)

For CNF changes, this law is often applied to reach the desired form, a conjunction of disjunctions.Utilizing this law correctly is key to turning even complex nested expressions, like those involving combinations from different parts of the exercise, into CNF. Every use should be double-checked to ascertain the final expression adheres to the rule of a conjunction of disjunctions.

Simplification of Logical Expressions

Simplifying logical expressions involves reducing them to their simplest equivalent form. This is key in preparing an expression for CNF transformation:

• Simplification can involve removing tautologies, contradictions, and using known logical identities.
• Remove unnecessary brackets, simplify double negations \((eg(eg a) = a)\), or constants like \(T\) (true) and \(F\) (false).

In part (a), the expression \(eg(p \wedge T)\) simplifies directly to \(eg p\), since any proposition and \(T\) results in the proposition itself.Simplification helps by making the transformation process more straightforward, eventually bringing the expression closer to CNF without unnecessary complexity. Careful step-by-step simplification sets the foundation for achieving a CNF effectively.