Computer organization refers to the structure and behavior of a computer system, particularly how its components are interconnected and interact. It focuses on implementation details, delving into the physical structure of hardware and the control flow of instructions within the CPU.
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 10
OR AND
01
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 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)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller amartyabs186. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.39. You're not tied to anything after your purchase.
