Логика и таблицы
Логические задачи на экзамене проверяют, умеете ли вы переводить условие на язык высказываний, составлять таблицу вариантов и отбирать подходящие строки. В этой теме собраны основные таблицы истинности, логические приемы и алгоритмы, которые помогают решать задания без перебора наугад.
Высказывания и логические связки
Высказывание — это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно. Например: «Число 12 делится на 3» — истинное высказывание, а «Число 12 простое» — ложное. Вопросы, команды и предложения с неизвестными переменными сами по себе высказываниями не являются.
Высказывания обозначают буквами \(A\), \(B\), \(C\). Значение «истина» часто записывают как 1, а «ложь» — как 0. Из высказываний с помощью логических связок получают сложные выражения.
| Связка | Обозначение | Когда выражение истинно |
|---|---|---|
| Отрицание | \(\neg A\) | когда \(A\) ложно |
| Конъюнкция, «и» | \(A\land B\) | когда истинны и \(A\), и \(B\) |
| Дизъюнкция, «или» | \(A\lor B\) | когда истинно хотя бы одно из \(A\), \(B\) |
| Импликация, «если ..., то ...» | \(A\to B\) | кроме случая \(A=1\), \(B=0\) |
| Эквиваленция, «тогда и только тогда» | \(A\leftrightarrow B\) | когда значения \(A\) и \(B\) совпадают |
Подробные свойства отдельных связок разобраны на страницах конъюнкция, дизъюнкция, импликация и равносильность высказываний. Здесь важно помнить смысл связок и порядок вычислений.
Если скобок нет, сначала выполняют отрицание, затем конъюнкцию, потом дизъюнкцию, после неё импликацию и в конце эквиваленцию. При сомнении выражение лучше сразу заключить в скобки.
Алгоритм составления таблицы истинности
Таблица истинности содержит все возможные наборы значений исходных высказываний и значение сложного выражения для каждого набора. Если исходных переменных \(n\), число строк равно \(2^n\). Поэтому для трёх переменных нужно \(2^3=8\) строк, а для четырёх — уже 16.
- Выпишите все исходные переменные и определите число строк: \(2^n\).
- Заполните столбцы \(A\), \(B\), \(C\) всеми наборами нулей и единиц.
- Разбейте выражение на простые части, начиная с внутренних скобок.
- Добавьте отдельный столбец для каждой промежуточной операции.
- В последнем столбце вычислите всё выражение и сравните строки с условием задачи.
Для двух переменных стандартный порядок строк можно взять таким: \(00\), \(01\), \(10\), \(11\). Для трёх переменных удобно использовать \(000\), \(001\), \(010\), \(011\), \(100\), \(101\), \(110\), \(111\). Порядок допустимо менять, но пропускать варианты нельзя.
Некоторые выражения можно заменить более простыми: \(A\land 1=A\), \(A\lor 0=A\), \(A\land 0=0\), \(A\lor 1=1\), \(\neg\neg A=A\). По законам де Моргана: \(\neg(A\land B)=\neg A\lor\neg B\) и \(\neg(A\lor B)=\neg A\land\neg B\). Подробнее см. законы де Моргана.
Замена импликации формулой \(\neg A\lor B\) особенно полезна при построении таблицы: отдельный столбец для специальной связки не требуется. Чтобы получить отрицание всего выражения, ставьте знак отрицания перед скобками, а затем применяйте законы де Моргана.
В каком случае импликация \(A\to B\) ложна?
Разобранный пример: поиск подходящей строки
Пусть \(A\), \(B\) и \(C\) — высказывания. Известно, что выражение \(F=(A\to B)\land(\neg C\lor A)\) истинно. Какие значения могут иметь \(A\), \(B\), \(C\)? Решим задачу по столбцам, не вычисляя всё в уме.
Выражение истинно в четырёх случаях: \(000\), \(010\), \(110\) и \(111\). Если в условии требуется единственный набор, значит, обычно добавлено ещё одно ограничение — например, значение другой формулы или количество истинных высказываний.
Логические приемы для экзамена
Во многих задачах полная таблица не нужна. Сначала ищите ограничения, которые сразу исключают часть вариантов. Для конъюнкции \(X\land Y=1\) обе части должны быть истинны. Для дизъюнкции \(X\lor Y=0\) обе части должны быть ложными. Это позволяет рассуждать «от результата».
- Если \(A\land B\) истинно, то \(A=1\) и \(B=1\).
- Если \(A\lor B\) ложно, то \(A=0\) и \(B=0\).
- Если \(A\to B\) ложно, то сразу \(A=1\), \(B=0\).
- Если \(A\leftrightarrow B\) истинно, то \(A\) и \(B\) равны.
- Если \(\neg A\) истинно, то \(A\) ложно.
В задачах на соответствие часто встречается неизвестный порядок строк или столбцов. Тогда полезно сравнивать не отдельные значения, а характерные признаки: число единиц, наличие строки из одних нулей, симметрию таблицы. Для нескольких условий применяйте метод перебора вариантов, а для последовательных выборов — дерево возможных вариантов.
Если условие требует, чтобы формула была ложной, найдите единственный способ получить ложь. Например, для \(A\land B\) это означает хотя бы один ноль, а для \(A\to B\) — строго пару \((1,0)\). Такой обратный ход часто быстрее полного перебора.
Логические задачи с текстовым условием
Сначала замените длинные фразы короткими буквами. Например, \(A\) — «введён пароль», \(B\) — «открыта дверь». Фразу «дверь открыта только тогда, когда введён пароль» переводят как \(B\to A\), потому что открытая дверь является следствием введённого пароля. Слово «только» часто меняет направление импликации.
Фраза «хотя бы одно» означает дизъюнкцию, «ровно одно» — что истинно одно из высказываний, но не оба, а «не менее двух» — условие на количество единиц. Если нужно проверить все возможные значения нескольких признаков, составьте таблицу вариантов.
1. Путают «или» в математике с исключающим «или»: \(A\lor B\) допускает случай, когда истинны оба высказывания. 2. Считают импликацию ложной при \(A=0\) — это неверно. 3. Забывают скобки при отрицании: \(\neg(A\lor B)\) не равно \(\neg A\lor B\). 4. Выписывают не все \(2^n\) наборов. 5. Переводят «только если» как \(A\to B\), хотя обычно верно \(B\to A\).
Связь с упрощением и логическими уравнениями
Если выражение содержит много повторяющихся частей, используйте упрощение логических выражений: раскрывайте импликации, применяйте законы де Моргана, выносите общие множители. Если неизвестными являются значения переменных, а условие задаёт равенство логических выражений, это уже логическое уравнение.
Проверяйте результат обратной подстановкой. После преобразований полезно выбрать несколько наборов значений и убедиться, что исходная и новая формулы дают одинаковый результат. Полное доказательство равносильности выполняют сравнением последних столбцов таблиц истинности.
Для \(n\) переменных — \(2^n\) строк. Импликация ложна только на \((1,0)\). В конъюнкции нужна одна единица во всех частях, в дизъюнкции достаточно одной истинной части. Любое сложное выражение вычисляйте по промежуточным столбцам.
Итоговая проверка
Главное
- Высказывание имеет одно из двух значений: истина или ложь; сложные высказывания строятся логическими связками.
- Для \(n\) переменных таблица истинности содержит \(2^n\) строк, а вычисления выполняются по промежуточным столбцам.
- Импликация \(A\to B\) равносильна \(\neg A\lor B\) и ложна только при \(A=1\), \(B=0\).
- При решении используйте обратное рассуждение: анализируйте, какие значения необходимы для истинности или ложности всей формулы.
- В текстовой задаче сначала выделите простые высказывания, затем переведите фразы в формулу и только после этого перебирайте варианты.