11 мин чтениялогикатаблица истинностиимпликациябитовые операцииКЕГЭ
Логика и алгебра высказываний
Логические операции, таблицы истинности, законы алгебры логики и решение уравнений и систем с логическими выражениями.
Открываем тему…
Логические операции
- Отрицание ¬A: меняет значение на противоположное.
- Конъюнкция A ∧ B (И): истинна, только когда оба операнда истинны.
- Дизъюнкция A ∨ B (ИЛИ): ложна, только когда оба ложны.
- Импликация A → B: ложна, только когда A истинно, а B ложно; равносильна ¬A ∨ B.
- Эквивалентность A ≡ B: истинна, когда значения совпадают.
- Исключающее ИЛИ A ⊕ B: истинно, когда значения различны.
Интерактивная иллюстрация
AND
0
OR
1
XOR
1
- Поглощение: A ∨ (A ∧ B) = A; A ∧ (A ∨ B) = A.
- Дистрибутивность: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), и наоборот.
- A ∧ ¬A = 0, A ∨ ¬A = 1, A ∧ 1 = A, A ∨ 0 = A.
Анализ таблиц и уравнений
В заданиях на таблицы истинности вам дан фрагмент таблицы и нужно определить, какой переменной соответствует каждый столбец. Начинайте с строк, в которых функция принимает редкое значение (например, единственная 1 у конъюнкции или единственный 0 у дизъюнкции) — они сразу ограничивают варианты.
ПримерКоличество решений
Сколько существует наборов (x₁, x₂, x₃), для которых истинно (x₁ → x₂) ∧ (x₂ → x₃)?
Решение
Условие означает, что последовательность x₁ ≤ x₂ ≤ x₃ не убывает: допустимые наборы 000, 001, 011, 111. Ответ — 4. Для цепочки из n переменных получится n + 1 набор.
ПримерПроверка перебором на Python
Для выражения (x ∨ y) → (z ∧ ¬w) постройте таблицу истинности.
Решение
from itertools import product
print('x y z w F')
for x, y, z, w in product([0, 1], repeat=4):
F = (not (x or y)) or (z and not w)
print(x, y, z, w, int(F))
Для сопоставления столбцов в задании достаточно выводить только строки, где F принимает «редкое» значение.
Поразрядные операции и отрезки
Задачи с «Делится(x, A)» и «x & A ≠ 0» решаются анализом по битам: если выражение должно быть истинно для всех x, придерживайтесь минимального A. Для проверки используйте перебор x в диапазоне, например, до 1000, и выбор ответа среди найденных значений A.
ПримерЦепочка дизъюнкций
Сколько существует наборов (x₁, x₂, x₃, x₄), для которых истинно (x₁ ∨ x₂) ∧ (x₂ ∨ x₃) ∧ (x₃ ∨ x₄)?
Решение
Каждая скобка запрещает пару нулей в соседних переменных, то есть в наборе нет двух нулей подряд. Пусть aₙ — число двоичных строк длины n без «00». Если строка заканчивается на 1, перед ней может стоять любая допустимая строка длины n − 1 (aₙ₋₁ вариантов); если заканчивается на 0, то перед ним обязательно 1 и перед ней — любая допустимая строка длины n − 2 (aₙ₋₂). Поэтому aₙ = aₙ₋₁ + aₙ₋₂ (числа Фибоначчи): a₁ = 2, a₂ = 3, a₃ = 5, a₄ = 8. Ответ — 8.
Проверка:
from itertools import product
print(sum(1 for x in product([0, 1], repeat=4) if (x[0] or x[1]) and (x[1] or x[2]) and (x[2] or x[3])))
ПримерПобитовая конъюнкция и параметр A
Через x & y обозначается поразрядная конъюнкция. Для какого наименьшего натурального A выражение (x & A = 0) → ((x & 20 ≠ 0) → (x & 7 ≠ 0)) тождественно истинно при любом неотрицательном целом x?
Решение
Выражение ложно, когда одновременно x & A = 0, x & 20 ≠ 0 и x & 7 = 0. Здесь 20 = 10100₂ (биты 4 и 2), 7 = 111₂ (биты 0, 1, 2). Условие x & 7 = 0 означает, что в x нет битов 0, 1, 2; тогда x & 20 ≠ 0 возможно только за счёт бита 4 (число 16). Значит, «опасны» все x с битом 16 и без битов 0–2. Среди них есть x = 16: чтобы для него не выполнялось x & A = 0, в A должен быть бит 16. Если бит 16 есть в A, то любой «опасный» x имеет x & A ≠ 0, и ложность невозможна. Наименьшее такое A равно 16.
Проверка:
for A in range(1, 64):
if all(not (x & A == 0 and x & 20 != 0 and x & 7 == 0) for x in range(1024)):
print(A)
break
ПримерНаименьший отрезок A
Заданы отрезки P = [14; 30] и Q = [20; 45]. Какова наименьшая возможная длина отрезка A, при которой формула (x ∈ P) → ((x ∈ Q) ∨ (x ∈ A)) тождественно истинна?
Решение
Импликация ложна при x ∈ P, x ∉ Q и x ∉ A. Чтобы ложных значений не было, множество P \ Q обязано лежать внутри A. P \ Q = [14; 20) — точки из P, не попавшие в Q. Наименьший отрезок, покрывающий [14; 20), — это [14; 20], его длина 20 − 14 = 6.