New version page

GSU CSC 2510 - ch07s1

Documents in this Course
ch02s2

ch02s2

5 pages

ch04s2

ch04s2

8 pages

ch01s6

ch01s6

10 pages

ch01s1

ch01s1

21 pages

ch02s4

ch02s4

10 pages

ch08s2

ch08s2

21 pages

ch08s3

ch08s3

15 pages

ch07s3

ch07s3

21 pages

ch04s3

ch04s3

23 pages

ch06s3

ch06s3

16 pages

ch01s3

ch01s3

15 pages

ch03s4

ch03s4

11 pages

ch03s6

ch03s6

6 pages

ch03s5

ch03s5

9 pages

ch06s2

ch06s2

9 pages

ch03s1

ch03s1

19 pages

ch02s1

ch02s1

14 pages

ch08s1

ch08s1

15 pages

ch02s5

ch02s5

9 pages

ch01s4

ch01s4

13 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-3-4 out of 11 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Boolean Algebra and Computer LogicModels or AbstractionsDefinition and PropertiesSlide 4Slide 5Slide 6Slide 7Isomorphic Boolean AlgebrasSlide 9Slide 10Slide 11Boolean Algebra and Computer LogicMathematical Structures for Computer ScienceChapter 7Copyright © 2006 W.H. Freeman & Co. MSCS Slides Boolean Algebra StructureSection 7.1 Boolean Algebra Structure 2Models or AbstractionsMathematical principles are models or abstractions intended to capture properties that may be common to different instances or manifestations.These principles are sometimes expressed as mathematical structures—abstract sets of objects, together with operations on or relationships among those objects that obey certain rules.Section 7.1 Boolean Algebra Structure 3Definition and PropertiesA Boolean algebra is a set B on which are defined two binary operations and and one unary operation and in which there are two distinct elements 0 and 1 such that the following properties hold for all x, y, z  B: x + y = y + x (commutative properties)(x + y) + z = x + (y + z) (associative properties)x + (y * z) = (x + y) * (x + z) (distributive properties)x + 0 = x (identity properties)x + x = 1 (complement properties)Andx * y = y * x (commutative properties)(x* y) * z = x * (y * z) (associative properties)x * (y + z) = (x * y) + (x * z) (distributive properties)x * 1 = x (identity properties)x * x = 0 (complement properties)Section 7.1 Boolean Algebra Structure 4Definition and PropertiesThe formalization of a Boolean algebra structure helps us focus on the essential features common to all examples of Boolean algebras, and we can use these features—these facts from the definition of a Boolean algebra—to prove other facts about Boolean algebras.We denote a Boolean algebra by [B, +, -, , 0, 1].Section 7.1 Boolean Algebra Structure 5Definition and PropertiesFor example, The idempotent property x + x = xholds in any Boolean algebra because:x + x = (x + x) - 1= (x + x) - (x + x) = x - (x+ x)= x + 0= xOrdinary arithmetic is not a Boolean algebra because the property x + x = x does not hold for ordinary numbers and ordinary addition unless x is zero.Section 7.1 Boolean Algebra Structure 6Definition and PropertiesHints for proving Boolean algebra equalities:Usually the best approach is to start with the more complicated expression and try to show that it reduces to the simpler expression.Think of adding some form of 0 (like x - x ) or multiplying by some form of 1 (like x + x ).Remember the distributive property of addition over multiplication—easy to forget because it doesn’t look like arithmetic.Remember the idempotent properties x + x = x and x - x = x.Section 7.1 Boolean Algebra Structure 7Definition and PropertiesFor x an element of a Boolean algebra B, the element x is called the complement of x. The complement of x satisfies:x + x = l and x - x = 0THEOREM ON THE UNIQUENESS OF COMPLEMENTS For any x in a Boolean algebra, if an element x1 exists such that x + x1 = 1 and x - x1 = 0, then x1 = x.Section 7.1 Boolean Algebra Structure 8Isomorphic Boolean AlgebrasTwo instances of a structure are isomorphic if there is a bijection (called an isomorphism) that maps the elements of one instance onto the elements of the other so that important properties are preserved.If two instances of a structure are isomorphic, each is a mirror image of the other, with the elements simply relabeled.The two instances are essentially the same. Therefore, we can use the idea of isomorphism to classify instances of a structure, lumping together those that are isomorphic.Section 7.1 Boolean Algebra Structure 9Isomorphic Boolean AlgebrasSuppose we have two Boolean algebras, [B, +, -, , 0, 1] and [b, &, -, , φ, 1].If x is in B, x is the result of performing on x the unary operation defined in B.If z is an element of b, z is the result of performing on z the unary operation defined in b.To prove isomorphism, we need a bijection f from B onto b.Then f must preserve in b the effects of the various operations in B.There are three operations, so we use three equations to express these preservations.Section 7.1 Boolean Algebra Structure 10Isomorphic Boolean AlgebrasDEFINITION: ISOMORPHISM FOR BOOLEAN ALGEBRAS Let [B, +, -, , 0, 1] and [b, &, -, , φ, 1] be Boolean algebras. A function B  b is an isomorphism from [B, +, -, , 0, 1] to [b, &, -, , φ, 1] if:f is a bijection f (x + y) = f (x) & f (y) f (x . y) = f (x) - f (y)f (x) = ( f (x))Section 7.1 Boolean Algebra Structure 11Isomorphic Boolean AlgebrasTHEOREM ON FINITE BOOLEAN ALGEBRASLet B be any Boolean algebra with n elements. Then n = 2m for some m, and B is isomorphic to ({1, 2, ... , m}).The theorem above gives us two pieces of information:The number of elements in a finite Boolean algebra must be a power of 2.Finite Boolean algebras that are power sets are—in our lumping together of isomorphic things—really the only kinds of finite Boolean


View Full Document
Download ch07s1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch07s1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch07s1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?