Boolean Algebra: Operations and Functions
B
B
o
o
o
o
l
l
e
e
a
a
n
n
A
A
l
l
g
g
e
e
b
b
r
r
a
a
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
1
B
B
o
o
o
o
l
l
e
e
a
a
n
n
F
F
u
u
n
n
c
c
t
t
i
i
o
o
n
n
s
s
•
In Boolean algebra we work with the
set
{0,1},
where:
•
0 ≡ F
(False) &
1 ≡ T
(True).
•
The 3 Operations used in Boolean Algebra
The 3 Operations used in Boolean Algebra
are:
are:
1.
C
o
m
p
l
e
m
e
n
t
a
t
i
o
n
(
-
ـ
ـ
ـ
ـ
ـ
ـ
ـ
ـ
,
¬
)
.
2.
Boolean sum (
+
;
OR,
V
).
3.
Boolean product(
.
;
AND,
Λ
).
•
Where (
¬, V
,
Λ
) are the
Logical Operations.
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
2
The Operations In Boolean Algebra
1.
T
h
e
c
o
m
p
l
e
m
e
n
t
a
t
i
o
n
o
f
a
n
e
l
e
m
e
n
t
,
d
e
n
o
t
e
d
w
i
t
h
a
b
a
r
“
-
ـ
ـ
ـ
ـ
ـ
ـ
ـ
ـ
”
i
s
d
e
f
i
n
e
d
b
y
:
2.
The sum
(
+
;
OR
):
1+1=1; 1+0=1; 0+1=1; 0+0=0.
3. Boolean product
(
.
;
AND
).
1.1=1, 1.0=0, 0.1=0, 0.0=0
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
3
Example1:
Find the value of
Solution:
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
4
Translation into a Logical Equivalence
Translation into a Logical Equivalence
•
0 ≡ F,
•
1 ≡ T ,
•
. ≡
Λ
,
•
+ ≡ V,
•
ــــــــ
≡ ¬
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
5
Example 2:
Solution:
•
0 ≡ F,
•
1 ≡ T ,
•
. ≡
Λ
,
•
+ ≡ V,
•
ــــــــ
≡ ¬
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
6
Example 3:
Solution:
•
0 ≡ F,
•
1 ≡ T ,
•
. ≡
Λ
,
•
+ ≡ V,
•
ــــــــ
≡ ¬
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
7
Boolean Expressions and Boolean
Boolean Expressions and Boolean
Functions
Functions
Let B= {0,1} . Then Bn
={(x1
, x
2
, • • • , x
n
)/x
i
ϵ
B for
1 ≤ i ≤n} is the set of all possible n -tuples of
Os and 1s. The variable x is called a Boolean
variable if it assumes values only from B , that
is, if its only possible values are 0 and 1 . A
function from B
n
to B is called a
Boolean
function of degree n
.
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
8
EXAMPLE 4
The function
from the set of ordered
pairs of Boolean
variables to the set {0,1}is a
Boolean function of
degree 2
with
F ( 1,1)=0, F (1,0) = 1 , F
(0,1) = 0, and F(0, 0) = 0.
We display these values of
F in Table 1 .
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
9
Boolean Expressions
Boolean Expressions
Boolean functions can be represented using
expressions made up from variables and
Boolean operations (., +,
ــــــــ
).
The Boolean expressions in the variables x
1
, x
2
,
• • • , x
n
are defined recursively as
•
0, 1 , x
1
, x
2
, • • • , x
n
are Boolean expressions;
•
if E
1
and E
2
are Boolean expressions, then ,
(E
1
.E
2
), and (E
1
+E
2
) are Boolean expressions.
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
10
10
EXAMPLE 5
Find the values of the Boolean function
represented by
Solution:
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
11
11
E
E
q
q
u
u
a
a
l
l
i
i
t
t
y
y
o
o
f
f
B
B
o
o
o
o
l
l
e
e
a
a
n
n
F
F
u
u
n
n
c
c
t
t
i
i
o
o
s
s
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
12
12
Identities of
Identities of
Boolean
Boolean
Algebra
Algebra
EXAMPLE 8
Show that the distributive law
x(y+z)=xy+xz
is valid.
Solution:
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
13
13
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
14
14
EXAMPLE 9
Translate the distributive
law
x+yz=(x+y)(x+z)
in
Table 5 into a logical
equivalence.
Solution:
Put
x
≡p, y≡q, & z≡r, and use
the translation of
Boolean operations
This transforms the
Boolean identity into
the logical equivalence
pV(q
Λ
r)≡(pVq)
Λ
(p Vr).
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
15
15
Duality
Duality
•
The dual of a Boolean expression is obtained by
interchanging Boolean sums and Boolean
products and interchanging Os and 1 s.
•
Duality of a Boolean function
F
is denoted by
F
d
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
16
16
EXAMPLE 11
Solution:
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
17
17
Duality Principle
Duality Principle
An identity between functions represented
by Boolean expressions remains valid when the
duals of both sides of the identity are taken.
This result, called
the duality principle
, is useful
for obtaining new identities.
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
18
18
EXAMPLE 12
Construct an identity from the
absorption law x(x+y)=x
by taking
duals
.
Solution:
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
19
19
Homework
Homework
Page 756
•
1(a),
•
4(a,b),
•
5(a),
•
11,
•
28(a,d).
L
A
l
-
z
a
i
d
M
a
t
h
1
1
0
1
20
20
Delve into the world of Boolean Algebra, where we manipulate binary values to model logical operations like complementation, summation, and product. Learn how Boolean functions are defined and represented, along with practical examples and logical equivalences. Discover the essence of Boolean expressions, functions, and their applications in problem-solving.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Boolean Algebra 1 L Al-zaid Math1101
Boolean Functions In Boolean algebra we work with the set {0,1}, where: 0 F (False) & 1 T (True). The 3 Operations used in Boolean Algebra are: 1. Complementation ( - , ). 2. Boolean sum (+; OR, V). 3. Boolean product(. ; AND, ). Where ( , V, ) are the Logical Operations. 2 L Al-zaid Math1101
The Operations In Boolean Algebra 1. The complementation of an element, denoted with a bar - is defined by: 2. The sum (+; OR): 1+1=1; 1+0=1; 0+1=1; 0+0=0. 3. Boolean product(. ; AND). 1.1=1, 1.0=0, 0.1=0, 0.0=0 3 L Al-zaid Math1101
Example1: Find the value of Solution: 4 L Al-zaid Math1101
Translation into a Logical Equivalence 0 F, 1 T , . , + V, 5 L Al-zaid Math1101
Example 2: Solution: 0 F, 1 T , . , + V, 6 L Al-zaid Math1101
Example 3: 0 F, 1 T , . , + V, Solution: 7 L Al-zaid Math1101
Boolean Expressions and Boolean Functions Let B= {0,1} . Then Bn={(x1, x2, , xn)/xi B for 1 i n} is the set of all possible n -tuples of Os and 1s. The variable x is called a Boolean variable if it assumes values only from B , that is, if its only possible values are 0 and 1 . A function from Bnto B is called a Boolean function of degree n. 8 L Al-zaid Math1101
EXAMPLE 4 The function from the set of ordered pairs of Boolean variables to the set {0,1} is a Boolean function of degree 2 with F ( 1,1)=0, F (1,0) = 1 , F (0,1) = 0, and F(0, 0) = 0. We display these values of F in Table 1 . 0 F, 1 T , . , + V, 9 L Al-zaid Math1101
Boolean Expressions Boolean functions can be represented using expressions made up from variables and Boolean operations (., +, ). The Boolean expressions in the variables x1, x2, , xnare defined recursively as 0, 1 , x1, x2, , xnare Boolean expressions; if E1and E2are Boolean expressions, then , (E1.E2), and (E1+E2) are Boolean expressions. 10 L Al-zaid Math1101
EXAMPLE 5 Find the values of the Boolean function represented by Solution: 11 L Al-zaid Math1101
Equality of Boolean Functios 12 L Al-zaid Math1101
Identities of Boolean Algebra EXAMPLE 8 Show that the distributive law x(y+z)=xy+xz is valid. Solution: 13 L Al-zaid Math1101
14 L Al-zaid Math1101
EXAMPLE 9 Translate the distributive law x+yz=(x+y)(x+z) in Table 5 into a logical equivalence. Solution: Put x p, y q, & z r, and use the translation of Boolean operations This transforms the Boolean identity into the logical equivalence pV(q r) (pVq) (p Vr). 0 F, 1 T , . , + V, 15 L Al-zaid Math1101
Duality The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean products and interchanging Os and 1 s. Duality of a Boolean function F is denoted by Fd 16 L Al-zaid Math1101
EXAMPLE 11 Solution: 17 L Al-zaid Math1101
Duality Principle An identity between functions represented by Boolean expressions remains valid when the duals of both sides of the identity are taken. This result, called the duality principle, is useful for obtaining new identities. 18 L Al-zaid Math1101
EXAMPLE 12 Construct an identity from the absorption law x(x+y)=x by taking duals. Solution: 19 L Al-zaid Math1101
Homework Page 756 1(a), 4(a,b), 5(a), 11, 28(a,d). 20 L Al-zaid Math1101
