Пред.Страница  След.Страница  Раздел  Содержание


8.4. ПОЛНОТА ФУНКЦИОНАЛЬНЫХ БАЗИСОВ

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

Прежде чем приступить к решению поставленной задачи, необходимо уточнить два вопроса:

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

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

Определение: Пусть имеется некоторое множество В переключательных функций. Назовем множество В функциональным базисом, а входящие в него функции - базисными. Определим понятие формулы (над функциональным базисом В):
  • выражение f(x1,...,xn), где f ∈ В, есть формула над В;
  • если f(x1,...,xm) - базисная функция, а выражения F1,...,Fm являются символами переменных либо формулами, то суперпозиция f(F1,...,Fm) также есть формула над В.


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


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



8.4.1. Переключательные функции одной и двух переменных

Существует четыре различных функции одной переменной на множестве {0,1}: константа "0", константа "1", переменная x и инверсия переменной x (). Нетрудно убедиться, что из этих функций с помощью операций суперпозиции и подстановки можно получить только функцию одной переменной.

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



Таблица 4.1
х 0011 Название функции Обозначение Класс
y 0101 T0 T1 S M L
f0(x,y) 0000 Константа “0” 0 +     + +
f1(x,y) 0001 Конъюнкция x ∧ y, xy + +   +  
f2(x,y) 0010 Операция запрета по y x +        
f3(x,y) 0011 Переменная x x + + + + +
f4(x,y) 0100 Операция запрета по x y +        
f5(x,y) 0101 Переменная y y + + + + +
f6(x,y) 0110 Сумма по модулю 2 x ⊕ y +       +
f7(x,y) 0111 Дизъюнкция x ∨ y + +   +  
f8(x,y) 1000 Операция Пирса x ↓ y          
f9(x,y) 1001 Равнозначность x ∼ y   +     +
f10(x,y) 1010 Инверсия y     +   +
f11(x,y) 1011 Импликация от y к x y → x   +      
f12(x,y) 1100 Инверсия x     +   +
f13(x,y) 1101 Импликация от x к y x → y   +      
f14(x,y) 1110 Операция Шеффера x / y          
f15(x,y) 1111 Константа “1” 1   +   + +


Индекс функции fi(x, y) является десятичным эквивалентом двоичного числа, образованного из вектора значений функции на упорядоченном множестве наборов значений аргументов: {(0,0),(0,1),(1,0),(1,1)}. Функции f0, f3, f5, f10, f12, f15 являются расширением на случай двух переменных уже известных функций одной переменной. Функции f1(x,y) = x ∨ y (конъюнкция) и f7(x,y) = x ∧ y (дизъюнкция) совместно с функцией инверсии (f10, f12) были использованы в предыдущих разделах для построения форм представления переключательных функций, пригодных для аналитической записи переключательных функций произвольной сложности.

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

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

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

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



Пред.Страница  След.Страница    Раздел    Содержание