Подтема 2 из 4
Формула и её таблица
В каком порядке вычислять формулу, как выглядит полная таблица и как найти строки, где F = 1.
Формула по частям
Вернёмся к задаче темы: F = ¬x ∧ (y ∨ z) ∧ (z → w). Чтобы подобрать столбцы, сначала нужно знать, при каких значениях x, y, z, w формула равна 1.
Составную формулу вычисляют по частям — от скобок к внешней операции; по известному F идут обратно — от внешней операции к переменным. Сначала разберём порядок действий и полную таблицу на формулах поменьше, затем найдём наборы задачи темы.
Порядок действий
Операции выполняются в порядке: скобки, ¬, ∧, ∨, →, ≡. И выполняется раньше ИЛИ — как умножение раньше сложения. Например, ¬x ∨ y ∧ z означает (¬x) ∨ (y ∧ z), а (¬x ∨ y) ∧ z — другая формула: при x = y = z = 0 первая равна 1, вторая — 0.
Операция, которая выполняется последней, — внешняя: она делит формулу на части. В F = ((¬x ∨ y) → z) ≡ (x ∧ w) внешняя — равнозначность, её части — вся стрелка слева и x ∧ w справа. При x = 1, y = 0, z = 0, w = 1 считаем снизу вверх: ¬x = 0, ¬x ∨ y = 0, 0 → z = 0 → 0 = 1, x ∧ w = 1, и в конце 1 ≡ 1 = 1.
Если теперь поменять только w на 0, правая часть станет 0, и F = 1 ≡ 0 = 0: одна переменная может изменить всю формулу.
Тонкости:несколько стрелок
(A → B) → C и A → (B → C) — разные формулы: при A = B = C = 0 первая равна 1 → 0 = 0, вторая — 0 → 1 = 1. В заданиях у стрелок ставят скобки — сохраняй их, когда переписываешь формулу.
Полная таблица
Полная таблица функции от n переменных содержит 2ⁿ строк. Каждая новая переменная удваивает число наборов: у одной их 2 (0 и 1), у двух — 4 (00, 01, 10, 11), у трёх — 8, у четырёх — 16. Наборы удобно выписывать по порядку двоичного счёта: последняя переменная меняется в каждой строке, предпоследняя — через две строки.
Построим таблицу для F = (x ∨ y) ∧ (x → z). Сначала два промежуточных столбца — A = x ∨ y и B = x → z, затем F = A ∧ B.
| x | y | z | A = x ∨ y | B = x → z | F = A ∧ B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Набор пишут цифрами подряд и рядом называют порядок переменных: 101 в порядке xyz — это x = 1, y = 0, z = 1. Здесь F = 1 на наборах 010, 011, 101, 111.
От F к входам
По известному F выводят значения переменных — от внешней операции внутрь. У формулы задачи темы четыре переменные, полная таблица — 16 строк. Быстрее рассуждать от результата, по таблице выводов:
| Известно | Что обязательно следует |
|---|---|
| A ∧ B = 1 | A = 1 и B = 1 |
| A ∧ B = 0 | A = 0 или B = 0 (может, оба) |
| A ∨ B = 0 | A = 0 и B = 0 |
| A ∨ B = 1 | A = 1 или B = 1 (может, оба) |
| A → B = 0 | A = 1 и B = 0 |
| A → B = 1 | любая пара, кроме A = 1, B = 0 |
| A ≡ B = 1 | A и B одинаковы |
| A ≡ B = 0 | A и B различаются |
Где в правой колонке «и», значения известны сразу. Где «или», случаев несколько — выписывают каждый, а не выбирают один наугад.
В F = ¬x ∧ (y ∨ z) ∧ (z → w) снаружи И, и F = 1. Значит, все три части равны 1: ¬x = 1, то есть x = 0; y ∨ z = 1; z → w = 1. Две последние части связаны через z — разберём оба его значения.
При z = 0 стрелка 0 → w истинна при любом w, а y ∨ 0 = y требует y = 1. При z = 1 часть y ∨ 1 истинна при любом y, а 1 → w требует w = 1.
Наборы с F = 0 ищут так же. Например, у F = (x ∨ y) ∧ (x → z) И равно 0, если ложна хотя бы одна часть: x ∨ y = 0 при x = y = 0 (наборы 000 и 001) или x → z = 0 при x = 1, z = 0 (наборы 100 и 110).
Итого
- Порядокскобки, ¬, ∧, ∨, →, ≡
- Внешняя операциявыполняется последней и делит формулу на части
- 2ⁿстрок в полной таблице n переменных; у четырёх — 16
- F = 1, снаружи ∧все части равны 1
- F = 0, снаружи ∨все части равны 0
- «или» в выводевыписать каждый случай
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Значение формулы
Вычисли F = (x ∧ ¬y) → (z ≡ x) при x = 1, y = 0, z = 0.
Введите число.
Подсказка
Внешняя операция — стрелка: сначала вычисли обе её части.
Решение
Левая часть: ¬y = 1, x ∧ ¬y = 1 ∧ 1 = 1. Правая: z ≡ x = 0 ≡ 1 = 0. Стрелка 1 → 0 — запрещённая пара, F = 0.
Ответ: 0
Строки таблицы пяти переменных
Сколько строк в полной таблице функции от переменных a, b, c, d, e?
Введите число.
Подсказка
Каждая переменная удваивает число наборов.
Решение
32 = 2⁵: у каждой из пяти переменных два значения.
Ответ: 32
Нули функции (x → y) ∨ ¬z
Для F = (x → y) ∨ ¬z найди все наборы xyz, при которых F = 0.
Введите наборы через пробел в порядке возрастания, каждый — цифрами подряд.
Подсказка
ИЛИ ложно, только если обе части равны 0.
Решение
ИЛИ ложно, только если обе части 0; ¬z = 0 даёт z = 1, а x → y = 0 — только x = 1, y = 0.
Ответ: 101
Наборы с равнозначностью
Для F = (x ≡ y) ∧ ¬z найди все наборы xyz, при которых F = 1.
Введите наборы через пробел в порядке возрастания, каждый — цифрами подряд.
Подсказка
Снаружи И: обе части равны 1.
Решение
Снаружи И, поэтому x ≡ y = 1 и ¬z = 1. Значит, z = 0, а x и y одинаковы: 00 или 11. Наборы 000 и 110.
Ответ: 000 110
Нули функции четырёх переменных
Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w. Найди все наборы значений xyzw, при которых F = 0. Наборы запиши в порядке xyzw.
Введите наборы через пробел в порядке возрастания, каждый — цифрами подряд.
Подсказка
Снаружи ИЛИ и F = 0: каждая из трёх частей равна 0.
Решение
Внешнее ИЛИ требует трёх нулей — w = 1, y и z различны, x ∧ ¬y = 0. При y = 0, z = 1 нужно x = 0; при y = 1, z = 0 x любое.
Ответ: 0011 0101 1101