2.2 Логические функции и таблицы их истинности.

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

Логической функцией являются:

– всякая логическая переменная и символы "истина"("1") и "ложь"("0");

– составные высказывания: ¬А,   А & В,   А v В,   А →B,   А ↔В (в

случае если А и В являются логическими функциями).

Используя вышеописанные логические функции можно образовать более сложные функции.

Значения каждой логической функции описывается таблицей истинности.

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

Для N переменных существует 2^N всевозможных наборов значений переменных.

Например функция, которая содержит две переменные, имеет четыре (2² = 4) набора значений переменных: (0, 0), (0, 1), (1, 0), (1, 1).

Если функция содержит три переменные, то возможных наборов значений переменных восемь (2³ = 8): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),

(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Составим таблицу истинности основных логических функций двух переменных (таблица 5.1).

Таблица 5.1 – Таблица истинности элементарных логических функций

X	Y	X	X & Y	X V Y	X  Y	X  Y
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

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

Пример 5.1 Составить таблицу истинности для функции, которая содержит две переменные x и y, ¬x&y v ¬(x v y) v x (таблица 21.2.2).

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

Из таблицы 5.2 видно, что при всех наборах значений переменных x и y, функция ¬x&y v ¬( x v y ) v x принимает значение 1.

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

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

Таблица 5.2 – Таблица истинности для функции ¬x&y v ¬(x v y) v x.

Переменные		Промежуточные логические функции					Результат
X	y	¬x	¬x&y	x v y	¬( x v y)	¬(x v y)vx	¬x&y v ¬(x v y)v x
0	0	1	0	0	1	1	1
0	1	1	1	1	0	0	1
1	0	0	0	1	0	1	1
1	1	0	0	1	0	1	1

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

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

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