Логическая функция F задаётся выражением (¬x ∨ ¬y) ∧ ¬(x ≡ z) ∧ w.
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 1 | 0 | 0 | 1 | |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 1 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Рассмотрим данное выражение. Преобразуем логическое выражение (¬x ∨ ¬y) ∧ ¬(x ≡ z) ∧ w и получим систему, при которой оно истинно:
Заметим, что переменная w должна принимать значение 1, иначе выражение будет ложным. Значит, переменная w соответствует первому столбцу.
Значения переменных x и z не могут быть равны. Из второй строки заключаем, что столбец четыре не может соответствовать переменным x и y. Следовательно, четвёртый столбец соответствует переменной z.
Рассмотрим первую строку таблицы. Переменная z равна 0, значит, для истинности выражения переменная x должна принимать значение 1. Следовательно, во втором столбце в первой строке должен быть 0.
Поскольку строки в таблице не повторяются, в третьей строке в третьем и четвёртом столбцах могут стоять значения
Таким образом, ответ: wxyz.
Ответ: wxyz.
Приведем другое решение.
Составим таблицу истинности для выражения (¬x ∨ ¬y) ∧ ¬(x ≡ z) ∧ 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) or not(y)) and not(x == z) and w:
print(x, y, z, w)
Далее выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w.
Получим следующие наборы:
(0, 0, 1, 1),
(0, 1, 1, 1),
(1, 0, 0, 1).
Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.
Во всех наборах переменная w равна 1. Следовательно, первый столбец соответствует переменной w. В первой и второй строках таблицы как минимум по две переменные принимают нулевые значения. Следовательно, им соответствую наборы (0, 0, 1, 1) и (1, 0, 0, 1), тогда третьей строке соответствует набор (0, 1, 1, 1). Следовательно, второй столбец — это переменная x, которая в этом наборе принимает значение 0.
Тогда вторая строка таблицы соответствует набору (0, 0, 1, 1), и третий столбец — это переменная у, принимающая в данном наборе нулевое значение, а четвертый столбец — это переменная z, принимающая в этом наборе единичное значение.
Приведем программу Михаила Глинского для построения таблицы истинности.
Программа на языке Паскаль выводит на экран наборы переменных, при которых значение заданного выражения равно 1.
begin
for var x:=false to true do
for var y:=false ro true do
for var z:=false to true do
for var w:=false to true do
if (not(x) or not(y)) and (x<>z) and w then writeln(ord(x), ord(y), ord(z), ord(w));
end.