Персональный сайт - Логика_преобразование выражений урок 3

Бинарные функции

Булева функция Материал из Википедии — свободной энциклопедии

http://ru.wikipedia.org/wiki/%D0%91%D1%83%D0%BB%D0%B5%D0%B2%D0%B0_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F

Содержание

При n = 2 число булевых функций равно 2^2² = 2⁴ = 16.

Таблица значений булевых функций от двух переменных:

x	y	x↓y	x←y	x	x→y	y	x⊕y	x\|y	x & y	x ≡ y	y	x→y	x	x←y	x ∨ y	1
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Названия булевых функций от двух переменных:

Обозначение

Название

0

тождественный ноль, тождественная ложь, тождественное "НЕТ"

x ↓ y, x ИЛИ-НЕ y, ИЛИ-НЕ(x,y), x NOR y, NOR(x,y)

НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса

x < y, x ← y, x LT y, LT(x,y)

меньше, инверсия обратной импликации

x, НЕ1(x,y), NOT1(x,y), x', ¬x

отрицание (негация, инверсия) первого операнда

x > y, x → y, x GT y, GT(x,y)

больше, инверсия прямой импликации

y, НЕ2(x,y), NOT2(x,y), y', ¬y

отрицание (негация, инверсия) второго операнда

x ⊕ y, x +₂ y, x ≠ y, x >< y, x <> y, x XOR y, XOR(x,y)

сложение по модулю 2, не равно, измена, исключающее «или»

x | y, x NAND y, NAND(x,y), x И-НЕ y, И-НЕ(x,y)

НЕ-2И, 2И-НЕ, антиконъюнкция, штрих Ше́ффера

x & y, x · y, xy, x ∧ y, x AND y, AND(x,y), x И y, И(x,y), min(x,y)

2И, конъюнкция

x ≡ y, x = y, x EQV y, EQV(x,y), x ~ y, x ↔ y

равенство, эквивалентность

y, ДА2(x,y), YES2(x,y)

второй операнд

x → y, x ≤ y, x ⊃ y, x LE y, LE(x,y)

меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)

x, ДА1(x,y), YES1(x,y)

первый операнд

x ← y, x ≥ y, x ⊂ y, x GE y, GE(x,y)

больше или равно, обратная импликация (от второго аргумента к первому)

x ∨ y, x + y, x ИЛИ y, ИЛИ(x,y), x OR y, OR(x,y), max(x,y)

2ИЛИ, дизъюнкция

тождественная единица, тождественная истина, тождественное "ДА", тавтология

Основные сведения

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2ⁿ. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 2^2ⁿ. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

x₁	x₂	…	x_n	f(x₁,x₂,…,x_n)
0	0	…	0	f(0,0,…,0)
1	0	…	0	f(1,0,…,0)
0	1	…	0	f(0,1,…,0)
1	1	…	0	f(1,1,…,0)
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
0	1	…	1	f(0,1,…,1)
1	1	…	1	f(1,1,…,1)

Практически все булевы функции малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной.

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

При n = 0 количество булевых функций сводится к двум 2^2⁰ = 2¹ = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.

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

При n = 1 число булевых функций равно 2^2¹ = 2² = 4. Определение этих функций содержится в следующей таблице.

Таблица значений булевых функций от одной переменной:

x	0	x̅	x	1
0	0	1	0	1
1	0	0	1	1

Названия булевых функций от одной переменной:

Обозначение	Название
0	тождественный ноль, тождественная ложь, тождественное "НЕТ"
x̅, ¬x, x'	отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
x	тождественная функция, логическое "ДА", "YES"(англ.)
1	тождественная единица, тождественная истина, тождественное "ДА", тавтология

Тернарные функции

При n = 3 число булевых функций равно 2^2³ = 2⁸ = 256. Некоторые из них определены в следующей таблице:

x	y	z	x↓y↓z	≥2(x,y,z)	x≠y≠z	x\|y\|z	min(x,y,z)	x=y=z	x⊕y⊕z	≥2(x,y,z)	f₁	f₂	max(x,y,z)
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

Названия булевых функций трех переменных:

