Введение в логику

Эквивалентность формул

Показывать лекцию целиком
Записаться

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

Две формулы эквивалентны, если они задают одну и ту же функцию. Как можно установить эквивалентность формул? Один из способов состоит в том, чтобы построить таблицу истинности. Если две формулы на всех возможных значениях переменных дают одно и то же значение, то они определяют одну и ту же функцию, следовательно, формулы эквивалентны.

Давайте установим эквивалентности для некоторых функций из таблицы 3 предыдущего урока.

Исключающее Или эквивалентно отрицанию эквивалентности: $$(X \oplus Y) \equiv \neg (X \equiv Y)$$

Построим таблицы истинности для этих двух формул:

$$X$$ $$Y$$ $$X \equiv Y$$ $$\neg (X \equiv Y)$$ $$X \oplus Y$$
0 0 1 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 0 0

Два последних столбца таблицы совпадают, - следовательно, формулы эквивалентны.

Штрих Шеффера эквивалентен отрицанию конъюнкции: $$(X \uparrow Y) \equiv \neg(X Y)$$

Построим таблицы истинности для этих двух формул:

$$X$$ $$Y$$ $$X Y$$ $$\neg (X Y)$$ $$X \uparrow Y$$
0 0 0 1 1
0 1 0 1 1
1 0 0 1 1
1 1 1 0 0

Два последних столбца таблицы совпадают, - следовательно, формулы эквивалентны.

Операцию Штрих Шеффера называют антиконъюнкцией.

Стрелка Пирса эквивалентна отрицанию дизъюнкции: $$(X \downarrow Y) \equiv \neg(X | Y)$$

Построим таблицы истинности для этих двух формул:

$$X$$ $$Y$$ $$X | Y$$ $$\neg (X | Y)$$ $$X \downarrow Y$$
0 0 0 1 1
0 1 1 0 0
1 0 1 0 0
1 1 1 0 0

Два последних столбца таблицы совпадают, - следовательно, формулы эквивалентны.

Операцию Стрелка Пирса называют антидизъюнкцией.

Импликация $$X \to Y$$ эквивалентна дизъюнкции $$Y$$ и отрицания $$X$$: $$(X \to Y) \equiv (\neg X | Y)$$

Построим таблицы истинности для этих двух формул:

$$X$$ $$Y$$ $$\neg X$$ $$\neg X | Y$$ $$X \to Y$$
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1

Два последних столбца таблицы совпадают, - следовательно, формулы эквивалентны.

Эту эквивалентность, позволяющую избавиться от импликаций, часто используют при преобразовании формул.

Конъюнкция $$X Y$$ эквивалентна отрицанию дизъюнкции отрицаний: $$(X Y) \equiv \neg (\neg X | \neg Y)$$

Построим таблицы истинности для этих двух формул:

$$X$$ $$Y$$ $$\neg X$$ $$\neg Y$$ $$\neg X | \neg Y$$ $$\neg (\neg X | \neg Y)$$ $$X Y$$
0 0 1 1 1 0 0
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 0 1 1

Два последних столбца таблицы совпадают, - следовательно, формулы эквивалентны.

Дизъюнкция $$X | Y$$ эквивалентна отрицанию конъюнкции отрицаний: $$(X | Y) \equiv \neg (\neg X \neg Y)$$

Построим таблицы истинности для этих двух формул:

$$X$$ $$Y$$ $$\neg X$$ $$\neg Y$$ $$\neg X \neg Y$$ $$\neg (\neg X \neg Y)$$ $$X | Y$$
0 0 1 1 1 0 0
0 1 1 0 0 1 1
1 0 0 1 0 1 1
1 1 0 0 0 1 1

Два последних столбца таблицы совпадают, - следовательно, формулы эквивалентны.

Почему на практике используется небольшое число функций?

Логических функций много, особенно функций многих переменных. Почему же мы знаем и оперируем небольшим числом функций? Связано это с тем, что одни функции можно выражать через другие, как мы видели на примерах. А можно ли любую функцию выразить через немногие, базисные функции? Ответ на этот вопрос положителен.

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

Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^