Section 2.4  Basic Theorems and Properties of Boolean Algebra    43
presentation is necessary for developing the theorems and properties of the algebraic 
system. The two‐valued Boolean algebra defined in this section is also called “switching 
algebra” by engineers. To emphasize the similarities between two‐valued Boolean alge-
bra and other binary systems, that algebra was called “binary logic” in Section 1.9. From 
here on, we shall drop the adjective “two‐valued” from Boolean algebra in subsequent 
discussions.   
2.4     BASIC THEOREMS AND PROPERTIES 
OF BOOLEAN ALGEBRA 
Duality 
In Section 2.3, the Huntington postulates were listed in pairs and designated by part 
(a)and part (b). One part may be obtained from the other if the binary operators and 
the identity elements are interchanged. This important property of Boolean algebra is 
called the duality principle and states that every algebraic expression deducible from 
the postulates of Boolean algebra remains valid if the operators and identity elements 
are interchanged. In a two‐valued Boolean algebra, the identity elements and the ele-
ments of the set B are the same: 1 and 0. The duality principle has many applications. If 
the dual of an algebraic expression is desired, we simply interchange OR and AND 
operators and replace 1’s by 0’s and 0’s by 1’s.  
Basic Theorems 
Table   2.1    lists six theorems of Boolean algebra and four of its postulates. The notation 
is simplified by omitting the binary operator whenever doing so does not lead to 
confusion. The theorems and postulates listed are the most basic relationships in Boolean 
Table 2.1 
Postulates and Theorems of Boolean Algebra 
Postulate 2 
(a) 
+ 0=x    
(b) 
x
#
1 =x    
Postulate 5 
(a) 
x′ =1    
(b) 
x
#
x′ =0    
Theorem 1 
(a) 
+=x    
(b) 
x
#
=x    
Theorem 2 
(a) 
+ 1=1    
(b) 
x
#
0= 0    
Theorem 3, involution 
(x′)′=x    
Postulate 3, commutative  (a) 
y=x    
(b) 
xy =yx    
Theorem 4, associative 
(a)     + (+z) =(+y) +z    
(b) 
x(yz) =(xy)z    
Postulate 4, distributive 
(a) 
x(yz) =xy +xz    
(b) 
yz =(+y)(z)    
Theorem 5, DeMorgan 
(a) 
(+y)′=xy′    
(b) 
(xy)′=x′ +y    
Theorem 6, absorption 
(a) 
+xy=x    
(b)     x(y) =x    
Pdf conversion to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
how to change pdf to powerpoint; how to convert pdf to powerpoint slides
Pdf conversion to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf file to powerpoint online; how to convert pdf to powerpoint on
44    Chapter 2  Boolean Algebra and Logic Gates
algebra. The theorems, like the postulates, are listed in pairs; each relation is the dual of 
the one paired with it. The postulates are basic axioms of the algebraic structure and 
need no proof. The theorems must be proven from the postulates. Proofs of the theorems 
with one variable are presented next. At the right is listed the number of the postulate 
which justifies that particular step of the proof. 
  
THEOREM 1(a):
     
=x.
Statement 
Justification 
=(xx)
#
1
postulate 2(b) 
= (x)(xx′)
5(a) 
+xx
4(b) 
+0
5(b) 
x
2(a) 
THEOREM 1(b):
     
x
#
=x.
Statement 
Justification 
x
#
xx + 0
postulate 2(a) 
xx xx
5(b) 
x(x′)
4(a) 
x
#
1
5(a) 
x
2(b) 
Note that theorem 1(b) is the dual of theorem 1(a) and that each step of the proof 
in part (b) is the dual of its counterpart in part (a). Any dual theorem can be similarly 
derived from the proof of its corresponding theorem.  
THEOREM 2(a):
+ 1 =1.
Statement 
Justifi cation 
+ 1 =1
#
(+ 1)    
postulate 2(b) 
= (x′)(+ 1)    
5(a) 
x
#
1    
4(b) 
x    
2(b) 
= 1    
5(a) 
THEOREM 2(b):
     x
#
0 =0    by duality.  
 
THEOREM 3: 
    
