Software Layers 2 Introduction to unix 2

Boolean Algebra

• 
  Boolean Algebra = formal system of describing Boolean logical statements (functions)  invented by Geoge Boole (1800’s)
  
• 
  Algebra = a set of elements (the carrier of the algebra), and operators defined on the carrier
  
• 
  Calculus = a method of reasoning by calculation with symbols...
  

• 
  NOT: NOT X = 0 if X is 1, = 1 otherwise (X')
  
• 
  AND: X AND Y = 1 if X and Y are 1, = 0 otherwise (X*Y or X.Y)
  
• 
  NAND: X NAND Y = 0 if X & Y are 1, = 1 otherwise
  
• 
  OR: X OR Y = 0 if X & Y are 0, = 1 otherwise (X+Y)
  
• 
  NOR: X NOR Y = 1 if X & Y are 0, = 0 otherwise
  
• 
  XOR: X XOR Y = 0 if X & Y are the same, = 1 otherwise
  
• 
  XNOR: X XNOR Y = 1 if X & Y are the same, = 0 otherwise
  

Analysing Boolean functions:

Method 1: Truth Tables

Given a function: F = (X OR (X AND Y)) OR (Y AND (Y OR (NOT Z)))

note: operator precedence is: NOT > AND > OR

Inputs			Intermediate computations...					Output
X	Y	Z	X AND Y	X OR (X AND Y)	NOT Z	Y OR (NOT Z)	Y AND (Y OR (NOT Z))	F
0	0	0	0	0	1	1	0	0
0	0	1	0	0	0	0	0	0
0	1	0	0	0	1	1	1	1
0	1	1	0	0	0	1	1	1
1	0	0	0	1	1	1	0	1
1	0	1	0	1	0	0	0	1
1	1	0	1	1	1	1	1	1
1	1	1	1	1	0	1	1	1

note: we can deduce that F = X OR Y
Method 2: Boolean algebra

Typical shorthand: *  AND +  OR '  NOT
F = (X OR (X AND Y)) OR (Y AND (Y OR (NOT Z)))

= (X + (X * Y)) + (Y * (Y + Z'))

F is a combination of: the logic operators (+, *, ') & operands (X, Y, Z)

Many operators (and functions) can be constructed from these basic ones:

• 
  X NAND Y = (X * Y)'
  
• 
  X NOR Y = (X + Y)'
  
• 
  X XOR Y = (X' * Y) + (X * Y')
  

eg: Evaluate: F = (X + (X * Y)) + (Y * (Y + Z')) when X = 1, Y = 0, Z = 1

= (1 + (1 * 0)) + (0 * (0 + 1'))

= (1 + 0) + (0 * (0 + 0))

= 1 + (0 * 0)

= 1 + 0

= 1
To simplify F we can use some laws:

• 
  Law 1: P * P = P
  
• 
  Law 2: P * (Q + R) = (P * Q) + (P * R)
  
• 
  Law 3: P + (P * Q) = P
  

F = (X + (X * Y)) + (Y * (Y + Z'))

= X + (Y * (Y + Z')) {using Law 3}

= X + ((Y * Y) + (Y * Z')) {using Law 2}

= X + (Y + (Y * Z')) {using Law 1}

= X + (Y) {using Law 2}

= X + Y

Directory: student
student -> How to Create a Student Recital Program
student -> Tracks, Mixes, Masters, and More!: Analyzing Preservation Priorities for Multitrack Recordings
student -> A chronology 1660-1832 The Restoration Settlement
student -> Introduction
student -> Disaster planning and recovery: post-katrina lessons for mixed media collections
student -> Comparing Hurricanes and Hurricane Seasons
student -> Storm Surge: a rising Danger
student -> Dr. Jeff Masters' WunderBlog
student -> April 9, 2008 Hurricanes (Continued)
student -> Instructions for Writing Hurricane Term Paper

Download 0.58 Mb.

Share with your friends: