Способы задания булевых функций таблицы истинности

называемое номером набора y. Например, двоичные наборы 101 и 111 имеют номера 5 и 7 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл. 1.2).
Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 2 8 = 256 строк. Поэтому для задания функций многих переменных удобно использовать модификацию таблицы истинности.
Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: х₁, х₂, . х_j-1 и х_j, х_j+1, . х_n. Переменными x₁, x₂, . x_n отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными x_j, x_j+i, . x_n отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 1.3).

Таблица 1.3
x₁,x₂. x_j-1	x_j, x_j+1, . x_n
x₁,x₂. x_j-1	00. 0	0. 1	.	11. 1
00. 0	.
00. 1	.
.	.	.	.	.
11. 1

При геометрическом способе булева функция f (х₁, . х_n) задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор у = y_i E <0,1>есть n-мерный вектор, определяющий точку n-мерпого пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичное (либо нулевое) значение, получим геометрическое представление функции. Например, булева функция, заданная табл. 1.1, геометрически представляется 3-мерным кубом (рис. 1).

При аналитическом способе булева функция задается формулами, т. е. аналитическими выражениями, построенными на основе операций булевой алгебры. Аналитический способ задания булевых функций занимает особое место в проектировании цифровых автоматов. Фактически, все преобразования над булевыми функциями, необходимые для построения цифровых автоматов, ведутся на аналитическом уровне.
Рассмотрим области определения булевых функций. Как уже отмечалось, между двоичными наборами и двоичными числами существует взаимно однозначное соответствие. Следовательно, существует 2 n различных наборов двоичных переменных.
Таким образом, областью определения булевой функции n переменных при матричном способе задания является множество всех возможных двоичных наборов длины n, а при геометрическом способе задания — множество всех вершин n-мерного единичного куба.
Булеву функцию, определенную на всех своих наборах, называют полностью определенной. В табл. 1.1, 1.2 приведены примеры полностью определенных булевых функций.
Булеву функцию n переменных называют неполностью определенной или частичной, если она определена не на всех двоичных наборах длины n. Неполностью определенная булева функция не попадает под определение, данное в начале , но при произвольном доопределении (на всех наборах, на которых она не определена) это несоответствие снимается.
Легко убедиться, что если булева функция f не определена на m наборах аргументов, то путем ее доопределения можно получить 2 m различных полностью определенных функций. В табл. 1.5 приведен пример неполностью определенной булевой функции трех переменных.

Таблица 1.5
х₁х₂х₃	F
000 001 010 011 100 101 110 111	0 1 — 0 1 — 1 —

Существует не более чем 2 2^n различных булевых функций n переменных. К этому выводу легко прийти, пользуясь простыми комбинаторными рассуждениями, и вспомнив, что на каждом из 2 n наборов функции могут принимать два значения.
Функции двух переменных представлены в табл. 1.6.
Наиболее часто употребляются следующие:

Таблица 1.6
х₁х₂	f₀	f₁	f₂	f₃	f₄	f₅	f₆	f₇	f₈	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄	f₁₅
00 01 10 11	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1	1 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	1 1 1 1

f0 (x1, x2) = 0 — тождественный ноль (константа 0);
f1 (x1, x2) = x1 * x2 — конъюнкция. Вместо знака «*» иногда употребляется знак & или /\. Эту функцию часто называют логическим произведением или логическим умножением;
f3 (x1, х2) = x1 — повторение x1;
f5 (x1, x2) = x2 — повторение х2;
f6 (x1, x2) = х1 x2 — сложение по модулю 2 или сумма mod 2 (далее +);
f7 (х1, х2) = x1 V x2 — дизъюнкция (логическое ИЛИ);
f8 (x1, x2) = x1 | х2 — функция Вебба (стрелка Пирса);
f9 (х1, х2) = x1

x2 — эквивалентность;
f13(x1, x2) = x1 —> x2 — импликация;
f14(x1, x2) = x1\x2 — штрих Шеффера;
f15(x1, x2) = 1-тождественная единица (константа 1).

Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов). Например, из функции f1 (x1, x2) с помощью подстановки f3 (х4, x8), f2 = x3 вместо аргументов х1 и х2 соответственно получаем функцию f1 (f3 (x4, x8), x3). Последняя от переменных х1, и х2 уже не зависит.
Отметим, что реально элементарной функции соответствует реализующий ее элемент, а суперпозиции булевых функций соответ-ствует соединение элементов

Источник

Способы задания булевых функций

Для задания произвольной булевой функции широко используются табличный (матричный) и аналитическийспособы. При табличном способе булева функция f (х₁, . х_n) задается таблицей истинности (табл. 7), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значения функции на этих наборах.

№ набора	х₁х₂х₃	f
0 1 2 3 4 5 6 7	000 001 010 011 100 101 110 111	0 1 0 0 1 1 0 1

Под двоичным набором понимается совокупность значений аргументов х₁,х₂, . x_n булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества <0,1>. В табл. 7 представлены все двоичные наборы длины 3. Иногда двоичные наборы из таблицы истинности булевой функции удобно представлять их номерами. Запишем аргументы х₁,х₂, . x_n в порядке возрастания их индексов. Тогда любому двоичному набору можно поставить в соответствие целое десятичное число N, называемое номером набора. Например, двоичные наборы 011 и 101 имеют номера 3 и 5 соответственно. Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 2 8 = 256 строк. Для задания функций многих переменных удобно использовать модификацию таблицы истинности. Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: х₁, х₂, . х_j-1 и х_j, х_j+1, . х_n. Переменными x₁, x₂, . x_n отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными x_j, x_j+i, . x_n отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 8).

