Логические операции
Когда «И» истинно, а когда «ИЛИ»?
A ∧ B; A ∨ B; ¬A
- A
- первое высказывание (истина или ложь), 0 или 1
- B
- второе высказывание, 0 или 1
Конъюнкция ∧ («И») истинна только когда истинны оба. Дизъюнкция ∨ («ИЛИ») ложна только когда ложны оба. Отрицание ¬ переворачивает значение.
Импликация A → B ложна ровно в одном случае: A истинно, B ложно. Это самое частое место ошибок в таблицах истинности.
Законы де Моргана
Как раскрыть НЕ над скобкой, где стоит И или ИЛИ?
¬(A ∧ B) = ¬A ∨ ¬B ; ¬(A ∨ B) = ¬A ∧ ¬B
- A
- первое высказывание (0 или 1)
- B
- второе высказывание (0 или 1)
Отрицание над скобкой переходит на каждое высказывание, а операция меняется на противоположную: И становится ИЛИ и наоборот. Например, НЕ(x > 3 И x < 10) превращается в (x ≤ 3) ИЛИ (x ≥ 10). Это главный инструмент упрощения выражений в заданиях 2 и 15.
Частая ошибка — поменять операцию, но забыть навесить отрицания на A и B (или наоборот). Меняется и то и другое одновременно.
Импликация
Почему «если 2·2 = 5, то Луна из сыра» — истинное высказывание?
A → B = ¬A ∨ B
- A
- посылка — высказывание до стрелки
- B
- следствие — высказывание после стрелки
Импликация A → B ложна в единственном случае: A истинно, а B ложно. Из ложной посылки следует что угодно, поэтому «если 2·2 = 5, то Луна из сыра» — истина. Для преобразований заменяй стрелку по формуле: (x > 5) → (x > 3) = (x ≤ 5) ИЛИ (x > 3), а это истинно при любом x.
Импликация не симметрична: A → B и B → A — разные выражения. При ложном A результат — истина при любом B.
Побитовые операции
Что на самом деле делает операция & с двумя числами?
&: единица там, где 1 у обоих · |: единица там, где 1 хотя бы у одного · считай столбиком в двоичной
Поразрядные операции сравнивают числа бит за битом в двоичной записи. Для 12 & 10 запиши 1100 и 1010 столбиком: единица остаётся там, где она у обоих чисел, — выйдет 1000, то есть 8. А 12 | 10 = 1110 = 14, потому что ИЛИ зажигает бит, когда единица есть хотя бы в одном из чисел.
Проверка бита: x & 2ᵏ ≠ 0 означает, что бит номер k (нумерация с нуля, справа) равен единице. Записывай оба числа с одинаковым числом разрядов, дописывая нули слева.
Все карточки предмета — в разделе «Формулы»