| Home Notation Parse Trees Predicate Logic Propositional Logic Proofs Sets Evaluating wffs Binary Boolean Functions Counting About |
| BINARY BOOLEAN
functions | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| "[the problems aren't always easy]... get
over it..." K. Holladay, 18 November 1998 "I have often noticed that when people come to understand a mathematical proposition in some other way than that of the ordinary demonstration, they promptly say, 'Oh, I see. That's how it must be.' This is a sign that they understand from within their own system." Georg Christoph Lichtenberg | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary Boolean Functions: The
Sixteen Binary Boolean Functions 1. Show the truth table for each of the 16 binary Boolean functions 2. Identify the pairs of functions that are complementary. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary Boolean Functions:
Properties 1. How many are commutative? 2. How many are associative? 3. How many are distributive? | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| The solutions | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary Boolean Functions: Binary Boolean Functions: The Sixteen Binary Boolean Functions 1. Show the truth table for each of the 16 binary Boolean functions Two key ideas here: the functions are binary, so we are only looking at two variables: p and q; secondly, they're binary- so count in binary (0 ª false, 1 ª true) beginning with 0000 and ending with 1111.
Notice that all of them don't have common names. 2. Identify the pairs of functions that are complementary. 1) constant true and constant false, 2) NAND and AND, 3) OR and NOR, 4) XOR and IFF, 5) p and p', 6) q and q', 7) #2 and IMPLIES, 8) #11 and #4. Binary Boolean Functions: Properties The simplest, but most time-consuming strategy is to use truth tables (with the minimum number of variables) to determine the validity of each property for each function. A smarter strategy would be to look at the table of functions and consider whether p true, q false has the same value as p false, q true. If the two values are the same, then the function is commutative. 1. How many are commutative? Eight (0, 1, 6, 7, 8, 9, 14, 15) Only two variables are needed for each proof.
2 a. How many are associative? Eight (0, 1, 3, 5, 6, 7, 9, 15) b. How many are distributive? (0, 1, 3, 5, 7, 12, 15) You'll need a minimum of three variables for these: only the concluding columns for associative and distributive properties of f1 and f2 are shown.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||