Логическая функция F задаётся выражением (¬a ∧ ¬b) ∨ (b ≡ c) ∨ d. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c, d.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| 1 | 0 | |||
| 1 | 0 | 1 | 0 | |
| 0 | 0 | 1 | 1 | 0 |
В ответе напишите буквы a, b, c, d в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 2 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Заметим, что переменная d всегда должна быть равна 0, иначе выражение будет истинным. Сразу же можно определить столбец, в котором находятся значения переменной d, — столбец 2.
Найдем значения переменных a, b, c, при которых первое и второе подвыражения ложны:
Следовательно, с — первый столбец (единственно возможный с одной единицей), b — третий (единственный возможный для инвертированных значений с), а — четвертый по остаточному принципу.
Приведём программное решение.
| Паскаль |
|---|
var a, b, c, d: boolean; begin for a := False to True do for b := False to True do for c := False to True do for d := False to True do if not ((not a and not b) or (b=c) or d) then writeln(ord(a), ord(b), ord(c), ord(d)); end. |
| Python |
from itertools import *
for a, b, c, d in product([0, 1], repeat=4): if not ((not a and not b) or (b == c) or d): print(a, b, c, d) |
| С++ |
#include <iostream> using namespace std; int main(){ for(int a = 0; a <= 1; a++) for(int b = 0; b <= 1; b++) for(int c = 0; c <= 1; c++) for(int d = 0; d <= 1; d++) if !((!a and !b)||(b == c)||d) cout << a << ' '<< b << ' ' << c << ' ' << d; } |
После чего проведем анализ, аналогичный решению выше.
Приведем другое решение.
Составим таблицу истинности для выражения (¬a ∧ ¬b) ∨ (b ≡ c) ∨ d вручную или при помощи языка Python:
print("a b c d")
for a in range(0, 2):
for b in range(0, 2):
for c in range(0, 2):
for d in range(0, 2):
if not((not(a) and not(b)) or (b == c) or d):
print(a, b, c, d)
Далее выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке a, b, c, d. Получим следующие наборы:
(0, 1, 0, 0),
(1, 0, 1, 0),
(1, 1, 0, 0).
Заметим, что во всех наборах переменная d равна 0. Следовательно, переменной d соответствует второй столбец, где нет единичных значений.
Заметим, что набору (0, 1, 0, 0) может соответствовать только первая строка таблицы, поскольку в других строках как минимум две переменные принимают единичное значение. Следовательно, третий столбец соответствует переменной b.
В третьей строке таблицы переменная b равна 1. Следовательно, третья строка соответствует набору (1, 1, 0, 0), в котором единичное значение принимает также переменная a, тогда переменной a соответствует четвертый столбец, а переменной c — первый.
Ответ: cdba.