Полнота множества булевых функций

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

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

Другие примеры решений о булевых функциях:

Задачи и решения о классах Поста и полноте

Задача 1. Является ли полной система булевых функций, состоящая из дизъюнкции и импликации?

Задача 2. Доказать полноту (или неполноту) приведенной системы булевых функций.

$$ f_1=x_1 wedge x_2,, f_2=0, , f_3=x_1 sim x_2.$$

Задача 3. Определить, к каким классам Поста относится $F =
eg x1 x3 vee x1
eg x3$, добавить (если это необходимо) к $F$ элементарные функции, чтобы полученное множество было полным.

Задача 4. Является ли полной система функций?

Задача 5. а) Используя эквивалентные преобразования получить тупиковую ДНФ;
б)Построить функционально полную систему функций так, чтобы эта система была базисом и содержала $f (x, y, z, p)$

$$f (x, y, z, p)= ar p downarrow y o z vee p Leftrightarrow y oplus z |x Leftarrow p$$

Задача 6. Проверить леммы о нелинейной, немонотонной и несамодвойственной функциях для функции

Задача 7. Даны функции $f$ (таблица 2) и $w$ (таблица 3).
а) Вычислить таблицу значений функции $f$.
б) Найти минимальные ДНФ функций $f$ и $w$.
в) Выяснить полноту системы $$. Если система не полна, дополнить систему функцией $g$ до полной системы.
г) Из функциональных элементов, реализующих функции полной системы $$ или $$, построить функциональные элементы, реализующие базовые функции $<vee, wedge,
eg, 0, 1>$

$$ f=((x_3 o (x_1sim x_2))oplus (overline o overline)) o (overline|overline),\ w = (0, 1, 1, 0, 0, 1, 0, 1). $$

Решение задач на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ по дискретной математике, в том числе задания о проверке полноты системы булевых функций на заказ. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 150 рублей , оформление производится в Word, срок от 2 дней.

Классы Поста. Полнота системы функций

Математик Эмиль Пост ввел следующие замкнутые классы булевых функций:

• $T_0$ — Сохраняющие константу 0
• $T_1$ — Сохраняющие константу 1
• $S$ — Самодвойственные функции
• $M$ — Монотонные функции
• $L$ — Линейные функции

Теорема Поста (о полноте): Набор булевых функций $K$ является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов $S,M,L,T0,T1$.

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

Самые известные полные системы булевых функций:

• $wedge, vee,
  eg$ — (конъюнкция, дизъюнкция, отрицание). Используется для представления в виде ДНФ и КНФ.
• $wedge, oplus, 1$ — (конъюнкция, сложение по модулю два, константа один). Используется для представления в виде полинома Жегалкина.
• Штрих Шеффера
• Стрелка Пирса

Понятие функционально полной системы

Система функций ₂₎ . /„> называется функционально полной, если любая булева функция может быть записана в виде формул через функции этой системы. Одним из способов получения полных систем является использование некоторых существующих, ранее выявленных полных систем.

Теорема 2.1. Пусть даны две системы функций: В = ₂. /„> и D = _l,q₂,.

,q_m>. Относительно этих функций известно, что В — полная система и каждая ее функция может быть выражена в виде формул через функции второй системы. В этом случае система D — тоже полная.

Доказательство. Пусть И — это произвольная функция. В силу полноты В функция h может быть выражена в виде формул над В , т. е. h = F[f_x, /₂. f_n). Но любая из функций В по условию может быть выражена через функции D, т. е. /_х = ф_х (q_v q₂. ), /₂ = q>₂ (q_v q₂. ).

Таким образом, произвольная функция h может быть выражена через функции системы D. Поэтому система D — полная.

Доказанную теорему можно использовать для доказательства полноты двух следующих систем: S_x = |л, j и S₂ = jv, j. Известно, что S = |л, v, | — полная система (это вытекает из того факта, что любую булеву функцию можно представить в КНФ и ДНФ).

