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

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

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

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

Пример составления полинома Жегалкина

Совершенная дизъюнктивная нормальная форма

Фиксируем алфавит булевых переменных .

Напомним, что

Определение 1.Элементарной конъюнкцией ранга относительно алфавита назовем форму ,

где . При конъюнкция называется совершенной.

Определение 2. Дизъюнктивной нормальной формой (ДНФ) относительно алфавита называется любая дизъюнкция элементарных конъюнкций. Совершенной дизъюнктивной нормальной формой относительно алфавита называется любая дизъюнкция различных совершенных конъюнкций (СДНФ).

Отметим все важные свойства совершенных конъюнкций:

а) произведение двух различных совершенных конъюнкций равно ;

б) в совершенной дизъюнктивной нормальной форме относительно алфавита при подстановке фиксированного набора либо все совершенные конъюнкции равны нулю, либо равна одна единственная конъюнкция.

Действительно, при произведение

(1)

c одержит для некоторого множители и , отсюда , и поэтому произведение (1) равно . Далее для любого набора уравнение влечет ,..., – единственно возможное решение, т.к. если для некоторого имеем , то и нулю равна вся конъюнкция.

Теорема. Всякая функция алгебры логики представима совершенной дизъюнктивной нормальной формой относительно алфавита своих переменных ,.., :

(2)

Дизъюнкция идет по всем наборам, в которых функция равна . Формула (2) следует непосредственно из свойств совершенных конъюнкций.

Вопрос. Чем является функция ?

Ваш ответ :

ДНФ (дизъюнктивная нормальная форма)

Да, правильно. Так как во втором слагаемом нет переменной .

Составление СДНФ

Пример 1. Совершенные ДНФ для элементарных функций (табл. 2):

для конъюнкции: ;

для дизъюнкции: ;

для сложения по mod 2: ;

для импликации: ;

для эквиваленции: ;

для штриха Шеффера: ;

для «стрелки Пирса»: ;

для отрицания : ;

для селекторной функции : ;

для константы : ;

константа не имеет СДНФ.

Пример 2. Написать СДНФ относительно алфавита , , для функции голосования от трех переменных, заданной таблично (см. табл. 3).

СДНФ для содержит четыре совершенные конъ-юнкции (по числу единиц функции)

.

Пример 3. Преобразовать в СДНФ формулу относительно алфавита , , .

Данная формула есть ДНФ, но имеет несовершенные конъюнкции. С помощью преобразований вида доводим конъюнкции до совершенства:
,
раскроем скобки
,
собираем подобные члены по правилу :
.
Это и есть СДНФ.

Замечание. Если функция задана формулой, то можно для функции вычислить таблицу, а затем задача сведется к примеру 2. Однако создание таблицы может оказаться очень трудоемким. Так, например, если алфавит переменных состоит из переменных, то таблица имеет строк, что неприемлемо, так как потребуется много места на доске или бумаге.

Вопрос. Сколько элементарных конъюнкций содержится в СДНФ для функции, заданной своими значениями ?

Ваш ответ :

Три

Да, правильно. Потому что функция равна 1 только на трех наборах.

Полином Жегалкина

Элементарные конъюнкции вида , , …, , (конъюнкция нулевого ранга) называются положительными элементарными конъюнкциями.

Любая сумма по различных положительных конъюнкций называется полиномом Жегалкина. Константу считаем нулевым полиномом Жегалкина. Тогда справедливо утверждение:

Теорема.Всякая функция алгебры логики представима полиномом Жегалкина единственным образом с точностью до перестановки слагаемых.

Доказательство. Если , то представима СДНФ
. (3)
В силу совокупной ортогональности совершенных конъюнкций в (3) знаки дизъюнкции можно заменить на знаки , что приведет к формуле
. (4)
Удаляя в (4) отрицания переменных по формуле , раскрывая скобки и приведя подобные члены по правилу , мы получим полином Жегалкина. Единственность представления функции полиномом следует из того, что полиномов Жегалкина под алфавитом ,…, столько же, сколько и функций от переменных, то есть . ▲

Вопрос. Чем является данная функция ?

Ваш ответ :

Произвольной функцией

Да,правильно.

Пример составления полинома Жегалкина

Пример 1. Пусть задана функция таблицей.

Представим ее СДНФ
.
Отсюда имеем
.
Раскрываем скобки:
.
Приводим подобные члены:
.
Получили полином Жегалкина.

Пример 2. Пусть задана функция формулой .

ДНФ функции состоит из двух ортогональных конъюнкций ( ), поэтому
.
Получили полином Жегалкина.

Пример 3. Для элементарных функций табл. 2 полиномы Жегалкина имеют вид:

а) для конъюнкции – ;

б) для дизъюнкции – ;

в) для суммы по – ;

г) для импликации – ;

д) для эквиваленции – ;

е) для «штрих Шеффера» – ;

ё) для «стрелки Пирса» – ;

ж) для : ;

з) для , , , – без изменений.

Вопрос. Чему равен полином Жегалкина для функции ?

Ваш ответ :

Да, правильно.

Начало формы

Теорема двойственности

Функция называется двойственной к функции .

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

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

Отношение двойственности симметрично, .

Пример 1. Двойственные функции к элементарным функциям табл. 2:
, , ,
, , ,
, , , , .

Пример 2. Является ли функция самодвойственной?
Чтобы ответить на этот вопрос, можно составить (вычислить) таблицу и по таблице проверить значения функции на противоположных наборах, и если найдется пара противоположных наборов, на которых функция принимает одинаковые значения, то функция несамодвойственна.
Можно также перейти к двойственной функции

и вычислять одновременно значения двух функций и , и как только обнаружится, что на наборе будем иметь , значит, функция несамодвойственна. В противном случае – самодвойственная, но цена этому выводу высока – ведь вычислены таблицы двух функций. Наконец, если преобразовать и к полиномам Жегалкина, и полиномы оказались разные, то и – несамодвойственна.

Теорема двойственности. Пусть имеется формула (тождество)
,
тогда верно тождество
.

Доказательство.

. ▲

С помощью этой теоремы легко доказываются некоторые тождества. Например,

1) из формулы де Моргана и теоремы двойственности следует другая формула де Моргана, так как влечет ;

2) из формулы (формула сокращения) следует , по теореме двойственности получаем другую формулу сокращения ;

3) из формулы получаем и отсюда .

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

Вопрос. Является ли функция , заданная таблично, самодвойственной?

Ваш ответ :

Нет

Правильно, так как таблица не симметрична.

Определение СКНФ

Элементарной дизъюнкцией ранга относительно алфавита назовем форму
,
где . При дизъюнкция называется совершенной.

Любая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ). Любая конъюнкция совершенных дизъюнкций называется совершенной конъюнктивной нормальной формой (СКНФ).

Теорема. Всякая функция алгебры логики представима совершенной конъюнктивной нормальной формой
.