Булевы функции одной и двух переменных

Поможем в ✍️ написании учебной работы

Имя

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

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

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

Технические вопросы, связанные с составлением логических схем ЭВМ, можно решить с помощью математического аппарата, объектом исследования которого являются функции, принимающие, так же как и их аргументы, только два значения - “0” и “1”.

Таким аппаратом является математическая логика (алгебра логики, булева алгебра).

Логика - это наука о законах и формах мышления.

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

Основное понятие алгебры логики - высказывание. Высказывание - это некоторое предложение, о котором можно утверждать, что оно истинно или ложно.

Любое высказывание можно обозначить символом х и считать, что х=1, если высказывание истинно, а х=0 - если высказывание ложно. Истинному высказыванию соответствует утверждение -“Да”, ложному высказыванию - утверждение - “Нет”.

Логическая (булева) переменная - такая величина х, которая может принимать только два значения х={0,1}.

Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение х=1 при любых условиях.

Высказывание абсолютно ложно, если соответствующая ей логическая величина принимает значение х=0 при любых условиях.

Функция f, зависящая от n переменных x1,x2,...,xn, называется булевой, или переключательной, если функция f и любой из ее аргументов принимают значения только из множества {0,1}. Аргументы булевой функции также называются булевыми.

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

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

При матричном способе булева функция f(x1,...,xn) задается таблицей истинности (табл. 1 и 2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

Под двоичным набором понимается совокупность значений аргументов x1,x2,...,xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 1 и 2 перечислены все двоичные наборы соответственно длины 3 и 4.

Таблица 1 Таблица 3

х1	х2	х3	f(х1,х2,,х3)	Номер набора	f(х1,х2,,х3)
0	0	0	0	0	0
0	0	1	1	1	1
0	1	0	0	2	0
0	1	1	0	3	0
1	0	0	1	4	1
1	0	1	1	5	1
1	1	0	0	6	0
1	1	1	1	7	1

Таблица 2 Таблица 4.

x1	x2	x3	x4	f(х1..х4)	x1,x2,...,xj-1	xj,xj+1,...,xn
						00..0	0...1	...	11..1
0	0	0	0	1
0	0	0	1	0	00...0			...
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0	00...1			...
0	1	1	0	1				f(х1...хn)
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0	...	...	...	...	...
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0	11...1
1	1	1	0	1
1	1	1	1	0

Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы x1,x2,...,xn в порядке возрастания их индексов. Тогда любой двоичный набор можно рассматривать как целое двоичное число N, называемое номером набора. Например, двоичные наборы 0101 и 1000 имеют номера 5 и 8 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл.3).

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

Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: x1,x2,...,xj-1 и хj, xj,xj+1,...,xn. Переменными x1,x2,...,xj-1 отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными xj,xj+1,...,xn отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл.4.).

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

а) n=1 б) n=2 в) n=3

Рисунок 1- Геометрическое задание булевой функции:

а) одной переменной: б) двух переменных; в) трех переменных.

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

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

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

Булеву функцию, определенную на всех своих наборах, называют полностью определенной.

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

Минимизация булевых функций

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

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

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Определение. Минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию). Определение. Булева функция g(x1,x2,...,xn) называется импликантой булевой функции f1(x1,x2,...,xn), если для любого набора переменных, на котором g = 1, справедливо f = 1. Пример. Булева функция f задана таблицей 8. Там же приведены все ее импликанты. При записи функции и ее импликант в СДНФ имеем

f= Ú Ú

g1=

g2=

g3= V =

g4=

g5= vv =

g6= vv

g7= Ú Ú

Определение. Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

Из примера видно, что импликанты g3 и g5 являются простыми импликантами функции f. Другие импликанты не являются простыми, так как их части являются импликантами функции f, например g3 является частью g1. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.

2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ.

Перебор всех возможных импликант для булевой функции f из рассмотренного примера дает возможность убедиться, что простых импликант всего две: g3 и g5. Следовательно, сокращенная ДНФ функции f имеет вид:

f = g3 V g5 = V

Как видно из табл. 6.8., импликанты g3 и g5 в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты назовем лишними. Исключение лишних простых импликант из сокращенных ДНФ — второй этап минимизации.

Определение. Сокращенная ДНФ булевой функции называется тупиковой, если в ней отсутствуют лишние простые импликанты.

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

Утверждение. Тупиковые ДНФ булевой функции f, содержащие минимальное число букв, являются минимальными. Минимальных ДНФ тоже может быть несколько.

Рассмотрим несколько методов минимизации. Все они практически различаются лишь на первом этапе — этапе получения сокращенной ДНФ. Следует отметить, что, к сожалению, поиск минимальной ДНФ всегда связан с некоторым перебором решений. Существуют методы уменьшения этого перебора, однако он всегда остается.

