Таблицы истинности
Таблица истинности перечисляет все наборов значений переменных и значение логической функции на каждом из них. В задании 2 по фрагменту таблицы находят, какой переменной соответствует каждый столбец: сначала переменные с одним значением во всех строках, затем перебор оставшихся. Число наборов, на которых функция истинна, считают вручную через редкое значение или программой с перебором всех наборов.
Таблица истинности и задание 2
Таблица истинности функции от переменных содержит строк: по одной на каждый набор значений 0 и 1.
- Строки пишут по возрастанию двоичных чисел: , , , … В Python их по порядку даёт
product([0, 1], repeat=n). - Конъюнкция равна 1, только когда все множители равны 1. Дизъюнкция равна 0, только когда все слагаемые равны 0. Строка с таким редким значением задаёт значения переменных.
- Задание 2: запишите условия для строк фрагмента, найдите столбцы переменных с одним значением во всех строках, оставшиеся столбцы подберите так, чтобы строки были различны.
- Ответ задания 2 — буквы переменных в порядке столбцов таблицы.
- Число решений уравнения равно минус число наборов с .
Как построить таблицу истинности
Таблица истинности логической функции показывает её значение на каждом наборе значений переменных. У переменных наборов: каждая переменная независимо равна 0 или 1. Две переменные дают 4 строки, три — 8, четыре — 16. Наборы записывают по порядку, как двоичные числа от 0 до : так ни один набор не потеряется.
Для сложного выражения добавьте столбцы промежуточных значений: каждый столбец — одна операция в порядке приоритета. Последний столбец — значение функции . В Python все наборы по порядку перебирает product([0, 1], repeat=n) из модуля itertools.
Пример
Постройте таблицу истинности функции .
- 1.Две переменные — 4 строки: , , , .
- 2.Столбец : 0, 1, 1, 1. Столбец : 0, 0, 0, 1, его отрицание: 1, 1, 1, 0.
- 3. — конъюнкция двух последних столбцов: 0, 1, 1, 0.
- 4.Программа печатает те же четыре строки.
Ответ: столбец : 0, 1, 1, 0
Сколько бывает логических функций
Логическая функция от переменных задана столбцом из значений. В каждой клетке столбца стоит 0 или 1, поэтому разных функций : от одной переменной 4, от двух 16, от трёх 256.
Если значения известны только в строках, остальные клеток свободны, и этим строкам подходят функций. Поэтому по фрагменту таблицы нельзя восстановить само выражение.
Пример
Функция трёх переменных известна в 6 строках таблицы истинности. Сколько разных функций подходят к этим строкам?
- 1.Строк всего .
- 2.Неизвестны значения , каждое — 0 или 1.
- 3.Функций .
Ответ:
Строки с редким значением
У каждой операции есть редкое значение — то, которое она принимает только в одном случае. Конъюнкция равна 1 только при . Дизъюнкция равна 0 только при . Импликация равна 0 только при , . В строке с редким значением известны значения всех частей, а из них — значения переменных.
Пример
Найдите все наборы , на которых функция равна 0.
- 1.Импликация равна 0 только при посылке 1 и следствии 0: , .
- 2. на трёх парах из четырёх: , , .
- 3.Наборы: , , . На остальных пяти наборах функция равна 1.
Ответ: , ,
Задание 2: сопоставление столбцов
В задании 2 дан фрагмент таблицы истинности: несколько различных строк, часть клеток пустая, столбцы не подписаны. Нужно найти, какой переменной соответствует каждый столбец. Пустая клетка может содержать 0 или 1.
1) Посмотрите на столбец . Если во всех строках стоит редкое значение, запишите условие для каждой части выражения. 2) Переменная, которая во всех строках равна 1, стоит в столбце без нулей; переменная, равная 0, — в столбце без единиц. 3) Для оставшихся переменных переберите варианты: заполните пустые клетки по условию и проверьте, что все строки фрагмента различны. Вариант, где условие нарушено или две строки совпали, отпадает. 4) Запишите буквы в порядке столбцов: сначала переменную первого столбца.
Если в столбце есть строка с другим значением, сначала используйте строки с редким значением. В остальных строках условие должно нарушаться.
Пример задания
Открытый банк ФИПИ
Миша заполнял таблицу истинности функции F
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, х, у, z:
| F | ||||
| 0 | 0 | 0 | 1 | |
| 1 | 0 | 1 | ||
| 0 | 0 | 1 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, х, у, z. В ответе напишите буквы w, х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
| F | ||
| 0 | 1 | 0 |
В этом случае первому столбцу соответствует переменная y, а второму столбцу - переменная х. В ответе следует написать: yx.
Слагаемое с отрицанием
Если — дизъюнкция и во всех строках , каждое слагаемое равно 0. Слагаемое с отрицанием даёт значение без отрицания: означает , а означает . Импликация, равная 1, запрещает одну пару: , . Дальше столбцы подбирают так же, как для конъюнкции.
Пример задания
Открытый банк ФИПИ
Миша заполнял таблицу истинности функции F
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, х, у, z:
| F | ||||
| 1 | 0 | 0 | ||
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, х, у, z.
В ответе напишите буквы w, х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
| F | ||
| 0 | 1 | 0 |
В этом случае первому столбцу соответствует переменная y, а второму столбцу - переменная х. В ответе следует написать: yx.
Программа печатает нужные строки
Таблицу можно построить программой. Цикл for по product([0, 1], repeat=4) перебирает 16 наборов, а if печатает только строки с тем значением , которое стоит во фрагменте. Переменные в цикле идут в алфавитном порядке, и столбцы распечатки подписаны. Логические операции записывают по правилам Python.
Распечатку сопоставляют с фрагментом вручную: ищут переменную, которая совпадает со столбцом фрагмента во всех строках, и проверяют, что каждой строке фрагмента соответствует своя строка распечатки.
Пример
Выведите все наборы , на которых .
- 1.Импликация в Python —
(z <= w), её отрицание —(not (z <= w)). - 2.Строки с отбирает условие
if not F. - 3.Программа печатает три строки: в каждой и , а пары равны , , .
Ответ: , ,
Программа перебирает и столбцы
Программа может сделать и сопоставление. permutations('xyzw') из модуля itertools даёт все 24 порядка переменных по столбцам. Для каждого порядка программа заполняет пустые клетки всеми способами через product и проверяет два условия: строки различны, и на каждой строке функция равна значению из столбца . Пустую клетку в списке пишут как None.
Пример
Функция . Фрагмент из трёх различных строк, во всех . Строка 1: пусто, 0, 1, 0. Строка 2: 0, пусто, пусто, 0. Строка 3: пусто, 1, 1, пусто. Найдите порядок переменных по столбцам.
- 1.
table— строки фрагмента без столбца ,values— столбец . - 2.
blanks— число пустых клеток.fillперебирает все их заполнения,next(cells)ставит в пустые клетки значения по очереди. - 3.
setубирает одинаковые строки: если строк стало меньше, вариант отпадает. - 4.
dict(zip(order, r))сопоставляет каждой переменной её клетку, иFсчитает функцию на строке. Программа печатает yxzw.
Ответ: yxzw
Число решений логического уравнения
Логическое уравнение требует, чтобы выражение было истинно. Его решение — набор значений переменных, на котором . Число решений равно числу строк таблицы истинности со значением 1. Вручную удобно идти через редкое значение: найдите число наборов с и вычтите его из .
Программа перебирает все наборы через product и увеличивает счётчик count на каждом наборе, где выражение истинно.
Пример
Сколько решений у уравнения ?
- 1.Импликация равна 0 только при и .
- 2. на трёх парах из четырёх, тоже на трёх парах . Наборов с : .
- 3.Всего наборов , решений .
- 4.Программа печатает 7.
Ответ:
Система логических уравнений
Система логических уравнений требует, чтобы все уравнения были верны одновременно. Решение системы — набор, на котором верно каждое уравнение. Систему , заменяют одним уравнением , а в программе соединяют условия через and.
Цепочка импликаций истинна, только когда значения не убывают: после единицы нет нуля. Для трёх переменных это 4 набора: , , , .
Пример
Сколько решений у системы уравнений и ?
- 1.Первое уравнение: — один из наборов , , , .
- 2.Если (три набора), второе уравнение верно при любом : решений.
- 3.Если (набор ), нужно : одно решение.
- 4.Всего . Программа печатает 7.
Ответ: