Задание 2
тема 1 из 3

Таблицы истинности

Таблица истинности перечисляет все 2n2^n наборов значений nn переменных и значение логической функции на каждом из них. В задании 2 по фрагменту таблицы находят, какой переменной соответствует каждый столбец: сначала переменные с одним значением во всех строках, затем перебор оставшихся. Число наборов, на которых функция истинна, считают вручную через редкое значение или программой с перебором всех наборов.

Главная тема в задании2Реже в задании15На карте навыков

Таблица истинности и задание 2

Таблица истинности функции от nn переменных содержит 2n2^n строк: по одной на каждый набор значений 0 и 1.

  • Строки пишут по возрастанию двоичных чисел: 000000, 001001, 010010, … В Python их по порядку даёт product([0, 1], repeat=n).
  • Конъюнкция равна 1, только когда все множители равны 1. Дизъюнкция равна 0, только когда все слагаемые равны 0. Строка с таким редким значением задаёт значения переменных.
  • Задание 2: запишите условия для строк фрагмента, найдите столбцы переменных с одним значением во всех строках, оставшиеся столбцы подберите так, чтобы строки были различны.
  • Ответ задания 2 — буквы переменных в порядке столбцов таблицы.
  • Число решений уравнения F=1F = 1 равно 2n2^n минус число наборов с F=0F = 0.

Как построить таблицу истинности

Таблица истинности логической функции показывает её значение на каждом наборе значений переменных. У nn переменных 2n2^n наборов: каждая переменная независимо равна 0 или 1. Две переменные дают 4 строки, три — 8, четыре — 16. Наборы записывают по порядку, как двоичные числа от 0 до 2n−12^n - 1: так ни один набор не потеряется.

Для сложного выражения добавьте столбцы промежуточных значений: каждый столбец — одна операция в порядке приоритета. Последний столбец — значение функции FF. В Python все наборы по порядку перебирает product([0, 1], repeat=n) из модуля itertools.

Пример

Постройте таблицу истинности функции F=(x∨y)∧¬(x∧y)F = (x \lor y) \land \neg(x \land y).

  1. 1.Две переменные — 4 строки: 0000, 0101, 1010, 1111.
  2. 2.Столбец x∨yx \lor y: 0, 1, 1, 1. Столбец x∧yx \land y: 0, 0, 0, 1, его отрицание: 1, 1, 1, 0.
  3. 3.FF — конъюнкция двух последних столбцов: 0, 1, 1, 0.
  4. 4.Программа печатает те же четыре строки.

Ответ: столбец FF: 0, 1, 1, 0

Сколько бывает логических функций

Логическая функция от nn переменных задана столбцом FF из 2n2^n значений. В каждой клетке столбца стоит 0 или 1, поэтому разных функций 22n2^{2^n}: от одной переменной 4, от двух 16, от трёх 256.

Если значения FF известны только в kk строках, остальные 2n−k2^n - k клеток свободны, и этим строкам подходят 22n−k2^{2^n - k} функций. Поэтому по фрагменту таблицы нельзя восстановить само выражение.

Пример

Функция трёх переменных известна в 6 строках таблицы истинности. Сколько разных функций подходят к этим строкам?

  1. 1.Строк всего 23=82^3 = 8.
  2. 2.Неизвестны 8−6=28 - 6 = 2 значения FF, каждое — 0 или 1.
  3. 3.Функций 22=42^2 = 4.

Ответ: 44

Строки с редким значением

У каждой операции есть редкое значение — то, которое она принимает только в одном случае. Конъюнкция A∧B∧CA \land B \land C равна 1 только при A=B=C=1A = B = C = 1. Дизъюнкция A∨B∨CA \lor B \lor C равна 0 только при A=B=C=0A = B = C = 0. Импликация A→BA \to B равна 0 только при A=1A = 1, B=0B = 0. В строке с редким значением известны значения всех частей, а из них — значения переменных.

Пример