(x′)′= x.    From postulate 5, we have    x′ =1    and    x
#
x′= 0,    which 
together define the complement of x. The complement of    x    is x and is also    (x′)′.    
Online Convert PowerPoint to PDF file. Best free online export
area. Then just wait until the conversion from Powerpoint to PDF is complete and download the file. The perfect conversion tool.
export pdf into powerpoint; change pdf to powerpoint online
C# powerpoint - PowerPoint Conversion & Rendering in C#.NET
And detailed C# demo codes for these conversions are offered below. C# Demo Codes for PowerPoint Conversions. PowerPoint to PDF Conversion.
how to convert pdf to ppt using; drag and drop pdf into powerpoint
Section 2.4  Basic Theorems and Properties of Boolean Algebra    45
Therefore, since the complement is unique, we have    (x′)′= x.    The theorems involv-
ing two or three variables may be proven algebraically from the postulates and the 
theorems that have already been proven. Take, for example, the absorption theorem: 
THEOREM 6(a):
xyx.
Statement 
Justifi cation 
xyx
#
1+ xy    
postulate 2(b) 
x(1+ y)    
4(a) 
x(y+ 1)    
3(a) 
x
#
1    
2(a) 
x    
2(b) 
THEOREM 6(b): 
x(y) =x    by duality. 
The theorems of Boolean algebra can be proven by means of truth tables. In truth 
tables, both sides of the relation are checked to see whether they yield identical results 
for all possible combinations of the variables involved. The following truth table verifies 
the first absorption theorem: 
 y 
xy     xxy    
 0 
 1 
 0 
 1 
The algebraic proofs of the associative law and DeMorgan’s theorem are long and will 
not be shown here. However, their validity is easily shown with truth tables. For example, 
the truth table for the first DeMorgan’s theorem,    (+y)′= xy′,    is as follows: 
 y     xy    
(xy)    
x        y        xy    
 0 
 1 
 0 
 1 
Operator Precedence 
The operator precedence for evaluating Boolean expressions is (1) parentheses, 
(2)NOT, (3) AND, and (4) OR. In other words, expressions inside parentheses must be 
evaluated before all other operations. The next operation that holds precedence is the 
complement, and then follows the AND and, finally, the OR. As an example, consider 
the truth table for one of DeMorgan’s theorems. The left side of the expression is 
(y)′.    Therefore, the expression inside the parentheses is evaluated first and the 
.NET PDF Document Viewing, Annotation, Conversion & Processing
XDoc.PDF SDK for .NET. RasterEdge XDoc.PDF for .NET is a professional .NET PDF solution that provides complete and advanced PDF document processing features.
how to convert pdf file to powerpoint presentation; chart from pdf to powerpoint
C# powerpoint - Convert PowerPoint to TIFF in C#.NET
Supported. Load, Save Document. Preview Document. Conversion. Convert PowerPoint to PDF. Convert PowerPoint to HTML5. Convert PowerPoint to
convert pdf to powerpoint using; how to convert pdf into powerpoint
46    Chapter 2  Boolean Algebra and Logic Gates
Table 2.2 
Truth Tables for    F
1
and    F
2
F
1
F
2
result then complemented. The right side of the expression is    xy′,    so the complement 
of x and the complement of y are both evaluated first and the result is then ANDed. 
Note that in ordinary arithmetic, the same precedence holds (except for the comple-
ment) when multiplication and addition are replaced by AND and OR, respectively.   
2.5    BOOLEAN FUNCTIONS 
Boolean algebra is an algebra that deals with binary variables and logic operations. A 
Boolean function described by an algebraic expression consists of binary variables, the 
constants 0 and 1, and the logic operation symbols. For a given value of the binary variables, 
the function can be equal to either 1 or 0. As an example, consider the Boolean function 
F
1
=yz   
The function    F
1
is equal to 1 if x is equal to 1 or if both    y    and z are equal to 1.    F
1
is equal 
to 0 otherwise. The complement operation dictates that when    y′ ′ =1, y= 0.    Therefore, 
F
1
= 1    if    x= 1    or if    = 0    and    =1.    A Boolean function expresses the logical rela-
tionship between binary variables and is evaluated by determining the binary value of 
the expression for all possible values of the variables. 
A Boolean function can be represented in a truth table. The number of rows in the 
truth table is    2
n
,    where n is the number of variables in the function. The binary combina-
tions for the truth table are obtained from the binary numbers by counting from 0 
through    2
n
- 1.     Table   2.2    shows the truth table for the function    F
1
.    There are eight pos-
sible binary combinations for assigning bits to the three variables xy, and z. The column 
labeled    F
1
contains either 0 or 1 for each of these combinations. The table shows that 
the function is equal to 1 when    x= 1    or when    yz =01    and is equal to 0 otherwise. 
A Boolean function can be transformed from an algebraic expression into a circuit 
diagram composed of logic gates connected in a particular structure. The logic‐circuit 
diagram (also called a schematic) for    F
1
is shown in  Fig.   2.1   . There is an inverter for input 
to generate its complement. There is an AND gate for the term    yz    and an OR gate 
How to C#: Overview of Using XDoc.PowerPoint
XDoc.PowerPoint for .NET, like PPTXDocument and PPTXPage. PowerPoint Conversion. XDoc.PowerPoint SDK for .NET empowers C# developers
how to convert pdf to ppt online; convert pdf to ppt
C# powerpoint - Convert PowerPoint to PDF in C#.NET
PowerPoint to PDF Conversion Overview. RasterEdge XDoc.PowerPoint empowers your C#.NET application with advanced PowerPoint to PDF conversion functionality.
how to convert pdf slides to powerpoint; how to convert pdf into powerpoint on
Section 2.5  Boolean Functions    47
that combines x with    yz.    In logic‐circuit diagrams, the variables of the function are taken 
as the inputs of the circuit and the binary variable    F
1
is taken as the output of thecircuit. 
The schematic expresses the relationship between the output of the circuit and its inputs. 
Rather than listing each combination of inputs and outputs, it indicates how to compute 
the logic value of each output from the logic values of the inputs. 
There is only one way that a Boolean function can be represented in a truth table. 
However, when the function is in algebraic form, it can be expressed in a variety of ways, 
all of which have equivalent logic. The particular expression used to represent the function 
will dictate the interconnection of gates in the logic‐circuit diagram. Conversely, the inter-
connection of gates will dictate the logic expression. Here is a key fact that motivates our 
use of Boolean algebra: By manipulating a Boolean expression according to the rules of 
Boolean algebra, it is sometimes possible to obtain a simpler expression for the same 
function and thus reduce the number of gates in the circuit and the number of inputs to 
the gate. Designers are motivated to reduce the complexity and number of gates because 
their effort can significantly reduce the cost of a circuit. Consider, for example, the fol-
lowing Boolean function: 
F
2
xyzxyzxy    
A schematic of an implementation of this function with logic gates is shown in 
Fig.  2.2   (a). Input variables x and y are complemented with inverters to obtain    x′    and 
y′.    The three terms in the expression are implemented with three AND gates. The 
OR gate forms the logical OR of the three terms. The truth table for    F
2
is listed in 
Table   2.2   . The function is equal to 1 when    xyz =001    or 011 or when    xy= 10    (irre-
spective of the value of z) and is equal to 0 otherwise. This set of conditions produces 
four 1’s and four 0’s for    F
2
   
Now consider the possible simplification of the function by applying some of the 
identities of Boolean algebra: 
F
2
=xyzxyzxy′ =xz(y′ + y) +xy′ = xxy   
The function is reduced to only two terms and can be implemented with gates as shown 
in  Fig.   2.2   (b). It is obvious that the circuit in (b) is simpler than the one in (a), yet both 
implement the same function. By means of a truth table, it is possible to verify that the 
two expressions are equivalent. The simplified expression is equal to 1 when    xz= 01    or 
when    xy= 10.    This produces the same four 1’s in the truth table. Since both expressions 
F
1
x
y
z
FIGURE 2.1  
Gate implementation of    F
1
x yz          
VB.NET PDF Converter Library SDK to convert PDF to other file
Conversion of MS Office to PDF. This guide give a series of demo code directly for converting MicroSoft Office Word, Excel and PowerPoint document to PDF file
convert pdf to powerpoint online; pdf into powerpoint
C# PDF Converter Library SDK to convert PDF to other file formats
C#.NET PDF - PDF Conversion & Rendering SDK for C#.NET. A best C# PDF converter control for adobe PDF document conversion in Visual Studio .NET applications.
convert pdf file into ppt; how to convert pdf into powerpoint presentation
48    Chapter 2  Boolean Algebra and Logic Gates
produce the same truth table, they are equivalent. Therefore, the two circuits have the 
same outputs for all possible binary combinations of inputs of the three variables. Each 
circuit implements the same identical function, but the one with fewer gates and fewer 
inputs to gates is preferable because it requires fewer wires and components. In general, 
there are many equivalent representations of a logic function. Finding the most eco-
nomic representation of the logic is an important design task. 
Algebraic Manipulation 
When a Boolean expression is implemented with logic gates, each term requires a gate 
and each variable within the term designates an input to the gate. We define a literal to 
be a single variable within a term, in complemented or uncomplemented form. The 
function of  Fig.   2.2   (a) has three terms and eight literals, and the one in  Fig.   2.2   (b) has 
two terms and four literals. By reducing the number of terms, the number of literals, or 
both in a Boolean expression, it is often possible to obtain a simpler circuit. The manip-
ulation of Boolean algebra consists mostly of reducing an expression for the purpose of 
obtaining a simpler circuit. Functions of up to five variables can be simplified by the 
map method described in the next chapter. For complex Boolean functions and many 
(a)F
2
=xyzxyzxy
(b)F
2
=xy′+ xz
x
y
z
F
2
x
y
z
F
2
FIGURE 2.2  
Implementation of Boolean function    F
2
with gates       
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document. Provide Free Demo Code for PDF Conversion from Microsoft PowerPoint in C# Program.
convert pdf into ppt; convert pdf into ppt online
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
resolution, bit depth, scaling, etc. Implement Conversion from PowerPoint to PDF in VB.NET, Converting PowerPoint document to PDF
converting pdf to powerpoint slides; convert pdf to editable ppt
Section 2.5  Boolean Functions    49
different outputs, designers of digital circuits use computer minimization programs that 
are capable of producing optimal circuits with millions of logic gates. The concepts intro-
duced in this chapter provide the framework for those tools. The only manual method 
available is a cut‐and‐try procedure employing the basic relations and other manipulation 
techniques that become familiar with use, but remain, nevertheless, subject to human 
error. The examples that follow illustrate the algebraic manipulation of Boolean algebra 
to acquaint the reader with this important design task. 
EXAMPLE 2.1 
Simplify the following Boolean functions to a minimum number of literals. 
 1.      x(x′+ y) = xx′ + xy = 0 +xy =xy.     
