Вопросы и задачи

6.1. Найти число дуг в булевой n-сети.

6.2. Доказать, что объединение двух соседних граней размерности n - k булева куба Bⁿ является гранью размерности n - k + 1. Как найти направление этой грани?

6.3. Найти число вершин k-слоя булева куба Bⁿ.

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

а) (х → у) ∨ (х → (х · у));

б) (х → (х · у)) → (x ∨ z);

в) (х ·(у → х))→ x;

г) (х → (у → z)) → ((х → у) → (х → z));

д) (x·(y ∨ x))·((y → x) ∨ y).

6.5. Доказать, что если высказывания U и (U ⇒ В) тождественно истинны, то высказывание В тождественно истинно.

6.6. Доказать, что если формулы (U ∨ В) и (U ∨ W) тождественно истинны, то формула (В ∨ W) тождественно истинна.

6.7. Найти фиктивные переменные функции f, заданной вектором значений:

а) f = (0,0,1,1,0,0,1,1);

б) f = (0,0,1,1,1,1,0,0).

6.8. Показать, что х является фиктивным переменным функции f, представленной формулами:

а) f = ((z → у) ∨ х)(у → x)zx;

б) f = ((х ∨ y)(x ∨ z) → (x → yz))y.

6.9. Доказать, что для любой булевой функции f от n переменных имеет место следующее равенство:

f(x₁,...,x_i,...,x_n) = x_if(x₁,...,1,...,x_n) ∨ x _if(x₁,...,0,...,x_n).

(Это равенство называют разложением функции f по переменному x_i.)

6.10. Пусть булевы функции f и g имеют одно и то же число существенных переменных, равное r. Тогда каждый набор α˜ ∈ {0, 1}^r однозначно определяет набор значений существенных переменных каждой из функций. Пусть для любого такого α˜ значения функций f и g на соответствующих наборах своих существенных переменных равны. Следует ли отсюда, что эти функции равны?

6.11. Используя алгоритм Квайна - Мак-Клоски, найти минимальные ДНФ для функций:

а) f = (0,1,1,0,1,0,0,1);

б) f = (1,0,0,1,0,0,1,1);

в) f = {1, 3, 4, 7, 8, 11, 14, 15};

г) f = {2, 4, 6, 9, 10, 11, 13}.

6.12. Каждый из четырех членов комитета голосует "за", нажимая на кнопку. Решение считается принятым, когда не менее трех членов комитета голосуют "за". Найти минимальную ДНФ для функции голосования.

6.13. Определить число булевых функций от n переменных: а) сохраняющих константу (0 или 1); б) самодвойственных; в) несамодвойственных; г) линейных.

6.14. Доказать, что замыкание множества функций, состоящего из дизъюнкции и суммы по модулю 2, совпадает с классом Т₀.

6.15. Доказать, что множество Т₀ ∩ T₁ является замыканием одноэлементного множества {f = ху ⊕ z ⊕ t}.

6.16. Доказать, что число всех монотонных функций от n переменных равно числу всех антицепей булева куба размерности n. Одноэлементное множество считать антицепью.

6.17. Доказать, что сокращенная ДНФ, представляющая монотонную функцию, является минимальной.

6.18. Доказать, что любая монотонная функция, отличная от константы, может быть представлена ДНФ без отрицаний.

6.19. Доказать, что в булевом кубе размерности n существует антицепь, мощность которой составляет C^[n/2]n. Используя этот результат, доказать, что число монотонных функций от n переменных не меньше 2^C[n/2]n

6.20. Доказать, что число монотонных функций от n переменных не меньше

У к а з а н и е: используйте результаты задач 6.3 и 6.16.

6.21. Методом неопределенных коэффициентов найти полином Жегалкина для функций:

а) f = (0, 1, 1, 0, 1, 0, 0, 1);

б) f = (х₁|x₂) ↓ х₁;

в) f = (1, 0, 1, 0, 0, 0, 1, 1);

г) f = (1001 11000001 1000).

6.22. Выяснить, являются ли самодвойственными следующие функции:

а) xy(z(y → х)) → (x ~ у);

б) (((x ∨ y) ~ z) ~ (у ~ z)) → (x ∨ z);

в) f = (01101001);

г) f = (10101011);

д) f = (1100100101101100).

Для несамодвойственных функций найти двойственные функции.

6.23. Выяснить, полно ли множество булевых функций F:

а) F = {f₁ = x, f₂ = х(у ~ z) ~ yz, f₃ = х ⊕ y ⊕ z};

б) F = {f₁ = xy ⊕ yz ⊕ zt, f₂ = 0, f₃ = 1, f₄ = x ∨ y};

в) F = {f₁ = 0110, f₂ = (11000011), f₃ = (10010110)};

г) F = {f₁ = х ∨ y, f₂ = (1001101111110110)}.

Для полного множества F построить формулы над F, представляющие элементы стандартного базиса и базиса Жегалкина. Реализовать эти формулы схемами из функциональных элементов.

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

6.25. Проверить полноту множества F, состоящего из функций f₁ = ху ∨ xz, f₂ = х → у, 0 и х ⊕ zy. Выделить в нем всевозможные базисы.