Тема Дискретная математика

01 Булевы функции. Замкнутые и полные классы.

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела дискретная математика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#52409

Привести пример, когда $[A ∩ B] ⁄= [A ]∩ [B ]$ (при этом, напомним, всегда выполнено включение $[A ∩ B] ⊂ [A ]∩ [B ]$ ).

Показать ответ и решение

Возьмём, например, в качестве множества $A$ множество из одной булевой функции $A = {x∨ y}$ , в качестве множества $B$ тоже множество из одной функции $B = {x ∧y}$ .

Тогда, понятное дело, $A$ и $B$ не пересекаются, то есть $A ∩ B = ∅$ , а значит и подавно $[A ∩ B] = [∅ ] = ∅$ .

В то время как в пересечении $[A ]∩[B ]$ всё таки что-то лежит. Например, в $[A]$ лежит функция $f(x) = x$ . Действительно, её можно получить из дизъюнкции как $f (x) = x ∨ x$ . Аналогично, в в $[B ]$ лежит функция $f(x) = x$ . Действительно, её можно получить из конъюнкции как $f(x) = x ∧ x$ . Следовательно, $f(x) ∈ [A]∩ [B ]$ . В то время как $[A ∩B ] = ∅$ . Этот пример показывает, что бывают ситуации, когда включение $[A ∩ B] ⊂ [A ]∩ [B ]$ строгое, то есть равенство там стоять не обязано.

Ответ:

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#52410

Привести пример, когда $[A ∪ B] ⁄= [A ]∪ [B ]$ (при этом, напомним, всегда выполнено включение $[A ∪ B] ⊃ [A ]∪ [B ]$ ).

Показать ответ и решение

Возьмём, например, в качестве множества $A$ множество из одной булевой функции $A = {x∧ y}$ , в качестве множества $B$ тоже множество из одной функции $-- B = {x}$ .

Тогда, как мы знаем, система $-- A ∪B = {x ∧y,x }$ - полна, то есть $-- [x ∧y,x ] = P2$ .

Однако, понятно, что $[A ]$ будет состоять только из конъюнкций, сколь угодно длинных, то есть конъюнкций вида $xi1 ∧ xi2 ∧ ...∧ xik$ , однако ничего другого кроме таких длинных конъюнкций композициями одной только конъюнкции мы получить не сможем.

Точно так же $[B]$ будет представлять из себя только многократно навешиваемые отрицания на одну переменную, поэтому $[B ]$ состоит всего из двух функций - отрицания переменной и самой переменной, которая получится если дважды взять отрицание. То есть фактически $[B] = {x,x}$ (более чем двукратные отрицания будут сокращаться друг с дружкой, поскольку $-- x = x$ ).

Значит, в объединении $[A ]∪ [B ]$ будут лежать только сколь угодно длинные конъюнкции, переменная и её отрицание:

-- [A ]∪[B ] = {xi1 ∧ xi2 ∧ ...∧ xik,xi,xi}

А это явно не все возможные булевы функции. В то время как если разрешить композиции между функциями из $A$ и из $B$ , то есть рассмотреть $[A ∪ B ]$ , то получается, что $[A ∪ B ] = P2$ - это мы уже доказывали ранее.

Этот пример показывает, что бывают ситуации, когда включение $[A ∪ B ] ⊃ [A]∪ [B]$ строгое, то есть равенство там стоять не обязано.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 3#52411

Назовём булеву функцию $f (x1,...,xn)$ симметрической, если она не изменяет своего значения при любой перестановке своих аргументов.

То есть, иными словами, $f(σ1,...,σn ) = f(τ1,...,τn)$ , если набор $(σ1,...,σn)$ отличается от набора $(τ1,...,τn)$ лишь перестановкой.

Задача. Образует ли множество всех симметрических булевых функций замкнутый класс?

Показать ответ и решение