Для доказательства полноты S_x и S₂ нужно установить, что недостающая относительно S операция (в Sj — дизъюнкция, в S₂ — конъюнкция) может быть выражена через две остальные. Такое подтверждение дают правила де Моргана и двойного отрицания: х_х v х₂ = х, -х₂, х, л х₂ = х_х v х₂. Следовательно, ?, и S₂ — полные системы и их называют соответственно конюнктивным и дизъюнктивным базисом Буля.

Полной является также система 5₃ = <л, ®, 1>, которая сводится к конъюнктивному базису, так как отрицание в 5, может быть выражено через операции S₂ следующим образом: х = х © 1 (проверяемся по таблице истинности функции /₆, см. табл. 2.8).

Алгебра Жегалкина

Алгебра над множеством логических функций с двумя бинарными операциями (конъюнкция и сложение по модулю два) называется алгеброй Жегалкина. В этой алгебре выполняются следующие соотношения:

Для подтверждения полноты алгебры Жегалкина представим дизъюнкцию через функции этой алгебры: xvy = x-y = xy®x®y.

Полученная формула, имеющая вид суммы произведений, называется полиномом по модулю два или полиномом Жегалкина. Для каждой логической функции может быть получен полином Жегалкина, причем единственный для данной функции. Для этого следует привести заданное выражение к форме СДНФ, исключить операции дизъюнкции и отрицания и раскрыть скобки. В частном случае, если х у = 0, то х v у = х © у.

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

Для определения значений коэффициентов вычислим левую и правую части для четырех возможных наборов входных переменных:

Содержание

Полные системы функций [ править ]

Определение:

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

Определение:

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

Определение:

Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций.

Определение:

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

Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

• функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
• самодвойственныые функции [math]S[/math] ,
• монотонные функции [math]M[/math] ,
• линейные функции [math]L[/math] .

Замкнутые классы булевых функций [ править ]

Класс функций сохраняющих ноль [math]T_0[/math] .

Определение:

Говорят, что функция сохраняет ноль, если [math]f(0, 0, ldots, 0) = 0[/math] .

Класс функций сохраняющих единицу [math]T_1[/math] .

Определение:

Говорят, что функция сохраняет единицу, если [math]f(1, 1, ldots, 1) = 1[/math] .

Класс самодвойственных функций [math]S[/math] .

Определение:

Говорят, что функция самодвойственна (англ. self-dual), если [math]f(overline,ldots,overline)=overline[/math] . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.

Класс монотонных функций [math]M[/math] .

Определение:

Говорят, что функция монотонна (англ. monotonic function) , если [math]forall i (a_i leqslant b_i) Rightarrow f(a_1,ldots,a_n)leqslant f(b_1,ldots,b_n)[/math] .

Класс линейных функций [math]L[/math] .

Определение:

Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, ldots, a_n[/math] , где [math]a_i in <0, 1>, forall i=overline<1,n>[/math] , что для любых [math]x_1, x_2, ldots, x_n[/math] имеет место равенство: [math]f(x_1, x_2, ldots, x_n) = a_0oplus a_1cdot x_1oplus a_2cdot x_2 oplusldotsoplus a_ncdot x_n[/math] .

Количество линейных функций от [math]n[/math] переменных равно [math]

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

Формулировка и доказательство критерия Поста [ править ]

Теорема:

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

[math] riangleright[/math]

