Функции алгебры логики (ФАЛ). Алгебра логики. Геометрическая интерпретация ФАЛ. Минимальные ДНФ. Диаграммы Вейча

Лекция 6

Функции алгебры логики (ФАЛ). Алгебра логики.

Геометрическая интерпретация ФАЛ.

Минимальные ДНФ. Диаграммы Вейча.

1.  Функции алгебры логики (ФАЛ).

ФАЛ называются функция , аргументы и значения которой определены на множестве {0, 1}. Как обычно, сложная ФАЛ может быть определена как композиция из простых применением операции подстановки. Скобочная запись такой композиции называется формулой, которая строится по принятым в математике законам.

Пример: . Скобочная формула отражает структуру подстановок из составляющих функций f1, f2, f3, f4 .

В связи с тем, что число наборов значений аргументов конечно, ФАЛ удобно задавать таблицей.

Таблица истинности ФАЛ состоит из всех возможных наборов значений аргументов. Каждый набор отмечается либо «1» (единичные наборы), либо «0» (нулевые наборы). Эти отметки суть значения функции. Очевидно, что количество наборов значений ФАЛ – 2п, а количество различных функций на этих наборах (количество различных разметок) – (см. например, табл. 1).

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

Табл. 1. Таблица бинарных функций алгебры логики.

х1	0	1	0	1	Знак операции	Наименование функции	Свойства
х2	0	0	1	1
0	0	0	0	0		Конст. «0»
1	0	0	0	1	&;·; L	Конъюнкция, логич. умнож.
2	0	0	1	0	х1 х2 Ì	Запрет х2 Защелка х2	наддув воздуха в помещении дверь х2=0 х2=0 х2=1 х2=1   окно х1=0 х1=1 х1=0 х1=1
3	0	0	1	1	х2		х2
4	0	1	0	0	х2 х1	Запрет х1 Защелка х1
5	0	1	0	1	х1		х1
6	0	1	1	0		Слож. по mod 2
7	0	1	1	1		Дизъюнкция логич. слож.
Продолжение табл. 1
8	1	0	0	0		Стрелка Пирса функция Даггера
9	1	0	0	1		Эквиваленция совпадение
10	1	0	1	0	ù	Отрицание х1
11	1	0	1	1		Импликация следование «из х1 след. х2»
12	1	1	0	0		Отрицание х2
13	1	1	0	1		Импликация « из х2 след. х1»
14	1	1	1	0		Штрих Шеффера
15	1	1	1	1	F15 = 1	Конст. «1»

2. Алгебра логики и эквивалентные преобразования ФАЛ.

Алгебра логики представляет собой перечень свойств операций &, V, ù, заданных через соотношения эквивалентностей.

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

2)  Ассоциативность

3)  Дистрибутивность

4)  Идемпотентность ;

5)  Закон исключенного третьего (свойства «ù»)

6)  Закон Де Моргана

7)  Закон поглощения

Свойства операций задаются системой эквивалентных преобразований, любая эквивалентность проверяется по таблице. Эта система называется алгеброй логики. Почему логики? На самом деле, все эквивалентности, входящие в алгебру, являются логическими законами.

Определение эквивалентности (тождественности функций).

Пара функций называется эквивалентными, если значения функций совпадают на одинаковых наборах в таблице функций.

1) x1çx2= 2) x1­x2=

3) x1çx1= 4) x1çx1=

3. Стандартные формулы представления ФАЛ.

1)  Любая ФАЛ может быть представлена в виде совершенной дизъюнктивной нормальной формы (СДНФ).

– все возможные комбинации расстановок отрицаний над переменными (отрицание – s = 0, нет отрицания – s = 1)

Очевидно любая расстановка значений или 1 даёт конкретную реализацию функций (см. пример) из .

2)  Любая ФАЛ может быть представлена в виде совершенной конъюнктивной нормальной формы (СКНФ).

…

Любая расстановка значений или 1 даёт конкретную реализацию функций (см. пример) из .

Пример: Построение СДНФ и СКНФ по таблице истинности функций.

а) СДНФ состоит из элементов конъюнкции, соединённых знаком дизъюнкции. В таблице выделяются единичные наборы. Если в наборе , то в элементарной конъюнкции xi, иначе , то .

б) СКНФ состоит из элементов дизъюнкций, соединённых знаком конъюнкции. В таблице выделяются нулевые наборы. Если в наборе , то в элементарной дизъюнкции , иначе , то .

Табл.2

№	x1 x2 x3	f-
0	0 0 0	1
1	0 0 1	0
2	0 1 0	1
3	0 1 1	0
4	1 0 0	0
5	1 0 1	0
6	1 1 0	1
7	1 1 1	1

