Функциональная полнота систем переключательных функций

Элементарные переключательные функции позволяют получить сложные функции от большего числа аргументов путем подстановки в данную функцию вместо ее переменных других функций. Такой метод получения функций называется суперпозицией. Например, имея элементарные функции двух переменных z 1= х1х2и z 2= х3∨ х4, можно получить функции z 3= x 1( x 3∨ х4), z 4= x 3∨ х1x 2, зависящие от трех переменных.

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

Эта проблема называется проблемой функциональной полноты переключательных функций. Для ее решения были выделены следующие классы логических функций.

1. Класс функций, сохраняющих константу 0. В этот класс входят функции, которые на нулевом наборе переменных принимают нулевое значение: f (00...0) = 0. Такова, например, конъюнкция f 8(00) =0 · 0 = 0.

2. Класс функций, сохраняющих константу 1. В этот класс входят функции, которые на единичном наборе переменных принимают единичное значение: f (11... 1) = 1. Этим свойством также обладает конъюнкция f 8(11) = 1 · 1 = 1. Классы 1, 2 легко устанавливаются по таблице истинности.

3. Класс самодвойственных функций. Переключательные функции f ( x 1x 2... х n) и g ( x 1x 2... х n) называются двойственными, если имеет место равенство т. е. когда одна функция получается из другой, если провести замену всех переменных на их инверсии и провести инверсию функции. Например, f 8( x 1x 2) = х1х2и f 14(х1x 2) = х1∨ х2двойственны: Это можно доказать, построив таблицу истинности (табл. 27).

Таблица 27

Таблица истинности

Переключательная функция называется самодвойственной, если она двойственна по отношению к самой себе: Такова, например, функция

Самодвойственность устанавливается по таблице истинности следующим образом: значения функции, симметричные относительно середины таблицы, инверсны. Например, для f 10( x 1x 2) значения функции представляют собой вектор каждый разряд которого является инверсным по отношению к симметричному разряду относительно середины, отмеченной пунктиром.

Эти разряды соответствуют инверсным наборам х1х2: 00-11, 01-10. Самодвойственны функции

4. Класс линейных функций. Переключательная функция называется линейной, если возможно представление в виде линейного полинома, использующего функцию сложения по модулю 2:

f ( x 1х2) = с0⊕ с1х1⊕ с2х2, где с0, с1, с2— константы 0, 1,

Например, для функции f 6(х1х2) = х1⊕ х2при с0= 0, с1= с2= 1: f 6(х1х2) = 0 ⊕ 1 · х1⊕ 1х2.

Получим все линейные функции двух переменных, задав все возможные значения с0с1c 2(табл. 28).

Таблица 28

Линейные функции двух переменных

Из табл. 28 видно, что каждая линейная функция имеет инверсную ей функцию: константа 0 — константа 1; повторение х1, х2— инверсия сложение по модулю 2х1⊕ х2— эквиваленция х1↔ х2

5. Класс монотонных функций. Монотонная функция на большем сравнимом наборе переменных принимает не меньшие значения. Это удобно проверять на решетках Хассэ. Так, для двух переменных решетка имеет вид, как на рис. 37.

На рис. 37 проставлены значения монотонной функции х1. Видно, что 11 > 01 > 00, 11 > 10 > 00 (частично упорядоченное множество наборов).

Рис. 37. Решетка Хассэ для двух переменных с указанием значений fl0( x 1x 2) = x 1

Очевидно, что константы 0, 1 — монотонные функции, дизъюнкция и конъюнкция — монотонные функции, повторения х1, х2— монотонные функции.

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

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

● не сохраняющую константу 0;

● не сохраняющую константу 1;

● несамодвойственную;

● нелинейную;

● немонотонную.

⇐ Предыдущая18192021222324252627Следующая ⇒

Поделиться:

Популярное:

1. D. СОЦИОИДЕОЛОГИЧЕСКАЯ СИСТЕМА ВЕЩЕЙ И ПОТРЕБЛЕНИЯ
2. F. ЦИФРОВЫЕ СИСТЕМЫ РАСПРОСТРАНЕНИЯ
3. I. Местное самоуправление в системе институтов конституционного строя. История местного самоуправления
4. I. Методические принципы физического воспитания (сознательность, активность, наглядность, доступность, систематичность)
5. II. Проверка и устранение затираний подвижной системы РМ.
6. II.2. Локальные геосистемы – морфологические единицы ландшафта
7. III.3. Система классификационных единиц
8. IV. Падение отработочной системы.
9. IV. СООТНОШЕНИЕ СИМВОЛИЧЕСКИХ И ЕСТЕСТВЕННО-ЯЗЫКОВщХ СИСТЕМ КАК ФАКТОР, ОПРЕДЕЛЯЮЩИЙ ХАРАКТЕР КУЛЬТУРЫ
10. MRPII–система как черный ящик
11. V.1. Функциональная несостоятельность семей группы риска.
12. VI. Предотвращение негативного воздействия на работу централизованных систем водоотведения