Difference between revisions of "Boolean Algebra"
Marc Brown (talk  contribs) 
Marc Brown (talk  contribs) 

Line 180:  Line 180:  
Problems in this category are typically of the form "Given a Boolean expression, simplify it as much as possible" or "Given a Boolean expression,  Problems in this category are typically of the form "Given a Boolean expression, simplify it as much as possible" or "Given a Boolean expression,  
find the values of all possible inputs that make the expression ''true''.  find the values of all possible inputs that make the expression ''true''."  
=== Sample Problem 1: Simplify ===  === Sample Problem 1: Simplify ===  
Line 191:  Line 191:  
The simplification proceeds as follows:  The simplification proceeds as follows:  
:{  :$\overline{ \overline{A(A+B)} + B\overline{A}}$  
::{  
    
 <math>\overline{ \overline{A(A+B)} + B\overline{A}}</math>   <math>\overline{ \overline{A(A+B)} + B\overline{A}}</math>  
    
 <math>= \left(\overline{ \overline{A(A+B)}}\right) \cdot \left(\overline{ B\overline{A}}\right)</math>    style="width: 2em" <math>= \left(\overline{ \overline{A(A+B)}}\right) \cdot \left(\overline{ B\overline{A}}\right)</math>   
 (DeMorgan's Law)   (DeMorgan's Law)  
Line 254:  Line 255:  
:{ class="wikitable" style="textalign: center"  :{ class="wikitable" style="textalign: center"  
    
!1  !style="backgroundcolor: #cceeff; fontsize: xsmall" #1  
!2  !style="backgroundcolor: #cceeff; fontsize: xsmall" #2  
!3  !style="backgroundcolor: #cceeff; fontsize: xsmall" #3  
!4  !style="backgroundcolor: #cceeff; fontsize: xsmall" #4  
!5  !style="backgroundcolor: #cceeff; fontsize: xsmall" #5  
!6  !style="backgroundcolor: #cceeff; fontsize: xsmall" #6  
!7  !style="backgroundcolor: #cceeff; fontsize: xsmall" #7  
!8  !style="backgroundcolor: #cceeff; fontsize: xsmall" #8  
  
style="backgroundcolor: #cceeff"  
style="backgroundcolor: #cceeff"  
!style="backgroundcolor: #cceeff; fontsize: xsmall" OR of Col#1, Col#2  
!style="backgroundcolor: #cceeff; fontsize: xsmall" NOT of Col#3  
!style="backgroundcolor: #cceeff; fontsize: xsmall" NOT of Col#1  
!style="backgroundcolor: #cceeff; fontsize: xsmall" ADD of Col#1, Col#2  
!style="backgroundcolor: #cceeff; fontsize: xsmall" OR of Col#4, Col#6  
!style="backgroundcolor: #cceeff; fontsize: xsmall" NOT of Col#7  
    
Line 272:  Line 283:  
!<math>\overline{A+B} + \overline{A}B</math>  !<math>\overline{A+B} + \overline{A}B</math>  
!<math>\overline{\overline{A+B} + \overline{A}B}</math>  !<math>\overline{\overline{A+B} + \overline{A}B}</math>  
   
Revision as of 15:01, 23 July 2018
Boolean algebra is the branch of algebra in which the values of the variables and constants have exactly two values: true and false, usually denoted 1 and 0 respectively. This description borrows from the Wikipedia article on Boolean Algebra.
The basic operators in Boolean algebra are and, or, and not. The and of two values is true only whenever both values are true. The or of two values is true whenever either or both values are true. The not of a true value is false, and the not of a false value is true. The secondary operators are exclusive or (often called xor) and equivalence . The xor of two values is true whenever the values are different; the equivalence of two values is true when both values are the same. Just as algebra has basic rules for simplifying and evaluating expressions, so does Boolean algebra.
Why is Boolean Algebra Important for ACSL Students?
Boolean algebra is important to programmers, computer scientists, and the general population.
 For programmers, Boolean expressions are used for conditionals and loops. For example, the following snippet of code sums the even numbers that are not also multiples of 3, stopping when the sum hits 100:

s = 0 x = 1 while (s < 100): if (x % 2 == 0) and (x % 3 != 0): s = s + x x = x + 1
Both
s < 100
and(x % 2 == 0) and (x % 3 != 0)
are Boolean expressions.
 For computer scientists, Boolean algebra is the basis for digital circuits that make up a computer's hardware. The Digital Electronics category concerns a graphical representation of a circuit. That circuit is typically easiest to understand and evaluate by converting it to its Boolean algebra representation.
 The general population uses Boolean algebra, probably without knowing that they are doing so, when they enter search terms in Internet search engines. For example, the search expression "red sox yankees" is the Boolean expression
"red" and "sox" and not "yankees"
that will returns web pages that contain the words "red" and "sox", as long as it does not contain the word "yankees". The search expression "jaguar speed car" returns pages about the speed of the jaguar animal, not the Jaguar car.
Operations
Basic operations
The basic operations of Boolean algebra are and, or, and not.
 and (conjunction) is denoted as [math]x \& y[/math], [math]xy[/math], or [math]x \cdot y[/math]. The and of two values is true only when both values are true.
 or (disjunction) is denoted as [math]x + y[/math] . The or of two values is true whenever one or both values are true.
 not (negation) is denoted as [math]\neg x[/math] or [math]\bar{x}[/math] . The not of a value is its opposite; that is, the not of a true value is false whereas the not" of a false value is true.
The values of and, or, and not for all possible inputs is shown in the following truth table:

[math]x[/math] [math]y[/math] [math]x y[/math] [math]x + y[/math] [math]\bar{x}[/math] 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0
Secondary operations
The secondary Boolean operators are exclusive or and equivalence. They are secondary in the sense that they can be composed from the basic operations of and, or, and not.
 exclusive or, typically abbreviated as xor, is denoted as [math]x \oplus y[/math], or [math]x \text{ xor } y[/math]. The xor of two values is true when the values are different. It can also be represented by ands and ors:
 [math]x \oplus y = (x \cdot \bar{y}) + (\bar{x} \cdot y)[/math]
 equivalence is denoted as [math]x \equiv y[/math], [math]x \odot y[/math], or [math]x \text{ equ } y[/math] The equivalence of two values is true when the values are the same; it is the not of the xor function, or from ands and ors:
 [math]x \odot y = x \cdot y + \bar{x} \cdot \bar{y}[/math]
Here is the truth table of xor and equivalence for all four possible inputs.
[math]x[/math] [math]y[/math] [math]x \oplus y[/math] [math]x \odot y[/math] 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1
Laws
A law of Boolean algebra is an identity such as [math]x + (y + z) = (x + y) + z[/math] between two Boolean terms, where a Boolean term is defined as an expression built up from variables and the constants 0 and 1 using the operations and, or, and not.
Monotone laws
Boolean algebra satisfies many of the same laws as ordinary algebra when one matches up or with addition and and with multiplication. In particular the following laws are common to both kinds of algebra:
Associativity of or: [math]x + (y + z)[/math] [math]= (x + y) + z[/math] Associativity of and: [math]x \cdot (y \cdot z)[/math] [math]= (x \cdot y) \cdot z[/math] Commutativity of or: [math]x + y[/math] [math]= y + x[/math] Commutativity of and: [math]x \cdot y[/math] [math]= y \cdot x[/math] Distributivity of and over or: [math]x \cdot (y + z)[/math] [math]= x \cdot y + x \cdot z[/math] Identity for or: [math]x + 0[/math] [math]= x[/math] Identity for and: [math]x \cdot 1[/math] [math]= x[/math] Annihilator for and: [math]x \cdot 0[/math] [math]= 0[/math]
The following laws hold in Boolean Algebra, but not in ordinary algebra:
Annihilator for or: [math]x +1[/math] [math]= 1[/math] Idempotence of or: [math]x +x[/math] [math]= x[/math] Idempotence of and: [math]x \cdot x[/math] [math]= x[/math] Absorption 1: [math]x \cdot (x + y)[/math] [math]= x[/math] Absorption 2: [math]x + (x \cdot y)[/math] [math]= x[/math] Distributivity of or over and: [math]x + (y \cdot z)[/math] [math]=(x + y) \cdot (x +z)[/math]
Nonmonotone laws
Complement of and: [math]x \cdot \overline{x}[/math] [math]= 0[/math] Complement of or : [math]x + \overline{x}[/math] [math]= 1[/math] Double Negation: [math]\overline{ \overline{x}} [/math] [math]= x [/math]
De Morgan's Laws
DeMorgan 1: [math]\overline{ x} \cdot \overline{y}[/math] [math]= \overline{x + y}[/math] DeMorgan 1: [math]\overline{ x} + \overline{y}[/math] [math]= \overline{x \cdot y}[/math]
Sample Problems
Problems in this category are typically of the form "Given a Boolean expression, simplify it as much as possible" or "Given a Boolean expression, find the values of all possible inputs that make the expression true."
Sample Problem 1: Simplify
Problem: Simplify the following expression as much as possible: $ \overline{ \overline{A(A+B)} + B\overline{A}}$
Solution:
The simplification proceeds as follows:
 $\overline{ \overline{A(A+B)} + B\overline{A}}$
[math]\overline{ \overline{A(A+B)} + B\overline{A}}[/math] [math]= \left(\overline{ \overline{A(A+B)}}\right) \cdot \left(\overline{ B\overline{A}}\right)[/math] (DeMorgan's Law) [math]= \left(A(A+B)\right) \cdot \left( \overline{B}+\overline{\overline{A}}\right)[/math] (Double Negation; DeMorgan's Law) [math]= A \cdot \left( \overline{B}+A\right)[/math] (Absorption; Double Negation) [math]= A \overline{B}+AA[/math] (Distribution) [math]= A \overline{B}+A[/math] (Distribution) [math]=A \left( \overline{B}+1\right)[/math] [math]=A \left(1\right)[/math] [math]=A[/math]
Sample Problem 2: Find Solutions
Problem: Find all orderd pairs $(A,B)$ that make the following expression true: $ \overline{ \overline{(A+B)} + \overline{A}B }$
Solution:
There are typically two approaches to solving this type of problem. One approach is to simplify the expression as much as possible, until it's obvious what the solutions are. The other approach is to create a truth table of all possible inputs, with columns for each subexpression.
The simplification approach is as following:
 $ \overline{\overline{(A+B)} + \overline{A}B}$
 $= \overline{\overline{A+B}} \cdot \overline{\overline{A}B}$
 $= (A+B) \cdot (\overline{\overline{A}}+\overline{B} ) $
 $= (A+B) \cdot (A+\overline{B}) $
 $= AA + A\overline{B} + BA + B\overline{B} $
 $= A + A(\overline{B} + B) + 0 $
 $= A + A(1)$
 $= A + A$
 $=A$
This means that all inputs are valid whenever $A$ is true: $(1,0)$ and $(1,1)$
The truth table approach is as following. Each column is the result of a basic operation on two other columns.
#1 #2 #3 #4 #5 #6 #7 #8 OR of Col#1, Col#2 NOT of Col#3 NOT of Col#1 ADD of Col#1, Col#2 OR of Col#4, Col#6 NOT of Col#7 [math]A[/math] [math]B[/math] [math]A+B[/math] [math]\overline{A+B}[/math] [math]\overline{A}[/math] [math]\overline{A}B[/math] [math]\overline{A+B} + \overline{A}B[/math] [math]\overline{\overline{A+B} + \overline{A}B}[/math] 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1
The rightmost column is the expression we are solving; it is true for the 3rd and 4th rows, where the inputs are $(1,0)$ and $(1,1)$.
Online Resources
A great online tutorial on Boolean Algebra is part of Ryan's Tutorials.
The following YouTube videos show ACSL students and advisors working out some previous problems. To access the YouTube page with the video, click on the title of the video in the icon. (You can also play the video directly by clicking on the arrow in the center of the image; however, you'll probably want to have a larger viewing of the video since it contains writing on a whiteboard.) Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.
ACSL Prep  Mrs. Gupta  Boolean Algebra (MegaChristian5555)
Christian is a student participating in ACSL. This video shows how to solve a halfdozen or so Boolean Algebra problems that have appeared in ACSL contests in recent years in the Intermediate and Senior divisions.  
ACSL Boolean Algebra Contest 2 Worksheet 1 (misterminich)
Mr. Minich is an ACSL advisor. This video was one of two he created to help prepare his students for the ACSL Boolean algebra category. It shows solutions to 5 different problems that have appeared in recent years.  
ACSL Boolean Algebra Contest 2 Worksheet 2 (misterminich)
Mr. Minich is an ACSL advisor. This video was one of two he created to help prepare his students for the ACSL Boolean algebra category. It shows solutions to 5 different problems that have appeared in recent years.  
ACSL 3 1314 #1  AM (Gordon Campbell)
This video walks through the solution to finding all ordered triples that make the following Boolean expression true:
This problem appeared in 20132014 in the Senior Division, Contest #3.  
A general tutorial on boolean algebra that can be used for American Computer Science League. (Tangerine Code)
Walks through the simplification of the following Boolean expression:
