Функция f от n переменных такая что f x y z y

Определение булевой функции

Булевой функцией y=f(x₁, x₂ . x_n) от п переменных x₁, x₂, x_n называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц (x₁, x₂ . x_n) ставится в соответствие значение 0 или 1.

Булевы функции называются также функциями алгебры логики, двоичными функциями и переключательными функциями.

Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д. Последний набор состоит из n единиц и является двоичным разложением числа 2 n -1 (такой порядок расположения наборов назовем лексикографическим порядком). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо 1, заключаем, что существует всего 2 2 n различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.

Пример (голосование): Рассмотрим устройство, фиксирующее принятие некоторой резолюции "комитетом трех". Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов голосуют «за», то резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f(x,y,z), таблица истинности которой имеет вид:

x	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1
z	0	1	0	1	0	1	0	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(x₁, x₂ . x_n) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).

Сколько существует булевых функций от n переменных

Булевы функции 1 названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций — их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция — константа !). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через B двухэлементное множество <0,1>. Тогда

это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x₁, x_n): B n -> B . Каждый из ее аргументов x_i, 1 k . В нашем случае B=<0, 1>, а A = B n . Тогда m=2 и k= |B n | = 2 n . Отсюда следует утверждение теоремы.

Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим геометрическое и табличное представления, а также представление с помощью логических формул. В "Эквивалентность формул и нормальные формы" будет показано, как булевы функции можно представлять с помощью формул специального вида — дизъюнктивных и конъюнктивных нормальных форм и многочленов Жегалкина. Кроме того, в лекциях "Предварительные сведения" и "Индукция и комбинаторика" (курс "Введение в схемы, автоматы и алгоритмы") будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений.

Геометрическое представление

B_n можно рассматривать как единичный n-мерный куб. Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы B_n при n=3,4.

Рис. 3.1.

При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству соответствует его характеристическая функция

Например, верхней грани куба B 3 (ее вершины выделены на рисунке) соответствует функция f: f(0,0,1)=f(0,1,1)=f(1,0,1)=f(1,1,1) =1 и f(0,0,0)=f(0,1,0)=f(1,0,0)=f(1,1,0) =0. Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество A_f=<(x₁, . x_n)|f(x₁, . x_n)=1> вершин B n . Например, функция, тождественно равная 0, задает пустое множество , а функция, тождественно равная 1, задает множество всех вершин B n .

Табличное представление

Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции f(x₁, . x_n)имеет n+1 столбец. В первых n столбцах указываются значения аргументов x₁, . x_n , а в (n+1) -ом столбце значение функции на этих аргументах — f(x₁, . x_n) .

Таблица 3.1. Табличное представление функции f(x1, . xn)
x1	.	.	.	xn-1	xn	f(x1, . xn)
.	.	.	f(0, . 0,0)
.	.	.	f(0, . 0,1)
.	.	.	f(0, . 1,0)
.	.	.	.	.	.
.	.	.	f(1, . 1,1)

Наборы аргументов в строках обычно располагаются в лексикографическом порядке:

существует такое , что при , а .

Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая — 1, 3-я — 2, а последняя — 2 n -1 .

При больших n табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблицас 1024 строками. Но для малых n оно достаточно наглядно.

Формулы

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

Пусть — некоторое (конечное или бесконечное) множество булевых функций. Зафиксируем некоторое счетное множество переменных V=₁, X₂, . > . Определим по индукции множество формул над с переменными из V. Одновременно будем определять числовую характеристику формулы называемую ее глубиной, и множество ее подформул.

Определение 3.2.

1. Базис индукции. Каждая переменная и каждая константа является формулой глубины 0, т.е. dep(X_i)=dep(c)=0 . Множество ее подформул состоит из нее самой.

2. Шаг индукции. Пусть и A₁, . , A_m — формулы, и max <dep(A_i) | i = 1. m> = k . Тогда выражение является формулой, ее глубина равна k+1, а множество подформул включает саму формулу и все подформулы формул A₁, . A_m.

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

Базис индукции. Пусть . Тогда или . В первом случае задает функцию , во втором — функцию, тождественно равную константе c.

Шаг индукции. Пусть — произвольная формула глубины . Тогда , где и A₁, . A_m — формулы, для которых max₁

Сколько существует монотонных булевых функций от 3 переменных?

