Difference between revisions of "Boolean Algebra"

From Coder Merlin
(41 intermediate revisions by 4 users not shown)
Line 1: Line 1:
== Curriculum ==
{{MerlinCurriculumData|{{ROOTPAGENAME}}}}
== Background ==
== Background ==
The branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively.  It is a formal description of logical relations.  It was introduced by George Boole in his first book The Mathematical Analysis of Logic in 1847.
The branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively.  It is a formal description of logical relations.  It was introduced by George Boole in his first book The Mathematical Analysis of Logic in 1847.
Line 15: Line 17:


== Basic Operations ==
== Basic Operations ==
* ''AND'', formally termed '''conjunction''' and denoted by <math>A \and B</math>
There are three basic operations, all of which have two inputs and one output.
* ''OR'', formally termed '''disjunction''' and denoted by <math>A \or B</math>
 
* ''NOT'', formally termed '''negation''', and denoted by <math>\neg A</math>
* ''AND'', formally termed '''conjunction''' and denoted by <math>A \and B</math>.  The output is true '''iff''' (iff means ''if and only if'') ''both'' inputs are true.
* ''OR'', formally termed '''disjunction''' and denoted by <math>A \or B</math>.  The output is true if either of the inputs are true.  This is sometimes also referred to as '''inclusive disjunction'''.  This is because the output is true if either of the inputs are true, including the case where ''both'' inputs are true.
* ''NOT'', formally termed '''negation''', and denoted by <math>\neg A</math>.  The output is simply the opposite of the input.


There are also several "shortcut" notations that we can use for more succinct expressions:
There are also several "shortcut" notations that we can use for more succinct expressions:
Line 23: Line 27:
* ''disjunction'' may be written as addition, i.e. <math>A + B</math>
* ''disjunction'' may be written as addition, i.e. <math>A + B</math>
* ''negation'' may be written with a bar above the variable, i.e. <math>\bar{A}</math>
* ''negation'' may be written with a bar above the variable, i.e. <math>\bar{A}</math>
All Boolean operations can be expressed through a composition of these basic operations.
== Secondary Operations ==
* ''NAND'' is denoted by <math>A \overline{\land} B</math> and is equivalent to the negation of the result of <math>A \land B</math>, i.e. <math>\overline{A \land B}</math>.  The output is true in all cases except when both A and B are true.
* ''NOR'' is denoted by <math>A \overline{\lor} B</math> and is equivalent to the negation of the result of <math>A \lor B</math>, i.e. <math>\overline{A \lor B}</math>.  The output is true only if both A and B are false.
* ''EQUAL'', formally termed '''equivalence''' and denoted by <math>A \equiv B</math>.  The output is true iff both inputs have the same value.
* ''XOR'', formally termed '''exclusive disjunction''' and denoted by <math>A \oplus B</math>, <math>A \dot{\lor} B</math>, <math>A \underline{\lor} B</math>, <math>A \not\equiv B</math>.  The output is true if either of the inputs are true ''but both are not true''. Compare this to inclusive disjunction.
* ''IMPLY'', formally termed '''material implication''' and denoted by <math>A \rightarrow B</math>.  This is sometimes read as "if A then B" or "A implies B".  The output is true in all cases except the case where A is true and B is false.
* ''CONVERSE IMPLY'', formally termed '''converse implication''' and denoted by <math>A \leftarrow B</math>.  This is sometimes read as "if B then A" or "B implies A".  The output is true in all cases except the case where B is true and A is false.
* ''BIDIRECTIONAL IMPLY'', formally termed '''material biconditional''' and denoted by <math>A \leftrightarrow B</math>.  This is sometimes read as "A if and only if B" and abbreviated as "A iff B".  It is logically equivalent to <math>A \rightarrow B \land B \rightarrow A</math>.  The output is true if both A and B are true or if both A and B are false.
{{Observe|Section 1|
# Why is one of the symbols used for ''exclusive disjunction'' <math>\not\equiv</math>?
}}
== Order of Operations ==
Expressions with multiple operators are evaluated from left to right, respecting the operator precedence as follows:
# <math>\neg</math> (NOT) has the highest priority, followed by
# <math>\land</math> (AND), <math>\overline{\land}</math> (NAND)
# <math>\lor</math> (OR), <math>\overline{\lor}</math> (NOR)
# <math>\rightarrow</math> (IMPLY), <math>\leftarrow</math> (CONVERSE IMPLY)
# <math>\oplus</math>, <math>\dot{\or}</math>, <math>\underline{\lor}</math>, <math>\not\equiv</math> (XOR), <math>\equiv</math>, <math>\leftrightarrow</math> (EQUIV)
As always, parentheses may be used to both emphasize and override the order of operations.
For clarification, here are several examples of equivalent expressions:
{| class="wikitable"
! Without Parentheses
! With Parentheses
|-
| <math>A \or B \and C</math> || <math>A \or (B \and C)</math>
|-
| <math>A \and B \and C \or D</math> || <math>((A \and B) \and C) \or D</math>
|-
| <math>A \and B \or C \and D</math> || <math>(A \and B) \or (C \and D)</math>
|-
| <math>\neg A \and B \or C</math> || <math>((\neg A) \and B) \or C</math>
|}
{{Caution|
It is important to note that the precedence list above, while generally agreed upon, is not implemented by all computer programming languages.  It's important to pay close attention to the rules of each language, or, better yet, use parentheses to avoid ambiguity.
}}


