Миша заполнял таблицу истинности логической функции \(F = (x \land y \lor \neg x) \land w \lor z\). Он успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу соответствует каждая из переменных \(w, x, y, z\).
Определите, какому столбцу таблицы соответствует каждая из переменных \(w, x, y, z\).
В ответе напишите буквы \(w, x, y, z\) в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция \(F\) задана выражением \(\neg x \lor y\), зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная \(y\), а второму столбцу — переменная \(x\). В ответе следует написать: \(yx\).
Решение:
Для начала, давайте упростим логическую функцию \(F\).
\[F = (x \land y \lor \neg x) \land w \lor z\]
Рассмотрим часть \((x \land y \lor \neg x)\).
По закону дистрибутивности (или просто раскрывая скобки, если представить \(\neg x\) как \(\neg x \land 1\)):
\((x \land y \lor \neg x) = (x \lor \neg x) \land (y \lor \neg x)\)
Так как \((x \lor \neg x)\) всегда истинно (равно 1), то:
\((x \lor \neg x) \land (y \lor \neg x) = 1 \land (y \lor \neg x) = y \lor \neg x\)
Таким образом, функция \(F\) упрощается до:
\[F = (y \lor \neg x) \land w \lor z\]
Теперь построим полную таблицу истинности для функции \(F = (y \lor \neg x) \land w \lor z\).
У нас 4 переменные: \(w, x, y, z\). Всего \(2^4 = 16\) возможных комбинаций.
Давайте заполним таблицу истинности, вычисляя значения для \(\neg x\), \((y \lor \neg x)\), \((y \lor \neg x) \land w\) и, наконец, \(F\).
| w |
x |
y |
z |
\(\neg x\) |
\(y \lor \neg x\) |
\((y \lor \neg x) \land w\) |
\(F = ((y \lor \neg x) \land w) \lor z\) |
| 0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
| 0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
| 0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
| 0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
| 0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
| 0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
| 1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
| 1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
| 1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
| 1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
| 1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
Теперь сравним этот фрагмент с данной в задаче таблицей:
| ??? |
??? |
??? |
??? |
F |
| 0 |
|
0 |
|
1 |
|
1 |
|
1 |
0 |
|
1 |
|
0 |
0 |
Давайте перепишем данный фрагмент, чтобы было удобнее сопоставлять:
| C1 |
C2 |
C3 |
C4 |
F |
| 0 |
? |
0 |
? |
1 |
| ? |
1 |
? |
1 |
0 |
| ? |
1 |
? |
0 |
0 |
Ищем строки в нашей полной таблице истинности, которые соответствуют этим условиям.
Строка 1: \(C1=0\), \(C3=0\), \(F=1\).
Из нашей таблицы истинности ищем строки, где \(F=1\).
Строки с \(F=1\):
(0,0,0,1) -> F=1
(0,0,1,1) -> F=1
(0,1,0,1) -> F=1
(0,1,1,1) -> F=1
(1,0,0,0) -> F=1
(1,0,0,1) -> F=1
(1,0,1,0) -> F=1
(1,0,1,1) -> F=1
(1,1,0,1) -> F=1
(1,1,1,0) -> F=1
(1,1,1,1) -> F=1
Теперь нужно найти среди них те, где два столбца равны 0.
Предположим, что \(C1, C2, C3, C4\) соответствуют \(w, x, y, z\) в каком-то порядке.
Давайте рассмотрим свойства функции \(F = (y \lor \neg x) \land w \lor z\).
\(F\) может быть 0 только в нескольких случаях.
Если \(z=1\), то \(F=1\). Значит, если \(F=0\), то \(z\) обязательно должен быть 0.
Если \(F=0\), то \(z=0\) и \((y \lor \neg x) \land w = 0\).
Это означает, что либо \(w=0\), либо \((y \lor \neg x)=0\).
\((y \lor \neg x)=0\) только если \(y=0\) и \(\neg x=0\), то есть \(y=0\) и \(x=1\).
Итак, условия для \(F=0\):
1. \(z=0\)
2. \((w=0)\) или \((x=1 \text{ и } y=0)\)
Рассмотрим строки из фрагмента, где \(F=0\):
Строка 2: \(C2=1\), \(C4=1\), \(F=0\).
Строка 3: \(C2=1\), \(C4=0\), \(F=0\).
Из условия \(F=0\), мы знаем, что \(z=0\).
В строке 2, \(C4=1\), но \(F=0\). Это противоречит тому, что если \(z=1\), то \(F=1\).
Значит, \(C4\) не может быть \(z\).
В строке 3, \(C4=0\), \(F=0\). Это согласуется с \(z=0\).
Значит, \(C4\) может быть \(z\).
Давайте предположим, что \(C4\) это \(z\).
Тогда для строк с \(F=0\), \(C4\) должен быть 0.
Строка 2: \(C2=1\), \(C4=1\), \(F=0\). Если \(C4=z\), то \(z=1\), но \(F=0\). Это невозможно, так как если \(z=1\), то \(F=1\).
Следовательно, \(C4\) не может быть \(z\).
Это означает, что наше предположение о том, что \(F = (y \lor \neg x) \land w \lor z\) является окончательным, было верным, и мы должны внимательно сопоставить.
Давайте перепроверим упрощение функции.
\(F = (x \land y \lor \neg x) \land w \lor z\)
Используем закон поглощения: \(A \lor (\neg A \land B) = A \lor B\).
Здесь \(A = \neg x\), \(B = y\).
Тогда \((x \land y \lor \neg x) = (\neg x \lor (x \land y))\).
Это не совсем закон поглощения.
Используем дистрибутивность: \((A \lor B) \land (A \lor C) = A \lor (B \land C)\).
\((x \land y \lor \neg x) = (\neg x \lor x) \land (\neg x \lor y) = 1 \land (\neg x \lor y) = \neg x \lor y\).
Упрощение верное. \(F = (\neg x \lor y) \land w \lor z\).
Вернемся к анализу строк.
Строка 1: \(C1=0\), \(C3=0\), \(F=1\).
Строка 2: \(C2=1\), \(C4=1\), \(F=0\).
Строка 3: \(C2=1\), \(C4=0\), \(F=0\).
Рассмотрим строки, где \(F=0\).
Из нашей полной таблицы истинности, строки, где \(F=0\):
(0,0,0,0) -> F=0
(0,0,1,0) -> F=0
(0,1,0,0) -> F=0
(0,1,1,0) -> F=0
(1,1,0,0) -> F=0
Все эти строки имеют \(z=0\).
Значит, если \(F=0\), то переменная, соответствующая \(z\), должна быть 0.
В строке 2 фрагмента, \(C4=1\), но \(F=0\). Это означает, что \(C4\) не может быть \(z\).
В строке 3 фрагмента, \(C4=0\), \(F=0\). Это согласуется с \(C4=z\).
Значит, \(C4\) может быть \(z\).
Если \(C4\) это \(z\), то в строке 2, где \(F=0\), \(C4\) должен быть 0. Но он 1.
Это означает, что \(C4\) не может быть \(z\).
Это очень важное наблюдение. Если \(F=0\), то \(z\) обязательно 0.
В строке 2: \(F=0\), но \(C4=1\). Значит, \(C4 \ne z\).
В строке 3: \(F=0\), но \(C4=0\). Это может быть \(z\).
Давайте рассмотрим, какая переменная может быть \(C4\).
Если \(C4\) не \(z\), то \(C4\) может быть \(w, x, y\).
Рассмотрим столбец \(C2\). В строках 2 и 3, \(C2=1\).
Строка 2: \(C2=1\), \(C4=1\), \(F=0\).
Строка 3: \(C2=1\), \(C4=0\), \(F=0\).
Если \(F=0\), то \(z=0\).
И \((y \lor \neg x) \land w = 0\).
Это означает, что либо \(w=0\), либо \((y \lor \neg x)=0\).
\((y \lor \neg x)=0\) только если \(y=0\) и \(\neg x=0\), то есть \(y=0\) и \(x=1\).
Итак, для \(F=0\):
1. \(z=0\)
2. \((w=0)\) или \((x=1 \text{ и } y=0)\)
Давайте посмотрим на строки 2 и 3 фрагмента:
Строка 2: \(C2=1\), \(C4=1\), \(F=0\).
Строка 3: \(C2=1\), \(C4=0\), \(F=0\).
Так как \(F=0\), то \(z\) должен быть 0.
В строке 2, \(C4=1\). Значит, \(C4\) не может быть \(z\).
В строке 3, \(C4=0\). Значит, \(C4\) может быть \(z\).
Если \(C4\) это \(z\), то строка 2 невозможна, так как \(z=1\) при \(F=0\).
Это означает, что \(C4\) не может быть \(z\).
Это очень важно. Если \(C4\) не \(z\), то \(z\) должен быть одним из \(C1, C2, C3\).
И так как \(F=0\) в строках 2 и 3, то \(z\) должен быть 0 в этих строках.
Давайте предположим, что \(z\) это \(C1\).
Тогда в строке 1: \(C1=0\), \(C3=0\), \(F=1\).
Если \(C1=z\), то \(z=0\).
Если \(z=0\), то \(F = (\neg x \lor y) \land w\).
Для \(F=1\), должно быть \(\neg x \lor y = 1\) и \(w=1\).
Значит, если \(C1=z\), то в строке 1: \(z=0\), \(w=1\), и \(\neg x \lor y = 1\).
Но в строке 1, \(C1=0\), \(C3=0\).
Если \(C1=z\), то \(z=0\).
Если \(C3=w\), то \(w=0\). Тогда \(F = (\neg x \lor y) \land 0 \lor 0 = 0\).
Но \(F=1\) в строке 1. Значит, \(C3\) не может быть \(w\).
Давайте попробуем перебрать столбцы.
Переменные: \(w, x, y, z\).
Столбцы: \(C1, C2, C3, C4\).
Рассмотрим столбец, который принимает значение 1 в строке 2 и 0 в строке 3, при этом \(F=0\).
Это \(C4\).
Строка 2: \(C4=1\), \(F=0\).
Строка 3: \(C4=0\),