задан 14 Янв ’18 17:14

1 ответ

В отличие от других предполных классов, для количества монотонных функций от n переменных, хорошей общей формулы не имеется. Поэтому считать придётся вручную. Способов можно предложить несколько. Один из них такой: сразу учтём 2 константы. Остальные монотонные функции представляются в виде дизъюнкции элементарных конъюнкций. При этом более "слабые" члены не учитываются, что гарантирует единственность. Это означает, что если одна конъюнкция "содержит" другую — в том смысле, как xz "содержит" и x, и z, то x V xz равно x. Поэтому наличие члена xz исключает наличие более "слабых" членов x и z.

Тогда, если есть xyz, то больше ничего нет. Предположим, что члена 3-й степени нет, а члены 2-й степени есть. Если их три, то получается функция голосования xy V xz V yz. Других членов нет. Если их два, то это функция xy V xz, или симметричная ей. Всего таких 3 штуки. Других членов снова нет. Если есть только один член — скажем, xy, то он идёт или сам по себе, или вместе с z, то есть функция равна xy V z. С учётом симметрии, это ещё 6 случаев. Наконец, если члены имеют только первую степень, то функций будет 2^3-1=7 по числу непустых подмножеств в .

Теперь аккуратно всё складываем: 2+1+1+3+6+7=20. Это ответ.

Вот ещё один способ. От двух переменных имеется ровно 6 монотонных функций: две константы, две переменные, конъюнкция и дизъюнкция. Это легко проверяется. В виде векторов их легко выписать (в лексикографическом порядке): 0000, 0001, 0011, 0101, 0111, 1111. Теперь заметим, что при фиксации значения одной переменной у монотонной функции, это свойство сохраняется. Если для функции f(x,y,z) мы фиксируем x=0, то получим один из этих 6 наборов. Если фиксируем x=1, то снова получается набор из списка, который покоординатно не меньше предыдущего. Поэтому остаётся для каждого набора списка подсчитать число покоординатно не меньших, и всё сложить. Это даёт 6+5+3+3+2+1=20. Ответ тот же.

Дата добавления: 2015-07-23 ; просмотров: 4667 ; Нарушение авторских прав

Булевы функции 1) названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций — их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция — константа !). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через B двухэлементное множество <0,1>. Тогда

это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x₁, x_n): B n -> B . Каждый из ее аргументов x_i, 1 k . В нашем случае B=<0, 1>, а A = B n . Тогда m=2 и k= |B n | = 2 n . Отсюда следует утверждение теоремы.

Суперпозицией булевых функций f0 и f1. f_n называется функция f(x1. x_m) = f0(g1(x1. x_m). g_k(x1. x_m)), где каждая из функций g_i(x1,. x_m) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1. f_n.

19. Число булевых функций от n аргументов. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание (теорема о разложении функции по переменной и теорема о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание).

Дизъюнктивная нормальная форма

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

§ правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);

§ полная, если в неё каждая переменная (или её отрицание) входит ровно 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]<2^2>^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]<2^2>^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.

Унарные функции [ править ]

При [math]n = 1[/math] число булевых функций равно [math]<2^2>^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>^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]<2^2>^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<0>=1[/math]	[math]\overline<1>=0[/math]	[math]\overline<\overline>=x[/math]	[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]

(законы де Моргана)

[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 = \[/math] . Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре [math]\Sigma[/math] , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

• Как построить по данной функции представляющую её формулу?
• Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
  • В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?

  Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.

  Дизъюнктивная нормальная форма (ДНФ) [ править ]

  Определение:

  Дизъюнктивная нормальная форма (ДНФ) (англ. 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] 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_<1>, \ldots, x_) = f(x_<1>, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math]

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

  При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:

  1. [math] f(a,b) = a \vee b [/math]
  2. [math] g(a) = \neg a [/math]

  Отождествление переменных [ править ]

  Определение:

  Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_<1>, \ldots, x_, x_, \ldots, x_) = f(x_<1>, \ldots, x_, \ldots, x_, x_, x_, \ldots, x_)[/math]

  Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/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] несамодвойственная, т.е.

  Похожие публикации:

  1. Укажите номер первого слова которое начинается с буквы у
  2. Упражнение doc какой это файл
  3. Утилита атрибутов как удалить
  4. Файл занят другим процессом как удалить