- •1. Системы счисления и действия в них
- •2. Пространство сообщений. Коды обнаружения и исправления ошибок
- •3. Шифрование методом замены
- •7. Основные функции алгебры логики
- •Коммутативность
- •Ассоциативность
- •Дистрибутивность
- •8. Минимизация функций алгебры логики
- •Операторные и бинарные программы.
- •12. Булева алгебра. Функциональная полнота
- •Свойства алгебры Жегалкина
- •1. Коммутативность
- •2. Дистрибутивность
- •3. Идемпотентность
- •13. Информатика. Информация. Алфавит.
- •14. Основные свойства информации.
- •15. Мера информации.
- •16. Методы получения информации.
- •18. Шифрование методами перестановки
Коммутативность
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 = { X , если = 1; X , если = 0 } .
Утверждение. Любая функция алгебры логики кроме 0 может быть представлена в форме
f(x 1...xn) = x1 & x2 ... & xn (5.1)
При этом дизъюнкция в правой части берется только по тем наборам аргументов, на которых функция, заданная таблично, обращается в 1.
Определение. Представление функции алгебры логики в виде (5.1) называется ДСНФ - дизъюнктивной совершенной нормальной формой.
Для построения ДСНФ необходимо выполнить следующие шаги:
выбрать в таблице истинности заданной функции все наборы аргументов, на которых функция равна 1;
выписать соответствующие этим наборам конъюнкции, при этом, если аргумент xi входит в данный набор как 1, то он записывается без изменений, если же как 0 , то берется ;
все полученные конъюнкции объединяются под знаком дизъюнкции.
Утверждение. Любая функция алгебры логики кроме 1 может быть представлена в форме:
f ( x1, x2,...,xn ) = & (x1 v x2 v ... v xn ). ( 5. 2 )
Конъюнкция берется только по тем наборам , на которых функция
равна 0.
Определение. Представление функции алгебры логики в виде
формы (1. 2) называется СКНФ - совершенной конъюнктивной нормальной формой. Для ее получения используют следующие действия:
выбрать в таблице истинности заданной функции все наборы аргументов, на которых функция равна 0;
выписать дизъюнкции, соответствующие этим наборам аргументов , учитывая ;
все полученные дизъюнкции соединить под знаком конъюнкции.
8. Минимизация функций алгебры логики
Работа автомата может быть полностью описана с помощью следующей системы функций алгебры логики [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