Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Logic values
|
|
| x=0 |
| States of a switches determines the values of x, y and z |
| ∩ |
| y=0 |
| Lamp z = 0 |
Electronic circuit:
| Voltage levels represent logic values 0 and 1 |
3, 5 v =1 logic
| OR |
y
0, 5 v = 0 logic
| AND |
|
| x | y | x ˄ y |
| x=0 |
| y=1 |
| Lamp z = 0 (no light) |
|
x
| x | 
|
| x=1 |
A Boolean function f(x, y, z) = 
can be implemented by a logic circuit so:
| OR |
| AND |
| AND |
z
| OR |
| AND |
The above logic circuit is not the best for this function:
- It contains too many gates (9);
- There are 5 gates in a sequence (too many delays of a signal propagation from input to output)
We simplify the formula into a Sum-of-Products Form:
| AND |
((
) 
x
y
| AND |
| OR |
| AND |
| AND |
| Now: -The circuit contains 8 gates (cheaper). -There are less gates (3) connected (circuits is faster) |
There are different methods to simplify formulas into a SPF(Sum-of-Products Form) or PSF (Product-of- Sums Form) with the minimal number of variables.
One of them is based on Karnaugh maps.
Definition: A Karnaugh map is the truth table of a Boolean function presented as a matrix. The sets of variable values follow in a circular order.
| circular order: each set differs from its previous in one position |
| y 0 1 |
| x | y | f5(x, y) |
| x |
Karnaugh
f5(x, y)= 
|
neighboring squares are united in one rectangle
(i = 0, 1, 2, …)
| yz
0 0 |
| x | y | z | f(x, y, z) |
| x |
map
 neighboring squares are united in one rectangle
|
y
f’(x, y, z) = 
Note: we unite 
neighboring squares with unities are united into one rectangle of the largest possible size.
Note: coordinates of two2 neighboring squares differ in one position
Given function f" (x, y, z, t) 
x· 
| X | Y | Z | T | f''(x, y, z, t) |
| zt 00 01 11 10 10 |
| xy 00 01 11 10 |
The rule for writing a conjunctive term that represents squares with 1s in one rectangle in a Karnaugh map.
1.Move along the sides of the rectangle.
2. A variable that changes its value while moving along one side is not included into the conjunctive term.
3. A variable (say, x) that keeps its value 1 unchangeable is included in the term without negation (as x).
4. A variable (x) that keeps its value 0 unchangeable is included in the term with negation (as 
).
H/a. Simplify the above given functions f5 (x, y), f'(x, y, z), f''(x, y, z) by transforming them into CSPF and applying the laws of Boolean algebra.
H/a. Think how to write a simplified formula base on zeroes in a Karnaugh map.
Example of finding of a minimal product of sums (Minimal conjunctive normal form)
| zt 00 01 11 10 10 |
| a |
xy
| a |
| a |
b
MCNF
H/a. Given a Karnaugh map.
- Find Min DNF and make a diagram of a logic circuit
- Find Min CNF and make a diagram of a logic circuit
| OR |
| and |
| xy |
| zt |
F(x, y, z, t)