Материал: Методические указания к практическим занятиям по дисциплине «Модели безопасности компьютерных систем» для студентов специальности 090301 «Компьютерная безопасность». Гончаров И.В., Остапенко А.Г

Практическое задание №4 Минимизации логических функций

Цель лабораторной работы заключается в изучении методов шифрования и дешифрования данных.

Задачи лабораторной работы:

закрепить основные понятия алгебры логики;

изучить основные операции над булевыми переменными;

изучить и освоить алгоритм минимизации булевых функций;

научиться пользоваться таблицей истинности.

Теоретические сведения

Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является алгебра логика или булева алгебра (Дж. Буль - английский математик прошлого столетия, основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их оптимизации и проектирования [3].

Вся информация в ЭВМ представляется в двоичной системе счисления. Поставим в соответствие входным сигналам отдельных устройств ЭВМ соответствующие значения хi(i=1,n), а выходным сигналам - значения функций yj(j=1,m)

(рис. 6.).

Рис. 6. Представление схемы ЭВМ

29

Известно, что количество всевозможных функций N от п аргументов выражается зависимостью

N=22n.

При n=0 можно определить две основные функции (N=2), не зависящие от каких-либо переменных: у0 , тождественно равную нулю (у0=0), и у1 , тождественно равную единице (у1=1). Технической интерпретацией функции у1=1 может быть генератор импульсов. При отсутствии входных сигналов на выходе этого устройства всегда имеются импульсы (единицы). Функция у0=0 может быть интерпретирована отключенной схемой, сигналы от которой не поступают ни к каким устройствам.

При п=1 зависимость дает N=4. Представим зависимость значений этих функций от значения аргумента х в виде специальной таблицы истинности (табл. 5).

Таблица 5

Таблица функций от одной переменной

Таблицы истинности получили такое название, потому что они определяют значение функции в зависимости от комбинации входных сигналов. В этой таблице, как и ранее, у0=0 и y1=1. Функция y2=х, а функция у3=x- (инверсия x).

При п=2, N=l6, т.е. от двух переменных, можно построить шестнадцать различных функций. В табл. 5 представлена часть из них, имеющая фундаментальное значение при построении основных схем ЭВМ.

30

Заметим, что в левой части табл. 6 перечислены всевозможные комбинации входных переменных (наборы значений),

ав правой - возможные реакции выходных сигналов. Функции у0-у3, полностью соответствующие функциям в таблице выше,

атакже новые, часто используемые и интересные функции у4- у9. При этом местоположение функций и их нумерация в таблице особого значения не имеют. По данной таблице нетрудно составить аналитическое выражение (зависимость) для каждой функции от двух аргументов. Для этого наборы переменных, на которых функция принимает значение единицы, записываются как конъюнкции (логическое умножение) и связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормальных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значениях, то такая форма функций называется совершенной [3].

Функция у4представляет собой функцию логического сложения, дизъюнкцию. Она принимает значение единицы, если значение единицы имеет хотя бы одна переменная х1 или

х2:

.

31

Тождественность приведенных аналитических зависимостей можно установить, пользуясь законами алгебры логики, приведенными ниже.

Функция y5 является инверсной функцией по отношению к y4:

Она имеет название ⌠ отрицание дизъюнкции. Иногда в литературе встречается ее специальное название ⌠ стрелка Пирса, по фамилии математика, исследовавшего ее свойства.

Функция у6 является функцией логического умножения. Она очень похожа на операцию обычного умножения и принимает значение единицы в тех случаях, когда все ее переменные равны единице:

Функция y7 является инверсной функцией по отношению к у6:

Она называется ⌠отрицание конъюнкции или ⌠ штрих Шеффера. Функция к называется логической равнозначностью, она принимает значение единицы, если все ее переменные имеют одинаковое значение (или 0 или 1):

Функция y9 является инверсной по отношению к y8:

32

Она принимает значение единицы, если ее переменные имеют противоположные значения. Ниже будет показано, что функции у8 и у9 являются основой для построения сумматоров, так как они соответствуют правилам формирования цифр двоичных чисел при сложении (вычитании).

Законы алгебры логики

Из определения вышеприведенных функций можно установить целый ряд простейших свойств:

В алгебру логики установлен целый ряд законов, с помощью которых возможно преобразование логических функций (ЛФ):

коммутативный (переместительный)

x1*x2=x2*x1

ассоциативный (сочетательный)

(x1*x2)*x3=(x1*x3)*x2=x1*(x2*x3)

Эти законы полностью идентичны законам обычной ал-

гебры;

дистрибутивный (распределительный)

33