Compound propositions, then, correspond naturally with combinatorial logic circuits. But we have still not quite settled the question of just how powerful these circuits and propositions are. We’ve looked at a number of logical operators and noted that they can all be expressed in terms of ∧, ∨, and ¬. But might there be other operators that cannot be so expressed? Equivalently, might there be other types of logic gates—possibly with some large number of inputs—whose computations cannot be duplicated with and, or, and not gates? Any logical operator or logic gate computes a value for each possible combination of logical values of its inputs. We could always make a truth table showing the output for each possible combination of inputs. As it turns out, given any such truth table, it is possible to find a proposition, containing only the ∧, ∨, and ¬ operators, whose
Figure 2.6: Finding the proposition whose value is computed by a combinatorial logic circuit. Each wire in the circuit is labeled with the proposition that it represents. The numbering of the labels shows one of the orders in which they can be associated with the wires. The circuit as a whole computes the value of ¬(A ∧ B) ∧ (B ∨ ¬C).
value for each combination of inputs is given precisely by that table.
To see why this is true, it is useful to introduce a particular type of compound proposition. Define a simple term to be either a propositional variable or the negation of
a propositional variable. A conjunction of simple terms would then consist of one or more simple terms put together with ∧ operators. (A ‘conjunction of one simple term’ is just a single simple term by itself. This might not make grammatical sense, but it’s the way mathematicians think.) Some examples of conjunctions of simple terms would bep∧q, p,¬q,and p∧¬r∧¬w∧s∧t. Finally,we can take one or more such conjunctions and join them into a ‘disjunction of conjunctions of simple terms’. This is the type of compound proposition we need. We can avoid some redundancy by assuming that no propositional variable occurs more than once in a single conjunction (since p ∧ p can be replaced by p, and if p and ¬p both occur in a conjunction, then the value of the conjunction is false, and it can be eliminated.) We can also assume that the same conjunction does not occur twice in the disjunction.
Normal forms are part of the syllabus for Reasoning & Logic. These normal forms, such as Disjunctive Normal Form (this subsection) and Conjunctive Normal Form (see the exercises), are important in propositional logic. There are normal forms for other logics, too, such as for predicate logic which we’ll look at in the next Section 2.4.
A compound proposition is said to be in disjunctive normal form, or DNF, if it is a disjunction of conjunctions of simple terms, and if, furthermore, each pro- positional variable occurs at most once in each conjunction and each conjunction occurs at most once in the disjunction.
Using p, q, r, s, A, and B as propositional variables, here are a few examples of pro- positions that are in disjunctive normal form:
(p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ r ∧ s) ∨ (¬p ∧ ¬q)
(p ∧ ¬q)
(A ∧ ¬B) ∨ (¬A ∧ B)
p ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r ∧ w)
Propositions in DNF are just what we need to deal with input/output tables of the type that we have been discussing. Any such table can be computed by a proposition in disjunctive normal form. It follows that it is possible to build a circuit to compute that table using only and, or, and not gates.
Consideratablethatlistsalogicaloutputvalueforeverycombinationofvaluesof several propositional variables. Assume that at least one of the output values is true. Then there is a proposition containing those variables such that the value of the proposition for each possible combination of the values of the variables is precisely the value specified in the table. It is possible to choose the proposition to be in disjunctive normal form.
Proof. Consider any row in the table for which the output value is T. Form a conjunction of simple terms as follows: For each variable, p, whose value is T in that row, include p itself in the conjunction; for each variable, q, whose value is F in the row, include ¬q in the conjunction. The value of this conjunction is T for the combination of variable values given in that row of the table, since each of the terms in the conjuction is true for that combination of variables. Furthermore, for any other possible combination of variable values, the value of the conjunction will be F, since at least one of the simple terms in the conjunction will be false.
Take the disjunction of all such conjunctions constructed in this way, for each row in the table where the output value is true. This disjunction has the value T if and only if one of the conjunctions that make it up has the value T—and that is precisely when the output value specified by the table is T. So, this disjunction of conjunctions satisfies the requirements of the theorem.
This is the first proof of a non-trivial claim that we’ve seen. You will learn about theorems and proofs, and proof techniques, at the end of this chapter and in Chapter 3.
As an example, consider the table in Figure 2.7. This table specifies a desired output value for each possible combination of values for the propositional variables p, q, and r. Look at the second row of the table, where the output value is true. According to the proof of the theorem, this row corresponds to the conjunction (¬p ∧ ¬q ∧ r). This conjunction is true when p is false, q is false, and r is true; in all other cases it is false,
Figure 2.7: An input/output table specifying a desired output for each combination of values of the propositional variables p, q, and r. Each row where the output is T corresponds to a conjunction, shown next to that row in the table. The disjunction of these conjunctions is a proposition whose output values are precisely those specified by the table.
since in any other case at least one of the terms ¬p, ¬q, or r is false. The other two rows where the output is true give two more conjunctions. The three conjunctions are combine d to produce the DNF proposition (¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧q∧r). This proposition computes all the output values specified in the table. Using this proposition as a blueprint, we get a logic circuit whose outputs match those given in the table.
Now, given any combinatorial logic circuit, there are many other circuits that have the same input/output behaviour. When two circuits have the same input/output table, the compound propositions associated with the two circuits are logically equivalent. To put this another way, propositions that are logically equivalent produce circuits that have the same input/output behaviour. As a practical matter, we will usually prefer the circuit that is simpler. The correspondence between circuits and propositions allows us to apply Boolean algebra to the simplification of circuits.
Our preference for simpler applies to compound propositions, whether or not they correspond to circuits. We usually prefer the equivalent form of the proposition that is simpler. Any proposition has an equivalent proposition in DNF. So when proving a theorem about compound propositions, it is sufficient to consider only DNF propositions. This can make the proof easier to write.
For example, consider the DNF proposition corresponding to the table in Figure 2.7. In (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ r), we can factor (q ∧ r) from the last two terms, giving (¬p ∧ ¬q ∧ r) ∨ ((¬p ∨ p) ∧ (q ∧ r)). Since ¬p ∨ p ≡ T, and T ∧ Q ≡ Q for any proposition Q, this can be simplified to (¬p ∧ ¬q ∧ r) ∨ (q ∧ r). Again, we can apply the distributive law to this to factor out an r, giving ((¬p ∧ ¬q) ∨ q) ∧ r). This compound proposition is logically equivalent to the one we started with, but implementing it in a circuit requires only five logic gates, instead of the ten required by the original proposi- tion.8
If you start with a circuit instead of a proposition, it is often possible to find the asso- ciated proposition, simplify it using Boolean algebra, and use the simplified proposition to build an equivalent circuit that is simpler than the original. And simplifying a pro- position to DNF is often a sensible approach.
One way to simplify propositions is using a Karnaugh-map (or K-map for short) as you will learn in Computer Organisation. Using a K-map you can find what they will call a ‘minimal sum of products’. Notice that a sum of products is just a proposition written in DNF. For the course of Reasoning & Logic we may ask you to translate propositions to a DNF form. You can then choose to either do so using rewrite rules, but you are also free to use a K-map if you prefer. In one of the pencasts of this course we show how both methods lead to a result in DNF: youtu.be/GwVngCU9eYY.