Построение и анализ таблиц истинности логических выражений

Урок #2

Время на выполнение - 3 мин.

Что нужно знать: 

• условные обозначения логических операций 

¬ A, не A (отрицание, инверсия) 

A Ù B,  A и B (логическое умножение, конъюнкция) 

A Ú B, A или B (логическое сложение, дизъюнкция) 

A → B   импликация (следование) 

A º B   эквивалентность (равносильность)(° - 3-е равенство - 3 паралельные черточки)

• операцию «импликация» можно выразить через «ИЛИ» и «НЕ»: 

A → B = ¬ A Ú B или в других обозначениях A → B = 

• * иногда для упрощения выражений полезны формулы де Моргана: 

¬ (A Ù B) = ¬ A Ú ¬ B  

¬ (A Ú B) = ¬ A Ù ¬ B  

• если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя – «эквивалентность» 

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

• если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных); 
• количество разныхлогических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующихстрок; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся) 
• логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно) 
• логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно) 
• логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно 
• эквивалентность АºB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1 

Ход решения:

1)записываем выражение в более попятной форме

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

3)выбираем для начальной подготовки переменную, которая чаще всего встречается в выражении и поэтому подстановка её значения даст наибольшую информацию

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

5)затем сравниваем нашу таблицу с таблицей в задании и получаем ответ.

P.S. Мы взяли условно значение функции ноль, чаще встречается значение функции единица.