© К. Поляков, 2009-2016

18(Повышенный уровень, время – 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

• для упрощения выражений можно использовать формулы

(т.к. )(т.к.)

Связь логики и теории множеств:

• пересечение множеств соответствует умножению логических величин, а объединение – логическому сложению;

• пустое множество – это множество, не содержащее ни одного элемента, оно играет роль нуля в теории множеств;

• универсальное множество – это множество, содержащее все возможные элементы заданного типа (например, все целые числа), оно играет роль логической единицы: для любого множества целых чиселXсправедливы равенстваX + I = IиX · I = X(для простоты мы используем знаки сложения и умножения вместо знаков пересеченияи объединениямножеств)

• дополнениемножестваX– это разность между универсальным множествомIи множествомX(например, для целых чисел– все целые числа, не входящие вX)

• пусть требуется выбрать множество Aтак, чтобы выполнялось равенствоA + X = I; в этом случае множествоAдолжно включать дополнение, то есть(или «по-простому» можно записать), то есть

• пусть требуется выбрать множество Aтак, чтобы выполнялось равенство, в этом случае множестводолжно включать дополнение, то есть; отсюда, то есть

Пример задания (м.В. Кузнецова):

Р-23. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение (( (X & A  0)  (X & 12  0))  ((X & A =0)  (X & 21 0)))  ((X & 21  0)  (X & 12 =0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Решение:

1. Введём обозначения:

P = (X & 12  0), Q = (X & 21  0), A=(X & A  0)

2. перепишем исходное выражение и преобразуем его, используя свойство импликации:

Выражение в первой скобке упрощаем, используя следствие из распределительного закона

Полученное выражение также можно упростить, используя ещё одно следствие из распределительного закона

3. перейдем к импликации

4. таким образом, для всех x, для которых, нам нужно обеспечить(или)

5. Запишем двоичное представление чисел 21 = 10101₂и 12 = 1100₂

6. означает, что биты 3 и 2 числаx– нулевые

7. означает, что среди битов 4, 2 и 0 есть ненулевые

8. условие говорит о том, что какие-то биты числа нулевые; из пункта 6 мы можем точно сказать, что биты 3 и 2 числаx– нулевые, поэтому в числеAэти биты можно установить в 1; (а остальные биты числаxмогут быть равны 1!)

9. поэтому A_max= 2³ + 2² = 12.

10. Ответ: 12.