Найдите все наборы (x,y,z)(x, y, z), на которых функция (x∨y)→z(x \lor y) \to z равна 0.

  1. 1.Импликация равна 0 только при посылке 1 и следствии 0: x∨y=1x \lor y = 1, z=0z = 0.
  2. 2.x∨y=1x \lor y = 1 на трёх парах из четырёх: 0101, 1010, 1111.
  3. 3.Наборы: 010010, 100100, 110110. На остальных пяти наборах функция равна 1.

Ответ: 010010, 100100, 110110

Задание 2: сопоставление столбцов

В задании 2 дан фрагмент таблицы истинности: несколько различных строк, часть клеток пустая, столбцы не подписаны. Нужно найти, какой переменной соответствует каждый столбец. Пустая клетка может содержать 0 или 1.

1) Посмотрите на столбец FF. Если во всех строках стоит редкое значение, запишите условие для каждой части выражения. 2) Переменная, которая во всех строках равна 1, стоит в столбце без нулей; переменная, равная 0, — в столбце без единиц. 3) Для оставшихся переменных переберите варианты: заполните пустые клетки по условию и проверьте, что все строки фрагмента различны. Вариант, где условие нарушено или две строки совпали, отпадает. 4) Запишите буквы в порядке столбцов: сначала переменную первого столбца.

Если в столбце FF есть строка с другим значением, сначала используйте строки с редким значением. В остальных строках условие должно нарушаться.

Пример задания

Открытый банк ФИПИ

Миша заполнял таблицу истинности функции F
(x→y)∧z∧¬w,\left(x \rightarrow y\right) \land z \land \neg w ,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, х, у, z:

      F
0 0 0 1
1 0 1
0 0 1


Определите, какому столбцу таблицы соответствует каждая из переменных w, х, у, z. В ответе напишите буквы w, х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением −x∨y,- x \lor y , зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

    F
0 1 0


В этом случае первому столбцу соответствует переменная y, а второму столбцу - переменная х. В ответе следует написать: yx.

Слагаемое с отрицанием

Если FF — дизъюнкция и во всех строках F=0F = 0, каждое слагаемое равно 0. Слагаемое с отрицанием даёт значение без отрицания: ¬y=0\neg y = 0 означает y=1y = 1, а ¬(z→w)=0\neg(z \to w) = 0 означает z→w=1z \to w = 1. Импликация, равная 1, запрещает одну пару: z=1z = 1, w=0w = 0. Дальше столбцы подбирают так же, как для конъюнкции.

Пример задания

Открытый банк ФИПИ

Миша заполнял таблицу истинности функции F
¬(z→w)∨x∨¬y,\neg ( z \rightarrow w ) \lor x \lor \neg y ,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, х, у, z:

      F
1 0   0
0 0 0 0
0 0 0


Определите, какому столбцу таблицы соответствует каждая из переменных w, х, у, z.

В ответе напишите буквы w, х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x∨y,\neg x \lor y , зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

    F
0 1 0


В этом случае первому столбцу соответствует переменная y, а второму столбцу - переменная х. В ответе следует написать: yx.

Программа печатает нужные строки

Таблицу можно построить программой. Цикл for по product([0, 1], repeat=4) перебирает 16 наборов, а if печатает только строки с тем значением FF, которое стоит во фрагменте. Переменные в цикле идут в алфавитном порядке, и столбцы распечатки подписаны. Логические операции записывают по правилам Python.

Распечатку сопоставляют с фрагментом вручную: ищут переменную, которая совпадает со столбцом фрагмента во всех строках, и проверяют, что каждой строке фрагмента соответствует своя строка распечатки.

Пример

Выведите все наборы (x,y,z,w)(x, y, z, w), на которых ¬(z→w)∨x∨¬y=0\neg(z \to w) \lor x \lor \neg y = 0.

  1. 1.Импликация z→wz \to w в Python — (z <= w), её отрицание — (not (z <= w)).
  2. 2.Строки с F=0F = 0 отбирает условие if not F.
  3. 3.Программа печатает три строки: в каждой x=0x = 0 и y=1y = 1, а пары (z,w)(z, w) равны (0,0)(0, 0), (0,1)(0, 1), (1,1)(1, 1).

