Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
лекции Информатика_4.rtf
Скачиваний:
19
Добавлен:
31.08.2019
Размер:
4.36 Mб
Скачать
  1. Коммутативность

x1 & x2 = x2 & x1.

x1 v x2 = x2 v x1.

  1. Ассоциативность

x1 v (x2 v x3) = (x1 v x2) v x3.

x1 & (x2 & x3) = (x1 & x2) & x3.

  1. Дистрибутивность

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 , то берется ;

  • все полученные конъюнкции объединяются под знаком дизъюнкции.

    1. 3.6. Булева алгебра. Функциональная полнота

Определение. Алгеброй над множеством логических функций с двумя бинарными операциями, обозначаемыми как логическое умножение & и логическое сложение v и одной унарной операцией ( отрицанием )

  • называется булевой алгеброй. Будем обозначать ее символом SB.

Рассмотрим свойства булевой алгебры.

  1. Замкнутость

для " A и B Î SB

A v B Î SB

A & B Î SB

  1. Коммутативность

A & B = B & A

A v B = B v A

3. Ассоциативность

A v ( B v C) = (A v B) v C

  1. Дистрибутивность

A & ( B v C) = (A & B) v (A & C)

A v ( B & C) = (A v B) & (A v C)

  1. Идемпотентность

A v A = A & A = A.

  1. Булева алгебра содержит элементы 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. Закон Де Моргана

    1. 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