Question

Миша заполнял таблицу истинности логической функции $F = (y 	o 
eg(x 	o z)) \lor w$.

Успел заполнить лишь фрагмент из трёх различных строк, не указав, какому столбцу соответствует каждая переменная $x$, $y$, $z$, $w$.

| ??? | ??? | ??? | ??? | F |
|---|---|---|---|---|
| | 0 | | | 0 |
| 0 | 1 | | | 0 |
| 1 | | | 0 | 0 |

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

Accepted Answer

xzyw

Answer

Идея решения: найти все наборы переменных, при которых функция равна 0, а затем сопоставить их с данными строками таблицы.

Выпишем логическое выражение явно: $F = (y 	o 
eg(x 	o z)) \lor w$.

Функция равна 0 только когда оба слагаемых дизъюнкции равны 0:
- $w = 0$
- $y 	o 
eg(x 	o z) = 0$

Импликация $y 	o 
eg(x 	o z)$ равна 0 только при $y = 1$ и $
eg(x 	o z) = 0$, то есть $x 	o z = 1$.

Импликация $x 	o z$ равна 1 при $(x = 0, z = 0)$, $(x = 0, z = 1)$ или $(x = 1, z = 1)$.

Таким образом, $F = 0$ при следующих наборах $(x, y, z, w)$:
- $(0, 1, 0, 0)$
- $(0, 1, 1, 0)$
- $(1, 1, 1, 0)$

Проверим с помощью программы:

```python
print("x y z w")
for x in range(2):
    for y in range(2):
        for z in range(2):
            for w in range(2):
                f = (y <= (not(x <= z))) or w
                if not f:
                    print(x, y, z, w)
```

Вывод:
```
0 1 0 0
0 1 1 0
1 1 1 0
```

Теперь сопоставим эти наборы с фрагментом таблицы.

Заметим, что третий столбец содержит только значение 0 (в строках 1 и 3). Среди наших наборов только переменная $y$ принимает значение 1 ровно один раз (во всех трёх наборах). Значит, третий столбец — это $y$.

Первая строка таблицы: `?, 0, ?, ?` с $F = 0$. Это может быть только набор $(0, 1, 0, 0)$, где второй элемент — 1, но в таблице стоит 0. Проверим: если третий столбец — $y$, то первая строка имеет вид `?, 0, ?, ?`. Из наборов с $y = 1$ подходит $(0, 1, 0, 0)$, где первый элемент 0 совпадает со вторым столбцом таблицы.

Вторая строка: `0, 1, ?, ?` с $F = 0$. Это набор $(0, 1, 0, 0)$ или $(0, 1, 1, 0)$.

Третья строка: `1, ?, ?, 0` с $F = 0$. Это набор $(1, 1, 1, 0)$.

Из третьей строки: первый столбец = 1, четвёртый столбец = 0. Набор $(1, 1, 1, 0)$ имеет $x = 1$, $z = 1$, $w = 0$. Значит, первый столбец — $x$, четвёртый столбец — $w$, второй столбец — $z$.

Проверка:
- Строка 1: $(x, z, y, w) = (0, 0, 1, 0)$ ✓
- Строка 2: $(x, z, y, w) = (0, 1, 1, 0)$ ✓
- Строка 3: $(x, z, y, w) = (1, 1, 1, 0)$ ✓

Порядок столбцов: $x$, $z$, $y$, $w$.

Задание №2Математическая логикаЕГЭ по информатике