== Truth Tables ==
== Truth Tables ==
'''Truth tables''' provide us with a straightforward means to specify the required output(s) for the specified input(s), in table form.  On the left-hand side of the table we enumerate the input(s) and on the right-hand side of the table we specify the output(s).  Assuming that we have <math>n</math> inputs we may label each input as <math>I_1, I_2, I_3, ... I_n</math>.  The value of the inputs on any given row, may be referred to as an '''input tuple'''.  Likewise, assuming that we have <math>m</math> outputs we may label each output as <math>O_1, O_2, O_3, ... O_n</math>, and the value of these outputs on any given row may be referred to as an '''output tuple'''.  The number of rows in any such table is given by the formula <math>2^n</math>.  When there is a single output, we can formalize the relationship as <math>O_1 = f(I_1, I_2, I_3, ...)</math>
'''Truth tables''' provide us with a straightforward means to specify the required output(s) for the specified input(s), in table form.  On the left-hand side of the table we enumerate the input(s) and on the right-hand side of the table we specify the output(s).  Assuming that we have <math>n</math> inputs we may label each input as <math>I_1, I_2, I_3, ... I_n</math>.  The value of the inputs on any given row, may be referred to as an '''input tuple'''.  Likewise, assuming that we have <math>m</math> outputs we may label each output as <math>O_1, O_2, O_3, ... O_m</math>, and the value of these outputs on any given row may be referred to as an '''output tuple'''.  The number of rows in any such table is given by the formula <math>2^n</math>.  When there is a single output, we can formalize the relationship as <math>O_1 = f(I_1, I_2, I_3, ...)</math>


{{Question|
{{Observe|Section 2|
Why is the formula for determining the number of rows in a truth table related only to the number of inputs, and why is the formula <math>2^n</math>?
# Why is the formula for determining the number of rows in a truth table related only to the number of inputs, and why is the formula <math>2^n</math>?
}}
}}


Line 59: Line 106:
   {{Bar}}}
   {{Bar}}}


Rather than memorizing the entire table, we can just memorize the output column, i.e. 0 0 0 1.  And, in most cases, we really only need to memorize the exceptional cases.  
Rather than memorizing the entire table, we can just memorize the output column, i.e. 0 0 0 1.  And, in most cases, we really only need to memorize the exceptional cases. We call this the '''standard order''', i.e. ascending order of the binary inputs.


}}
}}
Line 91: Line 138:
!
!
|-
|-
| Contradiction  || 0                     ||  || 0 || 0 || 0 || 0 || Always false
| Contradiction  ||                     ||  || 0 || 0 || 0 || 0 || Always false
|-  
|-  
| AND        || <math>x \cdot y</math> ||  || 0 || 0 || 0 || '''1''' || x and y are true
| AND        || <math>x \cdot y</math> ||  || 0 || 0 || 0 || '''1''' || x and y are true
Line 121: Line 168:
| NAND || <math>\overline{x \cdot y}</math> || || '''1''' || '''1''' || '''1''' || 0 || x and y are not both true
| NAND || <math>\overline{x \cdot y}</math> || || '''1''' || '''1''' || '''1''' || 0 || x and y are not both true
|-  
|-  
| Tautology  || 1                     ||  || '''1''' || '''1''' || '''1''' || '''1''' || Always true
| Tautology  ||                     ||  || '''1''' || '''1''' || '''1''' || '''1''' || Always true
|}
|}


