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

02 Булевы функции. Таблицы истинности. Булев куб.

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

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

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

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

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

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

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

Задача 1#50803

Действительно ли любую булеву функцию можно представить в СДНФ, то есть в виде

∨ f(x1,...,xn) = xσ11∧ x σ22 ∧ ...x σnn по всем наборам (σ1,...,σn) на которых f равна 1

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

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

Однако если мы рассмотрим функцию, тождественно равную нолю:

f(x ,...,x ) = 0 н а лю бом набор е (x ,...,x ) 1 n 1 n

То справа получится пустая дизъюнкция - ведь нет ни одного набора, на котором функция была бы равна 1. Поэтому формально тождественный ноль выразить в СДНФ нельзя.

Комментарий. Однако, через систему ${∧,∨, x}$ тождественный ноль все таки выражается, например, как $-- x∧ x$ .

Ответ:

Нет

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

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

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

Задача 2#50811

Написать СДНФ для функции $--------- f (x1,x2,x3 ) = (x1 ∧x2) ∨ (x2 → x3)$ .

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

Для начала, запишем таблицу истинности этой функции.

| | |--------- | x1 |x2 |x3 |(x1 ∧ x2)∨ (x2 → x3)| -----|---|----|--------------------| 0 |0 |0 |1 | 0 |0 |1 |1 | | | | | 0 |1 |0 |1 | 0 |1 |1 |1 | 1 |0 |0 |1 | | | | | 1 |0 |1 |1 | 1 |1 |0 |0 | | | | | 1 |1 |1 |1 |

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

Тогда для такой $f$ СДНФ будет выглядеть так: $--- --- --- --- --- f (x1,x2,x3) = (x1 ∧ x2 ∧ x3)∨ (x1 ∧ x2 ∧ x3)∨$
$--- --- --- --- --- --- ∨ (x1 ∧ x2 ∧ x3) ∨(x1 ∧ x2 ∧ x3)∨ (x1 ∧ x2 ∧ x3)∨ (x1 ∧x2 ∧ x3)∨ (x1 ∧ x2 ∧ x3)$ .

Ответ:

$f(x1,x2,x3) = (x1 ∧ x2-∧ x3)∨ (x1 ∧ x2-∧ x3)∨$
$--- --- --- --- --- --- ∨ (x1 ∧ x2 ∧ x3) ∨(x1 ∧ x2 ∧ x3)∨ (x1 ∧ x2 ∧ x3)∨ (x1 ∧x2 ∧ x3)∨ (x1 ∧ x2 ∧ x3)$

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

Задача 3#50812

Написать таблицу истинности и СДНФ для функции $-------------------- f(x1,x2,x3) = (x1 ⊕ x3) → (x1 ∨ x2)$

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

Таблица истинности:

| | | -------------------- | x1 |x2 |x3 | (x1 ⊕ x3) → (x1 ∨ x2) | -----|---|---|----------------------| 0 |0 |0 | 0 | 0 |0 |1 | 1 | | | | | 0 |1 |0 | 0 | 0 |1 |1 | 0 | 1 |0 |0 | 0 | | | | | 1 |0 |1 | 0 | 1 |1 |0 | 0 | | | | | 1 |1 |1 | 0 |

Тогда для такой $f$ СДНФ будет выглядеть так:

f(x1,x2,x3) = x1-∧ x2 ∧ x3

Ответ:

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

Задача 4#50816

Можно ли функцию $x1 ⊕ x2$ выразить, пользуясь только функциями $x1 ∧ x2$ и $x1 ∨ x2$ ?

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

Заметим, что $x1 ∧ x2$ и $x1 ∨x2$ обладают таким свойством, что они равны 1, если обе $x1$ и $x2$ равны 1.

Следовательно, и любая функция, составленная при помощи композиции из конъюнкций и дизъюнкций, тоже будет на наборе $(1,1)$ принимать значение единица.

