2 (базовый уровень, время – 3 мин)
Тема: Построение и анализ таблиц истинности логических выражений.
Про обозначения
К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (Ù,Ú,¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù,Ú,¬), что еще раз подчеркивает проблему.
Что нужно знать:
- условные обозначения логических операций
¬ A, не A (отрицание, инверсия)
A Ù B, A и B (логическое умножение, конъюнкция)
A Ú B, A или B (логическое сложение, дизъюнкция)
A → B импликация (следование)
A º B эквивалентность (равносильность)
- операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
A → B = ¬ A Ú B
- иногда для упрощения выражений полезны формулы де Моргана:
¬ (A Ù B) = ¬ A Ú ¬ B
¬ (A Ú B) = ¬ A Ù ¬ B
- если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя – «эквивалентность»
- таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
- если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
- количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно 2^k, где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 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
ПРИМЕР ЗАДАНИЯ
Р-21. Логическая функция F задаётся выражением
((x Ù ¬y) Ú (w ® z)) º (z º x).
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
?
|
?
|
?
|
?
|
F
|
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
|
|
1
|
1
|
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
|