x₁,x₂. x_j-1	x_j, x_j+1, . x_n
00. 0	0. 1	.	11. 1
00. 0
00. 1
.
11. 1

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

Основные понятия алгебры логики

Существует не более чем различных булевых функций n перемен-ных. К этому выводу легко прийти, пользуясь простыми комбинаторными рассуждениями, и вспомнив, что на каждом из 2 n наборов функции могут принимать два значения.

Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, то есть функция, значение которой совпадает с аргументом и функция отрицания значение которой противоположно значению аргумента. Отрицание будем обозначать x.

x 0 x x 1

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

Переменная x_i называется фиктивной (несущественной) переменной функции f(x₁,···,x_n), если

Функции двух переменных представлены в табл. 9 .

х₁х₂	f₀	f₁	f₂	f₃	f₄	f₅	f₆	f₇	f₈	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄	f₁₅
00 01 10 11	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1	1 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	1 1 1 1

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

f₀ (x1, x2) = 0 — тождественный ноль (константа 0);

f₁ (x1, x2) = x₁ ∙ x₂ – конъюнкция (логическое произведение, И). Иногда употребляется знак & или /\:

f₆ (x1, x2) = x₁ Åx₂ — сложение по модулю 2 или сумма mod 2;

f₇ (х1, х2) = x₁ + x₂ — дизъюнкция (логическое сложение, ИЛИ) или знак V;

f₈ (x1, x2) = x₁ ↓ x₂ — функция Вебба (стрелка Пирса, ИЛИ-НЕ);

f₁₅(x1, x2) = 1-тождественная единица (константа 1).

Основными операциями булевой алгебры являются: отрицание, логическое сложение и логическое умножение. В булевой алгебре возведение в степень и извлечение корня являются вырожденными логическими операциями, поскольку значения, принимаемые аргументами при возведении в степень и извлечении корня, остаются неизменными, если принять справедливость равенств 1·1= 1 и 0·0= 0. Операции вычитания и деления не рассматриваются и не допускаются.

Логическое отрицание (функция НЕ). Логическим отрицанием высказывания x называется такое сложное высказывание f₁(x), которое истинно, когда x ложно, и наоборот. Функция НЕ записывается следующим образом f₁=x. Реализующий функцию НЕ элемент приведен на рис. 13а.

Логическое умножение (конъюнкция). Конъюнкция (функция И) двух переменных x₁ и x₂ это сложное высказывание, которое истинно только тогда, когда истинны x₁ и x₂, и ложно для всех остальных наборов переменных. Логическая функция конъюнкции имеет вид f=x₁·x₂. Для обозначения операции конъюнкции используются также символы & и Λ. Функция логического умножения (И) от n переменных имеет вид f₂=(x₁, x₂, …, x_n)= x₁·x₂· … ·x_n = Λ x_i. Элемент, реализующий операцию логического умножения, изображен на рис. 13б.

Логическое сложение (дизъюнкция). Дизъюнкция (функция ИЛИ) двух переменных x₁ и x₂ – это сложное высказывание, которое истинно тогда, когда истинна хотя бы одна из переменных x₁ и x₂, и ложно, когда они обе ложны. Логическая функция дизъюнкции имеет вид f=x₁+x₂. Для обозначения операции дизъюнкции используется также символ V. Функция логического сложения (ИЛИ) от n переменных имеет вид f₂=(x₁, x₂, …, x_n)= x₁+x₂+ … +x_n = V x_i. Элемент, реализующий операцию логического сложения, изображен на рис. 13в.

Отрицание конъюнкции (операция Шеффера). Отрицание конъюнкции (функция И-НЕ) двух переменных x₁ и x₂ – сложное высказывание, ложное только при истинности обоих аргументов x₁ и x₂. Логическая функция И-НЕ имеет вид f=x₁·x₂. Элемент, реализующий указанную операцию, изображен на рис. 13г и называется элементом Шеффера или элементом И-НЕ.

Отрицание дизъюнкции (операция Пирса (Вебба)). Отрицание дизъюнкции (функция ИЛИ-НЕ) двух переменных x₁ и x₂ – сложное высказывание, истинное только тогда, когда оба аргумента принимают ложное значение. Логическая функция ИЛИ-НЕ имеет вид f=x₁+x₂. Элемент, реализующий указанную операцию, изображен на рис. 13д и называется элементом Пирса или элементом ИЛИ-НЕ.

Сложение по модулю 2 (исключающее ИЛИ). Сложение по модулю два это сложное высказывание, которое истинно только тогда, когда истинна только одна из переменных x₁ и x₂. Логическая функция ”сумма по модулю два” имеет вид f=x₁Åx₂. Если число переменных n>2, то функция истинна на тех наборах, в которых число единиц нечетно. Элемент, реализующий операцию сумма по модулю два, изображен на рис. 13ж.

Импликация. Это высказывание, принимающее ложное значение только в случае если x₁ истинно и x₂ ложно.

Простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции.

Функция f(x,y) = (x & y) является суперпозицией функций и &. Функция g(x,y) = x Å (x Ú y) является суперпозицией функций Å и Ú. Функция h(x,y,z) = (x & y) Å z является суперпозицией функций Å и &.

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

§ одна и та же функция может быть представлена разными формулами;

§ каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;

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

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

Источник