Логические (булевы) функции

Булева функция (F) является результатом выполнения логических операций над двоичными переменными – аргументами (A, B, C, …) и полностью зависит от их значений.

Задать булеву функцию – значит указать ее значения (0 или 1) при всех возможных комбинациях значений переменных.

Каждая комбинация аргументов называется набором, при N аргументах существует 2^N наборов.

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

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

Рассмотрим два примера словесного задания булевой функции.

Полностью определенная функция F₁ трех аргументов A, B, C принимает значение 1, если два любых аргумента (или все три) равны 1. В других случаях функция равна нулю. Количество наборов равно 2³ = 8.

Недоопределенная функция F₂ трех аргументов A, B, C принимает значение 1, если два любых аргумента равны 1, и равна нулю в остальных случаях, кроме случаев однозначности всех трех аргументов.

Если пронумеровать наборы от 0 до 2³ – 1, эти словесно заданные функции можно представить в виде таблицы истинности (табл. 1).

Таблица 1

Номера наборов	A	B	C	F₁	F₂	F₃	F₄
0	0	0	0	0	–	0	0
1	0	0	1	0	0	0	1
2	0	1	0	0	0	0	1
3	0	1	1	1	1	0	1
4	1	0	0	0	0	0	1
5	1	0	1	1	1	0	1
6	1	1	0	1	1	0	1
7	1	1	1	1	–	1	1

Функция F ₂ не определена на 0 и 7 наборах, где все три аргумента однозначны, поэтому в таблице 1 против этих наборов проставлены прочерки.

Отдельный интерес представляют функции F₃ и F₄ .

Конституентой единицы (F₃) называют функцию n аргументов, которая принимает значение, равное единице, только на одном наборе аргументов. На всех остальных наборах она равна нулю.

Конституентой нуля (F₄) называют функцию n аргументов, которая принимает значение, равное нулю, только на одном наборе аргументов.

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

Совершенной дизъюнктивной, нормальной формой (Сов ДНФ) функции называют дизъюнкцию конституент единицы – минтермов, взятых на тех наборах, на которых единице равна сама функция.

Минтерм – конъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно единице, либо в инверсном виде, если их значение в наборе равно нулю.

Функция F₁ в Сов ДНФ будет иметь вид:

Совершенной конъюнктивной, нормальной формой (Сов КНФ) функции называют конъюнкцию конституент нуля – макстермов, взятых на тех наборах, на которых нулю равна сама функция.

Макстерм – дизъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно нулю, либо в инверсном виде, если их значение в наборе равно единице.

Функция F₁ в Сов КНФ примет вид:

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

к оглавлению

Знаете ли Вы, что только в 1990-х доплеровские измерения радиотелескопами показали скорость Маринова для CMB (космического микроволнового излучения), которую он открыл в 1974. Естественно, о Маринове никто не хотел вспоминать. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМА

Рыцари теории эфира