Построение таблиц истинности

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

Для проверки равносильности выражений А → В и ¬А ∨ В построим таблицу истинности выражения ¬А ∨ В. Операции будем выполнять в соответствии с их приоритетами: первой выполняется операция отрицания,второй — дизъюнкции. В таблице количество строк равно четырём.Количество столбцов определяется количеством логических переменных и логических операций в выражении.

Результат в четвёртом столбце получен дизъюнкцией значений третьего и второго столбцов. Он совпадает с таблицей истинности операции импликации, записанной в последнем столбце.

Для построения таблицы истинности логического выражения необходимо:

1. определить количество строк таблицы по формуле 2^N, где N — количество используемых логических переменных;
2. определить порядок выполнения операций в формуле с учётом приоритетов и скобок;
3. найти значения промежуточных формул и конечного результата в соответствии с таблицами истинности.

Построим таблицу истинности для выражения ¬А & В ∨ А & ¬В, чтобы убедиться в том, что оно равносильно исключающему ИЛИ А ⊕ В.

В первую очередь выполняется операция отрицания (столбцы 3 и 4). Затем конъюнкция (логическое умножение) столбцов 3 и 2, столбцов 1 и 4. Результат в столбце 7 получен дизъюнкцией (логическим сложением)значений пятого и шестого столбцов, он совпадает с таблицей истинности операции исключающего ИЛИ (последний столбец).