Boolean functions and expressions

Boolean functions and expressions

We consider Boolean functions and expressions. Circuits realizing boolean functions are the hardware basis
of modern computers. The next segment of the course introduces the ideas of computer hardware and
architecture.
Boolean functions
Boolean values in Scheme are #t and #f for true and false. In hardware, it is customary to use 1 for true
and 0 for false, so we will shift to that convention for this topic. A Boolean function is a function that takes
some fixed number of arguments, each of which may be 0 or 1, and returns a 0 or a 1 as its value.
For concreteness, we consider Boolean functions of two arguments. The domain of such a function is all
ordered pairs in which each element is either 0 or 1. Listed as a set, the domain is

{(0, 0), (0, 1), (1, 0), (1, 1)}.

We will display Boolean functions in truth tables giving every domain element and the value of the function
for that domain element. We’ll use (x * y) to denote the “and” function, true when both of its arguments
are true, and false otherwise. Its truth table is as follows.

x y | (x * y)
---------------
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1

The “or” function, true when either or both of its arguments are true will be denoted (x + y), and has the
following truth table.

x y | (x + y)
---------------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

We’ll use the notation x’ for the “not” function, which has only one argument and is true when that argument
is false and false when that argument is true. Its truth table is as follows.

x | x’
---------------
0 | 1
1 | 0

Note that this truth table has only two lines because it displays the values of a function with only one
argument. Here is another truth table

x y | (x XOR y)
---------------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

This function is the “exclusive or”, which is true when exactly one of its two arguments is true and the other
is false. Note that it differs from (x + y) when both x and y are 1.
How many two-argument Boolean functions are there? If we consider the possible tables of values, we
have:

x y | (x OP y)
---------------
0 0 | ?
0 1 | ?
1 0 | ?
1 1 | ?

Boolean expressions
We may combine constants, variables, and operators to get more complicated Boolean expressions. 

Our definition of Boolean expressions is inductive.
1. 0 and 1 are Boolean expressions
2. Variables x, y, z, x1, y1, z1, . . . are Boolean expressions
3. If E is a Boolean expression, then (E)0
is a Boolean expression, the negation of E.
4. If E1 and E2 are Boolean expressions, then (E1 · E2) is a Boolean expression, the conjunction of E1
and E2.
5. If E1 and E2 are Boolean expressions, then (E1 + E2) is a Boolean expression, the disjunction of E1
and E2.

Logic Gates

What are logic gates?

logic gate (AND, OR, XOR, NOT, NAND, NOR, and XNOR)

A logic gate is an elementary building block of a digital circuit. Most logic gates have two inputs and one output. At any given moment, every terminal is in one of the two binary conditions low (0) or high (1), represented by different voltage levels. The logic state of a terminal can, and generally does, change often, as the circuit processes data. In most logic gates, the low state is approximately zero volts (0 V), while the high state is approximately five volts positive (+5 V).

There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and XNOR.

The AND gate is so named because, if 0 is called "false" and 1 is called "true," the gate acts in the same way as the logical "and" operator. The following illustration and table show the circuit symbol and logic combinations for an AND gate. (In the symbol, the input terminals are at left and the output terminal is at right.) The output is "true" when both inputs are "true." Otherwise, the output is "false."
 

AND gate

Input 1	Input 2	Output
	1
1
1	1	1

The OR gate gets its name from the fact that it behaves after the fashion of the logical inclusive "or." The output is "true" if either or both of the inputs are "true." If both inputs are "false," then the output is "false."

OR gate

Input 1	Input 2	Output
	1	1
1		1
1	1	1

The XOR ( exclusive-OR ) gate acts in the same way as the logical "either/or." The output is "true" if either, but not both, of the inputs are "true." The output is "false" if both inputs are "false" or if both inputs are "true." Another way of looking at this circuit is to observe that the output is 1 if the inputs are different, but 0 if the inputs are the same.

XOR gate

Input 1	Input 2	Output
	1	1
1		1
1	1

A logical inverter , sometimes called a NOT gate to differentiate it from other types of electronic inverter devices, has only one input. It reverses the logic state.

Inverter or NOT gate 

Input	Output
1
	1

The NAND gate operates as an AND gate followed by a NOT gate. It acts in the manner of the logical operation "and" followed by negation. The output is "false" if both inputs are "true." Otherwise, the output is "true."

NAND gate

Input 1	Input 2	Output
		1
	1	1
1		1
1	1

The NOR gate is a combination OR gate followed by an inverter. Its output is "true" if both inputs are "false." Otherwise, the output is "false."

NOR gate

Input 1	Input 2	Output
		1
	1
1
1	1

The XNOR (exclusive-NOR) gate is a combination XOR gate followed by an inverter. Its output is "true" if the inputs are the same, and"false" if the inputs are different.

XNOR gate

Input 1	Input 2	Output
		1
	1
1
1	1	1

Using combinations of logic gates, complex operations can be performed. In theory, there is no limit to the number of gates that can be arrayed together in a single device. But in practice, there is a limit to the number of gates that can be packed into a given physical space. Arrays of logic gates are found in digital integrated circuits (ICs). As IC technology advances, the required physical volume for each individual logic gate decreases and digital devices of the same or smaller size become capable of performing ever-more-complicated operations at ever-increasing speeds.

 

 

MCA 1st Year Semester I

1  MCA-101  Computer Architecture

Combinational Digital  Circuits: 

Gates,  

Boolean  Functions  and  Expressions, 

Designing Gate Networks,  

Useful  Combinational  Parts,  

Programmable  Combinational  Parts,  

Timing  and Control,  

Latches,  

Flip-Flops  and  Registers,  

Sequential  Circuits,  

Useful  Sequential  Parts,
Programmable Sequential Parts, 

Clocks and Timing of Events.

Computer  System  Technology:  

Components  to  Applications,  

Computer  Systems  and  their Parts,  

Generations,  

Processor  and  Memory  Technologies,  

Peripherals  I/O  and Communications, 

Software Systems and Applications.
Instruction and addressing,  

instruction  formats,  

types,  

addressing modes. 

Assembly Language Programs,  

Assembler  Directives,  

Pseudo  Instructions,  

Macroinstructions,  

Linking  and Loading,

8085 Instruction Set.

Arithmetic/Logic  Unit:  

Number  Representation,  

Arithmetic  Operations, 

Floating-Point Arithmetic.

Memory System Design: 

Main Memory Concepts, 

Cache Memory Organization, 

Mass Memory Concepts, 

Virtual Memory and Paging.
Input/Output  and  Interfacing,  

Input/Output  Devices,  

Input/Output  Programming,
Interrupts. 
Vector And Array Processing, 

Shared-Memory, 

Multiprocessing,

Distributed Multi Computing. 
Programming in 8085 Microprocessor.