3.2 Логические функции и таблицы их истинности
С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической функцией.
Логической функцией являются:
– всякая логическая переменная и символы "истина"("1") и "ложь"("0");
– составные высказывания: ¬А, А & В, А v В, А →B, А ↔В (в
случае если А и В являются логическими функциями).
Используя вышеописанные логические функции можно образовать более сложные функции.
Пример 3.2.1. Обозначим через А логическую функцию "Я куплю яблоки", через В — логическую функцию "Я куплю абрикосы", а через С — логическую функцию "Я приготовлю пирог". Логические функции А, В, С – элементарные. Высказывание "я куплю яблоки или абрикосы", также является элементарной логической функцией A V B (это следует из определения логической функции). Используя элементарные логические функции A V B и С можно образовать функцию (A V B) → С, которой соответствует высказывание: "Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Такая же формула соответствует высказыванию "Если Игорь знает английский или японский язык, то он получит работу переводчика".
Значения каждой логической функции описывается таблицей истинности.
Таблица истинности представляет собой таблицу, устанавливающую соответствие между всевозможными наборами значений переменных и значениями функций.
Для N переменных существует 2N всевозможных наборов значений переменных.
Например функция, которая содержит две переменные, имеет четыре (22 = 4) набора значений переменных: (0, 0), (0, 1), (1, 0), (1, 1).
Если функция содержит три переменные, то возможных наборов значений переменных восемь (23 = 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).
Количество наборов для функции с четырьмя переменными равно шестнадцати (24 = 16) и т.д.
Для логической функции двух переменных существует 24=16 логических функций. Нами рассматриваются основные логические функции.
Составим таблицу истинности основных логических функций двух переменных (таблица 3.2.1).
Таблица 3.2.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 |
Удобной формой записи при нахождении значений сложной логической функции является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Пример 3.2.2. Составить таблицу истинности для функции F которая содержит две переменные x и y. F = ¬x&y v ¬(x v y) (таблица 3.2.2).
В двух первых столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных функций, а в последнем столбце — результат.
Таблица 3.2.2 – Таблица истинности для функции F.
Переменные |
Промежуточные логические функции |
Результат |
||||||
x |
y |
¬x |
¬x&y |
x v y |
¬( x v y) |
¬x&y v ¬(x v y) |
||
0 |
0 |
1 |
0 |
0 |
1 |
1 |
||
0 |
1 |
1 |
1 |
1 |
0 |
1 |
||
1 |
0 |
0 |
0 |
1 |
0 |
0 |
||
1 |
1 |
0 |
0 |
1 |
0 |
0 |
||
Пример 3.2.3. Составить таблицу истинности для функции
G = ¬( z v ¬y) v ¬z&y (таблица 3.2.3).
Таблица 3.2.3 – Таблица истинности для функции G.
Переменные |
Промежуточные логические функции |
Результат |
||||||
z |
y |
¬y |
z v ¬y |
¬(z v ¬y) |
¬z |
¬ z&y |
¬( z v ¬y) ¬z&y |
|
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
Пример 3.2.4. Составить таблицу истинности для функции
R = (a b) & (a & ¬b) (таблица 3.2.4).
Таблица 3.2.4 – Таблица истинности для функции R.
Переменные |
Промежуточные логические функции |
Результат |
|||||
a |
b |
a b |
¬ b |
a& ¬b |
(a b) & (a & ¬b) |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
Функция, которая принимает значение "истина" для всех наборов значений переменных, называется тождественно истинной функцией или тавтологией.
Функция, которая принимает значение "ложь" для всех наборов значений переменных, называется тождественно ложной функцией или противоречием.
Функция, которая принимает для некоторых наборов значений переменных значение "истина", а для других – значение "ложь", называется выполнимой логической функцией.
Из примера 3.2.2 видно, что функция F в некоторых случаях принимает значение 1, а в некоторых – 0, следовательно является выполнимой. В примере 3.2.3 функция F для всех наборов переменных принимает значение 1, таким образом она является тождественно истинной. функция R (пример 3.2.4) на всех наборах переменных принимает значение 0 и является тождественно ложной.
Пример 3.2.5. Составить таблицу истинности для функции, которая содержит три переменные x, y и z, S = ¬( x v ¬y) v ¬x&z (таблица 3.2.5).
Таблица 21.2.5. – Таблица истинности для функции S.
Переменные |
Промежуточные логические функции |
Результат |
|||||||
x |
y |
z |
¬y |
x v ¬y |
¬( x v ¬y) |
¬x |
¬ x&z |
¬( x v ¬y) v ¬x&z |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
Из таблицы 3.2.5. видно, что функция S является выполнимой.