Обозначения	Названия
x $\downarrow$ y $\downarrow$ z = $\downarrow$ (x,y,z) = Webb₂(x,y,z)	3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
$\neg(> = 2(x,y,z))$	Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v)	Неравенство
x $\mid$ y $\mid$ z = $\mid$ (x,y,z)	3-И-НЕ, штрих Шеффера
x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z)	3-И, минимум
(x=y=z) = [=(x,y,z)] = EQV(x,y,z,v)	Равенство
x⊕₂y⊕₂z = x+₂y+₂z = ⊕₂(x,y,z) = +₂(x,y,z)	Тернарное сложение по модулю 2
[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x)	переключатель по большинству, 3-ППБ, мажоритарный клапан
f₁	Разряд займа при тернарном вычитании
f₂	Разряд переноса при тернарном сложении
(x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)	3-ИЛИ, максимум

[править] Полные системы булевых функций

Основная статья: Замкнутые классы булевых функций

[править] Суперпозиция и замкнутые классы функций

Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции $f(x,y,z)=\overline{x(\overline{y}\lor z)}$ (суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:

$x$	$y$	$z$	$f (x, y, z)$
0	0	0	1
1	0	0	0
0	1	0	1
1	1	0	1
0	0	1	0
1	0	1	0
0	1	1	1
1	1	1	0

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

В качестве простейших примеров замкнутых классов булевых функций можно назвать множество ${x}$ , состоящее из одной тождественной функции, или множество ${0}$ , все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций $\{x,\overline{x}\}$ и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы ${0}$ и $\{x,\overline{x}\}$ , мы с помощью суперпозиции $\overline{0}$ сможем получить константу 1, которая в исходных классах отсутствовала.

Разумеется, множество $P 2$ всех возможных булевых функций тоже является замкнутым.

[править] Тождественность и двойственность

Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
$f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)$

Просмотрев таблицы истинности булевых функций, легко получить такие тождества:

$\overline{0}=1$	$\overline{1}=0$	$\overline{\overline{x}}=x$	$xy=yx\!$	$x\lor y=y \lor x$
$0x=0\!$	$1x=x\!$	$0\lor x=x$	$1\lor x=1$	$xx=x\lor x=x$

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

$x\overline{x}=0$

$x\lor\overline{x}=1$

$\overline{x\cdot y}=\overline{x}\lor\overline{y}$

$\overline{x}\cdot\overline{y}=\overline{x\lor y}$

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

$x(y\lor z)=xy\lor xz$
$x\lor yz=(x\lor y)(x\lor z)$ (дистрибутивность конъюнкции и дизъюнкции)

Функция $g(x_1,x_2,\dots,x_n)$ называется двойственной функции $f(x_1,x_2,\dots,x_n)$ , если $f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}$ . Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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

[править] Полнота системы, критерий Поста

Основная статья: Критерий Поста

Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством $P 2$ .

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

Функции, сохраняющие константу $T 0$ и $T 1$ ;
Самодвойственные функции $S$ ;
Монотонные функции $M$ ;
Линейные функции $L$ .

Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с $P 2$ , целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.

[править] Представление булевых функций

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций $\Sigma = \{f_1,\ldots,f_n\}$ . Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре $Σ$ , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

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

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

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

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

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

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

Например $a \overline{b} c\lor b c\lor\overline{a}$ — является ДНФ.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: $a \overline{b} c\lor a b c\lor\overline{a} b\overline{c}$ .

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора $b=(b_1,b_2,\ldots,b_n)$ построить конъюнкцию $x_1^{b_1} x_2^{b_2}\ldots x_n^{b_n}$ , где $x_i^1 = x_i$ $x_i^0 = \overline{x_i}$ . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации $x\to y$ результатом является $\overline{x} y \lor \overline{x}\, \overline{y}\lor x y$ , что можно упростить до $\overline{x}\lor y$ .

Этот раздел не завершён.
Вы поможете проекту, исправив и дополнив его.

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

Основная статья: Конъюнктивная нормальная форма

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

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

$a (b\lor c)\to a b\lor a c$

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить и… Продолжение »

Бесплатный конструктор сайтов — uCoz