Функция равна нулю только на наборе (1, 1, 0), поэтому

f(x₁ x₂ x₃)=x₁ Úx₂ Úx₃ =x₁⁰Úx₂⁰Úx₃¹= Ú Ú x₃

 

31. Понятие полинома логической функции (полинома Жегалкина). Понятие линейной логической функции.

 

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

Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде

или в более формализованном виде как

Примеры полиномов Жегалкина:

 

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

1. Хотя бы одна функция, не сохраняющая 0.

2. Хотя бы одна функция, не сохраняющая 1.

3. Хотя бы одна нелинейная функция.

4. Хотя бы одна немонотонная функция.

5. Хотя бы одна несамодвойственная функция.

Этому требованию отвечает система функций . На её основе и строятся полиномы Жегалкина.

По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных штук. При этом конъюнкций вида существует ровно 2ⁿ, так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

Алгоритм построения полинома Жигалкина:

Метод преобразований

1. Построить СДНФ данной булевой функции.

2. Заменить дизъюнкцию в полученной СДНФ на сложение по модулю два.

3. Сделать замену: .

4. Раскрыть скобки, пользуясь дистрибутивностью конъюнкции относительно сложения по модулю два: .

5. Сократить лишние сомножители и слагаемые, пользуясь эквивалентностями:

 

Многочлен Жигалкина называется нелинейным, если он содержит конъюкции переменных, а если он не содержит конъюнкции переменных, то он называется линейным.

Функция f(x1,x2,..x_n) называется линейной, если имеет вид a₀⊕a₁x₁⊕…⊕a_nx_n, и не линейным в противном случае.

Чтобы узнать, линейна ли функция, надо выразить ее через полином Жегалкина и посмотреть, не встречается ли там операция &. Если нет, то функция линейна. Для функций от 1 и 2 переменных мы уже приводили формулы, выражающие их через &, и константы.

 

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

 

Переменная или называется литералом (или буквой).

 

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

 

Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией. Существуют два направления минимизации: 1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ. 2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу). При этом следует учесть, что ни один из способов минимизации не универсален.

Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:

· на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;

· на втором этапе — переход от сокращённой формы к минимальной форме.