Задание 2 · Таблицы истинности
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — подписать столбцы фрагмента для F = ¬x ∧ (y ∨ z) ∧ (z → w) — прошла через все подтемы, и каждая добавляла к решению новый шаг. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Логические операции»: снаружи И — все части равны 1. Точками отмечены новые строки.
- Подтема 2, «Формула и её таблица»: от F к переменным: 4 набора из 16.
- Подтема 3, «Фрагмент и столбцы»: подписи столбцов по строкам.
- Подтема 4, «Решение программой»: те же наборы — перебором. Ответ задачи темы — wxzy.
Задача не менялась — менялся способ: сначала смысл операций, потом наборы с F = 1 рассуждением, потом подписи столбцов и, наконец, те же наборы программой. Так решается любое задание 2.
Карта темы
Каждая подтема дала несколько правил, и любое решение собирается из них. Сверху — путь от формулы к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Формулакакие наборы дают нужное F
- Фрагментстроки с пустыми клетками
- Ответбуквы столбцов слева направо
1Логические операции
- A ∧ B = 1только при A = B = 1
- A ∨ B = 0только при A = B = 0
- A → B = 0только 1 → 0; 0 → 0 истинно
- A ≡ B = 1значения совпали, 0 ≡ 0 тоже
2Формула и её таблица
- порядок действийскобки, ¬, ∧, ∨, →, ≡
- 2ⁿстрок в полной таблице n переменных
- от F к входамначинают с внешней операции
- «или» в выводевыписать каждый случай, не выбирать наугад
3Фрагмент и порядок столбцов
- пустая клетка0 или 1, не третье значение
- подпись столбцаодна и та же во всех строках
- строкипосле заполнения все разные, порядок любой
- начать сособого столбца или строки с редкими значениями
4Решение программой
a <= bимпликация a → ba == bравнозначность, в скобкахproduct((0, 1), repeat=n)все наборы n переменных- вывод программынаборы, а не ответ: столбцы подбирают сам
Как решать
Любое задание 2 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Готовый ответ проверяют четырьмя вопросами:
- Сохранены ли все известные цифры фрагмента?
- Одинаковы ли подписи столбцов во всех строках?
- Даёт ли формула нужное F в каждой строке?
- Различны ли восстановленные строки?
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- «или» — оба
- из A ∨ B = 1 делают A = B = 1 → достаточно одной единицы. Спроси себя: а если A = 1, B = 0?подтема 1
- 0 → 0 ложно
- 0 → 0 считают ложным → стрелка ложна только на 1 → 0. Спроси себя: это запрещённая пара 1 → 0?подтема 1
- направление стрелки
- A → B читают как B → A → единица слева, ноль справа — ложь. Спроси себя: что стоит слева от стрелки?подтема 1
- один случай
- при «или» в выводе взяли один случай → выписывают каждый случай. Спроси себя: все ли наборы с нужным F я нашёл?подтема 2
- пустая клетка — ноль
- пустую клетку приняли за 0 → в ней 0 или 1. Спроси себя: а если там единица?подтема 3
- набор дважды
- двум строкам дали один набор → строки фрагмента различны. Спроси себя: не совпали ли восстановленные строки?подтема 3
- x <= y == z
x <= y == z→(x <= y) == z. Спроси себя: Python не прочтёт это как цепочку сравнений?подтема 4- буквы не по столбцам
- ответ записан как xyzw → буквы по столбцам слева направо. Спроси себя: какая буква подписана над первым столбцом?подтема 3
Итог
Тема пройдена: задача темы решена от смысла операций до ответа wxzy. Вот что взять с собой.
- ПорядокФормула, наборы с нужным F, столбцы, строки, проверка.
- ОперацииИ — все единицы, ИЛИ — все нули, стрелка ложна на 1 → 0.
- НаборыОт внешней операции внутрь или перебором product.
- ФрагментПустая клетка — 0 или 1, строки разные, подпись одна.
- Задача темыC1 = w, C2 = x, C3 = z, C4 = y — ответ wxzy.
Проверьте себя
Ответь сначала сам, потом открой ответ.
F = (x → y) ∧ ¬z, и F = 1. Что известно о z, x и y?
ОтветСкрыть ответ
Снаружи И, значит, обе части равны 1: z = 0 и x → y = 1, то есть любая пара x, y, кроме x = 1, y = 0.
Во всех наборах с F = 1 переменная x равна 0, а во фрагменте единицы есть во всех столбцах, кроме второго. Что это значит?
ОтветСкрыть ответ
Второй столбец — x: в столбце x единиц быть не может, а в любом другом столбце с единицей x стоять не может.
Программа напечатала четыре набора, а во фрагменте три строки. Это ошибка?
ОтветСкрыть ответ
Нет: фрагмент — несколько строк полной таблицы, не обязательно все наборы с нужным F.
Подписи подобраны: C1 = w, C2 = x, C3 = z, C4 = y. Что записать в ответ?
ОтветСкрыть ответ
wxzy — буквы в порядке столбцов слева направо, без пробелов.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Порядок столбцов: единицы переменных
Логическая функция F задаётся выражением (y → x) ∧ (z ≡ ¬x). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определи, какому столбцу соответствует каждая из переменных x, y, z. В ответе напиши буквы в том порядке, в котором идут соответствующие им столбцы.
| C1 | C2 | C3 | F |
|---|---|---|---|
| 1 | 0 | 1 | |
| 1 | 0 | 1 | |
| 0 | 1 | 1 |
Введите буквы переменных подряд, без пробелов, в порядке столбцов.
Подсказка
Выпиши наборы с F = 1 и посчитай, сколько раз в них равна 1 каждая переменная.
Решение
F = 1 на наборах xyz 001, 100, 110. В C1 две единицы, а y и z равны 1 лишь в одном наборе каждая — C1 = x. В строке 3 x = 0 — это 001, единица в C2 — z: C2 = z, C3 = y.
Ответ: xzy
Порядок столбцов: цепочка
Логическая функция F задаётся выражением (x → y) ∧ (y → z) ∧ (z → w). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определи, какому столбцу соответствует каждая из переменных x, y, z, w. В ответе напиши буквы в том порядке, в котором идут соответствующие им столбцы.
| C1 | C2 | C3 | C4 | F |
|---|---|---|---|---|
| 1 | 0 | 1 | ||
| 1 | 0 | 1 | ||
| 0 | 1 | 1 |
Введите буквы переменных подряд, без пробелов, в порядке столбцов.
Подсказка
Цепочка стрелок: в строке переменная с нулём стоит раньше переменной с единицей.
Решение
Строка 1 — C3 раньше C2, строка 2 — C4 раньше C1, строка 3 — C2 раньше C4. Вдоль цепочки C3, C2, C4, C1 — это x, y, z, w, а в порядке столбцов — w, y, x, z.
Ответ: wyxz
Порядок столбцов: нули F
Логическая функция F задаётся выражением ¬(x ∨ y) ∨ (z ≡ w) ∨ (x ∧ ¬z). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определи, какому столбцу соответствует каждая из переменных x, y, z, w. В ответе напиши буквы в том порядке, в котором идут соответствующие им столбцы.
| C1 | C2 | C3 | C4 | F |
|---|---|---|---|---|
| 0 | 1 | 0 | ||
| 0 | 0 | 0 | ||
| 0 | 0 | 0 |
Введите буквы переменных подряд, без пробелов, в порядке столбцов.
Подсказка
Выпиши наборы с F = 0. Нули есть в C1 и C3 в двух строках — у каких переменных два нуля?
Решение
F = 0 на 0101, 0110, 1010, 1110 (xyzw). Нули в C1 стоят в двух строках, в C3 — тоже в двух; два нуля бывают только у x и w — значит, C1 и C3 — это x и w, а C2 и C4 — y и z. Если C2 = y, строки 1 и 2 обе восстанавливаются в 0110. Значит, C2 = z; в строке 3 z = 0 — набор 0101, где ноль у x: C1 = x, C3 = w, C4 = y.
Ответ: xzwy
Порядок столбцов: одинаковые строки
Логическая функция F задаётся выражением ((y → z) ∧ ¬w) ≡ (x ∨ w). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определи, какому столбцу соответствует каждая из переменных x, y, z, w. В ответе напиши буквы в том порядке, в котором идут соответствующие им столбцы.
| C1 | C2 | C3 | C4 | F |
|---|---|---|---|---|
| 0 | 1 | 1 | ||
| 1 | 1 | 1 | ||
| 0 | 1 | 1 |
Введите буквы переменных подряд, без пробелов, в порядке столбцов.
Подсказка
Выпиши наборы с F = 1: одна переменная в них всегда равна 0. Строки 1 и 3 одинаковы на вид — им нужны разные наборы.
Решение
F = 1 на 0100, 1000, 1010, 1110 (xyzw), во всех w = 0 — значит, w в C3, где единиц нет. Строкам 1 и 3 нужны два разных набора с нулём в C2 и единицей в C4; среди x, y, z так бывает только у y = 0, x = 1 (1000 и 1010). Значит, C2 = y, C4 = x, C1 = z; строка 2 — набор 1110.
Ответ: zywx
Порядок столбцов: разные F
Логическая функция F задаётся выражением ¬(x → z) ∨ (y ∧ z). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определи, какому столбцу соответствует каждая из переменных x, y, z. В ответе напиши буквы в том порядке, в котором идут соответствующие им столбцы.
| C1 | C2 | C3 | F |
|---|---|---|---|
| 1 | 1 | 0 | |
| 0 | 0 | 1 | |
| 1 | 0 | 0 |
Введите буквы переменных подряд, без пробелов, в порядке столбцов.
Подсказка
Выпиши наборы с F = 1 и с F = 0 и сверяй каждую строку со списком своего F.
Решение
F = 1 на 011, 100, 110, 111, F = 0 — на 000, 001, 010, 101 (xyz). Строка 2 с двумя нулями и F = 1 — только 100, значит, C3 = x, а C1 и C2 — y и z. В строке 1 x = 1 и F = 0 — это 101, где единица у z: C1 = z, C2 = y.
Ответ: zyx