- •Определение булевой функции
- •Способы задания булевых функций
- •Формулы. Реализация функций формулами
- •Понятие суперпозиции
- •Эквивалентность формул. Основные тавтологии алгебры логики
- •Принцип двойственности
- •Разложение булевых функций по переменным. Совершенные
- •Полнота и замкнутость. Примеры функционально полных систем
- •Представление булевых функций полиномом Жегалкина
- •Класс функций, сохраняющий константу 0
- •Класс функций, сохраняющий константу 1
- •Класс самодвойственных функций
- •Класс линейных функций
- •Теорема Поста о полноте
- •Понятие днф. Проблема минимизации булевых функций
- •Геометрическая интерпретация задачи минимизации булевых функций
- •Определение тупиковой днф
- •Построение тупиковых днф методом упрощения совершенной днф
- •Определение сокращенной днф и геометрический метод ее построения
- •19.Минимизация булевых функций на основе построения тупиковых д. Н. Ф.
- •20. Минимизация булевых функций методом карт Карно.
- •21.Минимизация булевых функций методом Квайна-Мак-Класски
- •23.Задачи анализа и синтеза схем из функциональных элементов. Элементарные методы синтеза.
- •Элементарные методы синтеза
- •26 Синтез схем дешифратора и двоичного сумматора
- •28. Определение конечного автомата
- •Способы задания конечного автомата
- •29. Задача синтеза автоматов
- •Элементарные автоматы
- •Машина Тьюринга
- •Что собой представляет машина Тьюринга?
- •Пример работы машины Тьюринга
Класс функций, сохраняющий константу 0
Обозначим через класс всех булевых функций из , сохраняющих константу 0, то есть функций, которые равны нулю на нулевом наборе переменных:
.
Заметим, что если , а , то и .
Легко убедиться, что функции 0, , , , принадлежат классу , а функции 1, , , не входят в .
Поскольку таблица для функции из класса в первой строке содержит значение 0, то в содержится ровно булевых функций от переменных.
Покажем, что – замкнутый класс. Для этого надо доказать следующее утверждение.
Лемма 1. Суперпозиция функций из класса является функцией класса .
Для доказательства необходимо убедиться, что применение операций и к функциям, сохраняющим 0, всякий раз дает функцию, сохраняющую 0.
В результате операции для функции имеем формулу , которая при нулевых значениях своих аргументов совпадает с .
Теперь покажем, что функция , полученная в результате применения операции , принадлежит , если принадлежат :
.
Лемма доказана.
Пример 1. Функции и входят в , поэтому суперпозиция этих функций будет сохранять 0. Следовательно, система неполная.
Класс функций, сохраняющий константу 1
Обозначим через класс всех булевых функций из , сохраняющих константу 1, то есть функций, которые равны 1 на единичном наборе переменных:
.
Например, функции 1, , , принадлежат классу , а функции 0, , не входят в .
В силу того, что класс двойствен классу , нетрудно перенести результаты о классе на класс . Так, если , а , то и . Класс содержит булевых функций от переменных и является замкнутым классом, то есть суперпозиция функций из класса является функцией класса .
Класс монотонных функций
Рассмотрим множество двоичных слов длины . Зададим на этом множестве отношение порядка (предшествования) следующим образом: будем говорить, что слово
предшествует слову
,
если
.
Тот факт, что слово предшествует слову будем обозначать .
Отношение предшествования удовлетворяет аксиомам рефлексивности, антисимметричности и транзитивности.
Например, 00 10 11, 0010 0111 1111.
Слова 01 и 10 не находятся в отношении предшествования. Такие слова называются несравнимыми.
Отношение “ ” можно представить в виде ориентированного графа. Для имеем следующий граф:
111
Рис. 1. Представление отношения предшествования в виде ориентированного графа
Слово предшествует слову , если от к можно пройти по стрелкам.
Функция называется монотонной, если для любых наборов переменных и выполняется условие
,
то есть значение функции на меньшем наборе не превосходит значения функции на большем наборе.
Очевидно, что функция, равная монотонной функции, также является монотонной.
Например, монотонными функциями будут 0, 1, , , .
Обозначим через множество всех монотонных функций. Покажем, что класс монотонных функций замкнут.
Лемма 3. Суперпозиция функций из класса является функцией класса .
Доказательство. Доказательство леммы проведем на примере конкретной суперпозиции, рассуждение для общего случая будет аналогичным.
Пусть , где . Покажем, что . Рассмотрим два сравнимых набора значений аргументов функции :
.
Тогда , и в силу монотонности имеет место неравенство
.
Отсюда и в силу монотонности имеет место неравенство
.
В результате имеем
Таким образом, . Лемма доказана.
Будем называть наборы и соседними по -ой координате , если
, .
Докажем теперь лемму о немонотонной функции.
Лемма 4. Из немонотонной функции путем подстановки констант на места некоторых аргументов можно получить отрицание.
Доказательство. Пусть . Это значит, что
.
Покажем, что для функции найдется пара соседних наборов, для которых нарушается условие монотонности. Очевидно, пару соседних наборов и , для которых , всегда можно связать цепочкой соседних наборов. Возьмем пару соседних наборов , , для которых
, .
Рассмотрим функцию одного аргумента
.
Имеем
.
Так как , а , то . Лемма доказана.
10