Class notes engineering

1.9 BINARY LOGIC

Binary logic deals with variables that take on two discrete values and with operations that assume logical
meaning. The two values the variables assume may be called by different names (true and false, yes and
no, etc.), but for our purpose, it is convenient to think in terms of bits and assign the values 1 and 0



Definition of Binary Logic

Binary logic consists of binary variables and a set of logical operations. The variables are designated by
letters of the alphabet, such as A, B, C, x, y, z, etc., with each variable having two and only two distinct
possible values: 1 and 0. There are three basic logical operations: AND, OR, and NOT. Each operation
produces a binary result, denoted by z.
1. AND: This operation is represented by a dot or by the absence of an operator. For example, x⋅y=z or
xy=z is read “x AND y is equal to z.” The logical operation AND is interpreted to mean that z=1 if and
only if x=1 and y=1; otherwise z=0. The result of the operation x⋅y is z.
2. OR: This operation is represented by a plus sign. For example, x+y=z is read “x OR y is equal to z,”
meaning that z=1 if x=1 or if y=1 or if both x=1 and y=1. If both x=0 and y=0, then z=0.
3. NOT: This operation is represented by a prime (sometimes by an overbar). For example, x′=z (or x¯=z)
is read “not x is equal to z,” meaning that z is what x is not. In other words, if x=1, then z=0, but if x=0,
then z=1. The NOT operation is also referred to as the complement operation, since it changes a 1 to
0 and a 0 to 1, that is, the result of complementing 1 is 0, and vice versa.

For each combination of the values of x and y, there is a value of z specified by the definition of the logical
operation. Definitions of logical operations may be listed in a compact form called truth tables. A truth
table is a table of all possible combinations of the variables, showing the relation between the values that
the variables may take and the result of the operation.

Truth Tables of Logical Operations

AND OR NOT
X Y X.Y X Y X+Y X X’
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1


Logic Gates

Logic gates are electronic circuits that operate on one or more physical input signals to produce an output
signal. Electrical signals such as voltages or currents exist as analog signals having values over a given
continuous range, say, 0–3 V, but in a digital system these voltages are interpreted to be either of two
recognizable values, 0 or 1.

,FIG. Signal levels for binary logic values




FIG Symbols for digital logic circuits




AND and OR gates may have more than two inputs. An AND gate with three inputs and an OR gate with
four inputs are shown in Fig.

,2.4 BASIC THEOREMS AND PROPERTIES OF BOOLEAN ALGEBRA
Duality: Duality theorem states that the dual of the Boolean function can be easily obtained by
interchanging the logical AND operator with the logical OR operator and the zeros with ones and
vice versa.
AND OR 10
OR AND
01
Example
(A+B)C+D’
(A+B). (C+0)+D’
Applying Duality Principle
(A.B)+(C.1).D’
=AB+CD’

Basic Theorems
Table below lists six theorems of Boolean algebra and four of its postulates. The theorems and postulates
listed are the most basic relationships in Boolean algebra. The theorems, like the postulates, are listed in
pairs; each relation is the dual of the one paired with it.

Postulate Vs Theorem
Postulate (axiom) : A statement that is accepted as TRUE without proof.
Theorem: An important statement that must be proved before it can be accepted.

Postulates and Theorems of Boolean Algebra
Postulate 2 (a) x + 0 = x (b) x ⋅ 1 = x
Postulate 5 (a) x + x ′ = 1 (b) x ⋅ x ′ = 0
Theorem 1 (a) x + x = x (b) x ⋅ x = x
Theorem 2 (a) x + 1 = 1 (b) x ⋅ 0 = 0
Theorem 3, involution (x′)′=x
Postulate 3, commutative (a) x + y = y + x (b) x y = y x
Theorem 4, associative (a) x + ( y + z ) = ( x + y ) + z (b) x ( y z ) = ( x y ) z
Postulate 4, distributive (a) x ( y + z ) = x y + x z (b) x + y z = ( x + y ) ( x + z )

, Theorem 5, DeMorgan (a) ( x + y ) ′ = x ′ y ′ (b) ( x y ) ′ = x ′ + y ′
Theorem 6, absorption (a) x + x y = x (b) x ( x + y ) = x

THEOREM 1(a): x + x = x
Statement Justification
x+x=(x+x)⋅1 postulate 2(b)
=(x+x)(x+x′) 5(a)
=x+xx′ 4(b)
=x+0 5(b)
=x 2(a)

THEOREM 1(b): x ⋅ x = x
Statement Justification
x⋅x=xx+0 postulate 2(a)
=xx+xx′ 5(b)
=x(x+x′) 4(a)
=x⋅1 5(a)
=x 2(b)

Note that theorem 1(b) is the dual of theorem 1(a) and that each step of the proof in part (b) is the dual
of its counterpart in part (a). Any dual theorem can be similarly derived from the proof of its corresponding
theorem.

THEOREM 2(a): x + 1 = 1.
Statement Justification
x+1=1⋅(x+1) postulate 2(b)
=(x+x′)(x+1) 5(a)
=x+x′⋅1 4(b)
=x+x′ 2(b)
=1 5(a)

THEOREM 2(b): x ⋅ 0 = 0 by duality.

THEOREM 3: ( x ′ ) ′ = x . From postulate 5, we have x + x ′ = 1 and x ⋅ x ′ = 0 , which together define the
complement of x. The complement of x ′ is x and is also ( x ′ ) ′ . Therefore, since the complement is unique,
we have ( x ′ ) ′ = x . The theorems involving two or three variables may be proven algebraically from the
postulates and the theorems that have already been proven. Take, for example, the absorption theorem:

THEOREM 6(a): x + x y = x .
Statement Justification
x+xy=x⋅1+xy postulate 2(b)
=x(1+y) 4(a)
=x(y+1) 3(a)
= x ⋅ 1 theorem 2(a)