**BOOLEAN ALGEBRA**

BASIC CONCEPTS:RELATION

BOOLEAN ALGEBRA:AXIOMS

BOOLEAN ALGEBRA: THEOREMS

Theorem: Complement element is unique.

Theorem: a+1 = 1 and a. 0 = 0.

Theorem:0'=1 and 1'=0 .

Theorem:Idempotent (eşkuvvet) theorem

a+a = a and a.a = a.

BOOLEAN FUNCTIONS AND REPESENTATION

Cartesian product

of two sets X and Y denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y.

Relation (Bağıntı):

Assume that A «domain» (tanım kümesi), and B «range» (değer kümesi) are two sets, then R «relation»set is

Completely specified relation (Tamamen belirlenmiş bağıntı ) :

If the R relation includes all the elements in the domain of A then it is called «completely specified» relation

Functional relation (Fonksiyonel bağıntı):

In a «R» relation, for each element in A if there exists one and only one element corresponding in B then it is called as «functional relation»

Function:

Completely specified functional relation is called function.

It is shown as F : A→ B .

BASIC CONCEPTS:FUNCTION

EQUIVALENCE RELATION:

If R:A →A has the following properties then it is called as «equivalence relation» and shown as " = ".

Reflexive:

Symmetric:

Transitive:

ORDER RELATION:

If R:A →A has the following properties then it is called as «order relation» and shown as "<".

Symmetric:

Transitive:

Physical:time,

Mathematical model Real numbers (Order relation set)

Which arithmetic operation is an equivalence relation?

n-ary operation/n-variable function(n-lik işlem):

Assume that A^n =AXA...A is domain set and A is range set then

is called n-ary operation or n-variable function.

one-variable function examples: 5cos 2t ; 2x+3

two- variable function examples: x+5y; xy

Boolean Algebra is a mathematical system composed of three elements M = (S,R,A) such as

S: is a

finite-element-set

.

R: is a set of three operations defined on S:

Two 2-ary operations called ‘Summation, OR' and 'product, AND'

One 1-ary operation called ‘complement'.

A: is a set of axioms which defines R operations on S.

Assuming that a,b,c are the elements of S:

Axiom.1 Commutative (Yer değiştirme) axiom

1. a+ b = b+ a

2. a. b = b. a

Axiom.2. distributive (Dağılma) axiom

1. a +(b c) = (a+ b) (a+ c)

2. a. (b+ c) = (a b)+ (a c)

Axiom.3.Unit elements existence

1. a+ 0 = 0+ a = a

2. a .1 = 1 .a = a

Axiom.4.Complement (Tümleyen) element existence

1. a+ a' = a‘+ a = 1

2. a. a' = a' .a = 0

What is (are) the difference(s) between the known algebra and the Boolean Algebra?

DUALITY PRINCIPLE

For each axiom there is a dual axiom which is found by replacing (+) with (.) and (1) with (0)

and vice versa

Conclusion

Once a theorem is proved then it’s dual is also true without any proof.

Theorem:An elements complement’s

Complement is equal to itself (a' )'=a.

Theorem:absorb (Yutma)

a+a.b = a and a.(a+b) = a

Theorem

a+a' b = a+b and a.(a'+b) = ab

Theorem of ‘Associativity’ (guplandırma)

a+(b+c) = (a+b)+c and a.(b.c) = (a.b) .c dir.

De Morgan theorem:

(a+b)' = a' b' and ab)' = a'+b'

Consensus theorem

a.b + a' c + b.c = a.b + a'.c

BOOLEAN ALGEBRA EXAMPLE

Assuming that a,b,c are the elements of S:

Axiom.1 Commutative (Yer değiştirme) axiom

1. a+ b = b+ a

2. a. b = b. a

Axiom.2. distributive (Dağılma) axiom

1. a +(b c) = (a+ b) (a+ c)

2. a. (b+ c) = (a b)+ (a c)

Axiom.3.Unit elements existence

1. a+ 0 = 0+ a = a

2. a .1 = 1 .a = a

Axiom.4.Complement element existence

1. a+ a' = a‘+ a = 1

2. a. a' = a' .a = 0

NUMBER OF FUNCTIONS DEFINED ON A FINETE SET

Repeated N elements' n-tuple permutations is equal to

EXAMPLE

n-variable Boolean Function:

By applying (+), (.), (‘) operations to the x1, x2 ,...xn variables, each function defined is called «Boolean Function».

In other words each function written as a formula is a «Boolean Function»

All the functions other than Boolean are called Non-Boolean.

Fundamental theorem of Boolean Algebra is

Shannon theorem

Generalized Shannon Theorem

BOOLEAN /

NON BOOLEAN FUNCTIONS

"Second type canonical" or

"product of sums terms"

"First type canonical" or

"sum of products terms"

product terms:minterms

sum terms:maxterms

FUNCTION TRUTH TABLE / CANONICAL FORMS EXAMPLES

TRUE MINTERM/TRUE MAXTERM REPRESENTATION EXAMPLE

CANONICAL FORM REPRESENTATION EXAMPLE

**BOOLEAN FUNCTIONS**

**BOOLEAN ALGEBRA**

How many different representations are there for Boolean functions?

Assume that

**EXAMPLE**