Давайте рассмотрим $f(x,y) = x⊕ y$ - симметрическую функцию, поскольку очевидно, что $f(x,y ) = f(y,x)$ . Кроме того, $g(z,w) = z ∨ w$ - тоже симметрическая, поскольку $g(z,w) = g(w,z)$ .

Однако $f(x,g(z,w )) = x ⊕ (z ∨ w )$ симметрической уже не является, поскольку при наборе $x = 0,z = 1,w = 1$ значение такой композиции $x⊕ (z ∨ w)$ равно 1, а если просто переставить местами входные данные, взяв, скажем $x = 1,z = 1,w = 0$ (мы переставили местами значение $x$ и $w$ ), то на таком входном наборе композиция $x⊕ (z ∨ w)$ равна 0.

Следовательно, $f(x,g(z,w))$ - не симметрическая.

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

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 4#52412

Доказать, что класс ${x ∨ y,x}$ является полным.

Показать ответ и решение

Действительно, мы можем каждую функцию из полной системы ${x ∧ y,x∨ y,x-}$ выразить через функции класса $-- {x ∨ y,x}$ . А именно, нам достаточно научиться выражать $x ∧ y$ .

Но в силу правил де Моргана: $------ x∧ y = x ∨ y$ . Следовательно, раз мы каждую функцию полной системы ${∧, ∨,x}$ умеем выражать через систему ${∨,x}$ , то, по лемме (о сводимости полных систем), система $-- {∨, x}$ - тоже полна.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 5#52414

Доказать, что класс ${x ↓ y}$ является полным, где $x ↓ y$ - так называемая стрелка Пирса, которая определяется так: $----- x ↓ y = x ∨ y$

Показать ответ и решение

Действительно, из стрелки Пирса можно вывести отрицание одной переменной как $x-= x ↓ x$ .

Далее, дизъюнкция - это $x∨ y = (x ↓ y) ↓ (x ↓ y )$ . Следовательно, системой ${x ↓ y}$ можно породить систему $-- {x ∨ y,x}$ , которая полна. А, значит, система ${x ↓ y}$ сама полна по лемме о сводимости полных систем.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 6#52415

Пусть булева функция задана своей таблицей истинности

| | | | x |y | z |f(x,y,z) | ----|--|---|---------| 0 |0 | 0 |1 | 0 |0 | 1 |0 | | | | | 0 |1 | 0 |1 | 0 |1 | 1 |1 | 1 |0 | 0 |1 | | | | | 1 |0 | 1 |1 | 1 |1 | 0 |0 | | | | | 1 |1 | 1 |1 |

Задача: Построить её полином Жегалкина.

Показать ответ и решение

f(x,y,z) = c⊕ c1x ⊕ c2y ⊕ c3z ⊕ c4xy ⊕ c5xz ⊕ c6yz ⊕ c7xyz

1. Подставляя все нули в это выражение, получаем, что, так как $f(0,0,0) = 1$ , то $c = 1$ .

2. Подставляем $f(1,0,0) = 1$ , получаем, что $1 = c ⊕ c1 = 1 ⊕ c1$ . Следовательно, $c1 = 0$ .
Аналогично, $f(0,1,0) = 1$ , поэтому $1⊕ c2 = 1$ , а потому $c2 = 0$ .
Аналогично, $f(0,0,1) = 0$ , поэтому $1⊕ c3 = 0$ , а потому $c3 = 1$ .

3. Подставляя $f(1,1,0) = 0$ получаем, что $c⊕ c1 ⊕ c2 ⊕ c4 = 1 ⊕ 0⊕ 0 ⊕ c4 = 0$ , так что $c4 = 1$ .
Аналогично, $f(0,1,1) = 1$ , поэтому $1⊕ c2 ⊕ c3 ⊕ c6 = 1⊕ 0 ⊕ 1⊕ c6 = 1$ , поэтому $c6 = 1$ .
Аналогично, $f(1,0,1) = 1$ , поэтому $1⊕ c1 ⊕ c3 ⊕ c5 = 1⊕ 0 ⊕ 1⊕ c5 = 1$ , поэтому $c5 = 1$ .

