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

Определение.

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

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

Таблица истинности функции может иметь следующий вид (таблица 3.1).

Таблица 3.1 – Пример таблицы истинности функции

В столбцах 1, 2, 3 даны все возможные кортежи значений трех аргументов, т.е. сочетание нулевых и единичных значений трех аргументов. В столбце 4 – значения функции .

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

Булевы функции, которые зависят от одной переменной, приведены в таблице 3.2 (их количество равно ).

Таблица 3.2 - Таблица истинности для булевых функций одной переменной

Две функции и представляют собой функции-константы:

- - является абсолютно ложной (константа нуля);

- - является абсолютно истинной (константа единицы).

Функция (функция повторения аргумента) повторяет значения переменной и поэтому просто совпадает с ней. Функция , называемая отрицанием или инверсией (читается «не »), является единственной нетривиальной функцией. Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

Всевозможные булевы функции двух переменных представлены в таблице 3.3 (их количество равно ).

Таблица 3.3 - Таблица истинности для булевых функций двух переменных

В таблице 3.4 приведена характеристика булевых функций двух переменных.

Таблица 3.4 - Характеристика булевых функций двух переменных

Функция	Обозначения (другие обозначения)	Названия	Чтение
		Константа 0 (тождественный нуль, всегда ложно)	Константа 0 (Любое 0)
	() (AND, И)	Конъюнкция (произведение, пересечение, логическое «и»)	и (и и ). Истинна тогда, когда истинны обе переменные
	() (>)	Отрицание импликации (запрет)	, но не
		Повторение (утверждение) первого аргумента	Как
	()	Отрицание обратной импликации	Не , но
		Повторение второго аргумента	Как
	()	Сумма по модулю 2 (неравнозначность, антиэквивалетность)	не как (или или ). Истинна, когда истинны или , или в отдельности
	() (OR, ИЛИ)	Дизъюнкция (логическая сумма, логическое «или»)	или (или хотя бы ). Истинна тогда, когда истинны или , или , или обе переменные
	()	Стрелка Пирса (функция Вебба, отрицание дизъюнкции)	Не и не . Истинна только тогда, когда и ложны
	() (Eqv)	Эквиваленция (равнозначность, эквивалентность)	как (, если, и только если )
	()	Отрицание (инверсия) второго аргумента	Не
	()	Обратная импликация (обратное разделение с запретом)	Если , то (или не )
	()	Отрицание (инверсия) первого аргумента	Не
	() (Imp)	Импликация (следование, селекция)	Если , то (не или ). Ложна тогда и только тогда, когда истинна и ложна
	()	Штрих Шеффера (отрицание конъюнкции, несовместимость, логическое «не-и»)	Не или не . Ложна только тогда, когда и истинны
		Константа 1 (тождественная единица, всегда истинно)	Константа 1 (Любое 1)

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

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

Примеры элементарных функций одной переменной приведены в таблице 3.2.

Примеры элементарных функций двух переменных представлены в таблицах 3.3 и 3.4, это: отрицание (); дизъюнкция ; конъюнкция ; импликация ; эквивалентность ; сумма по модулю 2 ; штрих Шеффера ; стрелка Пирса .

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

- отрицание (функция , принимающая значения 1, когда , и значение 0, когда );

- дизъюнкция (функция , принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0);

- конъюнкция (функция , принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1).

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

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

Дата добавления: 2014-10-22