Ответ: 01000100, 01010101, 01110111

Программа перебирает и столбцы

Программа может сделать и сопоставление. permutations('xyzw') из модуля itertools даёт все 24 порядка переменных по столбцам. Для каждого порядка программа заполняет пустые клетки всеми способами через product и проверяет два условия: строки различны, и на каждой строке функция равна значению из столбца FF. Пустую клетку в списке пишут как None.

Пример

Функция ((x≡¬y)→¬(w→x))∨¬z((x \equiv \neg y) \to \neg(w \to x)) \lor \neg z. Фрагмент из трёх различных строк, во всех F=0F = 0. Строка 1: пусто, 0, 1, 0. Строка 2: 0, пусто, пусто, 0. Строка 3: пусто, 1, 1, пусто. Найдите порядок переменных по столбцам.

  1. 1.table — строки фрагмента без столбца FF, values — столбец FF.
  2. 2.blanks — число пустых клеток. fill перебирает все их заполнения, next(cells) ставит в пустые клетки значения по очереди.
  3. 3.set убирает одинаковые строки: если строк стало меньше, вариант отпадает.
  4. 4.dict(zip(order, r)) сопоставляет каждой переменной её клетку, и F считает функцию на строке. Программа печатает yxzw.

Ответ: yxzw

Число решений логического уравнения

Логическое уравнение F=1F = 1 требует, чтобы выражение было истинно. Его решение — набор значений переменных, на котором F=1F = 1. Число решений равно числу строк таблицы истинности со значением 1. Вручную удобно идти через редкое значение: найдите число наборов с F=0F = 0 и вычтите его из 2n2^n.

Программа перебирает все наборы через product и увеличивает счётчик count на каждом наборе, где выражение истинно.

Пример

Сколько решений у уравнения (x∨y)→(z∧w)=1(x \lor y) \to (z \land w) = 1?

  1. 1.Импликация равна 0 только при x∨y=1x \lor y = 1 и z∧w=0z \land w = 0.
  2. 2.x∨y=1x \lor y = 1 на трёх парах (x,y)(x, y) из четырёх, z∧w=0z \land w = 0 тоже на трёх парах (z,w)(z, w). Наборов с F=0F = 0: 3⋅3=93 \cdot 3 = 9.
  3. 3.Всего наборов 24=162^4 = 16, решений 16−9=716 - 9 = 7.
  4. 4.Программа печатает 7.

Ответ: 77

Система логических уравнений

Система логических уравнений требует, чтобы все уравнения были верны одновременно. Решение системы — набор, на котором верно каждое уравнение. Систему F1=1F_1 = 1, F2=1F_2 = 1 заменяют одним уравнением F1∧F2=1F_1 \land F_2 = 1, а в программе соединяют условия через and.

Цепочка импликаций (x→y)∧(y→z)(x \to y) \land (y \to z) истинна, только когда значения не убывают: после единицы нет нуля. Для трёх переменных это 4 набора: 000000, 001001, 011011, 111111.

Пример

Сколько решений у системы уравнений (x→y)∧(y→z)=1(x \to y) \land (y \to z) = 1 и z∨w=1z \lor w = 1?

  1. 1.Первое уравнение: (x,y,z)(x, y, z) — один из наборов 000000, 001001, 011011, 111111.
  2. 2.Если z=1z = 1 (три набора), второе уравнение верно при любом ww: 3⋅2=63 \cdot 2 = 6 решений.
  3. 3.Если z=0z = 0 (набор 000000), нужно w=1w = 1: одно решение.
  4. 4.Всего 6+1=76 + 1 = 7. Программа печатает 7.

Ответ: 77

Потренируйте навык

Все задания на этот навык

Решать