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

Таблицы истинности — Python строит таблицу — ты находишь столбцы

Начнём заново: правильные подписи пока неизвестны

Умение упростить формулу полезно, но не обязательно. Python может перебрать значения переменных и напечатать нужные строки таблицы. После этого задача не исчезает: надо сопоставить напечатанные наборы с фрагментом из условия.

Разделяем две работы

Программа: перебрать наборы и вычислить F. Ты: определить, какие столбцы условия соответствуют x, y, z, w. Ответ не должен быть заранее записан в коде.

Шаг 1. Переводим знаки на Python

Логическая запись	Запись на Python
¬a	`not a`
a ∧ b	`a and b`
a ∨ b	`a or b`
a → b	`((not a) or b)`
a ≡ b	`(a == b)`
a ≡ ¬b	`(a == (not b))`

Первая часть формулы — x and (not z) and (not w). Вторая — x and (not z) and y. Между ними ставим or.

Знак = присваивает значение переменной, а == сравнивает значения. Скобки помогают сохранить смысл исходной формулы. Не переноси в Python порядок операций из математической записи без проверки.

Шаг 2. Разбираемся, что делает перебор

Команда for a in (0, 1) сначала даёт переменной a значение 0, затем 1. Внутренний цикл проходит целиком для каждого значения внешнего. Начнём с двух переменных:

print("a b")
for a in (0, 1):
    for b in (0, 1):
        print(a, b)

Получатся пары 0 0, 0 1, 1 0, 1 1. Сначала a = 0, а b успевает принять оба значения. Потом a = 1, и b снова принимает оба значения.

Для четырёх переменных нужны четыре таких цикла. Они проверят 2 × 2 × 2 × 2 = 16 наборов. Отступы важны: вычисление F выполняется внутри самого глубокого цикла.

Представь другую программу с тремя вложенными циклами по a, b, c. Каждый перебирает 0 и 1. Сколько наборов она проверит до отбора по F?

Проверить ответ

Шаг 3. Печатаем только строки с нужным F

Во всех строках условия F = 1, поэтому используем if f == 1. Выводим значения в обычном для нас порядке x y z w, а не в неизвестном порядке исходных столбцов.

print("x y z w F")

for x in (0, 1):
    for y in (0, 1):
        for z in (0, 1):
            for w in (0, 1):
                f = (x and (not z) and (not w)) or (x and (not z) and y)
                if f == 1:
                    print(x, y, z, w, int(f))

print("x y z w F") печатает заголовок. Четыре цикла перебирают наборы. Строка f = ... вычисляет функцию. Условие if оставляет только нужные наборы.

int(f) выводит значение как 0 или 1, а не как False или True. Для этих логических значений False соответствует 0, True — 1.

Та же программа, короче: product

Четыре вложенных цикла уже показывают, откуда берутся наборы. product((0, 1), repeat=4) задаёт те же четыре перебора одной строкой. Дальше используем этот вариант. Сам перебор выполняет компьютер; ученик анализирует только напечатанный фрагмент.

from itertools import product

print("x y z w F")
for x, y, z, w in product((0, 1), repeat=4):
    f = (x and (not z) and (not w)) or (x and (not z) and y)
    if f == 1:
        print(x, y, z, w, int(f))

Теперь ищем признаки в выводе

Не сравнивай подряд каждую строку с каждой. Начни с постоянных столбцов, затем найди запрещённую пару или характерное значение одной переменной. В интерактиве справа уже показан результат программы — перечислять 16 наборов вручную не нужно.

Python построил фрагмент — замечаем его особенности

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

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

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

Все шаги в текстовом виде — для повторения или без скрипта

Вывод программы, с которым сравниваем условие:

1. Python уже построил нужный фрагмент

Справа показаны все наборы с F = 1, в порядке x y z w. Перебирать их вручную не нужно. Найдём признаки, которые не исчезают при перестановке строк.

Действие: Какой факт действительно сохраняется, если строки вывода переставить?

Вывод: Начинаем не со сравнения строк по номерам, а с постоянных столбцов.

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

2. Один ноль исключает столбец для x

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

