ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Базис булевых функций. Теорема Поста

Таблицы истинности функций

Задана булева функция . Рассмотрим таблицы истинности для элементарных булевых функций, входящих в нее.

Отрицание, обозначение :

a
`

Дизъюнкция (логическое или), обозначение :

Сумма по модулю 2, обозначение :

Построим таблицу истинности заданной функции.

Укажем существенные и фиктивные переменные булевой функции f. Вначале рассмотрим булеву переменную и наборы и , которые являются соседними по этой переменной. , , . Т.е. переменная является существенной переменной булевой функции.

Аналогично рассмотрим оставшиеся булевы переменные. По переменной рассмотрим два набора и , , .

По переменной рассмотрим два набора и , , .

Таким образом, все переменные булевой функции являются существенными.

Нормальные формы и полиномы

Запишем по таблице истинности заданной функции совершенную дизъюнктивную нормальную форму (СДНФ). Для этого рассмотрим наборы, где функция принимает значение 1. В результате получим

Запишем по таблице истинности заданной функции совершенную конъюнктивную нормальную форму (СКНФ). Для этого рассмотрим наборы, где функция принимает значение 0 и возьмем каждый набор с отрицанием. В результате получим

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

В формуле надо раскрыть скобки и упростить выражения с помощью соотношений , , .

Для заданной функции получим

Степень полинома – 3.

Проверим правильность преобразований с помощью таблицы истинности.

Результат совпадает с исходной таблицей истинности.

Все три представления булевой функции эквивалентны. Далее будем рассматривать булеву функцию в классе ДНФ и полиномов Жегалкина.

Базис булевых функций. Теорема Поста

Проверим элементарные булевы функции, входящие в состав заданной, на образование базиса.

Сохрание 0,	Сохрание 1,	Самодвойственность, S	Монотонность, M	Линейность, L
		+		+
+	+		+
+				+

В таблице знаком «+» обозначено принадлежность функции к данному классу.

Для того чтобы функции составляли базис, по теореме Поста необходимо, чтобы хотя бы одна функция не сохраняла 0, хотя бы одна функция не сохраняла 1, хотя бы одна функция не была самодвойственной, хотя бы одна функция не была монотонной и хотя бы одна функция не была линейной. Из вышеприведенной таблицы видно, что данный набор функций составляет базис. Причем для базиса достаточно первых двух функций, то есть отрицания и дизъюнкции.

Проверим возможность получения из заданной булевой функции f путем суперпозиции некоторой булевой функции . Для этого проверим f на принадлежность классам Поста.

По таблице истинности , следовательно .

, следовательно .

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

Исходя из таблицы истинности , следовательно .

Рассмотрим два набора и . Согласно лексикографического порядка , но . Поэтому .

Степень полинома Жегалкина для заданной функции f равняется 3, поэтому .

Заданная функция f принадлежит к функционально полному в слабом значении классу, так как она немонотонная и нелинейная. Поэтому добавление констант 0 и 1 в класс позволит получить из f путем суперпозиции любую булеву функцию .