Задачи на логическое кодирование
Задачи на логическое кодирование проверяют умение переводить условие в логическое выражение, строить таблицу истинности и анализировать полученные строки. Перед изучением темы полезно повторить [[truth-table:таблицы истинности]], [[logical-operation:логические операции]] и [[boolean-value:логические значения]].
1. Что кодируется логическим выражением
В логических задачах высказывания обозначают переменными: \(A\), \(B\), \(C\) и так далее. Каждая переменная принимает одно из двух [[boolean-value:логических значений]]: 1 — истина, 0 — ложь. Например, \(A\) может означать «число делится на 3», а \(B\) — «число больше 10».
Из переменных с помощью операций строят [[logical-expression:логические выражения]]. Основные операции: отрицание \(\neg A\), конъюнкция \(A \land B\) («и»), дизъюнкция \(A \lor B\) («или»), исключающее «или» \(A \oplus B\) и импликация \(A \to B\) («если \(A\), то \(B\)»). Скобки задают порядок вычислений.
Логическое выражение — запись, составленная из логических переменных, констант 0 и 1, операций и скобок. Результат выражения также является логическим значением: 0 или 1.
Если скобки не указаны, сначала выполняется отрицание, затем конъюнкция, потом дизъюнкция и исключающее «или», после этого импликация. На экзамене безопаснее расставлять скобки явно и вычислять выражение по промежуточным столбцам.
2. Сколько строк должно быть в таблице
Если в выражении встречаются \(n\) различных переменных, таблица истинности содержит \(2^n\) строк — по одной строке для каждого набора значений. Например, для трёх переменных \(A\), \(B\), \(C\) будет \(2^3=8\) наборов.
| Число переменных | Число наборов |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
Переменные обычно записывают слева направо, а их значения перебирают систематически: последняя переменная меняется в каждой строке, предпоследняя — через одну строку, следующая — через две. Такой порядок похож на запись двоичных чисел от \(0\) до \(2^n-1\).
| A | B | C | Номер набора | Набор |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 000 |
| 0 | 0 | 1 | 2 | 001 |
| 0 | 1 | 0 | 3 | 010 |
| 0 | 1 | 1 | 4 | 011 |
| 1 | 0 | 0 | 5 | 100 |
| 1 | 0 | 1 | 6 | 101 |
| 1 | 1 | 0 | 7 | 110 |
| 1 | 1 | 1 | 8 | 111 |
Сначала выпишите все различные переменные, даже если одна из них встречается несколько раз. Затем вычислите число строк \(2^n\). Пропуск набора или повтор строки приводит к неверному ответу независимо от правильности дальнейших вычислений.
Сколько строк должна иметь таблица истинности выражения \((A\lor B)\land(\neg A\lor C)\)?
3. Алгоритм построения таблицы истинности
Полная таблица должна показывать не только исходные переменные, но и промежуточные результаты. Это уменьшает количество ошибок и позволяет быстро проверить отдельные части выражения.
- Выпишите все различные переменные и определите число строк \(2^n\).
- Заполните столбцы переменных всеми наборами нулей и единиц.
- Разбейте выражение на простые части, начиная с внутренних скобок.
- Для каждой части создайте отдельный столбец.
- Вычислите итоговый столбец и при необходимости выпишите номера строк, где результат равен 1.
Если требуется найти строки, в которых выражение истинно, достаточно просмотреть итоговый столбец. Если требуется восстановить выражение или установить соответствие между столбцами, сравнивайте столбцы по всем строкам, а не по нескольким выбранным примерам.
Итоговый столбец — это функция от переменных. Каждому набору входных значений соответствует ровно один результат. Два выражения равносильны, если их итоговые столбцы совпадают во всех строках.
4. Разобранный пример
Построим таблицу и найдём наборы, на которых истинно выражение \(F=(A\land\neg B)\lor(B\land C)\). Здесь три переменные, поэтому потребуется 8 строк. Удобно сначала вычислить \(\neg B\), затем \(A\land\neg B\) и \(B\land C\).
| A | B | C | ¬B | A ∧ ¬B | B ∧ C | F |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
Итог \(F=1\) получается в строках с наборами \((A,B,C)=(0,1,1)\), \((1,0,0)\), \((1,0,1)\) и \((1,1,1)\). Важно не перепутать номер строки с самим набором значений.
5. Анализ выражений и быстрые преобразования
Не всегда нужно строить полную таблицу. Иногда выражение можно упростить с помощью законов логики. Например, конъюнкция с единицей не меняет значение, а дизъюнкция с единицей всегда даёт 1.
Полезны законы де Моргана: отрицание конъюнкции превращается в дизъюнкцию отрицаний, а отрицание дизъюнкции — в конъюнкцию отрицаний. Эти преобразования помогают проверять ответ и сокращать выражения.
В задачах на перебор часто ищут количество наборов, где выражение истинно. Для небольших выражений надёжнее построить таблицу. Для больших выражений сначала используют ограничения: конъюнкция требует истинности всех множителей, а дизъюнкция становится истинной уже при одном истинном слагаемом.
1) Считают повторяющуюся переменную новой. 2) Используют \(n\) строк вместо \(2^n\). 3) Читают \(A\to B\) как «\(A\) и \(B\)»; импликация ложна только при \(A=1\), \(B=0\). 4) Неверно применяют отрицание к скобкам: \(\neg(A\lor B)\) не равно \(\neg A\lor\neg B\). 5) Выполняют операции слева направо, игнорируя скобки и приоритет.
6. Как решать экзаменационные задачи
В заданиях формата ЕГЭ-14 выражение может быть дано словами, таблицей, схемой или набором условий. Сначала переведите каждое условие в обозначение, затем определите, какие переменные действительно входят в задачу. После этого выберите способ решения: полная таблица, упрощение или перебор подходящих наборов.
- Обозначить высказывания короткими переменными.
- Проверить, что одинаковые высказывания имеют одинаковые обозначения.
- Расставить скобки и определить последнюю операцию.
- Сверить число строк с числом различных переменных.
- Проверить итог хотя бы на двух крайних наборах: всех нулей и всех единиц.
Для автоматической проверки можно представить наборы как двоичные числа, но на экзамене таблица обычно надёжнее программы. Связь логических значений с двоичным кодом особенно полезна при изучении общего раздела [[logic-coding:логического кодирования]].
Проверь себя
Главное
- Для \(n\) различных переменных таблица истинности содержит \(2^n\) строк.
- Выражение вычисляют по скобкам, приоритету операций и промежуточным столбцам.
- Итоговый столбец показывает значение функции на каждом наборе переменных.
- Импликация ложна только при \(A=1\) и \(B=0\); законы де Моргана помогают преобразовывать отрицания.
- Перед сдачей ответа проверьте число переменных, число строк и несколько строк итогового столбца.