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

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

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

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

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

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

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

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

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

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

$$J=\{ x\to \neg y, \neg x \wedge y \}$$

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

$$f (x, y, z, p)= \bar p \downarrow y \to z \vee p \Leftrightarrow y \oplus z |x \Leftarrow p$$

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

$$f(x)=(\overline{x_1} \vee \overline{x_2}) \to \overline{(x_3+x_1)}$$

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

$$f=((x_3 \to (x_1\sim x_2))\oplus (\overline{x_3} \to \overline{x_1}))\to (\overline{x_2}|\overline{x_3}),\\ 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, \neg$ - (конъюнкция, дизъюнкция, отрицание). Используется для представления в виде ДНФ и КНФ.
• $\wedge, \oplus, 1$ - (конъюнкция, сложение по модулю два, константа один). Используется для представления в виде полинома Жегалкина.
• Штрих Шеффера
• Стрелка Пирса