Необходимость. Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным. Достаточность. Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным. Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math] ). Тогда [math] f_0(1)[/math] может принимать два значения: [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, ldots, x) = 1[/math] . [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, ldots, x) = eg x[/math] . Рассмотрим функцию, не сохраняющую один — [math]f_1[/math] (то есть функцию, для которой [math]f_1(1) = 0[/math] ). Тогда [math]f_1(0)[/math] может принимать два значения: [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, ldots, x) = 0[/math] . [math]f_1(0) = 1[/math] , тогда [math]f_1(x, x, x, ldots, x) = lnot x[/math] . Таким образом, возможны четыре варианта: Мы получили функцию [math] eg [/math] . Используем несамодвойственную функцию [math]f_s[/math] . По определению, найдется такой вектор [math]x_0[/math] , что [math]f_s(x_0) = f_s(lnot x_0)[/math] . Где [math]x_0 = (x_<01>, x_<02>, ldots, x_<0k>)[/math] . Рассмотрим [math]f_s(x^<01>>, x^<02>>, ldots, x^<0k>>)[/math] , где либо [math]x^<0i>> = x[/math] , при [math]x_ <0i>= 1[/math] . Либо [math]x^<0i>> = lnot x[/math] , при [math]x_ <0i>= 0 [/math] . Нетрудно заметить, что [math]f_s(0) = f_s(1) Rightarrow f_s = operatorname [/math] . Таким образом мы получили одну из констант. Мы получили [math] eg [/math] и [math]0 Rightarrow[/math] имеем константу, равную [math]1[/math] , поскольку [math]lnot 0 = 1[/math] . Мы получили [math] eg [/math] и [math]1 Rightarrow[/math] имеем константу, равную [math]0[/math] , поскольку [math]lnot 1 = 0[/math] . Мы получили [math]1[/math] и [math]0[/math] . Рассмотрим немонотонную функцию [math]f_m[/math] . Существуют такие [math]x_1, x_2, ldots, x_n[/math] , что [math]f_m(x_1, x_2, ldots, x_, 0 , x_, ldots, x_n) = 1[/math] , [math]f_m(x_1, x_2, ldots, x_, 1 , x_, ldots, x_n) = 0[/math] , зафиксируем все [math]x_1, x_2, ldots, x_n[/math] , тогда [math]f_m(x_1, x_2, ldots, x_, x, x_, ldots, x_n)= lnot x[/math] . В итоге имеем три функции: [math] eg [/math] , [math]0[/math] , [math]1[/math] . Используем нелинейную функцию [math]f_l[/math] . Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math] . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 land x_2 [ oplus x_1] [oplus x_2][ oplus 1][/math] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов). Рассмотрим несколько вариантов: Присутствует член [math]oplus 1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]oplus 1[/math] исчезнет. Присутствуют три члена, без [math]oplus 1[/math] : [math]g_l= x_1 land x_2 oplus x_1 oplus x_2[/math] . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] vee [/math] . Присутствуют два члена, без [math]oplus 1[/math] . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] wedge [/math] через [math] eg [/math] и [math]g_l[/math] . Например, если функция [math]g_l(x_1, x_2, ldots, x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, ldots, i_m[/math] ложны, а все остальные истины, то функцию [math] wedge [/math] можно выразить как [math]g_l([lnot]x_1, [lnot]x_2, ldots, [lnot]x_n)[/math] , где [math]lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, ldots, i_m[/math] . Присутствует один член. Выразим [math] wedge [/math] через [math] eg [/math] и [math]g_l[/math] аналогично пункту 3. В итоге получим функцию [math] eg [/math] , а также либо функцию [math] wedge [/math] , либо функцию [math] vee [/math] . Поскольку функцию [math] wedge [/math] можно выразить через [math] vee [/math] и [math] eg [/math] , а функцию [math] vee [/math] через [math] wedge [/math] и [math] eg [/math] , то мы получили базис [math] wedge [/math] , [math] vee [/math] , [math] eg [/math] . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x land lnot x[/math] . Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.

[math] riangleleft[/math]

Примеры [ править ]

Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math] , [math]T_1[/math] , [math]S[/math] , [math]M[/math] , [math]L[/math] .

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.

Широко известны такие полные системы булевых функций:

• [math]left<land,lor,
  eg
  ight>[/math] (конъюнкция, дизъюнкция, отрицание);
• [math]left<land,oplus,1
  ight>[/math] (конъюнкция, сложение по модулю два, константа один).

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

Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]left<oplus,1
ight>[/math] можно назвать базисом класса линейных функций.