Статья Автор: Деникина Н.В., Деникин А.В.

Таблицы истинности — Упрощаем формулу: общий множитель

Одинаковый фрагмент можно записать один раз

В выражении (A ∧ B) ∨ (A ∧ C) часть A повторяется. Используем распределительный закон:

(A ∧ B) ∨ (A ∧ C) = A ∧ (B ∨ C)

Если A = 0, обе части слева равны 0. Если A = 1, остаётся B ∨ C. Поэтому преобразование сохраняет значение функции на каждом наборе.


Как узнать спрятанную импликацию

A → B = ¬A ∨ B

Обе записи ложны только при A = 1, B = 0. Поэтому ¬w ∨ y можно читать как w → y. Направление стрелки важно: отрицание стоит у её левой части.


Известно, что G = (p ∧ q) ∨ (p ∧ ¬r) и G = 1. Какая переменная обязательно равна 1? Запиши одну букву.


Один ноль, одна единица и одна решающая строка

F = (x ∧ ¬z ∧ ¬w) ∨ (x ∧ ¬z ∧ y)

№?столбец 1?столбец 2?столбец 3?столбец 4F
У11———1
У20—1—1
У3——001

Пустая клетка — неизвестное значение, не ноль. Полные строки различны. С подключённым компонентом здесь работает одна изменяющаяся таблица; без скрипта доступны все шаги ниже.

Все шаги в текстовом виде — для повторения или без скрипта
1. Находим повторяющийся фрагмент формулы

В обоих слагаемых есть x ∧ ¬z. Получаем F = x ∧ ¬z ∧ (¬w ∨ y). При F = 1 все три части равны 1.

Известно: x = 1; z = 0; w → y = 1

№?столбец 1?столбец 2?столбец 3?столбец 4F
У11———1
У20—1—1
У3——001
2. Один ноль исключает столбец для x

Столбец x состоит из единиц во всех подходящих строках. Сначала находим в условии столбцы с известным нулём.

Известно: x = 1; z = 0; w → y = 1

Действие: Какой столбец остаётся для x после исключения трёх столбцов с нулями?

Вывод: x — второй столбец. Заполняем его единицами сразу во всех строках.

№?столбец 1xстолбец 2?столбец 3?столбец 4F
У111——1
У2011—1
У3—1001
3. Одна единица исключает столбец для z

Теперь ищем постоянный ноль z. В первом и третьем столбцах есть 1. Второй уже занят x.

Известно: x = 1; z = 0; w → y = 1

Действие: Какой столбец остаётся для z?

Вывод: z — четвёртый столбец. Его пропуски заполняем нулями.

№?столбец 1xстолбец 2?столбец 3zстолбец 4F
У111—01
У201101
У3—1001
4. Ищем различающую пару, а не перебираем подписи

В строке У2 оставшиеся столбцы 1 и 3 содержат 0 и 1. Эти клетки относятся к w и y. Используем запрет: при истинной w → y невозможно одновременно w = 1 и y = 0.

Известно: x = 1; z = 0; Нельзя w = 1, y = 0

Действие: Какую переменную обозначает 0 в первом столбце строки У2?

Вывод: Первый столбец — w, третий — y. Остальные уже известны: w x y z.

№wстолбец 1xстолбец 2yстолбец 3zстолбец 4F
У111—01
У201101
У3—1001
5. Из одной единицы получаем другую

В строке У1 дано w = 1. Вспомни единственную запрещённую пару для истинной импликации w → y. Какое значение y поэтому остаётся?

Известно: w → y = 1

Действие: Допиши выведенное значение y в строке У1.

Вывод: В У1 получаем w = 1, y = 1.

№wстолбец 1xстолбец 2yстолбец 3zстолбец 4F
У111101
У201101
У3—1001
6. Из нуля в следствии получаем ноль в посылке

В строке У3 дано y = 0. Какое значение w сделало бы стрелку w → y ложной? Исключи его и допиши оставшееся значение.

Известно: w → y = 1

Действие: Допиши выведенное значение w в строке У3.

Вывод: В У3 получаем w = 0, y = 0.

№wстолбец 1xстолбец 2yстолбец 3zстолбец 4F
У111101
У201101
У301001
7. Проверяем ограничения, а не перебираем наборы

Во всех строках x = 1, z = 0. Пары (w, y) равны (1, 1), (0, 1), (0, 0): запрещённой пары (1, 0) нет. Значит, исходная F = 1. Строки различны. Все подписи получены из ограничений, без полного перебора.

Известно: x = 1; z = 0; w → y = 1

№wстолбец 1xстолбец 2yстолбец 3zстолбец 4F
У111101
У201101
У301001

Ответ: wxyz.


Какую импликацию можно записать вместо ¬r ∨ p? В ответе напиши сначала букву слева от стрелки, затем справа, без самой стрелки.


Следующий способ не требует замечать общий множитель

В следующей тетради построим таблицу для той же исходной формулы на Python. Программа будет знать только формулу, но не правильный порядок столбцов. Мы снова получим ответ — другим путём.
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Печать