4. В конце концов $f (1,1,1) = 1$ , поэтому

1 ⊕ c1 ⊕ c2 ⊕ c3 ⊕ c4 ⊕ c5 ⊕ c6 ⊕ c7 = 1⊕ 0 ⊕ 0⊕ 1 ⊕ 1 ⊕ 1⊕ 1 ⊕ c7 = 1

Значит, $c = 0 7$ . Получаем такой полином Жегалкина:

f(x,y,z) = 1⊕ z ⊕ xy ⊕ xz ⊕ yz

Ответ:

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#52417

Построить полином Жегалкина функции

-- f(x,y,z) = xy ∨ xz ∨ xy z

Показать ответ и решение

Воспользуемся основным соотношением, верным для любых функций $g1,g2$ :

g1 ∨ g2 = g1 ⊕ g2 ⊕ g1g2

Таким образом, имеем:

xy ∨ xz ∨ xyz = (xy ⊕ xz ⊕ xyxz )∨ xyz-= (xy ⊕ xz ⊕ xyz )∨ xy(z ⊕ 1)

Здесь мы воспользовались тем, что, во-первых, $xyxz = xyz$ (поскольку $xx = x∧ x = x$ ) и, во-вторых, расписали отрицание $-- z$ как $z ⊕ 1$ .

Далее,

(xy ⊕ xz ⊕ xyz )∨ xy(z ⊕ 1) = xy ⊕ xz ⊕ xyz ⊕ xy(z ⊕ 1) ⊕ (xy ⊕ xz ⊕ xyz )(xy (z ⊕ 1)) =

= xy ⊕ xz ⊕ xyz ⊕ xyz ⊕ xy ⊕ (xy ⊕ xz ⊕ xyz )(xyz ⊕ xy) =

= xy ⊕ xz ⊕ xyz ⊕ xyz ⊕ xy ⊕ xyxyz ⊕ xyxy ⊕ xzxyz ⊕ xzxy ⊕ xyzxyz ⊕ xyzxy =

= xy ⊕ xz ⊕ xyz ⊕ xyz ⊕ xy ⊕ xyz ⊕ xy ⊕ xyz ⊕ xyz ⊕ xyz ⊕ xyz

В одном из преобразований выше мы раскрыли скобки по правилу дистрибутивности

g1 ∧ (g2 ⊕ g3) = g1g2 ⊕ g1g3

А еще мы сокращали в конъюнкциях одинаковые буковки. В конце коцнов выражение $xy ⊕ xz ⊕ xyz ⊕ xyz ⊕ xy ⊕ xyz ⊕ xy ⊕ xyz ⊕ xyz ⊕ xyz ⊕ xyz$ преобразуется как

xz ⊕ xy ⊕ xyz

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

g ⊕ g = 0

- этим мы и пользовались в последнем преобразовании.

Итого получился ответ:

xy ∨ xz ∨ xyz-= xz ⊕ xy ⊕ xyz

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 8#52418

Для каждой булевой функции действительно можно построить полином Жегалкина. Но почему он будет единственным? Может ли у какой-то булевой функции быть несколько полиномов Жегалкина?

Показать ответ и решение

Всего в полиноме Жегалкина от $n$ переменных будет $2n$ слагаемых - столько, сколько существует различных конюънкций вида $xi1...xik$ при $k = 0,1,...,n$ .

Каждая конъюнкция может либо входить в полином Жегалкина функции (коэф. перед ней 1), либо не входить (коэф. перед ней 0).

То есть всего получается $n 22$ различных полиномов Жегалкина от $n$ переменных.

Но булевых функций от $n$ переменных тоже $n 22$ .

Поэтому, если бы какой-то функции соответствовало бы 2 различных полинома Жегалкина, то какой-то функции не соответсововало бы вообще ни одного.

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

