Difference between revisions of "Boolean Algebra"

From ACSL Category Descriptions
Jump to navigation Jump to search
 
(94 intermediate revisions by 5 users not shown)
Line 1: Line 1:
''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 overview is loosely based on the Wikipedia article on [[https://en.wikipedia.org/wiki/Boolean_algebra|Boolean Algebra]].  
''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.  


The basic operators in Boolean algebra are "and", "or", and "not". The "and" of two variable results in true only whenever both variables are true. The "or" of two variables is true whenever either or both variables are true. The "not" of a variable changes a true to false and a false to true. Just as algebra has basic rules for simplifying and evaluating expression, so does Boolean algebra.
== Operators ==


==Why is Boolean Algebra Important?==
The basic operators in Boolean algebra are '''AND''', '''OR''', and '''NOT'''. The secondary operators are ''eXclusive OR'' (often called '''XOR''') and ''eXclusive NOR'' ('''XNOR''', sometimes called '''equivalence'''). They are secondary in the sense that they
can be composed from the basic operators.


Boolean algebra is important to programmers, computer scientists, and the general population.
*The '''AND''' of two values is true only whenever both values are true. It is written as $xy$ or $x \cdot y$. The values of  ''and'' for all possible inputs is shown in the following truth table:
 
::{| class="wikitable" style="text-align: center"
*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:
|-
<syntaxhighlight lang="python">
!<math>\ \ \ \ x\ \ \ \ </math>
s = 0
!<math>\ \ \ \ y\ \ \ \ </math>
x = 1
!<math>\ x y\ </math>
while (s < 100):
    if (x % 2 == 0) and (x % 3 != 0):
        s = s + x
    x = x + 1
</syntaxhighlight>
Both
<syntaxhighlight lang="python" inline>s < 100</syntaxhighlight>
and 
<syntaxhighlight lang="python" inline>(x % 2 == 0) and (x % 3 != 0)</syntaxhighlight>
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 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) will be denoted as <math>x \wedge y</math>, <math>x \text{AND} y</math>,  <math>x \& y</math>, <math>xy</math>, or <math>x \cdot y</math>
* OR (disjunction) will be denoted as <math>x \vee y</math>, <math>x \text{OR} y</math>,  or <math>x + y</math>  
* NOT (negation) will be in denated as <math>\neg x</math>, <math>\text{NOT} x</math>, or <math>\bar{x}</math>  
 
The values of AND, OR, and NOT for all possible inputs is show in the following truth table:
 
 
<dl>
<dd>
{{col-begin}}
{{col-break|width=9%}}
{| class="wikitable" style="text-align: center"
|-
|-
!<math>x</math>
!0
!<math>y</math>
!0
!<math>x  y</math>
| 0
!<math>x + y</math>
|-
|-
!0
!0
!1
| 0
|-
!1
!0
!0
| 0 || 0
| 0  
|-
|-
!1
!1
!1
| 1
|}
* The '''OR''' of two values is true whenever either or both values are true. It is written as $x+y$. The values of  ''or'' for all possible inputs is shown in the following truth table:
::{| class="wikitable" style="text-align: center"
|-
!<math>\ \ \ \ x\ \ \ \ </math>
!<math>\ \ \ \ y\ \ \ \ </math>
!<math>\ x + y\ </math>
|-
!0
!0
| 0 || 1
!0
| 0  
|-
|-
!0
!0
!1
!1
| 0 || 1
| 1
|-
!1
!0
| 1  
|-
|-
!1
!1
!1
!1
| 1 || 1
| 1  
|}
|}  
{{col-break}}
 
{| class="wikitable" style="text-align: center"
* 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. It is written as $\overline{x}$ or $\neg{x}$. The values of  ''not'' for all possible inputs is shown in the following truth table:
::{| class="wikitable" style="text-align: center"
|-
|-
!<math>x</math>
!<math>\ \ \ \ x\ \ \ \ </math>
!<math>\neg x</math>
!<math>\ \ \ \ \overline{x}\ \ \ \ </math>
|-
|-
!0
!0
|1
| 1  
|-
|-
!1
!1
|0
| 0  
|}
|}  
{{col-end}}
</dd>
</dl>


* The '''XOR''' of two values is true whenever the values are different. It uses the $\oplus$ operator, and can be built from the basic operators: $x \oplus y = x \overline{y} + \overline{x} y$ The values of ''xor'' for all possible inputs is shown in the following truth table:
 
::{| class="wikitable" style="text-align: center"
===Secondary operations===
|-
The three Boolean operations described above are referred to as basic, meaning that they can be taken as a basis for other Boolean operations that can be built up from them by '''composition,''' the manner in which operations are combined or compounded. Operations composed from the basic operations include the following examples:
!<math>\ \ \ \ x\ \ \ \ </math>
!<math>\ \ \ \ y\ \ \ \ </math>
:<math>x \oplus y = (x \vee y) \wedge \neg{(x \wedge y)}</math>
!<math>\ x \oplus y\ </math>
:<math>x \equiv y = \neg{(x \oplus y)}</math>
 
These definitions give rise to the following truth tables giving the values of these operations for all four possible inputs.
 
:{| class="wikitable" style="text-align: center"
|-
|-
!<math>x</math>
!0
!<math>y</math>
!0
!<math>x \oplus y</math>
| 0
!<math>x \equiv y</math>
|-
|-
!0
!0
!1
| 1
|-
!1
!0
!0
| 0 || 1
| 1  
|-
|-
!1
!1
!1
| 0
|}
*The '''XNOR''' of two values is true whenever the values are the same. It is the '''NOT''' of the '''XOR''' function. It uses the $\odot$ operator: $x \odot y = \overline{x \oplus y}$. The ''xnor'' can be built from basic operators: $x \odot y = x  y + \overline{x}  \overline{y}$ The values of  ''xnor'' for all possible inputs is shown in the following truth table:
::{| class="wikitable" style="text-align: center"
|-
!<math>\ \ \ \ x\ \ \ \ </math>
!<math>\ \ \ \ y\ \ \ \ </math>
!<math>\ x \odot y\ </math>
|-
!0
!0
| 1 || 0
!0
| 1  
|-
|-
!0
!0
!1
!1
|1 || 0
| 0
|-
|-
!1
!1
!0
| 0
|-
!1
!1
| 0 || 1
!1
|}
| 1
|}  
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:
 
<dl>
<dd>
<syntaxhighlight lang="python">
s = 0
x = 1
while (s < 100):
    if (x % 2 == 0) and (x % 3 != 0)
        then s = s + x
    x = x + 1
</syntaxhighlight>
Both the conditional statement
<syntaxhighlight lang="python" inline>s < 100</syntaxhighlight>
and the Boolean expression with 2 conditional statements 
<syntaxhighlight lang="python" inline>(x % 2 == 0) and (x % 3 != 0)</syntaxhighlight>
evaluate to ''true'' or ''false''.
</dd>
</dl>


*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 first operation, ''x''&nbsp;⊕&nbsp;''y'', or J''xy'', is called '''[[exclusive or]]''' (often abbreviated as XOR) to distinguish it from disjunction as the inclusive kind. It excludes the possibility of both ''x'' and ''y''.
* 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 ''jaguar speed -car'' is parsed by the search engine as the Boolean expression <syntaxhighlight lang="python" inline>"jaguar" and "car" and not "speed"</syntaxhighlight>; it returns pages about the speed of the jaguar animal, not the Jaguar car.


The second operation, the complement of exclusive or, is '''equivalence''' or Boolean equality: ''x''&nbsp;≡&nbsp;''y'', or E''xy'', is true just when ''x'' and ''y'' have the same value. Hence ''x''&nbsp;⊕&nbsp;''y'' as its complement can be understood as ''x''&nbsp;≠&nbsp;''y'', being true just when ''x'' and ''y'' are different. Equivalence's counterpart in arithmetic mod 2 is ''x'' + ''y'' + 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, the constants 0 and 1, and operations ''and'', ''or'', ''not'', ''xor'', and ''xnor''.  


Like ordinary algebra, parentheses are used to group terms. When a ''not'' is represented with an overhead horizontal line, there is an implicit grouping of the terms under the line. That is, $x \cdot \overline{y + z}$ is evaluated as if it were written $x \cdot \overline{(y + z)}.$


==Laws==
=== Order of Precedence ===
A '''law''' of Boolean algebra is an [[identity (mathematics)|identity]] such as ''x''∨(''y''∨''z'') = (''x''∨''y'')∨''z'' 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 ¬. The concept can be extended to terms involving other Boolean operations such as ⊕, →, and ≡, but such extensions are unnecessary for the purposes to which the laws are put. Such purposes include the definition of a [[Boolean algebra#Boolean algebras|Boolean algebra]] as any [[model (logic)|model]] of the Boolean laws, and as a means for deriving new laws from old as in the derivation of ''x''∨(''y''∧''z'') = ''x''∨(''z''∧''y'') from ''y''∧''z'' = ''z''∧''y'' as treated in the section on [[Boolean algebra#Axiomatizing Boolean algebra|axiomatization]].


===Monotone laws===
The order of operator precedence is ''not''; then ''and''; then ''xor'' and ''xnor''; and finally ''or''. Operators with the same level of precedence are evaluated from left-to-right.
Boolean algebra satisfies many of the same laws as ordinary algebra when one matches up ∨ with addition and with multiplication. In particular the following laws are common to both kinds of algebra:<ref name="O'Regan_p33">{{cite book|author=O'Regan, Gerard|title=A brief history of computing|publisher=Springer|year=2008|isbn=978-1-84800-083-4|page=33|url=https://books.google.com/books?id=081H96F1enMC&pg=PA33}}</ref>
=== Fundamental Identities ===


:{|
{| class="wikitable" style="text-align: center"
|-
| style="text-align: left" | Commutative Law – The order of application of two separate terms is not important. || $x+y = y+x$ || $x \cdot y = y \cdot x$
|-
| style="text-align: left" | Associative Law – Regrouping of the terms in an expression doesn't change the value of the expression. ||$(x + y) + z$ = $x + (y + z)$ || $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
|-
|-
| Associativity of <math>\vee</math>: ||style="width:2em"| ||style="text-align: right"| <math>x \vee (y \vee z)</math> || <math>= (x \vee y) \vee z</math>
| style="text-align: left" | Idempotent Law – A term that is ''or'''´ed or ''and''´ed with itself is equal to that term. || $ x +x = x $ || $x \cdot x = x$
|-
|-
| Associativity of <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge (y \wedge z)</math> || <math>= (x \wedge y) \wedge z</math>
| style="text-align: left" | Annihilator Law – A term that is ''or'''´ed with 1 is 1; a term ''and''´ed with 0 is 0. || $x + 1 = 1$ || $ x \cdot 0 = 0 $
|-
|-
| Commutativity of <math>\vee</math>: || ||style="text-align: right"| <math>x \vee y</math> || <math>= y \vee x</math>
| style="text-align: left" | Identity Law – A term ''or''´ed 0 or  ''and''´ed with a 1 will always equal that term. || $x + 0 = x|| $x \cdot 1 = x$
|-
|-
| Commutativity of <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge y</math> || <math>= y \wedge x</math>
| style="text-align: left" | Complement Law – A term ''or''´ed with its complement equals 1 and a term ''and''´ed with its complement equals 0. || $x + \overline{x} = 1 $ || $x \cdot \overline{x} = 0$
|-
|-
| Distributivity of <math>\wedge</math> over <math>\vee</math>: || ||style="text-align: right"| <math>x \wedge (y \vee z)</math> || <math>= (x \wedge y) \vee (x \wedge z)</math>
| style="text-align: left" | Absorptive Law – Complex expressions can be reduced to a simpler ones by absorbing like terms. ||colspan=2|
$x+x  y = x$
 
$ x +\overline{x}y = x + y $
 
$x  (x+y) = x$
 
|-
|-
| Identity for <math>\vee</math>: || ||style="text-align: right"| <math>x \vee 0</math> || <math>= x</math>
| style="text-align: left" | Distributive Law – It's OK to multiply or factor-out an expression.||colspan=2|
 
$x \cdot (y + z) = xy + xz$
 
$(x+y) \cdot (p + q) = xp + xq +yp + yq$
 
$(x+y)(x+z)=x + yz $
 
|-
|-
| Identity for <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge 1</math> || <math>= x</math>
| style="text-align: left" | DeMorgan's Law – An ''or'' (''and'') expression that is negated is equal to the ''and'' (''or'') of the negation of each term.|| $\overline{x+y} = \overline{x} \cdot \overline{y}$||$\overline{x \cdot y} = \overline{x} + \overline{y}$
|-
| style="text-align: left" | Double Negation – A term that is inverted twice is equal to the original term.||colspan=2| $\overline{\overline{x}} = x $
|-
| style="text-align: left" | Relationship between XOR and XNOR|| colspan=2 | $ x\odot y = \overline{x\oplus y} = x \oplus \overline{y} =\overline{x} \oplus {y}$
|}
 
== 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''."  Simplify means writing an equivalent expression using the fewest number of operators.
 
=== Problem 1: Simplify the Expression ===
 
'''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}}$
::{|  
 
|-
|-
| Annihilator for <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge 0</math> || <math>= 0</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</math>  ||
| (Absorption)
|
|}
|}


The following laws hold in Boolean Algebra, but not in ordinary algebra:
=== Problem 2: Find Solutions ===
:{|
 
|- Annihilator for <math>\vee</math>: || ||style="text-align: right"| <math>x \vee 1</math> || <math>= 1</math>
'''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.
:{| class="wikitable" style="text-align: center"
|-
|-
|Annihilator for <math>\vee</math>: || ||style="text-align: right"| <math>x \vee 1</math>
!style="background-color: #cceeff; font-size: x-small" |#1
|<math>= 1</math>
!style="background-color: #cceeff; font-size: x-small" |#2
!style="background-color: #cceeff; font-size: x-small" |#3
!style="background-color: #cceeff; font-size: x-small" |#4
!style="background-color: #cceeff; font-size: x-small" |#5
!style="background-color: #cceeff; font-size: x-small" |#6
!style="background-color: #cceeff; font-size: x-small" |#7
!style="background-color: #cceeff; font-size: x-small" |#8
 
|-
|-
| Idempotence of <math>\vee</math>: || ||style="text-align: right"| <math>x \vee x</math> || <math>= x</math>
|style="background-color: #cceeff"|
|style="background-color: #cceeff"|
!style="background-color: #cceeff; font-size: x-small" |OR of Col#1, Col#2
!style="background-color: #cceeff; font-size: x-small" |NOT of Col#3
!style="background-color: #cceeff; font-size: x-small" |NOT of Col#1
!style="background-color: #cceeff; font-size: x-small" |ADD of Col#1, Col#2
!style="background-color: #cceeff; font-size: x-small" |OR of Col#4, Col#6
!style="background-color: #cceeff; font-size: x-small" |NOT of Col#7
 
|-
|-
| Idempotence of <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge x</math> || <math>= x</math>
!<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>
 
|-
|-
| Absorption 1: || ||style="text-align: right"| <math>x \wedge (x \vee y)</math> || <math>= x</math>
!0
!0
|0
|1
|1
|0
|1
!0
 
|-
|-
| Absorption 2: || ||style="text-align: right"| <math>x \vee (x \wedge y)</math> || <math>= x</math>
!0
!1
 
|1
|0
|1
|1
|1
!0
 
|-
|-
|Distributivity of <math>\vee</math> over <math>\wedge</math>:
!1
|
!0
|<math>x \vee (y \wedge z)</math>
 
|<math>=(x \vee y) \wedge (x \vee z)</math>
|1
|0
|0
|0
|0
!1
 
|-
|-
| Distributivity of <math>\vee</math> over <math>\wedge</math>:  |  
!1
!1
 
|1
|0
|0
|0
|0
!1
|}
|}


Taking x = 2 in the third law above shows that it is not an ordinary algebra law, since 2×2 = 4. The remaining five laws can be falsified in ordinary algebra by taking all variables to be 1, for example in Absorption Law 1 the left hand side would be 1(1+1) = 2 while the right hand side would be 1, and so on.
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)$.


All of the laws treated so far have been for conjunction and disjunction. These operations have the property that changing either argument either leaves the output unchanged or the output changes in the same way as the input. Equivalently, changing any variable from 0 to 1 never results in the output changing from 1 to 0. Operations with this property are said to be '''monotone'''. Thus the axioms so far have all been for monotonic Boolean logic. Nonmonotonicity enters via complement ¬ as follows.<ref name="givhal"/>
== Online Resources ==


===Nonmonotone laws===
===Websites===
The complement operation is defined by the following two laws.
A great online tutorial on Boolean Algebra is part of [https://ryanstutorials.net/boolean-algebra-tutorial/ Ryan's Tutorials]. There are many online Boolean Calculators.  This one gives Truth Tables [https://sheabunge.github.io/boolcalc/ calculator ]. This link that has ads also simplifies and uses ! for NOT [https://www.boolean-algebra.com/ calculator].


:<math>
===Videos===
\begin{align}
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
&\text{Complementation 1} & x \wedge \neg x & = 0 \\
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.
&\text{Complementation 2} & x \vee \neg x  & = 1
 
\end{align}
{|
</math>
|-
| <youtube width="300" height="180">https://youtu.be/HJdhEjpVYsY</youtube>
| [https://youtu.be/HJdhEjpVYsY ''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.
 
|-
| <youtube width="300" height="180">https://youtu.be/4io6xgz8Zwk</youtube>
| [https://youtu.be/4io6xgz8Zwk ''ACSL Boolean Algebra Contest 2 Worksheet 2'' ('''misterminich''') ]


All properties of negation including the laws below follow from the above two laws alone.<ref name="givhal"/>
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.  


In both ordinary and Boolean algebra, negation works by exchanging pairs of elements, whence in both algebras it satisfies the double negation law (also called involution law)
|-
| <youtube width="300" height="180">https://youtu.be/6vI1mO1XOjQ</youtube>
| [https://youtu.be/6vI1mO1XOjQ ''ACSL 3 13-14 #1 - AM'' ('''Gordon Campbell''')]


This video walks through the solution to finding all ordered triples that make the following
Boolean expression ''true'':
:<math>
:<math>
\begin{align}
(AB+\overline{C})(\overline{A}+BC)(A+\overline{B}+C)
&\text{Double negation} & \neg{(\neg{x})} & = x
\end{align}
</math>
</math>
This problem appeared in 2013-2014 in the Senior Division, Contest #3.


But whereas ''ordinary algebra'' satisfies the two laws
|-
| <youtube width="300" height="180">https://youtu.be/KRKTbAZYlLM</youtube>
| [https://youtu.be/KRKTbAZYlLM ''ACSL 3 #1 14-15 - AM'' ('''Gordon Campbell''')]


This video walks through the simplification of the expression:
:<math>
:<math>
\begin{align}
\overline{(\overline{A}+B)}(B+C)\overline{(A+\overline{C})}(A\overline{B}+BC)
(-x)(-y) & = xy \\
(-x) + (-y) & = -(x + y)
\end{align}
</math>
</math>
This problem appeared in 2014-2015 in the Senior Division, Contest #3.


Boolean algebra satisfies [[De Morgan's laws]]:
|-
| <youtube width="300" height="180">https://youtu.be/jDnni-zm2g8</youtube>
| [https://youtu.be/jDnni-zm2g8 ''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:
:<math>
:<math>
\begin{align}
\overline{ (\overline{A + \overline{B}})(AB)} +
&\text{De Morgan 1} & \neg x \wedge \neg y & = \neg{(x \vee y)} \\
\overline{ (A+B)(\overline{\overline{A}B})}
&\text{De Morgan 2} & \neg x \vee \neg y & = \neg{(x \wedge y)}
\end{align}
</math>
</math>
|}

Latest revision as of 21:15, 7 December 2021

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.

Operators

The basic operators in Boolean algebra are AND, OR, and NOT. The secondary operators are eXclusive OR (often called XOR) and eXclusive NOR (XNOR, sometimes called equivalence). They are secondary in the sense that they can be composed from the basic operators.

  • The AND of two values is true only whenever both values are true. It is written as $xy$ or $x \cdot y$. The values of and for all possible inputs is shown in the following truth table:
[math]\ \ \ \ x\ \ \ \ [/math] [math]\ \ \ \ y\ \ \ \ [/math] [math]\ x y\ [/math]
0 0 0
0 1 0
1 0 0
1 1 1
  • The OR of two values is true whenever either or both values are true. It is written as $x+y$. The values of or for all possible inputs is shown in the following truth table:
[math]\ \ \ \ x\ \ \ \ [/math] [math]\ \ \ \ y\ \ \ \ [/math] [math]\ x + y\ [/math]
0 0 0
0 1 1
1 0 1
1 1 1
  • 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. It is written as $\overline{x}$ or $\neg{x}$. The values of not for all possible inputs is shown in the following truth table:
[math]\ \ \ \ x\ \ \ \ [/math] [math]\ \ \ \ \overline{x}\ \ \ \ [/math]
0 1
1 0
  • The XOR of two values is true whenever the values are different. It uses the $\oplus$ operator, and can be built from the basic operators: $x \oplus y = x \overline{y} + \overline{x} y$ The values of xor for all possible inputs is shown in the following truth table:
[math]\ \ \ \ x\ \ \ \ [/math] [math]\ \ \ \ y\ \ \ \ [/math] [math]\ x \oplus y\ [/math]
0 0 0
0 1 1
1 0 1
1 1 0
  • The XNOR of two values is true whenever the values are the same. It is the NOT of the XOR function. It uses the $\odot$ operator: $x \odot y = \overline{x \oplus y}$. The xnor can be built from basic operators: $x \odot y = x y + \overline{x} \overline{y}$ The values of xnor for all possible inputs is shown in the following truth table:
[math]\ \ \ \ x\ \ \ \ [/math] [math]\ \ \ \ y\ \ \ \ [/math] [math]\ x \odot y\ [/math]
0 0 1
0 1 0
1 0 0
1 1 1

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)
        then s = s + x
    x = x + 1

Both the conditional statement s < 100 and the Boolean expression with 2 conditional statements (x % 2 == 0) and (x % 3 != 0) evaluate to true or false.

  • 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 jaguar speed -car is parsed by the search engine as the Boolean expression "jaguar" and "car" and not "speed"; it returns pages about the speed of the jaguar animal, not the Jaguar car.

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, the constants 0 and 1, and operations and, or, not, xor, and xnor.

Like ordinary algebra, parentheses are used to group terms. When a not is represented with an overhead horizontal line, there is an implicit grouping of the terms under the line. That is, $x \cdot \overline{y + z}$ is evaluated as if it were written $x \cdot \overline{(y + z)}.$

Order of Precedence

The order of operator precedence is not; then and; then xor and xnor; and finally or. Operators with the same level of precedence are evaluated from left-to-right.

Fundamental Identities

Commutative Law – The order of application of two separate terms is not important. $x+y = y+x$ $x \cdot y = y \cdot x$
Associative Law – Regrouping of the terms in an expression doesn't change the value of the expression. $(x + y) + z$ = $x + (y + z)$ $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
Idempotent Law – A term that is or'´ed or and´ed with itself is equal to that term. $ x +x = x $ $x \cdot x = x$
Annihilator Law – A term that is or'´ed with 1 is 1; a term and´ed with 0 is 0. $x + 1 = 1$ $ x \cdot 0 = 0 $
Identity Law – A term or´ed 0 or and´ed with a 1 will always equal that term. $x + 0 = x$ $x \cdot 1 = x$
Complement Law – A term or´ed with its complement equals 1 and a term and´ed with its complement equals 0. $x + \overline{x} = 1 $ $x \cdot \overline{x} = 0$
Absorptive Law – Complex expressions can be reduced to a simpler ones by absorbing like terms.

$x+x y = x$

$ x +\overline{x}y = x + y $

$x (x+y) = x$

Distributive Law – It's OK to multiply or factor-out an expression.

$x \cdot (y + z) = xy + xz$

$(x+y) \cdot (p + q) = xp + xq +yp + yq$

$(x+y)(x+z)=x + yz $

DeMorgan's Law – An or (and) expression that is negated is equal to the and (or) of the negation of each term. $\overline{x+y} = \overline{x} \cdot \overline{y}$ $\overline{x \cdot y} = \overline{x} + \overline{y}$
Double Negation – A term that is inverted twice is equal to the original term. $\overline{\overline{x}} = x $
Relationship between XOR and XNOR $ x\odot y = \overline{x\oplus y} = x \oplus \overline{y} =\overline{x} \oplus {y}$

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." Simplify means writing an equivalent expression using the fewest number of operators.

Problem 1: Simplify the Expression

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]= \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[/math] (Absorption)

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

Websites

A great online tutorial on Boolean Algebra is part of Ryan's Tutorials. There are many online Boolean Calculators. This one gives Truth Tables calculator . This link that has ads also simplifies and uses ! for NOT calculator.

Videos

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 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 13-14 #1 - AM (Gordon Campbell)

This video walks through the solution to finding all ordered triples that make the following Boolean expression true:

[math] (AB+\overline{C})(\overline{A}+BC)(A+\overline{B}+C) [/math]

This problem appeared in 2013-2014 in the Senior Division, Contest #3.

ACSL 3 #1 14-15 - AM (Gordon Campbell)

This video walks through the simplification of the expression:

[math] \overline{(\overline{A}+B)}(B+C)\overline{(A+\overline{C})}(A\overline{B}+BC) [/math]

This problem appeared in 2014-2015 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:

[math] \overline{ (\overline{A + \overline{B}})(AB)} + \overline{ (A+B)(\overline{\overline{A}B})} [/math]