§ 10. Булева (переключательная) функция
Булевой переменной назовем переменную, которая принимает одно из двух возможных значений. Ясно, что высказывание можно рассматривать как частный случай булевой переменной, ибо высказывание принимает только одно из двух значений: Л или И .
Функция ƒ (А 1 ,А 2 . A n ) называется булевой (переключательной)
функцией , если она может принимать одно из двух возможных значений, когда ее аргументы принимают тоже одно из этих двух значений.
Очевидно, что истинностная функция является частным случаем булевой функции.
Значения булевой функции и булевых переменных можно обозначать любыми символами, например, + и -, либо 1 и 0 . В дальнейшем значения булевых переменных и функций будем обозначать через 1 и 0 .
При исследовании высказываний, истинностных функций и пропозициональных форм нигде не использовалась природа значений «истина» ( И ) и «ложь» ( Л ). Тогда всюду И и Л можно рассматривать как символы, служащие для различения двух значений. Поэтому И можно переобозначить через 1 , а Л — через 0 , и все результаты, полученные для истинностных функций, будут справедливы для булевых функций. Более того, булевы функции можно отождествить с истинностными функциями.
Выражения ( А), (А&В), (А В), (А В), (А ≡ В) можно рассматривать как булевы функции, значения которых определяются по таблицам построенным для пропозициональных форм ( А), (А&В), (А В), (А В), (А ≡ В) соответственно, если в них всюду заменить И на 1 , а Л на 0 . Эти таблицы будем тоже называть таблицами истинности.
Очевидно, что пропозициональную форму можно рассматривать как булеву функцию, значения которой определяются по таблицам истинности.
Можно показать, что число различных булевых функций от n
переменных равно N= 2 2 n . Например: для n =1 N =4, для n =2 N =16, для n =3 N =256, для n =5 N — более четырех миллиардов.
Булеву функцию можно задать с помощью таблиц, аналитически, графически и т.п.
§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
Алгебра высказываний находит весьма широкое практическое применение. Рассмотрим приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем.
Контакты (переключатели) можно рассматривать как переменные и обозначать буквами А, В, С,. .. или теми же буквами с числовыми индексами: А 1 ,А 2 . В 1 ,В 2 . С 1 ,С 2 . . Каждая из переменных может принимать одно и только одно из двух возможных значений: если контакт А разомкнут, то по определению А=0 , если контакт А замкнут, то по определению А=1 .
Под контактной (переключательной) схемой понимается схема,
состоящая из замкнутых и разомкнутых контактов, соединенных параллельно, или последовательно, или смешанным образом.
Отрицанием контакта А называется контакт, равный 1 , если А=0 , и равный 0 , если А=1 . Отрицание контакта А обозначается через А .
Очевидно, что последовательное соединение двух контактов А и В моделируется конъюнкцией переменных А и В , а параллельное соединение — их дизъюнкцией, см. Рис. 1.1.
Определение булевой функции
Элементы булева множества [math]1[/math] и [math]0[/math] обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения [math]B^n[/math] называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается [math]P_2[/math] , а от n переменных — [math]P_2(n)[/math] . Булевы функции названы так по фамилии математика Джорджа Буля.
Основные сведения
| Определение: |
| А́рность (англ. arity) функции — количество ее аргументов. |
Каждая булева функция арности [math]n[/math] полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины [math]n[/math] . Число таких векторов равно [math]2^n[/math] . Поскольку на каждом векторе булева функция может принимать значение либо [math]0[/math] , либо [math]1[/math] , то количество всех n-арных булевых функций равно [math]^n[/math] . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
| Таблица истинности | |||||
|---|---|---|---|---|---|
| [math]x_1[/math] | [math]x_2[/math] | [math]\ldots[/math] | [math]x_n[/math] | [math]f(x_1,x_2,\ldots,x_n)[/math] | |
| [math]0[/math] | [math]0[/math] | [math]\ldots[/math] | [math]0[/math] | [math]f(0,0,\ldots,0)[/math] | |
| [math]1[/math] | [math]0[/math] | [math]\ldots[/math] | [math]0[/math] | [math]f(1,0,\ldots,0)[/math] | |
| [math]0[/math] | [math]1[/math] | [math]\ldots[/math] | [math]0[/math] | [math]f(0,1,\ldots,0)[/math] | |
| [math]1[/math] | [math]1[/math] | [math]\ldots[/math] | [math]0[/math] | [math]f(1,1,\ldots,0)[/math] | |
| [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | [math]\vdots[/math] | |
| [math]0[/math] | [math]1[/math] | [math]\ldots[/math] | [math]1[/math] | [math]f(0,1,\ldots,1)[/math] | |
| [math]1[/math] | [math]1[/math] | [math]\ldots[/math] | [math]1[/math] | [math]f(1,1,\ldots,1)[/math] | |
Практически все булевы функции малых арностей ( [math]0, 1, 2[/math] и [math]3[/math] ) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной (англ. dummy variable).
Нульарные функции
При [math]n = 0[/math] количество булевых функций равно [math]^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.
Унарные функции
При [math]n = 1[/math] число булевых функций равно [math]^1 = 2^2 = 4[/math] .
Таблица значений булевых функций от одной переменной:
| Функции от одной переменной | ||||
|---|---|---|---|---|
| [math]0[/math] | [math]x[/math] | [math]\neg x[/math] | [math]1[/math] | |
| 0 | [math]0[/math] | [math]0[/math] | [math]1[/math] | [math]1[/math] |
| 1 | [math]0[/math] | [math]1[/math] | [math]0[/math] | [math]1[/math] |
| Сохраняет 0 | ✓ | ✓ | ||
| Сохраняет 1 | ✓ | ✓ | ||
| Самодвойственная | ✓ | ✓ | ||
| Монотонная | ✓ | ✓ | ✓ | |
| Линейная | ✓ | ✓ | ✓ | ✓ |
Названия булевых функций от одной переменной:
| Обозначение | Название |
|---|---|
| [math]0[/math] | тождественный ноль, тождественная ложь, тождественное «НЕТ» |
| [math]x[/math] | тождественная функция, логическое «ДА», «YES»(англ.) |
| [math]\bar x,\ \neg x,\ x'[/math] | отрицание, логическое «НЕТ», «НЕ», «НИ», «NOT»(англ.), «NO»(англ.) |
| [math]1[/math] | тождественная единица, тождественная истина, тождественное «ДА», тавтология |
Бинарные функции
При [math]n = 2[/math] число булевых функций равно [math]^2 = 2^4 = 16[/math] .
Таблица значений булевых функций от двух переменных:
| Функции от двух переменных: | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| x | y | [math]0[/math] | [math]x \land y[/math] | [math]x \nrightarrow y[/math] | [math]x[/math] | [math]x \nleftarrow y[/math] | [math]y[/math] | [math]x \oplus y[/math] | [math]x \lor y[/math] | [math]x \downarrow y[/math] | [math]x = y[/math] | [math]\neg y[/math] | [math]x \leftarrow y[/math] | [math]\neg x[/math] | [math]x \rightarrow y[/math] | [math]x \triangledown y[/math] | [math]1[/math] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Сохраняет 0 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
| Сохраняет 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
| Самодвойственная | ✓ | ✓ | ✓ | ✓ | |||||||||||||
| Монотонная | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
| Линейная | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
Названия булевых функций от двух переменных:
| Обозначение | Другие обозначения | Название |
|---|---|---|
| [math]0[/math] | тождественный ноль, тождественная ложь, тождественное «НЕТ» | |
| [math]x \land y[/math] | [math]x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y), x [/math] И [math]y,[/math] И [math](x, y)[/math] | 2И, конъюнкция |
| [math]x \nrightarrow y[/math] | [math]x \gt y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)[/math] | больше, инверсия прямой импликации |
| [math]x[/math] | [math]YES1(x,y),[/math] ДА1 [math](x, y)[/math] | первый операнд |
| [math]x \nleftarrow y[/math] | [math]x \lt y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)[/math] | меньше, инверсия обратной импликации |
| [math]y[/math] | [math]YES2(x, y),[/math] ДА2 [math](x, y)[/math] | второй операнд |
| [math]x \oplus y[/math] | [math]x + _2 y,\ x \not = y,\ x \gt \lt y,\ x \lt \gt y,\ x\ XOR\ y,\ XOR(x,y)[/math] | сложение по модулю 2, не равно, ксор, исключающее «или» |
| [math]x \lor y[/math] | [math]x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),[/math] [math]x [/math] ИЛИ [math]y,[/math] ИЛИ [math](x, y)[/math] | 2ИЛИ, дизъюнкция |
| [math]x \downarrow y[/math] | [math]x\ NOR\ y,\ NOR(x,y)[/math] [math]x [/math] ИЛИ-НЕ [math]y,[/math] ИЛИ-НЕ [math](x, y)[/math] | НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса |
| [math]x = y[/math] | [math]x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y[/math] | равенство, эквивалентность |
| [math]\neg y[/math] | [math]NOT2(x, y),\ y’,\ \bar,[/math] НЕ2 [math](x, y)[/math] | отрицание (негация, инверсия) второго операнда |
| [math]x \leftarrow y[/math] | [math]x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)[/math] | больше или равно, обратная импликация (от второго аргумента к первому) |
| [math]\neg x[/math] | [math]NOT1(x,y),\ x’,\ \bar,[/math] НЕ1 [math](x, y)[/math] | отрицание (негация, инверсия) первого операнда |
| [math]x \rightarrow y[/math] | [math]x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)[/math] | меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму) |
| [math]x \triangledown y[/math] | [math]x \mid y,\ x\ NAND\ y,\ NAND(x,y),[/math] [math]x [/math] И-НЕ [math]y,[/math] И-НЕ [math](x, y)[/math] | НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера |
| [math]1[/math] | тождественная единица, тождественная истина, тождественное «ДА», тавтология |
Тернарные функции
При [math]n = 3[/math] число булевых функций равно [math]^3 = 2^8 = 256[/math] . Некоторые из них определены в следующей таблице:
| Таблица истинности некоторых тернарных функций | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [math]x[/math] | [math]y[/math] | [math]z[/math] | [math]x \downarrow y \downarrow z[/math] | [math]\neg (\geq 2(x,y,z))[/math] | [math]x \not = y \not = z[/math] | [math]x \mid y \mid z[/math] | [math]min(x,y,z)[/math] | [math]x=y=z[/math] | [math]x \oplus y \oplus z[/math] | [math]\geq 2(x,y,z)[/math] | [math]f_1[/math] | [math]f_2[/math] | [math]max(x,y,z)[/math] |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Названия булевых функций трех переменных:
| Обозначения | Другие обозначения | Названия |
|---|---|---|
| [math]x \downarrow y \downarrow z[/math] | [math]\downarrow (x,y,z) = Webb_2 (x,y,z)[/math] | 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса |
| [math]\neg (\geq 2(x,y,z))[/math] | Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией | |
| [math]x \not = y \not = z[/math] | [math][\not =(x,y,z)] = NE(x,y,z)[/math] | Неравенство |
| [math]x \mid y \mid z[/math] | [math]\mid(x,y,z)[/math] | 3-И-НЕ, штрих Шеффера |
| [math]x \land y \land z[/math] | [math]\land (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z) = \lt br/\gt (x[/math] И [math] y[/math] И [math] z) = [/math] И [math](x,y,z)[/math] | 3-И, минимум |
| [math]x=y=z[/math] | [math][=(x,y,z)] = EQV(x,y,z)[/math] | Равенство |
| [math]x \oplus y \oplus z[/math] | [math]x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)[/math] | Тернарное сложение по модулю 2 |
| [math]\geq 2(x,y,z)[/math] | [math](x [/math] И [math]y) [/math] ИЛИ [math](y[/math] И [math] z)[/math] ИЛИ [math](z [/math] И [math] x)[/math] | переключатель по большинству, 3-ППБ, мажоритарный клапан |
| [math]f_1[/math] | Разряд займа при тернарном вычитании | |
| [math]f_2[/math] | Разряд переноса при тернарном сложении | |
| [math]x+y+z[/math] | [math]+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) = (x [/math] ИЛИ [math] y [/math] ИЛИ [math] z) = [/math] ИЛИ [math](x,y,z)[/math] | 3-ИЛИ, максимум |
Представление функции формулой
| Определение: |
| Если выбрать некоторый набор булевых функций [math]A[/math] , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula). |
Например, если [math]A = \left\<\land,\neg\right\>[/math] , то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]
Тождественность и двойственность
| Определение: |
| Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. |
Тождественность функций f и g можно записать, например, так:
[math]f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)[/math]
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
| [math]\overline=1[/math] | [math]\overline=0[/math] | [math]\overline<\overline |
[math]x \land y=y \land x\![/math] | [math]x\lor y=y \lor x[/math] |
| [math]0 \land x=0\![/math] | [math]1 \land x=x\![/math] | [math]0 \lor x=x[/math] | [math]1\lor x=1[/math] | [math]x \land x=x \lor x=x[/math] |
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
| [math]x \land \overline=0[/math] | [math]x \lor \overline=1[/math] |
| [math]\overline=\overline\lor\overline[/math] | [math]\overline\land\overline=\overline |
(законы де Моргана) |
[math]x \land (y\lor z)=(x \land y)\lor (x \land z)[/math]
[math]x \lor (y \land z)=(x\lor y) \land (x\lor z)[/math] (дистрибутивность конъюнкции и дизъюнкции)
| Определение: |
| Функция [math]g(x_1,x_2,\dots,x_n)[/math] называется двойственной (англ. duality) функции [math]f(x_1,x_2,\dots,x_n)[/math] , если [math]f(\overline,\overline,\dots,\overline)=\overline[/math] . |
Легко показать, что в этом равенстве [math]f[/math] и [math]g[/math] можно поменять местами, то есть функции [math]f[/math] и [math]g[/math] двойственны друг другу. Из простейших функций двойственны друг другу константы [math]0[/math] и [math]1[/math] , а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Суперпозиции
Основная статья: Суперпозиции
| Определение: |
| Суперпозиция функций, композиция функций (англ. function composition) — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. |
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Пусть нам дан некоторый набор булевых функций [math]K[/math] . Получить новую функцию, являющеюся композицией функций из [math]K[/math] , мы можем следующими способами:
- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Полнота системы, критерий Поста
Основная статья: Теорема Поста о полной системе функций
| Определение: |
| Замыкание множества функций (англ. сlosure) — подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества. |
| Определение: |
| Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций. |
Американский математик Эмиль Пост [1] сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
- самодвойственныые функции [math]S[/math] ,
- монотонные функции [math]M[/math] ,
- линейные функции [math]L[/math] .
Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math] , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций [math]\Sigma = \
- Как построить по данной функции представляющую её формулу?
- Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
- В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Основная статья: ДНФ
Определение: Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов. Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.
Примеры ДНФ:
[math]f(x,y,z) = (x \land y) \lor (y \land \neg )[/math] .
[math]f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg) \lor (x \land \neg ) [/math] .
Конъюнктивная нормальная форма (КНФ)
Основная статья: КНФ
Определение: Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.
[math]f(x,y,z) = (x \lor y) \land (y \lor \neg)[/math]
[math]f(x,y,z,t) = (x \lor t) \land (y \lor \neg) \land (\neg \lor \neg) \land (\neg \lor \neg \lor z)[/math]
[math]f(x,y,z,t,m) = (x \lor m \lor \neg) \land (y \lor \neg) \land (y \lor t \lor \neg)[/math]
Полином Жегалкина
Основная статья: Полином Жегалкина
Определение: Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида [math]0[/math] и [math]1[/math] , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином Жегалкина имеет следующий вид:
[math]P = a_ <000\ldots000>\oplus a_ <100\ldots0>x_1 \oplus a_ <010\ldots0>x_2 \oplus \ldots \oplus a_ <00\ldots01>x_n \oplus a_ <110\ldots0>x_1 x_2 \oplus \ldots \oplus a_ <00\ldots011>x_ x_n \oplus \ldots \oplus a_ <11\ldots1>x_1 x_2 \ldots x_n [/math]
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] , который, в свою очередь, по теореме Поста является полным.
[math]f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 [/math]
[math]f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 [/math]
[math]f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 [/math]
Тождественные функции. Выражение функций друг через друга
Определение: Тождественные функции — функции, которые при любых одинаковых аргументах принимают равные значения. Приведение тождественной функции есть выражение булевой функции через другие.
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
Пример: Выразим следующие функции через систему функций [math]\ <\land, \lor, \lnot \>[/math] . [math] x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )[/math]
[math] x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y[/math]
Подстановка одной функции в другую
Определение: Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_, \ldots, x_) = f(x_, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math] Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:
1. [math] x_, \ldots, x_[/math] — аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math] 2. [math] x_, \ldots, x_ [/math] — используются как аргументы для вычисления значения функции [math]g(y_, \ldots, y_)[/math] 3. [math] x_, \ldots, x_ [/math] — аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math] - [math] f(a,b) = a \vee b [/math]
- [math] g(a) = \neg a [/math]
Отождествление переменных
Определение: Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_, \ldots, x_, x_, \ldots, x_) = f(x_, \ldots, x_, \ldots, x_, x_, x_, \ldots, x_)[/math] Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math] .
Пример: [math] f(a,b) = a \vee b [/math] — исходная функция [math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами
Схемы из функциональных элементов
Основная статья: Реализация булевой функции схемой из функциональных элементов
Определение: Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе [math]B[/math] , в котором: 1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Некоторые логические элементы:
И ИЛИ НЕ Штрих Шеффера Стрелка Пирса Стандартный базис
Определение: Стандартный базис — система булевых функций: [math]\ <\land, \lor, \lnot \>[/math] Если рассматривать множество бинарных булевых функций [math]P_2(2)[/math] , то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы [math] 0 [/math] с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
[math] x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) [/math]
[math] x \rightarrow y = \lnot x \lor y [/math]
[math] 0 = x \land \lnot x [/math]
Функции [math] \mid \ и \downarrow[/math] являются отрицаниями функций [math] \land \ и \ \lor[/math] соответственно.
[math] x \mid y = \lnot \left ( x \land y \right )[/math]
[math] x \downarrow y = \lnot \left ( x \lor y \right )[/math]
Тождественность функций можно доказать с помощью таблицы истинности.
Выразим через стандартный базис обратную импликацию [math] \left (x \leftarrow y \right ) [/math] .
[math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]
Полнота стандартного базиса
Стандартный базис является полной системой булевых функций
[math] x \land y = \lnot \left (\lnot x \lor \lnot y \right ) [/math]
[math] x \lor y = \lnot \left (\lnot x \land \lnot y \right ) [/math]
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
[math] \ < \land , \lnot \>[/math] (конъюнктивный базис Буля)
[math] \ < \lor , \lnot \>[/math] (дизъюнктивный базис Буля)
Теоремы о числе функций в базисе
Максимально возможное число булевых функций в безызбыточном базисе — четыре.
Рассмотрим произвольный безызбыточный базис [math] X[/math] . Тогда по теореме Поста [math]X[/math] содержит следующие функции (не обязательно различные):
[math]f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L[/math] , где [math] T_0, T_1, S, M, L[/math] — классы Поста.
Значит, так как [math]X[/math] — безызбыточный базис, а система [math]\[/math] — полная, то [math]\left | X \right | \le 5[/math]
Рассмотрим [math]f_0[/math] . Возможны два случая:
1. [math] f_0(1, 1, \ldots, 1) = 0 [/math] , тогда [math]f_0[/math] также не сохраняет единицу и немонотонная, т.е.
[math] f_0 = f_1 = f_m [/math] . Значит, [math]\left | X \right | \le 3[/math] .
2. [math] f_0(1, 1, \ldots, 1) = 1 [/math] , тогда [math]f_0[/math] несамодвойственная, т.е.
Для любого числа [math]k, 1 \le k \le 4 [/math] найдётся базис [math] X[/math] , что [math]\left | X \right | = k[/math] .
Приведём примеры базисов для каждого [math]k[/math] :
[math]k = 1 \Rightarrow X = \< \downarrow \>[/math] ;
[math]k = 2 \Rightarrow X = \< \lnot, \land \>[/math] ;
Докажем, что последняя система является базисом:
[math] 0 \notin T_1[/math] ;
[math] 1 \notin T_0[/math] ;
[math] x\land y \notin L\ и\ S[/math] ;
[math] x\oplus y\oplus z \notin M[/math]
См. также
- Специальные формы КНФ
- Сокращенная и минимальная ДНФ
- Пороговая функция
- Cумматор
- Полные системы функций. Теорема Поста о полной системе функций
Примечания
Источники информации
- Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
- Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
- Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
- Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
- Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
- Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
- Учебные пособия кафедры математической кибернетики ВМиК МГУ
- Булева функция — Википедия
- http://psi-logic.narod.ru/bool/bool.htm
- Дискретная математика и алгоритмы
- Булевы функции
C++: Логический тип
Начиная с 11 стандарта в С++ был добавлен новый для этого языка тип по имени bool . Он назван в честь английского математика Джорджа Буля, разработавшего математическое представление законов логики.
Булевская переменная может принимать два значения: true (истина) или false (ложь). Для хранения булевской переменной выделяется один байт:
bool is_even; std::cout sizeof(is_even); // => 1В ранних версиях языка С++ булевский тип отсутствовал. В место этого С++ интерпретировал ненулевые значения как true , а нулевые как false .
Литералы true и false могут быть преобразованы в тип int , причем истинна будет преобразована в единицу, а ложь в ноль:
int is_even < true >; int promise < false >; std::cout 1 std::cout 0Кроме того, любое числовое значение может быть преобразовано неявно в значение bool :
bool is_even < 0 >; // false bool promise < 1 >; // true false == 0; // trueЗадание
Допишите программу, которая принимает в качестве аргумента командной строки число и определяет его четность. Результат сохраните в переменной типа bool и выведите на экран.
Упражнение не проходит проверку — что делать? ��
Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:
- Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет ��
Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.
Мой код отличается от решения учителя ��
Это нормально ��, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.
В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.
Прочитал урок — ничего не понятно ��
Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.
Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.
Элементарные булевы функции
Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных.
1. Булева функция f(x1, x2 … xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.
2. Булева функция f(x1, x2 … xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: 0.
3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности:
Обозначения: ¬x. Запись ¬x читается «не икс» или «отрицание икс».
4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 0 0 0 1 Другие названия: логическое умножение (произведение); логическое «и».
Обозначения: x&y, x⋅y, min(x,y).
Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».
5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 0 1 1 1 Другие названия: логическое сложение (сумма); логическое «или».
Обозначения: x∨y, max(x,y).
Запись x∨y может читаться так: «икс или игрек» или «сумма икс и игрек».
6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 1 1 0 1 Другое название: логическое следование.
Обозначения: x→y, x⇒y, x⊃y.
Запись x→y может читаться так: «из икс следует игрек».
7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 1 0 0 1 Обозначения: x∼y, x↔y.
Запись x∼y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».
8. Cуммой по модулю 2 называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 0 1 1 0 Другое название: антиэквивалентность.
Обозначения: x⊕y, x+y.
Запись x⊕y может читаться так: «икс плюс игрек».
9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 1 1 1 0 Другое название: отрицание конъюнкции, логическое «не-и».
Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».
10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности:
x 0 0 1 1 y 0 1 0 1 f(x, y) 1 0 0 0 Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.
Обозначение: x↓y; для функции Вебба — x°y.
Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».
Замечание: Символы ¬, &, ∨, →, ∼, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.
x 0 0 0 0 0 1 1 1 y 0 0 1 1 1 0 0 1 z 0 1 0 0 1 0 1 1 f(x,y,z) 0 0 0 0 1 0 1 1 Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) = 0.
Вектором значений булевой функции y=f(x1, x2 … xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).