Однако $x1 ⊕ x2$ на наборе $(1,1)$ принимает значение ноль.

Следовательно, $x1 ⊕ x2$ нельзя выразить никакой композицией $x1 ∧ x2$ и $x1 ∨ x2$ .

Ответ:

Нет

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

Задача 5#50817

Доказать, что функция

(x1 → x2)∨ (x2 → x1)

принимает значение 1 на любом наборе входных данных.

Комментарий. Этот поучительный пример говорит о том, что было бы поспешно интерпретировать функцию импликации $x → y$ как союз $”$ ЕСЛИ $x$ , ТО $y$ $”$ . Поскольку странно считать, что какие бы два высказывания мы ни взяли, либо первое следует из второго, либо второе из первого. А если функция $(x1 → x2 )∨ (x2 → x1)$ принимает всегда значение 1, то это можно было бы по неосторожности прочесть именно так.

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

Действительно, построив таблицу истинности, убеждаемся:

|---|----|----------------------| |x1-|-x2-|(x1-→-x2)-∨-(x2-→--x1)-| | 0 | 0 | 1 | |---|----|----------------------| |-0-|-1--|----------1-----------| | 1 | 0 | 1 | |---|----|----------------------| --1---1-------------1-----------|

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

Задача 6#82377

Для функции $f(x1,x2,x3)$ , заданной своей таблицей истинности

| | | | x1 |x2 | x3 |f(x1,x2,x3) | ----|---|----|------------| 0 |0 | 0 |1 | 0 |0 | 1 |0 | | | | | 0 |1 | 0 |1 | 0 |1 | 1 |0 | 1 |0 | 0 |0 | | | | | 1 |0 | 1 |0 | 1 |1 | 0 |0 | | | | | 1 |1 | 1 |0 |

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

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

1. Поймем вначале, какие переменные у нее являются существенными, а какие - нет.

Во-первых, легко заметить, что $x1$ - существенная переменная, поскольку есть два набора

(0,0,0) и (1,0,0)

отличающиеся только в первой координате, на которых функция различна:

f (0,0,0) = 1, f(1,0,0) = 0

Далее, $x 3$ - тоже существенная переменная, поскольку есть два набора

(0,0,0) и (0,0,1)

отличающиеся только в третьей координате, на которых функция различна:

f (0,0,0) = 1, f(0,0,1) = 0

Переменная $x2$ - наоборот, несущественная. Поскольку на всех возможных наборах, отличающихся только во второй координате:

(0,0,0) и (0,1,0)

(0,0,1) и (0,1,1)

(1,0,0) и (1,1,0)

(1,0,1) и (1,1,1)

наша функция совпадает (на первых двух наборах она равна единице, а на всех остальных парах наборов она равна нулю).

Следовательно, переменная $x2$ - несущественная.

В таком случае, от переменной $x2$ можно насильно избавиться, и получить уже функцию от двух переменных $x ,x 1 3$ , которую мы не будем отличать от исходной функции $f$ .

Как избавиться от $x2$ ? Ну, просто вычеркнуть столбец $x2$ из таблицы истинности нашей функции:

| | | x1 |x3 |f (x1,x3) | -----|---|---------| 0 |0 |1 | 0 |1 |0 | | | | 0 |0 |1 | 0 |1 |0 | | | | 1 |0 |0 | 1 |1 |0 | | | | 1 |0 |0 | 1 |1 |0 |

И что же, на этом все? Нет конечно. Должна ведь получиться таблица истинности функции от двух переменных, а у нас получилась пока ерунда - функция уже от двух переменных, но таблица у неё слишком $”$ длинная $”$ .

Теперь надо склеить полностью совпадающие столбцы таблицы в один (а совпадающие столбцы обязательно будут, это, собственно, и означает, что $x2$ была фиктивной). Получим такую таблицу истинности:

