Питон и таблицы истинности
Таблица истинности — это таблица, где перечисляются комбинации аргументов некой логической функции и указывается, какие значения принимает эта функция.
В задаче 2 ЕГЭ по информатике требуется 1) уметь строить таблицы истинности логического выражения и 2) уметь сравнивать построенную таблицу истинности с таблицей, приведенной в условии задачи.
Первый пункт можно выполнить на компьютере, написав несложную (менее 10 строк) программу на Питоне.
Вообще говоря, в Питоне, как и в паскале, есть специальные логические значения True и False. Но в логических выражениях можно использовать и числа. При этом значение 0 считается ложью, а всё, отличное от нуля — истиной. (Тут создатель Питона позаимствовал идею из С.)
Рассмотрим задачу с сайта «Решу ЕГЭ». В ней требуется сопоставить переменные, входящие в логическую функцию
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| . | . | . | . | F |
| 1 | — | — | 1 | 0 |
| 1 | — | — | — | 0 |
| — | 1 | — | 1 | 0 |
Требуется выяснить, какая переменная в таблице обозначена как «переменная 1», «переменная 2» и т.д.
Из последнего столбца видно, что нам нужны те комбинации значений переменных, при которых функция ложна.
Так как в Питоне отсутствует логическая операция импликации, заменяем выражения вроде x → y на эквивалентные выражения not x or y. Операция эквивалентности — это сравнение «= ложь»:
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
f = ((not x or y ) and (not y or w)) or (z == ( x or y))
if not f: print(x,y,z,w)
Программа печатает следующую таблицу:
0 1 0 0
1 0 0 0
1 0 0 1
1 1 0 0
Столбцы слева направо — это значения переменных x, y, z, w соответственно.
Таким образом, мы очень упростили первую часть задачи — построение таблицы истинности. Осталась вторая часть.
В нашей таблице четыре строки, а в задаче — только три. Следовательно, одна строка в нашей таблице лишняя.
Заметим, что в таблице из задачи пять единиц, а в нашей таблице — шесть. Отсюда вытекают два вывода. Во-первых, мы не можем удалить из нашей таблицу строчку с двумя единицами — тогда у нас их останется четыре, т.е. менее, чем в таблице из задачи. Во-вторых, при удалении из нашей таблицы строки с одной единицей и в нашей таблице, и в таблице из задачи будет по пять единиц. Следовательно, во всех пустых клетках таблицы из задачи записаны нули.
Самую первую строку из нашей таблицы удалить нельзя: тогда у нас появляется столбец из трёх единиц, а такого столбца в таблица из задачи нет. Убираем вторую строку и получаем следующую таблицу:
В столбце переменной z — только нули. Следовательно, в задаче переменная 3 — это z.
В столбце переменной w только одна единица. Следовательно, переменная w — это переменная 2 в задаче.
Замечаем, что когда переменная w (переменная 2 в задаче) равна 1, то равна 1 также и переменная x (а в задаче это переменная 4). Следовательно, переменная 4 — это x. Оставшаяся переменная 1 — это переменная y.
Итак, наш ответ — ywzx. Именно такой ответ и приводится в задаче.
При записи логических выражений в Питоне можно столкнуться с тем, что выражения вроде (x ≡ ¬z) при буквальном их переводе (x == not z) вызывают синтаксическую ошибку. Чтобы избежать этого, надо либо заключить выражение not z в дополнительные скобки, т.е. написать (x == (not z)). Можно также заменить операцию «равно» на «не равно», т.е. записать это выражение как (x != z).
1. Как решать задание ЕГЭ
7. Задание проверяет умение работать с логическими переменными, выполнять логические операции, строить таблицы истинности.
но успел заполнить только фрагмент из трёх различных её строк, не указав, какому столбцу таблицы принадлежит каждая из переменных \(w\), \(x\), \(y\), \(z\).
В ответе напиши буквы \(w\), \(x\), \(y\), \(z\) в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пиши подряд, никаких разделителей между буквами ставить не нужно.
Данное задание можно решать несколькими способами: путём логических рассуждений; использовать электронные таблицы \(+\) логические рассуждения; с помощью программирования.
Для каждой переменной сформируем вложенный цикл, где будем перебирать все возможные значения (\(0\) и \(1\)) для каждой переменной;
in range (\(2\)): перебор значений \(0\) и \(1\), можно записать по другому: in range (\(0\),\(2\))
 | Полученный результат необходимо сравнить с таблицей из условия |
Сопоставим полученную таблицу истинности с таблицей из условия. Нам необходимо сравнивать условие с результатами, как по строкам, так и по столбцам, отыскивая некоторые закономерности и невозможности. Заметим, что столбец \(y\) содержит в себе три единицы, что может быть только в третьем столбце таблицы из условия. Четвёртый столбик таблицы из условия также можем дополнить единицей, и к этому столбику подходят как \(z\), так и \(w\).
Теперь проанализируем строки. В первой строке получилось три единицы, что соответствует четвёртой строке результата программирования, дополняем нулём первую строку. В третьей строке у нас два нуля, поэтому добавляем единицу. Проверяем, чтобы сошлось по строке. Заполним второй столбец, допишем единицу. Этот столбец как раз и будет являться \(x\). Остаётся проанализировать столбцы \(1\) и \(4\).
Рассмотрим первую строку: \(x = 0\), \(y = 1\), \(z = 0\), следовательно, \(z\) — это четвёртый столбик, а \(w\) — первый.
Составление таблицы истинности логической функции. Решение на Python. Задание 2 (ЕГЭ по информатике).
операция пояснение в программировании ¬ A, A не A (отрицание, инверсия) not(A) A ∧ B, A ⋅ B A и B (логическое умножение, конъюнкция) A and B A ∨ B, A + B A или B (логическое сложение, дизъюнкция) A or B A → B импликация (следование) A
Порядок выполнения операций: если нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», импликация, равносильность Еще о логических операциях: логическое произведение X∙Y∙Z∙… равно 1, т.е. выражение является истинным, только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0) логическая сумма X+Y+Z+… равна 0, т.е. выражение является ложным только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
Задача 1 ? ? ? ? F 1 1 1 1 1 1 1 Логическая функция F задаётся выражением ¬w /\ ( y \/ z → ¬x /\ y). На рисунке приведён фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Код программы для решения print(‘x y z w’) for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = not(w)and( (y or z)
Задание 2 ? ? ? ? F 0 0 0 0 0 0 0 0 0 0 Логическая функция F задаётся выражением ((x → w) \/ y /\ ¬z) /\ ((y → ¬z) \/ x /\ ¬w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Код программы для решения print(‘x y z w’) for x in range (0, 2): for y in range (0, 2): for z in range (0, 2): for w in range (0, 2): F = ((x<=w)or (y and not(z)))and ((y <= (not(z)))or (x and not(w))) if F==0: print(x, y, z, w)
Задание 3 ? ? ? ? F 0 0 0 0 0 1 0 0 0 1 0 Логическая функция F задаётся выражением ((x → y) \/ ¬ (z → w)) /\ ((w → ¬x) \/ (¬y → z)). На рисунке приведён фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Код программы print(‘x y z w’) for x in range (0, 2): for y in range (0, 2): for z in range (0, 2): for w in range (0, 2): F = ((x<=y)or (not(z<=w)))and((w<= (not(x)))or(not(y)<=z)) if F==0: print(x, y, z, w)