- •Определение булевой функции
- •Способы задания булевых функций
- •Формулы. Реализация функций формулами
- •Понятие суперпозиции
- •Эквивалентность формул. Основные тавтологии алгебры логики
- •Принцип двойственности
- •Разложение булевых функций по переменным. Совершенные
- •Полнота и замкнутость. Примеры функционально полных систем
- •Представление булевых функций полиномом Жегалкина
- •Класс функций, сохраняющий константу 0
- •Класс функций, сохраняющий константу 1
- •Класс самодвойственных функций
- •Класс линейных функций
- •Теорема Поста о полноте
- •Понятие днф. Проблема минимизации булевых функций
- •Геометрическая интерпретация задачи минимизации булевых функций
- •Определение тупиковой днф
- •Построение тупиковых днф методом упрощения совершенной днф
- •Определение сокращенной днф и геометрический метод ее построения
- •19.Минимизация булевых функций на основе построения тупиковых д. Н. Ф.
- •20. Минимизация булевых функций методом карт Карно.
- •21.Минимизация булевых функций методом Квайна-Мак-Класски
- •23.Задачи анализа и синтеза схем из функциональных элементов. Элементарные методы синтеза.
- •Элементарные методы синтеза
- •26 Синтез схем дешифратора и двоичного сумматора
- •28. Определение конечного автомата
- •Способы задания конечного автомата
- •29. Задача синтеза автоматов
- •Элементарные автоматы
- •Машина Тьюринга
- •Что собой представляет машина Тьюринга?
- •Пример работы машины Тьюринга
Теорема Поста о полноте
Перейдем к рассмотрению одного из основных вопросов алгебры логики – вопроса о необходимых и достаточных условиях полноты. Пусть
– произвольная система функций из . Спрашивается, как выяснить, будет она полной или нет? Ответ на этот вопрос дает следующая теорема.
Теорема Поста. Для того чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов .
Доказательство. Необходимость. Пусть – полна, то есть . Допустим, что содержится в одном из указанных классов – обозначим его через , то есть . Тогда в силу свойств замыкания и замкнутости имеем
.
Отсюда , что не так. Необходимость доказана.
Достаточность. Пусть целиком не содержится ни в одном из указанных классов. Тогда из можно выделить подсистему , содержащую не более пяти функций, которая обладает этим свойством. Для этого возьмем в функции , , , , и положим
.
Для доказательства достаточности убедимся, что из функций можно построить отрицание и конъюнкцию. Доказательство проведем в два этапа.
Построение при помощи функций , , и констант и отрицания.
Рассмотрим функции и . Построим функции одного аргумента:
и .
При сделанных предположениях
, .
В зависимости от того, какие значения имеют и , возможны четыре варианта.
, .
В этом случае , . В результате суперпозиции получаем константу 1: . Таким образом, отрицание и константы построены.
, .
В этом случае , . Строим , и первый этап закончен.
, .
Имеем . Воспользуемся функцией . Для этой функции найдется пара противоположных наборов и , на которых принимает одно и то же значение, так как
.
Рассмотрим функцию , в которой на место -го аргумента ставится , если , или , если . Тогда
.
Отсюда следует, что . С помощью отрицания построим другую константу.
, .
Следовательно, , . Воспользуемся немонотонной функцией . По лемме 4 из путем подстановки констант можно получить отрицание.
Покажем, что из функций можно построить конъюнкцию. При этом будем использовать построенные на первом этапе константы и отрицание. Воспользуемся нелинейной функцией . Подставим в нее константы и построим нелинейную функцию от двух аргументов, что возможно по лемме 6:
.
Рассмотрим функцию . Для построения функции нужно только отрицание, поскольку прибавление двоичной константы либо ничего не изменяет, если она равна 0, либо меняет переменную на ее отрицание. Например, при , , .
В общем случае
Раскрыв скобки, убеждаемся, что . Таким образом, конъюнкция построена из функций системы .
Теорема доказана.
Для проверки полноты конкретной системы функций удобно заполнять таблицу, в которой отмечается 1 или 0 вхождение или невхождение функции в классы , , , и . Например, для системы функций
, где , ,
имеем следующую таблицу:
Таблица 2
-
Функция
Класс
0
0
1
0
1
1
1
0
1
0
1
1
0
1
0
Пример. Импликация имеет следующую таблицу истинности:
-
0 0
1
0 1
1
1 0
0
1 1
1
Из таблицы следует, что не сохраняет 0, несамодвойственна, немонотонна. Кроме того, , так как
.
Добавляя к любую функцию, не сохраняющую 1, получим полную систему. Рассмотрим, например, систему , где . Построим отрицание и конъюнкцию:
, при и имеем ;
.
Таким образом, для любой функции можно написать формулу, в которую будут входить только импликации и нули. Например,
.
13