2.
xy= (x′)(+y) = 1(y) = y.
3.
(y)(+y′) = xy xy′+ yy′ =x(1 + yy′) = x.
4.
xy xyz xyxzyz(+x′)
xy +xxyz xyz    
xy(1+ z) + xz(1+ y)    
xy +xz.     
 5.      (y)(x′ + z)(yz) = (+y)(x′+ z),    by duality from function 4.    
Functions 1 and 2 are the dual of each other and use dual expressions in correspond-
ing steps. An easier way to simplify function 3 is by means of postulate 4(b) from 
Table   2.1   :    (y)(xy′) = yy′= x.    The fourth function illustrates the fact that 
an increase in the number of literals sometimes leads to a simpler final expression. 
Function 5 is not minimized directly, but can be derived from the dual of the steps used 
to derive function 4. Functions 4 and 5 are together known as the consensus theorem.  
Complement of a Function 
The complement of a function F is    F′    and is obtained from an interchange of 0’s for 1’s 
and 1’s for 0’s in the value of F. The complement of a function may be derived algebraically 
through DeMorgan’s theorems, listed in  Table   2.1    for two variables. DeMorgan’s theo-
rems can be extended to three or more variables. The three‐variable form of the first 
DeMorgan’s theorem is derived as follows, from postulates and theorems listed in  Table   2.1   : 
(ABC)′= (+x)′
let Bx
Ax
by theorem 5(a) (DeMorgan)
A′(BC)′   substitute Bx
A′(BC′)    by theorem 5(a) (DeMorgan)
ABC
by theorem 4(b) (associative)   
50    Chapter 2  Boolean Algebra and Logic Gates
DeMorgan’s theorems for any number of variables resemble the two‐variable case in 
form and can be derived by successive substitutions similar to the method used in the 
preceding derivation. These theorems can be generalized as follows: 
(+++
g
F)′ =ABCD′cF
(ABCDc
F)′= A′+ B′ + C′+ D′+
g
F   
The generalized form of DeMorgan’s theorems states that the complement of a func-
tion is obtained by interchanging AND and OR operators and complementing each 
literal. 
EXAMPLE 2.2 
Find the complement of the functions    F
1
xyz′+ xyz    and    F
2
x(yz′ +yz).    By 
applying DeMorgan’s theorems as many times as necessary, the complements are 
obtained as follows: 
F
=
1
= (xyz′+ xyz)′ =(xyz′)′(xyz)′ = (xy′+ z)(yz′)
F
=
2
= [x(yz′ + yz)]′  =x′+ + (yz′ + yz)′= x′ + (yz′)′(yz)′
x′+ (z)(y′ + z′)
x′+ yz′ +yz   
A simpler procedure for deriving the complement of a function is to take the dual of 
the function and complement each literal. This method follows from the generalized 
forms of DeMorgan’s theorems. Remember that the dual of a function is obtained from 
the interchange of AND and OR operators and 1’s and 0’s.  
EXAMPLE 2.3 
Find the complement of the functions    F
1
and    F
2
of Example 2.2 by taking their duals 
and complementing each literal. 
 1.      F
1
xyz′ + xyz.    
The dual of    F
1
is    (x′+ z′)(x′ +y′+ z).    
Complement each literal:    (y′+ z)(yz′) = F
=
1
.     
 2.      F
