LEARNING OBJECTIVES:
At the end of this class, the student will be able to:

1. Apply the DNF/CNF algorithm to concrete expressions to find their conjunctive and disjunctive normal forms.
2. Understand the use of simple and compound switches in propositional logic.
3. Identify the structure of compound switches and black boxes.
4. Use the truth table to summarize information about a device.
5. Extract the DNF and CNF of a device from its truth table.
6. Design a compound switch that has the same operation as a given device.

INDEX
THE DNF/CNF ALGORITHM
ALGORITHM FOR OBTAINING THE NORMAL FORM FROM TRUTH TABLES: BLACK BOXES AND COMPOUND SWITCHES
EXAMPLE EXERCISES

Although we have proven that all propositional logic expressions are equivalent to a normal form, we have not said anything about how to find such normal forms. To achieve this, we will review an algorithm whose goal is to generate expressions in normal form and, finally, we will review the applications that emerge from these topics.

The DNF/CNF Algorithm

The DNF/CNF algorithm is a series of steps that will allow you to find, from any expression in propositional logic, its equivalent expression in DNF or CNF (as appropriate). It is performed as follows:

• STEP 1: Replace all sub-expressions of the form (F\rightarrow G) with (\neg F\vee G), and similarly with (F\leftrightarrow G). Repeat this step until all implications and double implications in the expression are eliminated.
• STEP 2: Eliminate double negations and apply De Morgan’s laws where possible. The following replacements must be applied
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

    When there are no longer sub-expressions of the form \neg\neg G, \neg(G \wedge H) or \neg(G \vee H), continue with step 3.

• Step 3: This step is divided into two parts depending on whether you want to reach a DNF or a CNF
  • If you want to reach a CNF:

    Use \vee-distribution where possible. That is, the following replacements must be applied:

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    When there are no longer expressions of the form G\vee(H\wedge K) or (H\wedge K)\vee G, a CNF will have been reached.

  • If you want to reach a DNF:

    Use \wedge-distribution where possible. That is, the following replacements must be applied:

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    When there are no longer expressions of the form G\wedge(H\vee K) or (H\vee K)\wedge G, a DNF will have been reached.

Examples

Use the DNF/CNF Algorithm for the following expressions in their conjunctive and disjunctive normal forms.

1. (A\rightarrow (B\rightarrow A)) [SOLUTION]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [SOLUTION]

Algorithm for Obtaining the Normal Form from Truth Tables: Black Boxes and Compound Switches

The DNF/CNF algorithm allows us to find, for any expression in propositional logic, its equivalent expression in normal form. But there are situations where we do not have an initial expression to work with in the first place. This is the case when we have the result of a truth table of some expression F whose propositional structure we do not know. Explaining this in words is a long process; the technique, however, is much better understood by showing examples of how it is developed, so I will leave some examples that I will develop in a video, but first you must review the following concepts:

• Wire: Medium through which a signal circulates
• Node: Point where 3 or more wires meet.
• Simple switch: A device that admits the states of on (1) and off (0), always being in one, and only one, of those states. The on state allows the passage of a signal and the off state prevents it.
• Compound switch: It is a device composed of simple switches and wires.
• Black Box: It is any device whose internal structure cannot be observed.

Simple switches are modeled through propositional variables, and compound ones through expressions in propositional logic. The simplest cases are those obtained from the disjunction and conjunction connectors shown below

Conjunction Scheme

Disjunction Scheme

Example Exercises

1. A device is formed by a black box and 4 ordered switches. The activation of the device occurs under the following conditions
   • Condition 1: It is activated if there are two consecutive switches on. This condition stops working if there are three consecutive switches on.
   • Condition 2: It is activated if all the switches are off.
   • Exception: If the previous conditions are not met, then the device turns off.

   a) Summarize this information in a truth table [SOLUTION]

   b) From the truth table, extract the DNF and CNF that reproduce the operation of the machine. [SOLUTION]

   c) Use the CNF or DNF obtained in the previous step (the simplest one) to design a compound switch that has the same operation as the device. [SOLUTION]

2. The same as in the previous exercise, but now the device has 5 switches. [CHALLENGE FOR THE READER]