Логическая функция F задаётся выражением (x ≡ ¬y) → (z ≡ (y ∨ w)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 0 | 0 | 0 | ||
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 1 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Рассмотрим данное выражение. Преобразуем логическое выражение (x ≡ ¬y) → (z ≡ (y ∨ w)) и получим систему, при которой оно ложно:
Заметим, что третий и четвёртый столбцы таблицы истинности — это y и x. Из условия 
следует, что первому столбцу таблицы истинности соответствует переменная z. Следовательно, второму столбцу таблицы истинности соответствует w.
Приведем другое решение.
Составим таблицу истинности для выражения (x ≡ ¬y) → (z ≡ (y ∨ w)) вручную или при помощи языка Python:
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):
if not((x == (not y)) <= (z == (y or w))):
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z, w.
Получим следующие наборы:
(0, 1, 0, 0)
(0, 1, 0, 1),
(1, 0, 0, 1),
(1, 0, 1, 0).
Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.
Вторая строка таблицы может соответствовать только набору (0, 1, 0, 0). Следовательно, третий столбец соответствует переменной y, которая в этом наборе принимает единичное значение.
Заметим, что переменная z принимает нулевое значение в трех из имеющихся четырех наборах, а остальные переменные — только в двух. Следовательно, первый столбец таблицы соответствует переменной z.
Первая строка таблицы может соответствовать только набору (1, 0, 0, 1), где переменные y и z принимают нулевые значения. Следовательно, третья строка соответствует набору (0, 1, 0, 1), в котором нулевое значение принимает переменная x. Тогда x — это четвертый столбец, а w — второй столбец.
Ответ: zwyx.
Приведём решение Сергея Галеева на языке C++.
#include #include #include #include #include using namespace std; bool null(int x, int y, int z, int w) { return ((x == !y) <= (z == (y || w))); //(x ≡ ¬y) → (z ≡ (y ∨ w)). } int main() { srand(time(0)); vector while (act) { int active = 0; vector generate(f.begin(), f.end(), []() {return rand() % 2; }); if (f[0] == 0 && f[2] == 0 && s.empty()) s.push_back(f); if (f[0] == 0 && f[1] == 0 && f[3] == 0 && find(s.begin(), s.end(), f) == s.end()) s.push_back(f); if (f[0] == 0 && f[3] == 0 && find(s.begin(), s.end(), f) == s.end()) s.push_back(f); if (s.size() == 3) { while (active != 1000) { active++; int mass[4] = { 0, 1, 2, 3 }; for (int i = 0; i < 4; i++) swap(mass[rand() % 4], mass[rand() % 4]); if (!null(s[0][mass[0]], s[0][mass[1]], s[0][mass[2]], s[0][mass[3]])) if (!null(s[1][mass[0]], s[1][mass[1]], s[1][mass[2]], s[1][mass[3]])) if (!null(s[2][mass[0]], s[2][mass[1]], s[2][mass[2]], s[2][mass[3]]) && act) { cout « "x = " « mass[0] + 1 « " y = " « mass[1] + 1 « " z = " « mass[2] + 1 « " w = " « mass[3] + 1; act = false; } } if (active == 1000) s.clear(); } } return 0; }