2
x(yz′+ yz).    
The dual of    F
2
is    x+ (y′+ z′)(z).    
Complement each literal:    x′ ′ + (+z)(y′+ z′) ) = F
=
2
.         
Section 2.6  Canonical and Standard Forms    51
2.6    CANONICAL AND STANDARD FORMS 
Minterms and Maxterms 
A binary variable may appear either in its normal form (x) or in its complement form    (x′).    
Now consider two binary variables x and y combined with an AND operation. Since each 
variable may appear in either form, there are four possible combinations:    xy′, xyxy′,    
and xy. Each of these four AND terms is called a minterm, or a standard product. In a 
similar manner, n variables can be combined to form    2
n
minterms. The    2
n
different min-
terms may be determined by a method similar to the one shown in  Table   2.3    for three 
variables. The binary numbers from 0 to    2
n
- 1    are listed under the n variables. Each 
minterm is obtained from an AND term of the n variables, with each variable being 
primed if the corresponding bit of the binary number is a 0 and unprimed if a 1. A symbol 
for each minterm is also shown in the table and is of the form    m
j
,    where the subscript j 
denotes the decimal equivalent of the binary number of the minterm designated. 
In a similar fashion, n variables forming an OR term, with each variable being primed 
or unprimed, provide    2
n
possible combinations, called maxterms, or standard sums. The 
eight maxterms for three variables, together with their symbolic designations, are listed 
in  Table   2.3   . Any    2
n
maxterms for n variables may be determined similarly. It is impor-
tant to note that (1) each maxterm is obtained from an OR term of the n variables, with 
each variable being unprimed if the corresponding bit is a 0 and primed if a 1, and (2) 
each maxterm is the complement of its corresponding minterm and vice versa. 
A Boolean function can be expressed algebraically from a given truth table by form-
ing a minterm for each combination of the variables that produces a 1 in the function 
and then taking the OR of all those terms.  For example, the function    f
1
in  Table   2.4    is 
determined by expressing the combinations 001, 100, and 111 as    xyz, xyz′,    and xyz
respectively. Since each one of these minterms results in    f
1
= 1,    we have 
f
1
xyxyz′ + xyz =m
1
m
4
m
7
Table 2.3
Minterms and Maxterms for Three Binary Variables
Minterms
Maxterms
x
y
z
Term
Designation
Term
Designation
0
0
0
xyz
m
0
x++z
M
0
0
0
1
xyz
m
1
x++z
M
1
0
1
0
xyz
m
2
x+y′ +z
M
2
0
1
1
xyz
m
3
x+y′ +z
M
3
1
0
0
xyz
m
4
x′ ++z
M
4
1
0
1
xyz
m
5
x′ ++z
M
5
1
1
0
xyz
m
6
x′ +y′+ z
M
6
1
1
1
xyz
m
7
x′ +y′+ z
M
7
52    Chapter 2  Boolean Algebra and Logic Gates
Similarly, it may be easily verified that 
f
2
=xyzxyzxyz′+ xyz m
3
m
5
m
6
m
7
These examples demonstrate an important property of Boolean algebra: Any Boolean 
function can be expressed as a sum of minterms (with “sum” meaning the ORing of terms). 
Now consider the complement of a Boolean function. It may be read from the truth 
table by forming a minterm for each combination that produces a 0 in the function and 
then ORing those terms. The complement of    f
1
is read as 
f
=
1
=xyz′ + xyz′ + xyz xy+xyz   
If we take the complement of    f
=
1
,    we obtain the function    f
1
:    
f
1
= (+z)(+y′+ z)(x′ + yz′)(x′+ y′ + z)
M
0
#
M
2
#
M
3
#
M
5
#
M
6
Similarly, it is possible to read the expression for    f
2
from the table: 
f
2
= (yz)(yz′)(y′ +z)(x′+ z)
M
0
M
1
M
2
M
4
These examples demonstrate a second property of Boolean algebra: Any Boolean func-
tion can be expressed as a product of maxterms (with “product” meaning the ANDing 
of terms). The procedure for obtaining the product of maxterms directly from the truth 
table is as follows: Form a maxterm for each combination of the variables that produces 
a 0 in the function, and then form the AND of all those maxterms.  Boolean functions 
expressed as a sum of minterms or product of maxterms are said to be in  canonical form .   
Sum of Minterms 
Previously, we stated that, for n binary variables, one can obtain    2
n
distinct minterms and 
that any Boolean function can be expressed as a sum of minterms.  The minterms whose 
sum defines the Boolean function are those which give the 1’s of the function in a 
Table 2.4
Functions of Three Variables
x
y
z
Function f
1
Function f
2
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Documents you may be interested
Documents you may be interested