Следовательно, у каждой булевой функции полином Жегалкина единственный.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 9#54717

Пусть $P2(n)$ - все булевы функции от не более чем $n$ переменных. Вычислить, $|L ∩ P2(n)|$ , то есть посчитать количество линейных функций среди всех булевых функций из $P2(n)$ .

Показать ответ и решение

Каждая линейная функция однозначно определяется своим полиномом Жегалкина, то есть каждой $f ∈ L$ однозначно соответствует какой-то полином Жегалкина:

f ↦→ a x ⊕ a x ⊕ ...⊕ a x ⊕ a 1 1 2 2 n n 0

Где все $ai = 0$ или 1. Поэтому всего линейных булевых функций от $n$ переменных будет столько, сколькими способыми можно задать коэффициенты линейного полинома Жегалкина. Каждый из коэффициентов $a1,..,an,a0$ может быть равен 0 или 1, поэтому всего существует $2n+1$ различных вариантов для наборов коэффициентов $(a1,...,an, a0)$ . Следовательно,

|L ∩ P (n)| = 2n+1 2

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 10#54718

Пусть $P2(n)$ - все булевы функции от не более чем $n$ переменных. Вычислить, $|T0 ∩ P2(n )|$ , то есть посчитать количество функций, принимающих на нулевом наборе значение 0 среди всех булевых функций из $P2(n)$ .

Показать ответ и решение

Каждая булева функция из $T0$ должна быть равна 0 на наборе $(0,...,0)$ из всех нулей. На остальных наборах она может быть какой угодно. Остальных наборов длины $n$ из нулей и единиц есть всего $2n − 1$ , и на каждом из них наша функция может быть равна 0 или 1. Значит, всего будет $n 22− 1$ вариантов. То есть,

|T ∩ P (n)| = 22n−1 0 2

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 11#54719

Какие из следующих функций будут самодвойственными?

-- x, x,xy,0,1,x ∨y,x ⊕ y,x ⊕ y ⊕ z,m(x,y,z) = xy ∨ xz ∨ yz

Показать ответ и решение

Функция $f (x) = x$ - самодвойственна, поскольку очевидно, что $----- f(x) = x-= f (x )$ .

По аналогичным причинам $f(x) = x-$ - тоже самодвойственна.

Функция $f (x,y) = x ∧ y$ - не самодвойственна, поскольку $---- -- -- ------- ----- -- -- f(x,y) = x∧ y ⁄= f(x,y) = x ∧y = x ∨ y$

Константы 0 и 1 не будут самодвойственными, поскольку при отрицании их переменных они не меняются, а должны смениться на противоположные.

Функция $f (x,y) = x ∨ y$ - не самодвойственна, поскольку $---- -- -- ------- ----- -- -- f(x,y) = x∨ y ⁄= f(x,y) = x ∨y = x ∧ y$

Функция $f (x, y) = x ⊕ y$ - не самодвойственна, поскольку $------- f(x,y) = x⊕ y-= x ⊕ y ⁄= f(x,y) = x⊕-y-= x ⊕ y ⊕ 1$

Функция $f(x,y,z) = x⊕ y ⊕ z$ - самодвойственна, поскольку $--------- f(x,y,z-) = x-⊕ y ⊕ z-= (x ⊕ 1)⊕ (y ⊕ 1)⊕ (z ⊕ 1) = x ⊕ y ⊕ z ⊕ 1 = x ⊕ y ⊕ z$

Тот факт, что функция голосования $m (x,y,z ) = xy ∨ xz ∨ yz$ самодвойственна следует из того, что функция $m$ равна 1 тогда и только тогда, когда единиц в наборе $(x,y,z)$ больше, чем нулей. Отсюда легко понять, что если сменить значения всех переменных в наборе на противоположное, то единиц станет заведомо меньше, чем нулей, а значит функция сменит своё значение на противоположное. То есть, из этого рассуждения видно, что для $m$ выполняется соотношение самодвойственности:

--------- m (x, y,z) = m (x,y,z)

Ответ:

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#54720

Пусть $P2(n)$ - все булевы функции от не более чем $n$ переменных. Вычислить, $|S ∩ P2(n)|$ , то есть посчитать количество самодвойственных функций среди всех булевых функций из $P2(n )$ .

Показать ответ и решение

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

Рассмотрим таблицу истинности какой-то самодвойственной функции от $n$ переменных $f(x1,...,xn) ∈ S$ .

В первой половине таблицы нет двойственных наборов, на ней функцию можно задавать как угодно. Высота этой половины таблицы - равна ровно половине из $2n$ наборов, то есть $2n− 1$ .

Наоборот, значение $f$ на любом наборе из второй половины таблицы восстанавливается однозначно, так как оно должно быть противоположно значению $f$ на противоположном наборе из первой половине таблицы. Следовательно, мы задаем как угодно $f$ на $n−1 2$ наборах - для этого есть $22n−1$ вариантов, а на остальных наборах она определяется однозначно.

То есть,

2n−1 |S ∩P2 (n )| = 2

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 13#54721

Какие из следующих функций будут монотонными?

-- x,x,xy, 0,1,x∨ y,x ⊕ y,m (x, y,z) = xy ∨ xz ∨yz

Показать ответ и решение

Функция $f (x) = x$ - будет монотонной, поскольку различных наборов длины 1 всего 2, $0 ≤ 1$ и при этом $f (0) = 0 ≤ f(1) = 1$

Функция $f (x,y) = xy$ - будет монотонной, поскольку:

(0,0) ≤ (0,1) и f(0,0) = 0 ≤ f(0,1) = 0

(0,0) ≤ (1,0) и f(0,0) = 0 ≤ f(1,0) = 0

(1,0) ≤ (1,1) и f(1,0) = 0 ≤ f(1,1) = 1

(0,1) ≤ (1,1) и f(0,1) = 0 ≤ f(1,1) = 1

А других сравнимых наборов от двух переменных просто нет.

Функция $f (x,y) = x ∨ y$ - будет монотонной, поскольку:

(0,0) ≤ (0,1) и f(0,0) = 0 ≤ f(0,1) = 1

(0,0) ≤ (1,0) и f(0,0) = 0 ≤ f(1,0) = 1

(1,0) ≤ (1,1) и f(1,0) = 1 ≤ f(1,1) = 1

(0,1) ≤ (1,1) и f(0,1) = 1 ≤ f(1,1) = 1

А других сравнимых наборов от двух переменных просто нет.

Функция $f (x,y) = x ⊕ y$ - не будет монотонной, поскольку $(1,0) ≤ (1,1)$ , но $f(1,0) = 1 > f(1,1) = 0$

Функция $m (x,y,z) = xy ∨ xz ∨ yz$ будет монотонной, поскольку она зависит лишь от количества единиц в наборе, а поэтому если набор $(α ,α ,α ) ≤ (β ,β ,β ) 1 2 3 1 2 3$ , то единиц в наборе $β$ явно не меньше, а значит $f (α) ≤ f (β)$ .

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 14#54722

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

Показать ответ и решение

Раз система полная, то по необходимому условию из теоремы о функциональной полноте, она не лежит полностью ни в одном из классов $T0,T1,S,L, M$ . Следовательно, в ней найдутся $fT0/∈T0, fT1/∈T1, fS/∈S, fL/∈L, fM/∈M$ .

Но тогда, из доказательства достаточности в теореме о функциональной полноте следует, что этих не более чем пяти (т.к. некоторые из них могут совпадать) функций $fT0,fT1,fS,fL,fM$ хватит, чтобы породить все булевы функции. Их и извлечем из нашей полной системы.

Ответ:

Предыдущий раздел

Следующий раздел