(

f (СДНФ)

(

f1 (СКНФ)

3) Любая ФАЛ может быть представлена в виде полинома Жегалкина.

и т. д. все пары переменных

……………………………….…..и т. д. все тройки

……………………………….…..и т. д.

Любая расстановка значений или 1 даёт реализацию конкретной функции.

Пример: Для функции, заданной табл. 2, полином Жегалкина будет иметь вид:

Формы СДНФ, СКНФ, ПЖ суть коды функций. Количество различных кодов, построенных по соответствующим правилам, равно и поэтому каждый код является уникальным и соответствует конкретной функции.

4. Геометрическая интерпретация ФАЛ.

Введём пространство на множестве переменных в виде декартова произведения , где . Каждой точке пространства соответствует набор из «0» и «1». ФАЛ задаёт n – арное отношение , другими словами выделяет (отмечает) некоторые наборы значением функции равным «1».

4.1  Геометрия пространства Xn

Геометрия пространства задаётся координатами , где каждая координата . Каждая точка пространства суть некоторая вершина n – координатного гиперкуба (n – куба). Понятно, что n – куб содержит 2n точек. Каждой точке n – куба может быть соотнесена элементарная конъюнкция.

Например, для точке 010 соответствует конъюнкция, точке 101 – . Таким образом, для однозначно соответствует СДНФ функции. На рис.1а на одномерном кубе точке соответствует , а точке . Далее на рисунках выделенные точки (точки, входящие в отношение ) будут показаны «*». На рис.1б показан 2 – мерный куб, для удобства точки с бинарным набором нумеруются соответствующими десятичными числами. На 2 – мерном кубе выделены два подмножества:

соответствует СДНФ

соответствует СДНФ

а) Пространство б) Пространство 2-х переменных

1-й переменной x1

00=0 01=0 00 01

Интервалы – точки для

Интервалы – рёбра для .

Покрытия для, ДНФ=

, ДНФ=

, ДНФ=

в) Пространство 3-х переменных .

Рис.1. Геометрическая интерпретация ФАЛ.

4.2 Интервалы и покрытия в n – кубах, представляющие ДНФ функции алгебры логики.

Расстоянием Хомминга c для двух бинарных наборов

a и называется количество совпадений в них «0» и «1».

Например, и ;

и и .

Определим по индукции для .

а) J0 Интервал ранга «0» – пустое множество.

б) J1 Интервал ранга «1» – точка, соответствует некоторому

в) J2 Интервал ранга «2» – ребро=

г) J4 Интервал ранга «4» – грань=

……………………………………………………………..

д) J2n Интервал ранга «2n» – n–куб

Пусть в n – кубе выделены «m» точек для определения ФАЛ , тогда покрытием для f называется множество , состоящие из интервалов разного ранга, в которое входят все точки «m» и только они.

Каждый интервал Ji соответствует конъюнкции. Совокупность одинаковых переменных, входящих в конъюнкции, характеризующие все точки интервала, называется его инвариантом. Примеры инвариантов приведены на рис.1.

Пусть ФАЛ задана единичными значениями в точках .Различные покрытия и соответствующие ДНФ будут иметь вид:

а) СДНФ= (точки)

б) ДНФ= (точка)Ú (грань)

в) ДНФ= (ребро)Ú (ребро) (ребро)

5. Минимальная ДНФ.

При реализации ДНФ в дискретных устройствах естественно иметь её описание с наименьшими затратами символов. Напомним, что каждая переменная «х», входящая в ДНФ функции, это отдельный вход, каждая операция – это отдельный функциональный элемент. Очевидно, чем меньше при аппаратной реализации входов и функциональных элементов, тем эффективнее её работа.

Минимальной ДНФ называется такая запись формулы ФАЛ, которая содержит минимальное число конъюнкций, соответствующим максимальным интервалам (интервалам имеющим max ранг).

Естественно, что минимальная ДНФ (МДНФ) содержит минимальное число переменных и операций.

Пример. Минимальное покрытие и минимальная ДНФ.

Для рис.1в построим различные покрытия на шести точках трехмерного куба

а) СДНФ =

Число переменных m = 18.

б) Покрытие ребрами {(110,111), (111,011), (001,101), (000, 001)}

ДНФ = .

в) Минимальное покрытие {грань (111, 011, 101, 001),

ребро (000, 001), ребро (110, 111)}

min ДНФ = .

г) Покрытие

ДНФ=

6. Инженерные методы минимизации ФАЛ. Диаграммы Вейча (ДВ).

В основе ДВ лежит представление n-мерного пространства (n-мерного куба) в виде 2-мерной карты (матрицы), каждая клеточка которой соответствует точке п-мерного куба. Представление ФАЛ в виде такой матрицы чрезвычайно удобно для принятия решения о аппаратной реализации при визуальной оптимизации. Системы автоматизации проектирования дискретных устройств очень часто используют ДВ в качестве основного способа представления ФАЛ.

а) 2-мерный куб, 2ДВ и минимальное покрытие

б) 3-мерный куб 3ДВ и минимальное покрытие

в) 4-марный куб, 4ДВ и минимальное покрытие

Три варианта 4ДВ

х4 х3 х2 х1 х4 х3 х2 х1

8 = инвариант 7 = инвариант

0 = х3 = 0; х1 = 0 3 = х4 = 0; х2 = 1

2 = =

10 = ДНФ = 6 = ДНФ =

min ДНФ = .