Метод Квайна

Метод Квайна основывается на применении двух основных соотношений.

1. Соотношение склеивания

где А — любое элементарное произведение.

2. Соотношение поглощения

Справедливость обоих соотношений легко проверяется.

Теорема Квайна. Если в СДНФ булевой функции выполнить все возможные склеивания и поглощения, то в результате будет получена сокращенная ДНФ.

Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.

Для доказательства достаточно показать, что произвольная простая импликанта р = может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): по всем недостающим переменным исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р — ее импликанта.

Минимизация по методу Квайна выполняется по следующему алгоитму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл 9). Ее СДНФ имеет вид:

f= Ú Ú Ú Ú Ú

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2 ) конституента 2 с конституентой 4 и т. д. В результате получаем:

1-2:

1-3:

2-4:

3-4:

4-6:

5-6:

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

Ú = Ú Ú

с появлением одного и того же элементарного произведения . Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

Ú Ú

Переходим к следующему этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы — конституентами единицы, т. е. членами СДНФ булевой функции.

Пример (продолжение). Импликантная матрица имеет вид (табл. 10).

Таблица 10.

Простые	Конституенты единицы
импликанты
	Х	Х	Х	Х
				Х		Х
					Х	Х

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 10). Минимальные ДНФ строятся по импликантной матрице следующим образом:

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

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функции являются импликанты и . Импликанта - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

fmin= Ú

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2n-k, где k — число букв, содержащихся в простой импликанте.

Заметим также, что используя различные соотношения, можно расширить область применения метода Квайна за пределы совершенной ДНФ.

Метод Квайна-Мак-Класки

Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

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

2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.

3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна. Более подробно рассмотрим метод на примере решения следующей задачи: минимизировать методом Квайна-Мак-Класки булеву функцию f, заданную таблицей истинности (табл. 9).

1. В СДНФ функции f заменим все конституенты единицы их двоичными номерами: f=0001Ú0011Ú0101Ú0111Ú1110Ú1111

2. Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.11).

3. Склеим номера из соседних групп табл.11. Склеиваемые номера обозначим звездочками (номер отмечается в том случае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которым произошло склеивание, проставляются прочерки. Результаты склеивания занесем в табл. 12. Склеим номера из соседних групп табл. 12. Склеиваться могут только номера, имеющие прочерки в одинаковых позициях. Склеиваемые номера отметим. Результаты склеивания занесем в табл. 13.

4. Имеем три простые импликанты: -111, 111-, 0--1.

Таблица 11 Таблица 12 Таблица 13

Номер группы	Двоичные номера кон-ституент 1	Номер группы	Двоичные номера импликант	Номер группы	Двоичные номера импликант
0	-	1 (1-2)	00-1 *	1	0--1
1	0001 *		0-01 *		0--1
2	0011 *	2 (2-3)	0-11 *	2	-111
	0101 *		01-1 *		111-
3	0111 *	3 (3-4)	-111
	1110 *		111-
4	1111 *

Таблица 14

Простые	Конституенты единицы
импликанты
(0--1)	Х	Х	Х	Х
(-111)				Х		Х
(111-)					Х	Х

5. Строим импликантную матрицу (табл. 14). По таблице определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

fmin= Ú

Заметим, что разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.

Метод диаграмм Вейча

Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 15). Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В табл.15. это соответствие показано. В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 16). Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 17). Таким же образом, т. е. приписыванием еще одной диаграммы 4-х переменных, к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко.

Для приведенных диаграмм характерно следующее:

1) каждой клетке диаграммы соответствует свой набор;

Таблица 15. Таблица 16.


11	01	110	111	011	010
10	00	100	101	001	000

Таблица 17. Таблица 18.

						х1
х1	1100	1101	1001	1000		1	1	1
х1	1110	1111	1011	1010	х3			1
	0110	0111	0011	0010	х3
	0100	0101	0001	0000
		х4	х4

2) соседние наборы расположены рядом в строке либо в столбце. Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна-Мак-Класки). Например, для функции, заданной табл. 18, конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из двух букв:

О паре единиц в правой части диаграммы можно сказать то же самое: = .

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

Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение . Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:

m=n-log2M,

где n- число переменных,

M - число склеиваемых наборов.

Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме «с первого взгляда».

Минимизация булевой функции заключается в нахождении минимального покрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Вейча 4-х переменных примыкает к ее правому краю, а верхний край диаграммы примыкает к нижнему ее краю. Для удобства можно предположить, что диаграмма сворачивается в цилиндр как по горизонтали, так и по вертикали. После получения минимального покрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.

В диаграмме Вейча необходимо и достаточно, чтобы каждая единичная клетка участвовала в склейке хотя бы один раз.

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

