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

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 ]$ строгое, то есть равенство там стоять не обязано.

Ответ:

$A = {x∨ y}$ , $B = {x ∧ y}$

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

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

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

Задача 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]$ строгое, то есть равенство там стоять не обязано.

Ответ:

$A = {x∧ y}$ , $B = {x-}$

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

Задача 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

Ответ:

$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

Ответ:

$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

Ответ:

$2n+1$

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

Задача 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

Ответ:

$22n−1$

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

Задача 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

Ответ:

$22n−1$

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

Задача 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$ хватит, чтобы породить все булевы функции. Их и извлечем из нашей полной системы.

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

Задача 15#105106

Докажите, что система

{x ∧y,x ⊕ y}

- полна в $T0$ .

Показать доказательство

Ясно, что функции, лежащие в $T0$ - это те и только те функции, чей полином Жегалкина имеет нулевой свободный член. То есть

} T0 = {f | полином Ж егалкина f им еет вид P(x1,...,xn) = a1x1 ⊕ ...+ ⊕a12...nx1...xn

Но ясно, что любой полином Жегалкина без свободного члена можно породить лишь конъюнкцией $∧$ и сложением по модулю 2 $⊕$ . Следовательно, система ${ } x∧ y,x⊕ y$ - полна в $T0$ , т.к. она порождает всё $T0$ .

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

Задача 16#105107

Докажите, что система

{x∧ y,x → y}

- полна в $T1$ .

Показать доказательство

Пусть нам известно, что система ${x∧ y,x⊕ y}$ - полна в $T0$ .

Однако, если $f (x ,...,x ) 1 n$ - произвольная функция из класса $T 1$ , то функция

---------- g(x1,...,xn) = f(x1,...,xn)

- обязательно лежит в $T 1$ .

Более того, верно и обратное, то есть мы можем получить любую функцию $g(x1,...,xn) ∈ T1$ из некоторой функции $f(x1,...,xn) ∈ T0$ , навешивая отрицания на ее переменные, а также на всю функцию.

Поэтому, если любую функцию из $T0$ можно породить при помощи $x ∧y$ и $x⊕ y$ , то любую функцию из $T1$ можно породить при помощи двойственных к порождающим функциям $T0$ , то есть с помощью:

----- x∧ y = x ∨y

x⊕-y-= x⊕ y ⊕ 1 = (x → y)∧ (y → x)

Но раз так, то при помощи системы

{x∧ y,x → y}

можно породить все $T 1$ , потому что из них можно собрать $(x → y)∧ (y → x)$ (просто берем конъюнкцию импликации в одном и в другом порядке), а также $x ∨y$ (а именно, она получается как $(x → y) → y$ ). А через них, как мы видели выше, уже всё $T1$ выражается.