== Logic Gates ==
== Canonical Representation ==
An idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces one or more binary outputsThe table below provides the symbols that are used to represent common gates.  
As discussed above, regardless of the function being implemented, each input and output combination can be represented by a single row in a truth table.  Therefore, if we correctly represent each row, and then join those representations together, we'll be able to accurately recreate the function.  There's a very straightforward means of doing so:
* For each output, we consider only those rows where the output value is trueWe then form an expression representing all of the inputs for that same row, either the value of the input itself (if true) or its negation (if false), so that the result is true.
* We join each of the above expressions using disjunction.


Let's consider some examples:
{| class="wikitable"
{| class="wikitable"
! Formal Name
|+ CONJUNCTION
! Abbreviated Name
! row
! Symbol
! <math>x</math>
! Gate
! <math>y</math>
! Truth Table
! <math>x \land y</math>
|-
|-
| Buffer
| 1.
|
| 0
|
| 0
| [[File:Gate Buffer.png]]
| 0
|  
  {| class="wikitable" style="text-align: center; margin: auto;"
  ! Inputs
  ! Outputs
  |-
  ! <math>A</math>
  ! <math>Q = A</math>
  |-
  | 0 || 0
  |-
  | 1 || 1
  |}
|-
|-
| Conjunction
| 2.
| AND
| 0
| <math>A \and B</math>
| 1
| [[File:Gate AND.png]]
| 0
|
  {| class="wikitable" style="text-align: center;"
  !colspan="2"| Inputs
  ! Outputs
  |-
  ! <math>A</math>
  ! <math>B</math>
  ! <math>Q = A \and B</math>
  |-
  | 0 || 0 || 0
  |-
  | 0 || 1 || 0
  |-
  | 1 || 0 || 0
  |-
  | 1 || 1 || 1
  |}
|-
|-
| Disjunction
| 3.
| OR
| 1
| <math>A \or B</math>
| 0
| [[File:Gate OR.png]]
| 0
|  
  {| class="wikitable" style="text-align: center;"
  !colspan="2"| Inputs
  ! Outputs
  |-
  ! <math>A</math>
  ! <math>B</math>
  ! <math>Q = A \or B</math>
  |-
  | 0 || 0 || 0
  |-
  | 0 || 1 || 1
  |-
  | 1 || 0 || 1
  |-
  | 1 || 1 || 1
  |}
|-
|-
| Exclusive OR
| 4.
| XOR
| 1
| <math>A \oplus B</math>
| 1
| [[File:Gate XOR.png]]
| 1
|
  {| class="wikitable" style="text-align: center;"
  !colspan="2"| Inputs
  ! Outputs
  |-
  ! <math>A</math>
  ! <math>B</math>
  ! <math>Q = A \oplus B</math>
  |-
  | 0 || 0 || 0
  |-
  | 0 || 1 || 1
  |-
  | 1 || 0 || 1
  |-
  | 1 || 1 || 0
  |}
|-
|-
| Inverter
|}
| NOT
 
| <math>\neg A</math>
The first step is to scan through each row and note each case where the output is true.  In the case of conjunction, there is only one such row, row #4:
| [[File:Gate Inverter.png]]
{| class="wikitable" align="center"
|
|+ CONJUNCTION
  {| class="wikitable" style="text-align: center; margin: auto;"
! row
  ! Inputs
! <math>x</math>
  ! Outputs
! <math>y</math>
  |-
! <math>x \land y</math>
  ! <math>A</math>
  ! <math>Q = \overline{A}</math>
  |-
  | 0 || 1
  |-
  | 1 || 0
  |}
|-
|-
| Negated Conjunction
| #1
| NAND
| 0
| <math>\overline{A \and B}</math>
| 0
| [[File:Gate NAND.png]]
| <span style="color: gray;">0</span>
|
  {| class="wikitable" style="text-align: center;"
  !colspan="2"| Inputs
  ! Outputs
  |-
  ! <math>A</math>
  ! <math>B</math>
  ! <math>Q = \overline{A \and B}</math>
  |-
  | 0 || 0 || 1
  |-
  | 0 || 1 || 1
  |-
  | 1 || 0 || 1
  |-
  | 1 || 1 || 0
  |}
|-
|-
| Negated Disjunction
| #2
| NOR
| 0
| <math>\overline{A \or B}</math>
| 1
| [[File:Gate NOR.png]]
| <span style="color: gray;">0</span>
|
|-
  {| class="wikitable" style="text-align: center;"
| #3
  !colspan="2"| Inputs
| 1
  ! Outputs
| 0
  |-
| <span style="color: gray;">0</span>
  ! <math>A</math>
|-
  ! <math>B</math>
| #4
  ! <math>Q = \overline{A \or B}</math>
| '''1'''
  |-
| '''1'''
  | 0 || 0 || 1
| <span style="background: yellow;">1</span>
  |-
  | 0 || 1 || 0
  |-
  | 1 || 0 || 0
  |-
  | 1 || 1 || 0
  |}
|-
|-
| Negated Exclusive OR
| NOT XOR
| <math>\overline{A \oplus B}</math>
| [[File:Gate NOT XOR.png]]
|
  {| class="wikitable" style="text-align: center;"
  !colspan="2"| Inputs
  ! Outputs
  |-
  ! <math>A</math>
  ! <math>B</math>
  ! <math>Q = \overline{A \oplus B}</math>
  |-
  | 0 || 0 || 1
  |-
  | 0 || 1 || 0
  |-
  | 1 || 0 || 0
  |-
  | 1 || 1 || 1
  |}
|}
|}
The expression representing the inputs for this row is simply <math>xy</math>, that is, the conjunction of <math>x</math> and <math>y</math>.  Because there are no other rows for which the output is true, we're done.  Thus, the canonical representation of <math>x \land y</math> is simply <math>xy</math>.  Let's consider a slightly more challenging example:
{| class="wikitable" align="center"
|+ EXCLUSIVE DISJUNCTION
! row
! <math>x</math>
! <math>y</math>
! <math>x \oplus y</math>
|-
| #1
| 0
| 0
| <span style="color: gray;">0</span>
|-
| #2
| '''0'''
| '''1'''
| <span style="background: yellow;">1</span>
|-
| #3
| '''1'''
| '''0'''
| <span style="background: yellow;">1</span>
|-
| #4
| 1
| 1
| <span style="color: gray;">0</span>
|-
|}
Again, the first step is to scan through each row and note each case where the output is true. In the case of exclusive disjunction, there are two such rows: row #2 and row #3.  The expression representing the inputs for these rows are <math>\bar{x}y</math> for row #2 and <math>x\bar{y}</math> for row #3.  To complete the canonical representation, we combine the expression for each row with disjunction.  Thus, the canonical representation of <math>x \oplus y</math> is <math>\bar{x}y + x\bar{y}</math>.
Let's consider one final example, function ''f'':
{| class="wikitable" align="center"
|+ FUNCTION ''f''
! row
! <math>x</math>
! <math>y</math>
! <math>z</math>
! <math>f(x,y,z)</math>
|-
| #1
| 0
| 0
| 0
| <span style="color: gray;">0</span>
|-
| #2
| '''0'''
| '''0'''
| '''1'''
| <span style="background: yellow;">1</span>
|-
| #3
| 0
| 1
| 0
| <span style="color: gray;">0</span>
|-
| #4
| 0
| 1
| 1
| <span style="color: gray;">0</span>
|-
| #5
| 1
| 0
| 0
| <span style="color: gray;">0</span>
|-
| #6
| '''1'''
| '''0'''
| '''1'''
| <span style="background: yellow;">1</span>
|-
| #7
| '''1'''
| '''1'''
| '''0'''
| <span style="background: yellow;">1</span>
|-
| #8
| 1
| 1
| 1
| <span style="color: gray;">0</span>
|-
|}
We note those rows in which the output is true:  row #2, row #6, and row #7.  The expressions representing the inputs for these rows are:<br/>
row #2: <math>\bar{x}\bar{y}z</math><br/>
row #6: <math>x\bar{y}z</math><br/>
row #7: <math>xy\bar{z}</math>
Combining these expressions with disjunction yields our canonical representation: <math>\bar{x}\bar{y}z + x\bar{y}z + xy\bar{z}</math>.