Вся диаграмма должна быть покрыта наименьшим количеством склеек. В склейку может входить 2n соседних клеток (2, 4, 8, 16. и т.д.).

Рассмотрим несколько примеров.

Таблица 19 Таблица 20

X4 X3


х1					х1		1	1
х1	1	1		х3	х1	1	1	1	1	х3
		1	1	х3		1	1	1	1	х3
		1	1				1	1
		х4	х4				х4	х4

f1= v f2= X4 v X3

Карты Карно

Иногда удобно пользоваться несколько другим представлением диаграмм с цифровым кодом. Это карты Карно. Примеры карт Карно приведены на рисунке 2. По граням карты проставляются двоичные коды - коды Грея, что дает возможность легко проставлять значения функции и находить результат. Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча.

х2х3 х1	00	01	11	10	х3х4 х1х2	00	01	11	10
0	000	001	011	010	00	0000	0001	0011	0010
1	100	101	111	110	01	0100	0101	0111	0110
					11	1100	1101	1111	1110
					10	1000	1001	1011	1010
	а)							б)

Рисунок 2- Карты Карно:

а) функции 3-х переменных;

б) функции 4-х переменных.

Выводы

Известна более простая задача — задача факторизации, заключающаяся в упрощении дизъюнктивно-конъюнктивных форм, допуская отрицания лишь над переменными. Часто она называется задачей скобочной минимизации, и в настоящее время известно достаточно много методов такого упрощения. В общем виде задача факторизации не решена, но для булевого базиса, в ряде случаев, используя операцию вынесения за скобки общих членов, можно получить скобочную форму, значительно более простую, чем минимальная ДНФ булевой функции.

Литература

1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа” 1987.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.

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

Таким аппаратом является математическая логика (алгебра логики, булева алгебра).

Логика - это наука о законах и формах мышления.

Логическая (булева) переменная - такая величина х, которая может принимать только два значения х={0,1}.

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

Таблица 1 Таблица 3

х1	х2	х3	f(х1,х2,,х3)	Номер набора	f(х1,х2,,х3)
0	0	0	0	0	0
0	0	1	1	1	1
0	1	0	0	2	0
0	1	1	0	3	0
1	0	0	1	4	1
1	0	1	1	5	1
1	1	0	0	6	0
1	1	1	1	7	1

Таблица 2 Таблица 4.

x1	x2	x3	x4	f(х1..х4)	x1,x2,...,xj-1	xj,xj+1,...,xn
						00..0	0...1	...	11..1
0	0	0	0	1
0	0	0	1	0	00...0			...
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0	00...1			...
0	1	1	0	1				f(х1...хn)
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0	...	...	...	...	...
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0	11...1
1	1	1	0	1
1	1	1	1	0

а) n=1 б) n=2 в) n=3

Рисунок 1- Геометрическое задание булевой функции:

а) одной переменной: б) двух переменных; в) трех переменных.

Булеву функцию, определенную на всех своих наборах, называют полностью определенной.

Булевы функции одной и двух переменных

Рассмотрим наиболее употребимые булевы функции одной и двух переменных. Функции одной переменной представлены в табл. 5.

Таблица 5

f(х)	х		Усл.	Наименование
	0	1	обозн
f0 (х)	0	0	0	тождественный ноль (константа 0);
f1 (х)	0	1	х	тождественная функция
f2 (х)	1	0		отрицание х (инверсия);
f3 (х)	1	1	1	тождественная единица (константа 1).

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

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

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

Таблица 6

	х1	0	0	1	1	Наименование функции
	х2	0	1	0	1
f0 (х1,х2)		0	0	0	0	константа 0
f1 (х1,х2)		0	0	0	1	конъюнкция
f2 (х1,х2)		0	0	1	0	запрет по х2
f3 (х1,х2)		0	0	1	1	переменная х1
f4 (х1,х2)		0	1	0	0	запрет по х1
f5 (х1,х2)		0	1	0	1	переменная х2
f6 (х1,х2)		0	1	1	0	сумма по модулю 2
f7 (х1,х2)		0	1	1	1	дизъюнкция
f8 (х1,х2)		1	0	0	0	операция Пирса (ф-ция Вебба)
f9 (х1,х2)		1	0	0	1	логическая равнозначность
f10 (х1,х2)		1	0	1	0	инверсия х2
f11 (х1,х2)		1	0	1	1	импликация от х2 к х1
f12 (х1,х2)		1	1	0	0	инверсия х1
f13 (х1,х2)		1	1	0	1	импликация от х1 к х2
f14 (х1,х2)		1	1	1	0	штрих Шеффера
f15 (х1,х2)		1	1	1	1	константа 1

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

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

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

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

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

Дата: 2019-12-10, просмотров: 219.

12 3 Следующая ⇒