Известно: x = 1; z = 0; В выводе нет w = 1, y = 0

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

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

№	?столбец 1	xстолбец 2	?столбец 3	?столбец 4	F
У1	1	1	—	—	1
У2	0	1	1	—	1
У3	—	1	0	0	1

3. Одна единица исключает столбец для z

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

Известно: x = 1; z = 0; В выводе нет w = 1, y = 0

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

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

№	?столбец 1	xстолбец 2	?столбец 3	F
У1	1	1	—	1
У2	0	1	1	1
У3	—	1	0	1

4. Ищем различающую пару, а не перебираем подписи

В строке У2 столбцы 1 и 3 содержат 0 и 1. Справа среди пар (y, w) есть 00, 10, 11, но нет 01. Значит, единица в У2 не может быть w при y = 0.

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

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

Вывод: 0 в У2 — это w, 1 — это y. Названия найдены по одной различающей паре, без перебора всех порядков.

№	wстолбец 1	xстолбец 2	yстолбец 3	F
У1	1	1	—	1
У2	0	1	1	1
У3	—	1	0	1

5. Из одной единицы получаем другую

В строке У1 дано w = 1. Справа найди единственную единицу в столбце w. Прочитай значение y в той же строке: оно и определит пропуск слева. Это поиск по признаку, а не сравнение всех строк подряд.

Известно: В выводе нет w = 1, y = 0

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

Вывод: y = 1, и вся строка У1 соответствует П3.

№	wстолбец 1	xстолбец 2	yстолбец 3	F
У1	1	1	1	1
У2	0	1	1	1
У3	—	1	0	1

Соответствие: У1 → П3, У2 → П2.

6. Из нуля в следствии получаем ноль в посылке

В строке У3 дано y = 0. Справа найди единственный ноль в столбце y и прочитай значение w в той же строке. По этому признаку определяются сразу клетка и соответствие строки.

Известно: В выводе нет w = 1, y = 0

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

Вывод: w = 0. У3 соответствует П1. У2 с парой w = 0, y = 1 соответствует П2.

№	wстолбец 1	xстолбец 2	yстолбец 3	F
У1	1	1	1	1
У2	0	1	1	1
У3	0	1	0	1

Соответствие: У1 → П3, У2 → П2, У3 → П1.

7. Проверяем ограничения, а не перебираем наборы

Проверяем логически: x = 1, z = 0; ни в одной строке нет w = 1, y = 0. Все строки различны, поэтому исходная F = 1. Соответствие строк — У1 → П3, У2 → П2, У3 → П1. Python второй раз для проверки не нужен.

Известно: x = 1; z = 0; В выводе нет w = 1, y = 0

№	wстолбец 1	xстолбец 2	yстолбец 3	F
У1	1	1	1	1
У2	0	1	1	1
У3	0	1	0	1

Соответствие: У1 → П3, У2 → П2, У3 → П1.

Ответ: wxyz.

В другой программе заголовок вывода — w x y z F, а строка — 0 1 0 1 0. Чему равно y в этой строке?

Проверить ответ

Новый фрагмент нужно сопоставить с таким выводом программы:

№ числовой строки	a	b	c	G
1	0	0	1	1
2	0	1	0	1
3	1	0	0	1

Подписи исходного фрагмента уже найдены: c a b. В его строке стоят значения 0 — 1, G = 1. Какой номер строки вывода ей соответствует?

Проверить ответ

Проверь выводы для программного способа.

Проверить ответ

Если программа напечатала больше строк

Это нормально: в условии дан фрагмент. Из вывода выбирают подходящие разные наборы, а остальные могут не использоваться. В самостоятельной работе будет именно такой случай: подходящих наборов окажется больше, чем строк в условии.

Нельзя переносить частоту нулей и единиц из полного вывода на короткий фрагмент. А вот свойство «переменная всегда равна 0» или «всегда равна 1» переносится на любую выбранную часть.

Если в условии встречаются и F = 0, и F = 1, убери фильтр if и печатай все наборы вместе с F. Каждую строку условия сопоставляй только со строками нужного значения функции.

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать