Задание 2

Задание № 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) = ¬ A Ù ¬ B             

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

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

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

·      количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где  – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 2³=8 строчек, если заданы только 6 из них, то можно найти 2^8-6=2²=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)

·      логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)

·      логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)

·      логическое следование (импликация) А→В равна 0 тогда и только тогда, когда из A (посылка) истинна, а B (следствие) ложно

·      эквивалентность АºB  равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1

Пример задания:

Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:

x1	x2	x3	x4	x5	x6	x7	x8	F
	0						1	0
1			0					1
			1				1	1

Каким выражением может быть F?

1)  x1 Ù ¬x2 Ù x3 Ù  ¬x4 Ù x5 Ù x6 Ù ¬x7 Ù ¬x8

2)  x1 Ú x2 Ú x3 Ú  ¬x4 Ú ¬x5 Ú ¬x6 Ú ¬x7 Ú ¬x8

3)  ¬x1 Ù x2 Ù ¬x3 Ù  x4 Ù x5 Ù ¬x6 Ù ¬x7 Ù ¬x8

4)  x1 Ú ¬x2 Ú x3 Ú  ¬x4 Ú ¬x5 Ú ¬x6 Ú ¬x7 Ú ¬x8

Решение:

1)   перепишем выражения в более простой форме, заменив «И» (Ù) на умножение и «ИЛИ» (Ú) на сложение:

1)

2)

3)

4)

2)   в последнем столбце таблицы истинности видим две единицы, откуда сразу следует, что это не может быть цепочка операций «И» (конъюнкций), которая даёт только одну единицу; поэтому ответы 1 и 3 заведомо неверные

3)   анализируем первую строку таблицы истинности; мы знаем в ней только два значения - и

4)   для того, чтобы в результате в первой строке получить 0, необходимо, чтобы переменная  входила в сумму с инверсией (тогда из 1 получится 0!), это условие выполняется для обоих оставшихся вариантов, 2 и 4

5)   кроме того, переменная  должна входить в выражение без инверсии (иначе соответствующее слагаемое в первой строке равно 1, и это даст в результате 1);  этому условию не удовлетворяет выражение 4; остается один возможный вариант – выражение 2

6)   Ответ: 2.