Boolean Algebra: - Boolean Functions - Representing Boolean Functions - Logic Gates - Minimization of Circuits

Boolean Algebra
Boolean Functions Representing Boolean Functions Logic Gates Minimization of Circuits
Boolean Expressions and Boolean Functions

Let B = {0,1} x is called Boolean variable if it is assumes the values only from B. A function from Bn to B is called Boolean function of degree n. Boolean expressions:
0,1, and variables are boolean expressions If E1 and E2 are Boolean expressions then ~E1, (E1E2), and (E1 + E2) are Boolean expressions.
Bolean expression represents Boolean function

Example: Find the values of Boolean funtion represented by F(x,y,z) = xy + ~z
x 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 xy 1 1 0 0 0 0 0 0 ~z 0 1 0 1 0 1 0 1 xy + ~z 1 1 0 1 0 1 0 1
F = G iff F(b1,b2,b3,bn)=G(b1,b2,b3,bn) whenever b1, b2, b3,bn belong to B

Equivalent Boolean expression: Example xy xy + 0 xy.1 Complement: (~F)(x1,x2,x3,,xn)= ~(F(x1,x2,x3,,xn)) Boolean sum and Boolean product:
(F+G)(x1,x2,,xn) = F(x1,x2,,xn)+ G(x1,x2,,xn) (FG)(x1,x2,,xn) = F(x1,x2,,xn)G(x1,x2,,xn)
Identities of Boolean Algebra

~~x = x x+x = x x.x = x x+0 = x x.1 = x Law of double complement Idempoten laws Identity laws Dominance laws Comutative laws Associative laws Distributive laws De Morgans laws
x+1 = 1 x.0 = 0
x+y = y+x xy =yx x+(y+z) = (x+y)+z x(yz) = (xy)z x+(yz) = (x+y)(x+z) x(y+z) = xy+xz ~(xy) = ~x+~y ~(x+y) = (~x)(~y)
Examples:
Show that the distributive law is valid Prove the absorption law x(x+y) = x using the identities of Boolean algebra
Duality The Dual of a Boolean expressionis obtained by interchanging Boolean sums and Bolean product and interchanging 0s and 1s. Example: Find the dual of x(y+0) and (~x).1+ (~y)+z Solution: x+(y.1) ((~x)+0)(~y)z
The abstract definition of a Boolean algebra

Definition. A Boolean algebra is a set B with two binary operations and , elements 0 and 1, and operation ~ such that the following properties hold for all x, y, and z in B.
x0=x x1=x x ~x = 1 x ~x = 0 x (y z) = (x y) z x (y z) = (x y) z Identity laws Dominance laws Associative laws Comutative laws Distributive laws
xy=yx x y =y x
x (y z) = (x y) (x z) x (y z) = (x y) (x z)
Representing Boolean Functions

Sum-of-products Expansions Example: x y Find Boolean 1 1 expressions that 1 1 represent the 1 0 1 0 functions F(x,y,z) 1 and G(x,y,z) which 0 0 1 are given in the 0 0 following table. 0 0 Solution: x~yz and xy~z + ~xy~z
z 1 0 1 0 1 0 1 0
F 0 0 1 0 0 0 0 0
G 0 1 0 0 0 1 0 0
Definition. A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1, x2, , xn is a Boolean product y1, y2, , yn where yi = xi or yi = ~xi Example: Find a minterm that equals 1 if x1 = x3 = 0 and x2 = x4 = x5 = 1, and equals 0 otherwise.
Solution: ~x1x2~x3x4x5
Sum-of-products expansion: the sum of minterms that represent function Example: Find the sum-of-products expansion for the function F(x,y,z) = (x+y)~z
x 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 x+y ~z (x+y) ~z
F(x,y,z) = xy~z + x~y~z + ~xy~z
Functional Completeness
{., +, ~} is functionally complete: every Boolean function can be represented using the Bolean operators ., + and ~. x + y = ~(~x~y) {., ~} is functionally complete xy = ~(~x + ~y) {+, ~} is functionally complete
Defined operator or NAND: 11 = 0, 10 = 01 = 00 = 0 Defined operator or NOR: 00 = 1, 10 = 01 = 11 = 1
~x = xx and xy = (xy)(xy) { } is functionally complete

{ } is functionally complete
Rangkaian Digital Elektronik

x xy
x'
x y
x+ y
Gerbang AND
Gerbang NOT
Gerbang or
Contoh. Nyatakan fungsi f(x, y, z) = xy + xy ke dalam rangkaian logika.

