- •Оглавление
- •1. Информация, ее представление и измерение
- •2. Системы счисления и действия в них
- •3. Пространство сообщений. Коды обнаружения и исправления ошибок
- •4. Кодирование и шифрование информации
- •4.1. Криптография и криптоанализ
- •4.2. Традиционные симметричные криптосистемы
- •4.2. Шифрование методом замены
- •4.3. Шифрование методами перестановки
- •4.4. Шифрование методом гаммирования
- •4.3.Элементы криптоанализа
- •5. Функции алгебры логики. Программная реализация логических функций
- •5.1. Основные функции алгебры логики
- •Коммутативность
- •Ассоциативность
- •Дистрибутивность
- •5.2. Булева алгебра. Функциональная полнота
- •Свойства алгебры Жегалкина
- •1. Коммутативность
- •2. Дистрибутивность
- •3. Идемпотентность
- •5.3. Минимизация функций алгебры логики
- •5.4. Программная реализация логических функций и автоматов
- •6. Логические элементы эвм
- •8. Данные, типы данных, структуры и обработка
- •9. Методы разработки и анализа алгоритмов
- •10. Теория конечных автоматов
- •10.1. Определение конечного автомата
- •10.2. Способы представления конечных автоматов
- •11. Архитектура эвм
- •12. Программное и техническое обеспечение эвм
- •13. Информационные структуры
- •13.1. Последовательное и связанное распределение данных
- •13.2. Стеки и очереди
- •13.3. Деревья
- •13.4. Представление деревьев
- •13.5. Прохождение деревьев, леса
- •14. Формальные языки и грамматики
- •14.1. Введение в теорию формальных языков и грамматик
- •14.2. Выводы цепочек формальных грамматик. Деревья ксг
- •14.3. Основные понятия теории формальных языков и грамматик
- •Литература
Свойства алгебры Жегалкина
1. Коммутативность
x y = y x
x & y = y & x
2. Дистрибутивность
x & (y z)= x & y z & x
3. Идемпотентность
x x = 0
x 0 = x
x & x = x
Для алгебры Жегалкина характерно
= x 1
x y = x & y x y
Определение. Формула, имеющая вид полинома со сложением по модулю 2 называется полиномом Жегалкина для функции алгебры логики.
Замечание. От булевой формулы всегда можно перейти к полиному Жегалкина.
5.3. Минимизация функций алгебры логики
Работа автомата может быть полностью описана с помощью следующей системы функций алгебры логики [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.
V1
V2
V3
V4
& & & & &
& &
&
&
1
1
f1