Основные структуры. 
Информатика и математика

В результате освоения данной темы студент должен: знать

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

Понятие булевой функции

Функция п переменных z = /(*!,…,*") называется булевой функцией, если каждая из ее переменных и сама функция могут принимать только два значения: 0 и 1.

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

Между рассмотренными выше логическими высказываниями, логическими связками и булевыми функциями существует полная аналогия. Если логические высказывания могут принимать значения «истина» или «ложь», то для булевой функции аналогами этих значений будут значения 1 или 0.

Из определения булевой функции f (x_l9…, х_п) следует, что ее можно задать таблично, т. е. указать, какое значение функции соответствует каждому из всевозможных наборов значений ее переменных. В итоге получится таблица значений булевой функции, которую по аналогии с логикой высказываний обычно называют таблицей истинности (табл. 3.1).

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

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

Таблица истинности булевой функции.

	О.		О.	О.	/ (О, 0, О, 0) = 0 или 1.
	О.		О.		/ (0, 0, О, 1) = 0 или 1.
О.	О.				/(О, 0,…, 1, 1) = 0 или 1.
					/(1, 1, 1, 1) = 0или 1.

Таким образом, всего имеется 2²¹ = 4 булевые функции одной переменной и 2²² =16 булевых функций двух переменных. Приведем таблицы истинности этих функций (табл. 3.2, 3.3) и запишем их в виде формул, опуская в записи булевой функции z ее переменные.

Таблица 3.2

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

Формула.	Значения переменной и функций.		Наименование.
			Переменная.
			Константа.
			Константа.
			Отрицание.
			Совпадение с переменной.

Таблица 3.3

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

Формула.	Значения переменных и функций.				Наименование.
					Первая переменная.
					Вторая переменная.
					Константа.
					Константа.
					Совпадение с первой переменной.
					Совпадение со второй переменной.
					Отрицание первой переменной.
					Отрицание второй переменной.
					Конъюнкция (логическое умножение).
					Дизъюнкция (логическое сложение).

Формула.	Значения переменных и функций.				Наименование.
					Эквивалентность.
					Импликация.
					Импликация.
					Отрицание импликации.
					Отрицание импликации.
					Штрих Шеффера (отрицание конъюнкции).
					Стрелка Пирса (отрицание дизъюнкции).
					Сумма по модулю два (отрицание эквивалентности).

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

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

Еще три функции (последние в табл. 3.3) обозначаются специальными символами. Используя табл. 3.3, эти функции можно записать в виде формул:

— сумма по модулю представляет собой отрицание эквивалентности:

— стрелка Пирса — это отрицание дизъюнкции:

— штрих Шеффера — это отрицание конъюнкции:

Необходимо заметить, что в таблицах истинности обычно употребляется стандартное расположение наборов значений переменных х_1; …, х_п. Если набор рассматривать как запись числа в двоичной системе счисления, то расположение наборов соответствует естественному порядку следования десятичных чисел 0,1, 2, 3, 4,5, …, 2″ -1.

Например, при п = 3 всевозможные наборы значений трех логических переменных располагаются в 2³ = 8 строках, как показано в табл. 3.4, и соответствуют определенным десятичным числам.

Соответствие набора двоичных чисел десятичной системе счисления.