Как вычислять выражение с поразрядными операциями

Про обозначения

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (Ù, Ú,), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù, Ú,), что еще раз подчеркивает проблему. Далее во всех решениях приводятся два варианта записи.

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

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

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

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

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

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

· таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию «Логика»)

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

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

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

· иногда полезны формулы де Моргана[1]:

(A Ù B) = A Ú B

(A Ú B) = A Ù B

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

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

· некоторые свойства импликации

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

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

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

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

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

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

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

Задачи с поразрядными операциями

Как вычислять выражение с поразрядными операциями

В задачах ЕГЭ до настоящего времени использовалась только поразрядная логическая операция «И» (она обозначается символом &), которая выполняется между соответствующими битами двоичной записи двух целых чисел. Не забывайте, что

Результат поразрядной операции между целыми числами – это целое число!.

Например, найдём результат поразрядной операции 29 & 11:

29 = 11101₂

11 = 01011₂

9 = 01001₂

Серым фоном отмечены биты, которые в обоих числах равны 1. Только они и будут равны 1 в числе-результате. Таким образом, 29 & 11 = 9.

Теперь найдём результат операции (29 & 11 = 0). Не забывайте, что

Результаты операций (a & b = 0) и (a & b ¹ 0) – это логические значения (истина/ложь)!.

Вычислим значение выражения:

((x & 26 = 0) Ú (x & 13 = 0)) ® ((x & 78 ¹ 0) ® (x & A = 0))

при x = 5, A = 57:

((5 & 26 = 0) Ú (5 & 13 = 0)) ® ((5 & 78 ¹ 0) ® (5 & 57 = 0))

Вычисляем результаты поразрядного И (это числа!):

5 & 26 = 0 5 & 13 = 5
5 & 78 = 4 5 & 57 = 1

Теперь вычисляем логические значения (И – истина, Л – ложь):

(5 & 26 = 0) = И (5 & 13 = 0) = Л
(5 & 78 ¹ 0) = И (5 & 57 = 0) = Л

Наконец, подставляем эти логические значения в заданное выражение:

(И Ú Л) ® (И ® Л)
И ® Л = Л

При заданных условиях выражение ложно.