Составление таблицы истинности для логической формулы

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0), (0,1), (1,0), (1,1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т. д.

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

Пример. Составим таблицу истинности для формулы А∧B∨А∨B∨А.

Если задача сформулирована на естественном языке, её необходимо формализовать, то есть записать на языке алгебры высказываний. Полученное логическое выражение необходимо упростить и проанализировать. Упрощение логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов; не содержащему отрицаний неэлементарных формул) эквивалентному выражению путем использования основных законов алгебры логики. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь).

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

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

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

(к отрицаниям неэлементарных формул применяется правило де Моргана, используются законы двойного отрицания и поглощения).

(общий множитель А выносится за скобки, комбинируются слагаемые в скобках – первое с третьим и второе с четвертым, к дизъюнкции В ⋅С +В ⋅С применяется правило операций переменной с её инверсией).

Не нашли, что искали? Воспользуйтесь поиском: