Logic Circuits for IT Systems

• Module focuses on IT Systems (IT)
• Bachelor Programme AAI
• Lecture 02 covers Logic Circuits
• Prof. Dr. Marcel Tilly from the Faculty of Computer Science, Cloud Computing, teaches the module

Session Agenda

• Topics that will be covered include:
• Boolean algebra
• Boolean functions
• Truth tables
• Switching functions
• Logic gates
• Half and full adders

Objectives

• Intended learning outcomes:
• Understand Boolean algebra
• Calculate logical circuits
• Determine a Boolean function for a given logic circuit

Historical Context

• Past calculating machines include:
• Pascaline: For addition and subtraction
• Leibnitzrechenmaschine: For addition, subtraction, division, and multiplication
• ENIAC: For addition, subtraction, division, multiplication, and calculating square roots
• Addresses how computers perform calculations

Initial Setup

• Computer electronics operate digitally
• Digital system works with two voltage levels
• Digital Electronics work with two voltage levels
• Computers use '0' and '1' for transmitting data
• Binary system fulfills abstract digital electronic requirements
• '0' and '1' are inverse values of each other

Boolean Algebra

• Boolean algebra underlies bit-level information processing
• Origin: George Boole (1815-1864)
• Purpose: determine true or false statements
• Operates on two truth values: true and false
• Boolean algebra is related to logic
• Two states (false and true) in binary can be represented as 0 and 1

Electronics Application

• Boolean algebra applied to digital electronics is called switching algebra
• T (True), H (High), 1 (Bit set)
• F (False), L (Low), 0 (Bit not set)

Logic Operations

• Deals with links between truth values via logical operators
• Results are truth values
• Basic operations include:
• Negation (not a)
• Conjunction (a and b)
• Disjunction (a or b)
• Implication (if a then b)
• Equivalence (an exactly if b)

Boolean Algebra - Formal Definition

• Algebra is values, operations on values, and laws of computation
• Boolean algebra is based on binary set {0, 1} and operations v, ∧, and ¬
• Operations contains an operator that specifies the performed activity and the operands involved.
• Operations include:
• One-place operator ¬ (negation) with one operand a
• Two-digit operators ^ and ∨ with two operands a and b

Boolean Algebra Laws

• Laws of arithmetic that apply:
• Commutative law
• Associative law
• Distributive law
• Absorption law
• Neutral element
• Inverse element

Truth Functions

• Boolean function is a function f: Bⁿ -> B
• Boolean function is called an n-digit Boolean function
• There are 2^(2^n) n digit functions
• Combining arguments with the results will give n-digit function and is equal to 2^2 = 4
• Boolean functions with two-digits include
• constant 0, conjunction (AND), negation of implication, identity a, negation of implication, identity b, antivalence (XOR), disjunction (OR), non-or (NOR), equivalence, negation of b, implication, negation of a, implication, Not-And (NAND) and constant 1

Task 1

• Combining conjunction, disjunction, and negation can express all possible one- and two-digit logical operations

Laws of Boolean Algebra

• Rules for logical operation calculations are based on the definition of Boolean algebra
• Involutive ;aw, merge rules, De Morgan's laws, Idempotence law

Boolean Function

• Previous functions had 1-2 inputs and one output
• Current functions have n inputs and 1 output
• Boolean function assigns a binary output variable y ton binary input variables x1, ...,xn.
• Function is expressed as: y = f(x₁, x2, ..., xₙ) with y ∈ {0, 1} and xᵢ ∈ {0, 1}

Truth Tables

• Boolean functions are expressed by truth tables

Boolean Normal Form

• Can construct a Boolean expression from a truth table of a Boolean function using Boolean normal form theorem
• Switching functions are expressed only by the 3 base operators (¬,٧,٨)

Normal Forms

• Truth table is a unique way to define a boolean function.
• Multiple realizations exist using logic gates or descriptions in the form of a Boolean expression
• Normal forms, also known as canonical forms offer a standard representation for a Boolean expression in algebraic form

Minterm

• Given a Boolean function y = f(xₙ, ..., x₁, x₀) and the literals xᵢ
• The minterm evaluates to 1 for exactly one particular configuration of the variable xᵢ and 0 otherwise
• More precisely, the minterm evaluates to 1 if for all negated variables xᵢ = 0 and all non-negated variables xᵢ = 1
• Example of a minterm: y = ¬x₂ ∧ x₁ ∧ x₀

Maxterm

• Maxterm will evaluate to 0 if all negative values are 1 and non-negated are 0
• With the Boolean function y equals f to the power of xn etc and literals xi if the maximum evaluates to 1 for the particle configuration variable xi 0 otherwise
• Maxterm will evaluate to 0 if all negative values are 1 and non-negated are 0
• An example equation is y = ¬x2 ∨ ¬x1 ∨ x0

Disjunctive Normal Form

• A disjunctive normal form (DNF) is an OR operation v of minterms
• all configurations of minterms in which y = f(xn,..., x1, x0) = 1 must occur
• All literals are connected by conjunctions ^ ("and")
• An example equation is f(a,b,c)=(a^b^c)v(-a^b^c)v(a^-b^c)v

Value Table

• Each line represents full conjunction
• Function value "0" does not contribute

Conjunctive Normal Form

• A conjunctive normal form (CNF) is an AND-connection of maxterms
• All configurations of maxterms in which y = f(xn, ..., x₁, x₀) = 0 must occur
• Steps with value table will need form full conjunction for rows with function value 0

Example

• Disjunction and conjunction may be used

Shannon’s Theorem

• The negation of a logical formula composed only of the three basic operations (¬,∨,∧), variable names (a,b,..), and constants (0, 1) is obtained by replacing all variables and constants with their complement (1 → 0, 0 → 1, x → ¬x) and interchanging the operations ∧ and ∨.
• It is important to note that one must completely parenthesize before substitution and interchange, and the parentheses are preserved.
• The theorem is valid

Switching Functions

• Switch functions assign binary sequence

Logical Gates

• Switching networks and switching functions are made from logical gates
• Common logic gates are: Inverter, 2 Input OR-Gate ,2 Input AND-Gate 2 Input NOR-Gate 2 Input NAND-Gate, 2 Input XOR-Gate

Logical Gates - Example

• Switching functions and networks are composed of logical gates

Truth Table to Boolean Expression

• Switching functions or networks are obtained with represent desired behavior by using a truth table

Simplification Networks

• Distributive Law

Decoder

• Decoder has n-inputs and 2^n = m outputs
• Exactly one output is true for each input combination
• From binary coded decimal to decimal

Encoder

• Converts one active input to code binary
• Could look like an encoder and will have all one's out
• Inverts function

Half Adder

• Network which adds 2 single-dual numbers single-digit dual numbers
• The half adder (HA) is a switching network that adds two single-digit dual numbers without considering previous carries (carry) and returns the sum (S) and possibly a carry (C).
• The resulting carry is generated separately.
• This can be shown with a half-adder truth table

Full Adder

• The full adder differs from the half adder in that the previous carry is taken into account.
• Can be shown with a full adder truth table

Full Adder Usage

• Using the help of the full adder two n-digit dual numbers can be added to the computer.
• uses a chain of n full adders. - At the first addition (i=0) the incoming carry (c_ 1) is set to 0
• There are other calculations that are also realized with the full adder