Question

For the following formulns find equivalent formulas in CNF and DNF form. Draw combinatorial networks corresponding to the original formulas and their equivalent CNF forms. (a) \((p \wedge q) \leftrightarrow(p \wedge r)\) (b) \(((p \rightarrow q) \rightarrow r) \rightarrow p\)

Short answer

Part (a): CNF is \(((\neg p \vee \neg q \vee p) \wedge (\neg p \vee \neg q \vee r)) \wedge ((p \vee \neg p) \wedge (p \vee \neg r) \wedge (q \vee \neg p) \wedge (q \vee \neg r))\), DNF is \((p \wedge q \wedge r) \vee (\neg p \wedge \neg q) \vee (\neg p \wedge \neg r)\). Part (b): CNF is \((p \vee \neg p \vee q) \wedge (p \vee \neg r)\), DNF is \(((\neg p \wedge \neg r) \vee (q \wedge \neg r)) \vee p\).

Step-by-step solution

Understand the Original Formula (Part a)

The first formula is \((p \wedge q) \leftrightarrow (p \wedge r)\). This is a biconditional expression which means both sides are equivalent. We need to convert this into both CNF (Conjunctive Normal Form) and DNF (Disjunctive Normal Form).

Convert to CNF (Part a)

To convert the biconditional \((p \wedge q) \leftrightarrow (p \wedge r)\) into CNF, we rewrite it as \((eg(p \wedge q) \vee (p \wedge r)) \wedge ((p \wedge q) \vee eg(p \wedge r))\). Next, apply De Morgan's laws and distribution to get \(((eg p \vee eg q) \vee (p \wedge r)) \wedge ((p \wedge q) \vee (eg p \vee eg r))\). This simplifies to \(((eg p \vee eg q \vee p) \wedge (eg p \vee eg q \vee r) ) \wedge ((p \vee eg p) \wedge (p \vee eg r) \wedge (q \vee eg p) \wedge (q \vee eg r))\).

Convert to DNF (Part a)

For DNF, rewrite the biconditional \((p \wedge q) \leftrightarrow (p \wedge r)\) as: \(((p \wedge q) \wedge (p \wedge r)) \vee ((eg(p \wedge q)) \wedge eg(p \wedge r))\). This simplifies using the distributions to \((p \wedge q \wedge r) \vee ((eg p \vee eg q) \wedge (eg p \vee eg r))\). Further simplification gives \((p \wedge q \wedge r) \vee (eg p \wedge eg q) \vee (eg p \wedge eg r)\).

Construct Combinatorial Networks for Part a

Draw logic gates corresponding to the original expression and its CNF form: 1. For \((p \wedge q) \leftrightarrow (p \wedge r)\), use AND gates to create \(p \wedge q\) and \(p \wedge r\), and a XOR gate for the biconditional between them. 2. For CNF, represent each grouping of OR gates as separate lines and combine them with AND gates according to the structure derived.

Understand the Original Formula (Part b)

The formula \(((p \rightarrow q) \rightarrow r) \rightarrow p\) involves implications. We must first transform the implications for easier conversion into CNF and DNF.

Convert Implications (Part b)

Rewrite the implications: \((p \rightarrow q)\) is equivalent to \(eg p \vee q\). So, \((eg p \vee q) \rightarrow r\) becomes \((eg (eg p \vee q)) \vee r\), which simplifies to \((p \wedge eg q) \vee r\). The entire formula becomes \(((p \wedge eg q) \vee r) \rightarrow p\), which rewrites as \((eg ((p \wedge eg q) \vee r)) \vee p\). Simplifying gives \(((eg p \vee q) \wedge eg r) \vee p\).

Convert to CNF (Part b)

From the simplified formula \(((eg p \vee q) \wedge eg r) \vee p\), apply transformations to get it into CNF: 1. Distribute over \( \vee \) to get: \((p \vee eg p \vee q) \wedge (p \vee eg r)\).

Convert to DNF (Part b)

Further simplify for DNF: The original simplified expression \(((eg p \vee q) \wedge eg r) \vee p\) is already close to DNF; break it into: \(((eg p \wedge eg r) \vee (q \wedge eg r)) \vee p\).

Construct Combinatorial Networks for Part b

Create a network using logic gates for original and CNF parts: 1. Original: Use NAND gates converted from the implication structure. 2. CNF: Build using a series of OR gates first and merging them with AND gates to match the formula's logic.

Key concepts

Conjunctive Normal Form (CNF)

In Discrete Mathematics, Conjunctive Normal Form (CNF) is a standardized way of expressing logical formulas. It is particularly useful for simplifying complex logical expressions. CNF is composed of a conjunction (AND) of one or more disjunctions (ORs) of literals. A literal is either a variable or its negation. The primary benefit of CNF is that it facilitates certain computational operations, such as automated theorem proving and logic programming.

To convert a logical expression into CNF, we must ensure that the formula is expressed as a conjunction of clauses, where each clause is a disjunction of literals. For example, a formula in CNF might look like: \[(p \vee eg q) \wedge (eg p \vee q \vee r)\] This formula is CNF because it uses AND operations to join OR clauses. To transform non-CNF formulas into CNF, you can apply logical equivalences and distribution rules, such as De Morgan’s laws and the distributive law for logic.

In combinational logic, CNF helps in designing circuits that are optimized for specific logical functions. These circuits combine multiple logic gates in a structure that directly corresponds to the CNF expression.

Disjunctive Normal Form (DNF)

The Disjunctive Normal Form (DNF) is another way to standardize logical expressions. It is the counterpart to CNF and works by creating a formula that is a disjunction (OR) of conjunctions (ANDs) of literals. Each conjunctive clause represents a possible scenario where the entire logic formula holds true.

To convert into DNF, the formula needs to be expressed as ORs of clauses, with each clause being an AND of literals. For example, a valid DNF might be: \[(p \wedge q) \vee (eg p \wedge r)\] DNF is particularly useful as it breaks down the formula into specific scenarios, which can be easier to analyze or use as input for certain types of decision-making algorithms. Similar to CNF, transformations to DNF involve the use of logical distributions and equivalences, making it useful for cases where an exhaustive enumeration of possibilities is required.

In digital circuit design, DNF provides a guideline for constructing networks that ensure certain outputs from given inputs, helping in creating decision-making circuits.

Combinatorial Networks

Combinatorial Networks are arrangements of logic gates designed to perform specific logical operations that correspond to logical expressions, such as those in CNF or DNF. These networks do not use memory elements and their output depends purely on the current input values.

When designing a combinatorial network, you translate a logical formula into a circuit using logic gates like AND, OR, NOT, NAND, and NOR. Each logical operation in the formula corresponds directly to one or more logic gates in the network. For instance, a CNF expression might be implemented using a series of AND gates following OR gates for each clause.

The efficiency of a combinatorial network often derives from its direct correlation to the logical expression's simplified form, such as CNF or DNF. This ensures that the network performs optimally, reducing potential delays and resource usage. Such networks are crucial in digital electronics for implementing various operations, such as arithmetic computation or data path operations in processors.

Understanding how to construct combinatorial networks from logical formulas is an essential skill in disciplines such as computer engineering and electronic design.