Boolean Algebra
Podcast: Play in new window | Download (37.1MB) | Embed
Subscribe: Apple Podcasts | Spotify | Email | RSS | More
Boolean algebra is a set of rules to describe a problem whose outcome will either be true or false. They were formulated by an English mathematician named George Boole. He’s the namesake for the rules and for the boolean type in statically typed languages.
“Boolean logic can be used to implement binary arithmetic.” ~ Harry Fairhead
Boolean algebra is used to predict the outcome of logic gates in electric circuitry and programming. In computer or binary terms that is 1(true) or 0(false). The predicted outputs can be view with the aid of a truth table which shows the two inputs A and B then the result of the logic gate function.
Episode Breakdown
07:36 Boolean Algebra and Binary Arithmetic
In digital (on or off) circuitry you have the current pass through logic gates to create a response. Inputs have two values ON(1) or OFF(0) determined by the voltage entering. Outputs have the same values but are determined by the function of the gate. Gates can be stringed together to effect the ultimate output.
In boolean algebra there are only two possible inputs or outputs: 1 which also equates to true and 0 which also equates to false. Each logic gate has different algebraic functionality.
09:45 AND Gates
“Bear in mind that the inputs while they are a digital signal they can come out of other gates.”
Outputs a true if both values are true. It is true only if both inputs are true and false if either or both inputs are false. This is boolean algebra for multiplication. Like normal math anything times zero is zero (0A = 0). Also anything times one is itself (1A = A). Unlike normal math anything multiplied by itself is itself (AA = A). On a truth table AND is represented by a “.” or “*” so that A AND B is A.B or A*B.
12:56 OR Gates
“It’s hard to get your head around this, it’ll click suddenly.”
Outputs a true if at lease one of the values are true. It is true if either or both inputs are true and false only if both inputs are false. This is boolean algebra for addition. Anything plus zero is itself (A + 0 = A). Anything plus one is one (A + 1 = 1). Anything plus itself is itself (A + A = A). On a truth table OR is represented by a “+” so A OR B is A+B.
16:33 NOT Gates
“This is a unary operator.”
Outputs the opposite of the value entered. Algebraically if A=1 then NOT A=0. In boolean mathematics anything multiplied by it’s opposite is 0. At least one of the values must be 0. In boolean mathematics anything added to it’s opposite is 1. At least one of the values must be 1. Just like grammar double negatives mean the statement is true. On a truth table this is represented by a line over the entered value: A.
20:10 NAND Gates
NAND stands for NOT-AND gate. In digital circuitry it is an AND gate followed by a NOT gate. On a truth table this is represented by a line over the AND so a A.B. Outputs the opposite of the AND logic gate.
21:50 NOR Gates
NOR stands for NOT-OR gate. In digital circuitry it is an OR gate followed by a NOT gate. On a truth table this is represented as A+B. Outputs the opposite of the OR logic gate.
22:38 XOR Gates
“This is what people in English typically mean when they say ‘or’.”
EXOR stands for Exclusive-OR gate. On a truth table it is represented by a (+) with a circle around it. Outputs true only if on but not both inputs are true.
25:03 XNOR Gates
XNOR stands for Exclusive-NOT-OR. On a truth table it is represented with a line over the EXOR. Outputs true only if both inputs are the same.
25:47 Order of Precedence
- Within () always first
- NOT has highest
- AND has middle
- OR has lowest
“When you are doing stuff in code you better lay it out in paratheses the way you intend.”
27:30 Simplification of Boolean Algebra
These laws are used with AND and OR gates to simply the rules around using the gates.
Commutative Law: You can reverse the order of properties without changing the output.
- A + B = B + A
- A.B = B.A
Associative Law: You can associate groups of added or multiplied variable without changing output.
- A + (B + C) = (A + B) + C
- A(BC) = (AB)C
Distributive Law: Expressions of the product of a sum can be expanded or the sum of products can be factored out.
- A(B + C) = AB + AC
- A + (BC) = (A + B)(A + C)
Identity Law: Anything added to or multiplied by itself is itself.
- AA = A
- A + A = A
31:18 DeMorgan’s Theorems
“This is the one I struggled with the most in philosophy”
Inverting all inputs from a gate reverses the gates function from AND to OR. An OR gate with inputs negated acts as a NAND gate (AND then NOT). An AND gate with inputs negated acts as a NOR gate (OR then NOT). Inverting the output of a gate results in the same function ans the opposite gate type of gate with inverted inputs
- (AB) = A + B
- (A + B) = A * B
33:15 Use In Programming
“Boolean algebra finds its most practical use in the simplification of logic circuits.” ~ Tony R. Kuphaldt
Comes to play when evaluating the truth of a statement or the inverse of a statement.
IoTease: Product
Short Circuits Books and Project Kits
This a great way to get started in electronics. Good for kids of all ages. It comes with a book teaching the fundamentals of electronics and a kit will all the parts to do every project in the book.
Tricks of the Trade
Learn the underlying technology. It pays off in weird ways. Sometimes you’ll find that having an understanding of the deep underlying technology can help you reason about what’s going on. The time spent learning what’s under the technology you are using will ultimately help you when you run into snags.
This observation is easily proved as follows. Certainly any law satisfied by all concrete Boolean algebras is satisfied by the prototypical one since it is concrete. Conversely any law that fails for some concrete Boolean algebra must have failed at a particular bit position, in which case that position by itself furnishes a one-bit counterexample to that law. Nondegeneracy ensures the existence of at least one bit position because there is only one empty bit vector. But suppose we rename 0 and 1 to 1 and 0 respectively. Then it would still be Boolean algebra, and moreover operating on the same values. However it would not be identical to our original Boolean algebra because now we find ? behaving the way ? used to do and vice versa. So there are still some cosmetic differences to show that we’ve been fiddling with the notation, despite the fact that we’re still using and .