| | | x1 |x3 |f (x1,x3) | -----|---|---------| 0 |0 |1 | 0 |1 |0 | | | | 1 |0 |0 | 1 |1 |0 |

2. Как теперь задать эту функцию формулой? Во-первых, можно просто построить её СДНФ - это вообще универсальный способ перейти от таблице истинности к формуле. Но можно поступить быстрее. Ясно, что если взять отрицание этой функции:

| | | x1 |x3 | ¬f(x1,x3) | ----|---|-----------| 0 |0 | 0 | 0 |1 | 1 | | | | 1 |0 | 1 | 1 |1 | 1 |

То мы получим обыкновенную дизъюнкцию $x1 ∨ x3$ . Поэтому наша исходная функция - это отрицание дизъюнкции, т.к. если $¬f(x1,x3) = x1 ∨ x3$ , то

f(x1,x3) = ¬(x1 ∨ x3)

(здесь мы воспользовались законом двойного отрицания).

Ответ:

$f(x1,x3) = ¬(x1 ∨ x3)$ , а переменная $x2$ - несущественная.

Курсы

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

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

Задача 7#82378

a) Из теоремы о существовании СДНФ вывести, что любую (точнее, почти любую) булеву функцию можно разложить в виде

f(x ,...,x ) = ∧ xτ1∨ xτ2∨ ...xτn 1 n 1 2 n по всем наборам (τ1,...,τn) на которых f равна 0

где $({ τ x если τ = 0 x = ( -- x если τ = 1$ .

Такой вид называется совершенной конъюнктивной нормальной формой функции $f$ .

b) Представить в СКНФ булеву функцию $f (x1, x2,x3)$ , заданную формулой

f (x1,x2,x3) = (x1 → x2) ∧x3

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

a) Поступим аналогично с СДНФ. Во-первых, очевидно, что если функция $ψ$ равна нулю только на наборе $(τ1,τ2,...,τn)$ , то

ψ(x ,...,x ) = x τ1 ∨x τ2 ∨ ...xτn 1 n 1 2 n

(просто-напросто левая и правая части равенства равны нулю одновременно, и равны единице одновременно).

Но тогда верен и более общий факт. $”$ Любую $”$ функцию $f : Bn → B$ можно представить в виде

∧ τ1 τ2 τn f(x1,...,xn ) = x1 ∨ x2 ∨ ...xn по всем наборам (τ1,...,τn) на которых f равна 0

где $( τ { x если τ = 0 x = ( -- x если τ = 1$ .

Почему любая стоит в кавычках? Из этого правила есть ровно одно исключение. По аналогии с тем, как в СДНФ не получится выразить тождественно нулевую функцию, в нашем случае, то есть в СКНФ, не получится выразить тождественно единичную функцию. Все остальные - можно.

b) Как же выразить эту функцию

f (x1,x2,x3) = (x1 → x2) ∧x3

в СКНФ? Надо для начала составить её таблицу истинности.

| | | | x1 |x2 |x3 |(x1 → x2)∧ x3 | -----|---|----|--------------| 0 |0 |0 |0 | | | | | 0 |0 |1 |1 | 0 |1 |0 |0 | | | | | 0 |1 |1 |1 | 1 |0 |0 |0 | | | | | 1 |0 |1 |0 | 1 |1 |0 |0 | | | | | 1 |1 |1 |1 |

А далее, чтобы выписать СКНФ нашей функции, мы должны просто написать конъюнкцию по всем наборам, на которых $f$ равна 0 всевозможных дизъюнкций переменных или их отрицаний, причем в дизъюнкцию переменная входит с отрицанием, если соответствующая координата в соответствующем наборе равна единице. Получаем:

--- --- --- --- --- --- f(x1,x2,x3) = (x1 ∨ x2 ∨x3 )∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧(x1 ∨ x2 ∨ x3)∧ (x1 ∨x2 ∨ x3)

Интенсивы

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