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