== De Morgan's Laws ==
== De Morgan's Laws ==
De Morgan's Laws provide a helpful formula to obtain the same truth table of:
De Morgan's Laws provide a helpful formula to obtain the same truth table of:
* an AND gate by using negation and an OR gate, or
* an AND operation by using negation and an OR operation, or
* an OR gate by using negation and  an AND gate
* an OR operation by using negation and  an AND operation


The Laws are:
The Laws are:
* <math>A \and B \Leftrightarrow \neg (\neg X \or \neg Y)</math>
* <math>X \and Y \Leftrightarrow \neg (\neg X \or \neg Y)</math>
* <math>A \or B \Leftrightarrow \neg (\neg X \and \neg Y)</math>
* <math>X \or Y \Leftrightarrow \neg (\neg X \and \neg Y)</math>
 
== Exercises ==
{{W1013-Exercises}}


== References ==
== References ==
Line 316: Line 354:
* [https://en.wikipedia.org/wiki/Truth_table Truth Table] (Wikipedia)
* [https://en.wikipedia.org/wiki/Truth_table Truth Table] (Wikipedia)
* Schocken, Simon and Nisan, Noam. ''The Elements of Computing Systems''.  MIT Press, 2005.
* Schocken, Simon and Nisan, Noam. ''The Elements of Computing Systems''.  MIT Press, 2005.
{{Experience
|experienceID=W1013
|experienceUnit=Boolean algebra
|knowledgeAndSkills=§10.321;§10.322;§10.323;§10.324
|topicAreas=Boolean algebra
|classroomTime=60 minutes
|studyTime=4 hours
|acquiredKnowledge=understand the principles of Boolean algebra; understand the use of operators in Boolean algebra; understand the order of operations in Boolean algebra; understand how to use truth tables; understand how to represent a Boolean expression canonically; understand the use of DeMorgan's laws
|acquiredSkill=demonstrate proficiency in using Boolean algebra;demonstrate proficiency in constructing and using truth tables;demonstrate the use of canonical representation for arbitrary Boolean expressions;demonstrate the appropriate application of DeMorgan's laws
}}

Revision as of 02:18, 22 June 2021

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

Curriculum[edit]

ExercisesIcon.png
 Coder Merlin™  Computer Science Curriculum Data

Unit: Boolean algebra

Experience Name: Boolean Algebra (W1013)

Next Experience: ()

Knowledge and skills:

  • §10.321 Demonstrate understanding and proficiency in the use of Boolean algebra
  • §10.322 Demonstrate understanding and proficiency in the use of Boolean algebra truth tables
  • §10.323 Demonstrate understanding and proficiency in the use of Boolean algebra canonical representation
  • §10.324 Demonstrate understanding and proficiency in the use of DeMorgan's Laws

Topic areas: Boolean algebra

Classroom time (average): 60 minutes

Study time (average): 240 minutes

Successful completion requires knowledge: understand the principles of Boolean algebra; understand how to use truth tables; understand how to represent a Boolean expression canonically; understand the use of operators in Boolean algebra; understand the order of operations in Boolean algebra; understand using DeMorgan's laws

Successful completion requires skills: demonstrate proficiency in using Boolean algebra; demonstrate proficiency in constructing and using truth tables; demonstrate the appropriate application of DeMorgan's laws; demonstrate how to use canonical representation for arbitrary Boolean expressions

Background[edit]

The branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. It is a formal description of logical relations. It was introduced by George Boole in his first book The Mathematical Analysis of Logic in 1847.

Alternative names for true and false:

false true
no yes
0 1
F T

Basic Operations[edit]

There are three basic operations, all of which have two inputs and one output.

  • AND, formally termed conjunction and denoted by . The output is true iff (iff means if and only if) both inputs are true.
  • OR, formally termed disjunction and denoted by . The output is true if either of the inputs are true. This is sometimes also referred to as inclusive disjunction. This is because the output is true if either of the inputs are true, including the case where both inputs are true.
  • NOT, formally termed negation, and denoted by . The output is simply the opposite of the input.

There are also several "shortcut" notations that we can use for more succinct expressions:

  • conjunction may be written as multiplication, i.e. or, more simply,
  • disjunction may be written as addition, i.e.
  • negation may be written with a bar above the variable, i.e.

All Boolean operations can be expressed through a composition of these basic operations.

Secondary Operations[edit]

  • NAND is denoted by and is equivalent to the negation of the result of , i.e. . The output is true in all cases except when both A and B are true.
  • NOR is denoted by and is equivalent to the negation of the result of , i.e. . The output is true only if both A and B are false.
  • EQUAL, formally termed equivalence and denoted by . The output is true iff both inputs have the same value.
  • XOR, formally termed exclusive disjunction and denoted by , , , . The output is true if either of the inputs are true but both are not true. Compare this to inclusive disjunction.
  • IMPLY, formally termed material implication and denoted by . This is sometimes read as "if A then B" or "A implies B". The output is true in all cases except the case where A is true and B is false.
  • CONVERSE IMPLY, formally termed converse implication and denoted by . This is sometimes read as "if B then A" or "B implies A". The output is true in all cases except the case where B is true and A is false.
  • BIDIRECTIONAL IMPLY, formally termed material biconditional and denoted by . This is sometimes read as "A if and only if B" and abbreviated as "A iff B". It is logically equivalent to . The output is true if both A and B are true or if both A and B are false.


ObserveObserveIcon.png
Observe, Ponder, and Journal: Section 1
  1. Why is one of the symbols used for exclusive disjunction ?

Order of Operations[edit]

Expressions with multiple operators are evaluated from left to right, respecting the operator precedence as follows:

  1. (NOT) has the highest priority, followed by
  2. (AND), (NAND)
  3. (OR), (NOR)
  4. (IMPLY), (CONVERSE IMPLY)
  5. , , , (XOR), , (EQUIV)

As always, parentheses may be used to both emphasize and override the order of operations.

For clarification, here are several examples of equivalent expressions:

Without Parentheses With Parentheses
CautionWarnIcon.png

It is important to note that the precedence list above, while generally agreed upon, is not implemented by all computer programming languages. It's important to pay close attention to the rules of each language, or, better yet, use parentheses to avoid ambiguity.

Truth Tables[edit]

Truth tables provide us with a straightforward means to specify the required output(s) for the specified input(s), in table form. On the left-hand side of the table we enumerate the input(s) and on the right-hand side of the table we specify the output(s). Assuming that we have inputs we may label each input as . The value of the inputs on any given row, may be referred to as an input tuple. Likewise, assuming that we have outputs we may label each output as , and the value of these outputs on any given row may be referred to as an output tuple. The number of rows in any such table is given by the formula . When there is a single output, we can formalize the relationship as

ObserveObserveIcon.png
Observe, Ponder, and Journal: Section 2
  1. Why is the formula for determining the number of rows in a truth table related only to the number of inputs, and why is the formula ?

Note that for convenience we sometimes label inputs as A, B, C, etc. rather than etc. and do the same for outputs, often beginning with the letter Q.

Hint.pngHelpful Hint

When writing truth tables, it is very helpful to always write them in the same order. This helps in reading and memorizing the tables because we can simply memorize the output column(s), because the input columns will always be the same. For example, consider the AND truth table:

x y
0 0 0
0 1 0
1 0 0
1 1 1

Rather than memorizing the entire table, we can just memorize the output column, i.e. 0 0 0 1. And, in most cases, we really only need to memorize the exceptional cases. We call this the standard order, i.e. ascending order of the binary inputs.


There are possible single-output Boolean functions that can be defined over inputs. These are enumerated, with explanations, in the following table.

Function Name Boolean Algebraic Formula Truth Table Explanation
x 0 0 1 1
y 0 1 0 1
Contradiction 0 0 0 0 Always false
AND 0 0 0 1 x and y are true
AND NOT 0 0 1 0 x is true and y is false
0 0 1 1 x is true, y is irrelevant
NOT AND 0 1 0 0 x is false and y is true
0 1 0 1 y is true, x is irrelevant
XOR 0 1 1 0 x is true or y is true but both are not true
x is different than y
OR 0 1 1 1 Either x or y is true
NOR 1 0 0 0 Neither x nor y is true
EQUIVALENCE 1 0 0 1 x is the same as y
NOT 1 0 1 0 y is false, x is irrelevant
IMPLYs 1 0 1 1 x is true or y is false
NOT 1 1 0 0 x is false, y is irrelevant
IMPLYs 1 1 0 1 y is true or x is false
NAND 1 1 1 0 x and y are not both true
Tautology 1 1 1 1 Always true

Canonical Representation[edit]

As discussed above, regardless of the function being implemented, each input and output combination can be represented by a single row in a truth table. Therefore, if we correctly represent each row, and then join those representations together, we'll be able to accurately recreate the function. There's a very straightforward means of doing so:

  • For each output, we consider only those rows where the output value is true. We then form an expression representing all of the inputs for that same row, either the value of the input itself (if true) or its negation (if false), so that the result is true.
  • We join each of the above expressions using disjunction.

Let's consider some examples:

CONJUNCTION
row
1. 0 0 0
2. 0 1 0
3. 1 0 0
4. 1 1 1

The first step is to scan through each row and note each case where the output is true. In the case of conjunction, there is only one such row, row #4:

CONJUNCTION
row
#1 0 0 0
#2 0 1 0
#3 1 0 0
#4 1 1 1

The expression representing the inputs for this row is simply , that is, the conjunction of and . Because there are no other rows for which the output is true, we're done. Thus, the canonical representation of is simply . Let's consider a slightly more challenging example:

EXCLUSIVE DISJUNCTION
row
#1 0 0 0
#2 0 1 1
#3 1 0 1
#4 1 1 0

Again, the first step is to scan through each row and note each case where the output is true. In the case of exclusive disjunction, there are two such rows: row #2 and row #3. The expression representing the inputs for these rows are for row #2 and for row #3. To complete the canonical representation, we combine the expression for each row with disjunction. Thus, the canonical representation of is .

Let's consider one final example, function f:

FUNCTION f
row
#1 0 0 0 0
#2 0 0 1 1
#3 0 1 0 0
#4 0 1 1 0
#5 1 0 0 0
#6 1 0 1 1
#7 1 1 0 1
#8 1 1 1 0

We note those rows in which the output is true: row #2, row #6, and row #7. The expressions representing the inputs for these rows are:
row #2:
row #6:
row #7:

Combining these expressions with disjunction yields our canonical representation: .

De Morgan's Laws[edit]

De Morgan's Laws provide a helpful formula to obtain the same truth table of:

  • an AND operation by using negation and an OR operation, or
  • an OR operation by using negation and an AND operation

The Laws are:

Exercises[edit]

Template:W1013-Exercises

References[edit]


Experience Metadata

Experience ID W1013
Next experience ID
Unit Boolean algebra
Knowledge and skills §10.321
§10.322
§10.323
§10.324
Topic areas Boolean algebra
Classroom time 60 minutes
Study time 4 hours240 minutes <br />
Acquired knowledge understand the principles of Boolean algebra
understand the use of operators in Boolean algebra
understand the order of operations in Boolean algebra
understand how to use truth tables
understand how to represent a Boolean expression canonically
understand the use of DeMorgan's laws
Acquired skill demonstrate proficiency in using Boolean algebra
demonstrate proficiency in constructing and using truth tables
demonstrate the use of canonical representation for arbitrary Boolean expressions
demonstrate the appropriate application of DeMorgan's laws
Additional categories