x y xy xy+x'y x y x' x'y
x' x'y x y xy xy+x'y
Penyederhanaan Fungsi Boolean
Contoh. f(x, y) = xy + xy + y disederhanakan menjadi f(x, y) = x + y Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara: 1. Secara aljabar 2. Menggunakan Peta Karnaugh 3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
Penyederhanaan Secara Aljabar

Contoh:
f(x, y) = = = =
x + xy (x + x)(x + y) 1 (x + y ) x+y
f(x, y, z) = xyz + xyz + xy = xz(y + y) + xy = xz + xy
Peta Karnaugh
a. Peta Karnaugh dengan dua peubah

y x x xy xy y xy xy
b. Peta dengan tiga peubah yz x xyz x xyz yz xyz xyz yz xyz xyz yz xyz xyz
Contoh:

Sederhanakan SOP expansions a. xy + xy b. xy + xy c. xy + xy + xy
y
x x 1 1
y
x x
y
1 x x
y
1
Squares are said to be adjacent if the minterms that they represent differ in exactly one literal. Whenever there are 1s in two adjacent squares in the map, the minterms represented by these squares can be combined into a product involving just one of the variables. We circle blocks of squares in the map that represent minterms that can be combines. The goal is to identify the larges possibles blocks, and to cover all the 1s with the fewest blocks using the largest blocks
y x x
a.
y x x
y 1 x x
y 1
1 1
xy + xy
1
b. xy + xy
c. xy + xy + xy c. x + y
Jawab: a. y
b. xy + xy
Contoh. Minimisasi fungsi Boolean f(x, y, z) = xz + xy + xyz + yz

Jawab: xz = xz(y + y) = xyz + xyz xy = xy(z + z) = xyz + xyz yz = yz(x + x) = xyz + xyz

f(x, y, z) = xz + xy + xyz + yz = xyz + xyz + xyz + xyz + xyz + xyz + xyz = xyz + xyz + xyz + xyz + xyz Hasil penyederhanaan: f(x, y, z) = z + xy
yz
yz
yz
yz
Dont Care Conditions
Contoh: One way to code decimal expansions using bits is to use the four bits of binary expansions of each digit in the decimal expansion. Suppose that a circuit is to be built that produces an output of 1 if the decimal digit is 5 or greater and otherwise is 0. How can this circuit be simply built using OR gates, AND gates and inverters?
Digit w
0 1 2 3 4 5 0 0 0 0 0 0
x
0 0 0 0 1 1
y
0 0 1 1 0 0
z
0 1 0 1 0 1
F
0 0 0 0 0 1 wx yz d yz yz yz d d d
wx
wx wx
d
1
d
1
1
1
6
7 8 9
0
0 1 1
1
1 0 0
1
1 0 0
0
1 0 1
1
1 1 1

Boolean Algebra: - Boolean Functions - Representing Boolean Functions - Logic Gates - Minimization of Circuits

Uploaded by

Copyright:

Available Formats

Boolean Algebra: - Boolean Functions - Representing Boolean Functions - Logic Gates - Minimization of Circuits

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Boolean Algebra: - Boolean Functions - Representing Boolean Functions - Logic Gates - Minimization of Circuits

Uploaded by

Copyright:

Available Formats

Boolean Algebra

Boolean Functions Representing Boolean Functions Logic Gates Minimization of Circuits

Boolean Expressions and Boolean Functions

Bolean expression represents Boolean function

F = G iff F(b1,b2,b3,bn)=G(b1,b2,b3,bn) whenever b1, b2, b3,bn belong to B

Identities of Boolean Algebra

The abstract definition of a Boolean algebra

Representing Boolean Functions

F(x,y,z) = xy~z + x~y~z + ~xy~z

Defined operator or NAND: 11 = 0, 10 = 01 = 00 = 0 Defined operator or NOR: 00 = 1, 10 = 01 = 11 = 1

~x = xx and xy = (xy)(xy) { } is functionally complete

Rangkaian Digital Elektronik

Contoh. Nyatakan fungsi f(x, y, z) = xy + xy ke dalam rangkaian logika.

Penyederhanaan Fungsi Boolean

Penyederhanaan Secara Aljabar

f(x, y, z) = xyz + xyz + xy = xz(y + y) + xy = xz + xy

a. Peta Karnaugh dengan dua peubah

Sederhanakan SOP expansions a. xy + xy b. xy + xy c. xy + xy + xy

Contoh. Minimisasi fungsi Boolean f(x, y, z) = xz + xy + xyz + yz

Dont Care Conditions

You might also like