- •Оглавление
- •1. Информация, ее представление и измерение
- •2. Общая характеристика процессов сбора, передачи и обработки информации
- •2.1. Системы счисления и действия в них
- •2.2. Общая характеристика процессов передачи информации
- •2.3. Кодирование и шифрование информации
- •2.4. Компьютерные вирусы
- •3. Модели решения функциональных и вычислительных задач
- •3.1. Модели и моделирование
- •3.2. Основные свойства модели и моделирования
- •Моделирование – есть метод системного анализа.
- •3.3. Классификация видов моделирования
- •3.4. Компьютерное моделирование
- •3.5. Функции алгебры логики
- •Коммутативность
- •Ассоциативность
- •Дистрибутивность
- •3.6. Булева алгебра. Функциональная полнота
- •3.7. Минимизация функций алгебры логики
- •4. Программные средства реализации информационных процессов
- •5. Технические средства реализации информационных процессов
- •6. Алгоритмизация и программирование
Коммутативность
x1 & x2 = x2 & x1.
x1 v x2 = x2 v x1.
Ассоциативность
x1 v (x2 v x3) = (x1 v x2) v x3.
x1 & (x2 & x3) = (x1 & x2) & x3.
Дистрибутивность
x1 & (x2 v x3) = (x1 & x2) v ( x1 & x3 ).
x1 v (x2 & x3) = (x1 v x2) & ( x1 v x3 ).
Отметим также важные соотношения:
X v X = X, X & X = X, X v 1 = 1, X & 1 = X,
X v 0 = X, X & 0 = 0, X v ØX = 1, X & ØX = 0.
Положим x a = { X , если a = 1; ØX , если a = 0 } .
Утверждение. Любая функция алгебры логики кроме 0 может быть представлена в форме
f(x 1...xn) = Ú x1 a & x2 a... & xn a (3.1)
При этом дизъюнкция в правой части берется только по тем наборам аргументов, на которых функция, заданная таблично, обращается в 1.
Определение. Представление функции алгебры логики в виде (3.1) называется ДСНФ - дизъюнктивной совершенной нормальной формой.
Для построения ДСНФ необходимо выполнить следующие шаги:
выбрать в таблице истинности заданной функции все наборы аргументов, на которых функция равна 1;
выписать соответствующие этим наборам конъюнкции, при этом, если аргумент xi входит в данный набор как 1, то он записывается без изменений, если же как 0 , то берется ;
все полученные конъюнкции объединяются под знаком дизъюнкции.
3.6. Булева алгебра. Функциональная полнота
Определение. Алгеброй над множеством логических функций с двумя бинарными операциями, обозначаемыми как логическое умножение & и логическое сложение v и одной унарной операцией ( отрицанием )
называется булевой алгеброй. Будем обозначать ее символом SB.
Рассмотрим свойства булевой алгебры.
Замкнутость
для " A и B Î SB
A v B Î SB
A & B Î SB
Коммутативность
A & B = B & A
A v B = B v A
3. Ассоциативность
A v ( B v C) = (A v B) v C
Дистрибутивность
A & ( B v C) = (A & B) v (A & C)
A v ( B & C) = (A v B) & (A v C)
Идемпотентность
A v A = A & A = A.
Булева алгебра содержит элементы 0,1 , такие что для всякого
элемента A Î SB справедливо:
A v 0 = A, A v 1 = 1
A & 0 = 0, A & 1 = A.
7. Для каждого элемента A Î SB существует элемент , такой что
A v =1
A & =0.
8. Закон поглощения
A & (A v B) = A v A & B = A.
9. Закон Де Моргана
3.7. Минимизация функций алгебры логики
Введем понятие конечного автомата, как некоторой абстрактной системы, характеризующейся конечным числом состояний. Работа такого автомата напрямую связана с реализацией соответствующей ему логической функции в виде схемы или программы и поступающими из вне данными в каждый такт времени. На основе теории конечных автоматов организуется работа управляющих программ ЭВМ.
Работа конечного автомата может быть полностью описана с помощью следующей системы функций алгебры логики [7]:
y1= f1 (x1 ... xn )
y2= f2 (x1 ... xn )
...
ym= fm (x1 ... xn )
Здесь Pi = ( X1, X2, ...,Xn ); Qj = ( y1, y2, ...,ym ) - соответственно входное и выходное слово. Работа автомата может быть задана либо в виде конечных таблиц, либо в виде аналитической записи функций fi .
Проблема полноты системы функций эквивалентна проблеме выбора стандартного набора элементов, из которого будет строиться автомат, при этом все функции fi должны быть выражены через базисные функции. Уменьшение числа функций в базисе приводит к уменьшению стандартных элементов, на которых строится схема, однако, при этом увеличивается общее число элементов схемы. Возникает задача о “простейшем” представлении логических функций через систему базисных функций. Для этого используют методы минимизации:
- метод вынесения за скобки;
- метод неопределенных коэффициентов;
- метод с использованием карт Карно;
- метод Мак - Класки;
- метод Блэка.
Рассмотрим метод минимизации совершенной дизъюнктивной нормальной формы (СДНФ) с помощью карт Карно. Карта Карно - это диаграмма, состоящая из 2n квадратов, где n - число переменных. Клетка карты - одна из возможных конъюнкций, входящих в СДНФ. Минимизация на основе карт Карно осуществляется путем локализации на карте прямоугольных областей из числа клеток кратного 2.
Для работы с картой необходимо по таблице истинности составить СДНФ, затем для каждой элементарной конъюнкции проставить 1 в соответствующие клетки карты. Затем единицы объединяются таким образом, чтобы минимизировалось число логических сложений, умножений или отрицаний, что важно для экономного конструирования ЭВМ.
Рассмотрим карты Карно.
Для двух переменных: Для трех переменных:
a a
c
b
b
Для четырех переменных:
a
c
c d
d
b
Пример. Для логической функции заданной таблицей
-
x1
x2
x3
f
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
построить карту Карно и на ее основе минимизировать функцию.
Решение. Построим карту согласно описанным выше правилам.
x1
1 1 f = x1 v x2 & x3
x2 1 1 1
x3
Рассмотрим пример представления простейшей функции картой Карно
a
c 1 1
c 1 1 d
f = b
1 1 d
1 1
b
Рассмотрим построение логической схемы для функции вида:
f1 = V2 & V4 v V3 & ØV1 & ØV2 v ØV3 & ØV4 & V1.
V 1
V 2
V 3
V 4
& & & & &
& &
&
&
1
1
f1