A conditional expression uses simple Boolean-type logic. They enable programming branches and non-infinite loops. They use three basic operators, typically && (for And), || (for Or) and ! (for Not). And and Or operators have a left and right side. And is considered true if both sides are also true. Or is true as long as one side is true. Not switches between true and false. We generally write this as a truth table.
| A | B | Or | And |
|---|---|---|---|
| F | F | F | F |
| F | T | T | F |
| T | F | T | F |
| T | T | T | T |
| A | Not |
|---|---|
| F | T |
| T | F |
Note that conditional logic differs from Boolean logic. Boolean logic is evaluated with hardware while conditional logic is normally evaluated algorithmically. For example, if code contains: if (A && B) {exp}, the compiler evaluates A first. If A is false then B isn't checked and exp isn't executed. If A is true then it checks B. If B is true then exp is evaluated. Similarly, in the expression if (A || B) {exp}, A is evaluated first. If A is true then it just executes exp without checking B. If A is false then it evaluates B. If B is true then it executes exp. Programmers sometimes use this feature when writing conditional expressions.
Boolean algebra displays Boolean logic using mathematical operators. Multiplication is And while addition is Or. So A && B can be written as A*B or AB. In Boolean algebra, order of operations is the same as math. AB + CD is equivalent to (AB) + (CD). Not is written as a line over the variable like A. The following identities/laws apply:
- A(BC) = (AB)C
- A+(B+C) = (A+B)+C
- AB = BA
- A+B = B+A
- A(B+C) = AB+AC
- AF = F
- AT = A
- A+F = A
- A+T = T
- AA = A
- A+A = A
- A(A + B) = A
- A+AB = A
- A+AB = A+B
- A(A+B) = AB
- A+A = T
- AA = F
- A = A
- A B = A+B
- A+B = AB
Digital hardware has a great trick for simplifying logic expressions called a Karnaugh map. It's a visual and intuitive way to simplify logic expressions. Suppose there are two conditionals, A and B. These conditionals are true or false. True will be marked as A while false is A. We draw a rectangle with all potential combinations of A and B.
This is our Karnaugh Map. Fill in the map with the combinations. You can use anything that makes sense to you, such as numbers or T and F. Suppose our conditions are AB and AB. Fill it in like:
We can simplify the expression using Boolean arithmetic. AB + AB = A(B + B) = A (1) = A. The Karnaugh map provides the same answer. Circle the 1's on the map.
Now ask yourself what distinguishes ones from zeroes. In this case, the ones are in B and B, so B can't determine the result. Every 1 is in the A region. So the condition is A, identical to the Boolean arithmetic simplified result.
Now examine the rules of And and Or. Here are the Karnaugh maps for AB and A+B. A is marked in blue and B is marked in red.
AB = , A+B =
In terms of sets, And represents intersection while Or represents union. That's why they are sometimes written as intersection or union. So we can calculate the solution to various problems using a combination of intersections and unions. This isn't important for two variable Karnaugh maps but becomes more important for Karnaugh maps with more variables. Consider a Karnaugh map of four variables. Two variables have 4 combinations (22) while four variables have 16 combinations (24).
Let's fill in some values.
Look at the map and circle regions of 1's. In this case, you'll get:
In each circle, A and B don't matter. So the expression can be simplified to C D + C D. We can achieve the same result with Boolean algebra. The initial expression is:
A B C D + A B C D + A B C D + A B C D + A B C D + A B C D + A B C D + A B C D
= C D( A B + A B + A B + A B) + C D( A B + A B + A B + A B)
= C D( A(B + B) + A(B + B)) + C D( A(B + B) + A(B + B))
= C D( A(1) + A(1)) + C D( A(1) + A(1))
= C D( A + A) + C D( A + A)
= C D(1) + C D(1)
= C D + C D
So you can achieve the same result either way.
Conditional operators in most languages don't include xor or xnor, so we can't use those. Boolean xor/xnor operators exist, but not conditional operators. For conditional operators we're limited to && and ||, which represent and and or respectively. If our map is slightly more complex, the benefits will quickly become apparent. For example, consider this Karnaugh map.
We can solve this several ways. The first solution is:
This leads to a solution of: A C D + B C D + A C D + B C D. This can be further simplified to: C D(A + B) + C D (A + B) = (C D + C D)(A + B) You can also solve the Karnaugh map with:
The blue boxes are written as (C D + C D). The red boxes are A + B. We want the intersection of these two groups so we use: (C D + C D)(A + B) This is the solution.
This solution needs a little more explanation. Let's review intersection and union as they apply to Karnaugh maps. Intersection is multiplication (*) while union is addition (+).
(D) + (C) = (D+C)
(D) * (C) = (D C)
When written like this, intersection and union become simple. So the process of solving Karnaugh maps can be expressed as a series of intersections and unions of Karnaugh maps.
With the introduction out of the way, the real strength of Karnaugh Maps can be revealed. Conditional statements often have combinations that will never happen. These are really annoying to account for with Boolean algebra while a Karnaugh Map solves them intrinsically. Suppose we have the following map:
A dash represents a case that will never happen. With this in mind, we can simplify the solution to:
This solution is: C D + C D. This solution is not easy to find using Boolean algebra.
In addition to unknowns, a Karnaugh Map can also hold multiple cases. Suppose there are four potential responses.
C code for this Karnaugh Map would be:
if (C && D) {
// Code for case 1
} else if (!A && !B) {
// Code for case 2
} else if (!C && !D) {
// Code for case 3
} else {
// Code for case 0
}
A text version of the Karnaugh map can be kept in comments to explain the code.
Let's try a practical example of simplifying some code. Suppose you see the code:
if (((A && B) || (A && !B && !D) || (C && D)) && (!C && !D)) { ... }
This can be simplified with Karnaugh Maps to:
(A B) + (A B D) + (C D) =
* (C D) = = A C D
This can be written as:
if (A && !C && !D) { ... }
In conclusion, Karnaugh maps provide an interesting and powerful tool for simplifying conditional expressions.