Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Функциональная полнота

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все другие функции.
     Введем в рассмотрение ряд классов функций:
     1. Класс функций, сохраняющих константу 0, т.е. таких функций y=f(x1,x2 ... xn), что f(0,0 ... 0)=0. Например, xvy(¬x).
     2. Класс функций, сохраняющих константу 1, т.е. таких функций y=f(x1,x2 ... xn), что f(1,1 ... 1)=1. Например, xv¬(yx).
     3. Класс самодвойственных функций, т.е. таких функций y=f(x1,x2 ... xn), что f(x1,x2 ... xn)=¬(f(¬x1,¬x2 ... ¬xn)).
     4. Класс линейных функций, т.е. таких функций y=f(x1,x2 ... xn), которые могут быть представлены в виде f(x1,x2 ... xn)=c0⊕c1x1⊕c2x2⊕...⊕cnxn, где c0, c1, c2 - коэффициенты, которые могут принимать значение 0 или 1.
     5. Класс монотонных функций. На множестве наборов из нулей и единиц Bn={(x1,x2 ... xn):xi∈{0,1},i=1,2...n} введем частичный порядок следующим образом:
     (a1,a2...an)=(b1,b2...bn) тогда и только тогда когда a1=b1, a2=b2 ... an=bn. Функция f(x1,x2 ... xn) называется монотонной, если для любых двух элементов из Bn таких, что (a1,a2 ... an)=(b1,b2 ... bn) следует, что f(a1,a2 ... an)=f(b1,b2 ... bn).
     Система S булевых функций, суперпозицией которых может быть представлена любая булева функция, называется функционально полной. Говорят, что функционально полная система S булевых функций образует базис в логическом пространстве. Базис S называется минимальным, если удаление из него любой функции превращает эту систему в неполную.
     Критерий полноты (Теорема Поста): Система S булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.
     В таблице приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция).

НазваниеОбозначениеНе сохранимость константы 0Не сохранимость константы 1Не самодвойственностьНе линейностьНе монотонность
Конст. 00 **  
Конст. 11* *  
Отриц.¬**  *
Конъюн.&  ** 
Дизъюн.v  ** 
Имплик.* ***
Эквивал.* * *
Сумма по мод. 2 ** *
Штрих Шеффера|*****
Стрелка Пирса*****

     Используя теорему Поста и данную таблицу можно строить базисы из элементарных функций по следующему правилу. Выбрав любую элементарную булеву функцию и дополнив ее при необходимости другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте. Через функции этого базиса можно выразить все другие булевы функции.
     Построим некоторые часто используемые в приложениях базисы.
     1. Система функций S1={¬,&,v} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности:
         X→Y=¬XvY
         X↔Y=(Xv¬Y)(¬XvY)
         X⊕Y=¬XYvX¬Y
         X|Y=¬Xv¬Y
         X↓Y=¬X&¬Y
     2. Система S2={¬,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение XvY=¬(¬X•¬Y).
     3. Система S3={¬,v} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение X•Y=¬(¬Xv¬Y).
     4. Система S4={1,&,⊕} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения:
         ¬X=1⊕X
         XvY=X⊕Y⊕X•Y
     5. Система S5={|} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения:
         X•Y=¬(¬X|¬Y)
         ¬X=X|X
     6. Система S6={↓} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем использовать соотношения:
         XvY=¬(¬X|¬Y)
         ¬X=X↓X
     7. Система S7={→,0} образует базис.
     Пример: Записать функцию X↔(Y⊕Z) в базисе S1={¬,&,v}.
     X↔(Y⊕Z)=(Xv¬(Y⊕Z))•(¬Xv(Y⊕Z))=(Xv¬(¬Y•ZvY•¬Z))•(¬Xv¬Y•ZvY•Z)

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru