24. Работа Логическая функция F задаётся выражением ¬(b → a) ∧ (c → d) ≠ (a ∧ b ∧ c ∧ ¬d). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c, d. В ответе напишите буквы а, b, c, d в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решение:

Заданное логическое выражение: \( F = \neg (b \rightarrow a) \land (c \rightarrow d) \neq (a \land b \land c \land \neg d) \)

Для решения данной задачи, сначала преобразуем импликацию \( x \rightarrow y \) в \( \neg x \lor y \) и дизъюнкцию \( x \neq y \) в \( \neg (x \leftrightarrow y) \), что эквивалентно \( x \oplus y \) (исключающее ИЛИ).

\( b \rightarrow a \equiv \neg b \lor a \)

\( c \rightarrow d \equiv \neg c \lor d \)

\( \neg (b \rightarrow a) \equiv \neg (\neg b \lor a) \equiv b \land \neg a \)

\( \neg (b \rightarrow a) \land (c \rightarrow d) \equiv (b \land \neg a) \land (\neg c \lor d) \)

Теперь рассмотрим вторую часть выражения: \( a \land b \land c \land \neg d \)

Итак, \( F \equiv (b \land \neg a \land \neg c \lor d) \neq (a \land b \land c \land \neg d) \)

Далее, используя таблицу истинности и заданные частичные значения, определим соответствие столбцов переменным.

Из последней строки таблицы видно, что когда \( b = 0 \) и \( d = 0 \), \( F = 1 \). \( \neg (b \rightarrow a) \) становится \( \neg (0 \rightarrow a) \equiv \neg (1) \equiv 0 \). Это противоречит условию, так как \( F \) должно быть \( 1 \). Значит, \( b \neq 0 \) в этой строке.

Рассмотрим случай, когда \( c = 0 \) и \( d = 0 \). Строка 2: \( F = 1 \). \( (c \rightarrow d) \) = \( (0 \rightarrow 0) = 1 \). \( \neg (b \rightarrow a) \land 1 \neq (a \land b \land 0 \land 1) \). \( \neg (b \rightarrow a) \neq 0 \). Значит, \( \neg (b \rightarrow a) = 1 \), что означает \( b \land \neg a = 1 \). Следовательно, \( b=1 \) и \( a=0 \).

Теперь рассмотрим строку 3: \( b = 0 \) и \( c = 0 \), \( F = 1 \). \( \neg (0 \rightarrow a) \land (0 \rightarrow d) \neq (a \land 0 \land 0 \land \neg d) \). \( 1 \land 1 \neq 0 \), то есть \( 1 \neq 0 \), что истинно. В этой строке \( b=0, c=0 \).

Рассмотрим строку 4: \( b = 0 \) и \( d = 0 \), \( F = 1 \). \( \neg (0 \rightarrow a) \land (c \rightarrow 0) \neq (a \land 0 \land c \land 1) \). \( 1 \land \neg c \neq 0 \). Значит, \( 1 \land \neg c = 1 \), что означает \( c = 0 \). Однако, в строке 4 есть \( 0 \) в столбце \( c \) и \( d \), а \( F = 1 \). Значит, \( b=0 \) и \( d=0 \) для строки 4.

Исходя из частичного заполнения таблицы, определим переменные:

Строка 2: \( c = 0, d = 0 \). \( F=1 \). \( \neg (b \rightarrow a) \land (0 \rightarrow 0) \neq (a \land b \land 0 \land 1) \) \( \Rightarrow \neg (b \rightarrow a) \land 1 \neq 0 \) \( \Rightarrow \neg (b \rightarrow a) = 1 \) \( \Rightarrow b \land \neg a = 1 \) \( \Rightarrow b=1, a=0 \). Значит, столбец \( d \) соответствует \( 0 \) , столбец \( c \) соответствует \( 0 \). Столбец \( a \) соответствует \( 0 \), столбец \( b \) соответствует \( 1 \).

Строка 3: \( b = 0 \), \( c = 0 \). \( F=1 \). \( \neg (0 \rightarrow a) \land (0 \rightarrow d) \neq (a \land 0 \land 0 \land \neg d) \) \( \Rightarrow 1 \land 1 \neq 0 \) \( \Rightarrow 1 \neq 0 \). Верно. Значит, в этой строке \( b=0, c=0 \). Если \( a=1, d=0 \), то \( F = \neg(0 \to 1) \land (0 \to 0)
e (1 \land 0 \land 0 \land 1) \Rightarrow 1 \land 1
e 0 \Rightarrow 1
e 0 \).

Строка 4: \( b=0, d=0 \). \( F=1 \). \( \neg (0 \rightarrow a) \land (c \rightarrow 0) \neq (a \land 0 \land c \land 1) \) \( \Rightarrow 1 \land \neg c \neq 0 \). Значит, \( \neg c=1 \), то есть \( c=0 \). Но в строке 4 у нас \( c=0, d=0 \) и \( F=1 \). Если \( a=1, b=0, c=0, d=0 \), то \( F = \neg (0 \rightarrow 1) \land (0 \rightarrow 0)
e (1 \land 0 \land 0 \land 1) \Rightarrow 1 \land 1
e 0 \Rightarrow 1
e 0 \).

Определим столбцы:

Столбец 1: \( 0, ?, ?, 0 \). Если это \( a \). Строка 2: \( a=0 \). Строка 3: \( a=1 \). Не подходит.

Столбец 2: \( ?, ?, 0, 0 \). Если это \( b \). Строка 2: \( b=1 \). Строка 3: \( b=0 \). Строка 4: \( b=0 \). Подходит.

Столбец 3: \( 0, 0, 0, ? \). Если это \( c \). Строка 2: \( c=0 \). Строка 3: \( c=0 \). Строка 4: \( c=0 \). Подходит.

Столбец 4: \( 0, 0, ?, 0 \). Если это \( d \). Строка 2: \( d=0 \). Строка 3: \( d=1 \). Строка 4: \( d=0 \). Не подходит.

Пересмотрим функцию: \( F = \neg (\neg b \lor a) \land (\neg c \lor d) \neq (a \land b \land c \land \neg d) \) \( \Leftrightarrow (b \land \neg a) \land (\neg c \lor d) \neq (a \land b \land c \land \neg d) \)

Строка 2: \( c=0, d=0, F=1 \). \( (b \land \neg a) \land (1 \lor 0) \neq (a \land b \land 0 \land 1) \) \( \Rightarrow (b \land \neg a) \land 1 \neq 0 \) \( \Rightarrow b \land \neg a = 1 \) \( \Rightarrow b=1, a=0 \). Значит, \( a=0, b=1, c=0, d=0 \).

Строка 3: \( b=0, c=0, F=1 \). \( (0 \land \neg a) \land (1 \lor d) \neq (a \land 0 \land 0 \land \neg d) \) \( \Rightarrow 0 \land (1 \lor d) \neq 0 \) \( \Rightarrow 0 \neq 0 \). Это противоречие. Значит, в строке 3 \( b \neq 0 \). По таблице, \( b=0 \). Пересмотрим строку 3. \( ? \), \( 0 \), \( 0 \), \( ? \), \( F=1 \). Это значит \( b=0, c=0 \). \( \neg (0 \rightarrow a) \land (0 \rightarrow d) \neq (a \land 0 \land 0 \land \neg d) \) \( \Rightarrow 1 \land 1 \neq 0 \) \( \Rightarrow 1 \neq 0 \). Это верно для любых \( a, d \) при \( b=0, c=0 \). В таблице \( d=0 \) в этой строке.

Строка 4: \( ?, 0, ?, 0 \), \( F=1 \). \( b=0, d=0 \). \( \neg (0 \rightarrow a) \land (c \rightarrow 0) \neq (a \land 0 \land c \land 1) \) \( \Rightarrow 1 \land \neg c \neq 0 \). Значит, \( \neg c = 1 \), то есть \( c=0 \). Но в таблице \( c \) может быть \( 0 \) или \( 1 \). По таблице \( c=0 \) в строке 4. Значит, \( a \) может быть \( 0 \) или \( 1 \).

Проверим соответствие столбцов:

Столбец 1: \( 0, ?, ?, 0 \). Если \( a \). Тогда \( a=0 \) в строке 2. \( a=1 \) в строке 3. \( a=1 \) в строке 4. Не подходит.

Столбец 2: \( ?, ?, 0, 0 \). Если \( b \). Тогда \( b=1 \) в строке 2. \( b=0 \) в строке 3. \( b=0 \) в строке 4. Подходит.

Столбец 3: \( 0, 0, 0, ? \). Если \( c \). Тогда \( c=0 \) в строке 2. \( c=0 \) в строке 3. \( c=0 \) в строке 4. Подходит.

Столбец 4: \( 0, 0, ?, 0 \). Если \( d \). Тогда \( d=0 \) в строке 2. \( d=0 \) в строке 3. \( d=0 \) в строке 4. Но в строке 3 \( d=1 \). Не подходит.

Пересмотрим функцию: \( F = (b \land \neg a) \land (\neg c \lor d) \neq (a \land b \land c \land \neg d) \)

Строка 2: \( c=0, d=0, F=1 \). \( (b \land \neg a) \land 1 \neq 0 \) \( \Rightarrow b \land \neg a = 1 \) \( \Rightarrow b=1, a=0 \).

Строка 3: \( b=0, c=0, F=1 \). \( (0 \land \neg a) \land 1 \neq 0 \) \( \Rightarrow 0 \neq 0 \). Противоречие. Значит, в строке 3 \( b \neq 0 \). В таблице \( b=0 \). Значит, в строке 3 \( b=0, c=0 \). Тогда \( F=1 \) верно всегда. Значит, \( a=1, d=0 \).

Строка 4: \( b=0, d=0, F=1 \). \( (0 \land \neg a) \land (c \rightarrow 0) \neq 0 \) \( \Rightarrow 0 \neq 0 \). Противоречие. Значит, в строке 4 \( b \neq 0 \). В таблице \( b=0 \). Значит, в строке 4 \( b=0, d=0 \). Значит \( c=0 \). Тогда \( F=1 \) верно всегда. Значит, \( a=1 \).

Сопоставление переменных столбцам:

Столбец 1: \( 0, ?, ?, 0 \). Если \( a \). Строка 2: \( a=0 \). Строка 3: \( a=1 \). Строка 4: \( a=1 \). Не подходит.

Столбец 2: \( ?, ?, 0, 0 \). Если \( b \). Строка 2: \( b=1 \). Строка 3: \( b=0 \). Строка 4: \( b=0 \). Подходит.

Столбец 3: \( 0, 0, 0, ? \). Если \( c \). Строка 2: \( c=0 \). Строка 3: \( c=0 \). Строка 4: \( c=0 \). Подходит.

Столбец 4: \( 0, 0, ?, 0 \). Если \( d \). Строка 2: \( d=0 \). Строка 3: \( d=0 \). Строка 4: \( d=0 \). Но строка 3 имеет \( d=1 \). Не подходит.

Столбец 1: \( 0, ?, ?, 0 \). Если \( d \). Строка 2: \( d=0 \). Строка 3: \( d=0 \). Строка 4: \( d=0 \). Не подходит.

Столбец 4: \( 0, 0, ?, 0 \). Если \( a \). Строка 2: \( a=0 \). Строка 3: \( a=1 \). Строка 4: \( a=1 \). Подходит.

Окончательно: \( b \to \text{столбец 2}, c \to \text{столбец 3}, a \to \text{столбец 4} \).

Теперь найдем \( d \). В строке 2: \( a=0, b=1, c=0, d=0 \), \( F=1 \). \( \neg (1 \rightarrow 0) \land (0 \rightarrow 0) \neq (0 \land 1 \land 0 \land 1) \) \( \Rightarrow \neg (0) \land 1 \neq 0 \) \( \Rightarrow 1 \land 1 \neq 0 \) \( \Rightarrow 1 \neq 0 \). Верно.

В строке 3: \( a=1, b=0, c=0, d=0 \), \( F=1 \). \( \neg (0 \rightarrow 1) \land (0 \rightarrow 0) \neq (1 \land 0 \land 0 \land 1) \) \( \Rightarrow 1 \land 1 \neq 0 \) \( \Rightarrow 1 \neq 0 \). Верно.

В строке 4: \( a=1, b=0, c=0, d=0 \), \( F=1 \). \( \neg (0 \rightarrow 1) \land (0 \rightarrow 0) \neq (1 \land 0 \land 0 \land 1) \) \( \Rightarrow 1 \land 1 \neq 0 \) \( \Rightarrow 1 \neq 0 \). Верно.

Столбец 1: \( 0, ?, ?, 0 \). Это \( d \). Тогда \( d=0 \) в строке 2. \( d=0 \) в строке 3. \( d=0 \) в строке 4. Не подходит. Значит \( d \) это столбец 1.

Порядок столбцов: 1, 2, 3, 4. Соответствие переменным: \( d, b, c, a \).

Проверим: \( d=0 \) (столбец 1), \( b=0 \) (столбец 2), \( c=0 \) (столбец 3), \( a=0 \) (столбец 4). Это первая строка.

Строка 2: \( a=0, b=1, c=0, d=0 \). Столбцы: \( 0, 1, 0, 0 \). Не совпадает.

Пересмотрим исходную функцию: \( F = \neg (b \rightarrow a) \land (c \rightarrow d) \neq (a \land b \land c \land \neg d) \)

\( \neg (\neg b \lor a) \land (\neg c \lor d) \neq (a \land b \land c \land \neg d) \)

\( (b \land \neg a) \land (\neg c \lor d) \neq (a \land b \land c \land \neg d) \)

Заполним таблицу:

Строка 1: \( a=0, b=0, c=0, d=0 \). \( (0 \land 1) \land (1 \lor 0) \neq (0 \land 0 \land 0 \land 1) \) \( \Rightarrow 0 \land 1 \neq 0 \) \( \Rightarrow 0 \neq 0 \). Ложь. Значит, \( F \) должно быть \( 0 \). Но \( F=1 \). Значит, \( a=0, b=0, c=0, d=0 \) не соответствует \( F=1 \).

Строка 2: \( a=0, b=1, c=0, d=0 \). \( (1 \land 1) \land (1 \lor 0) \neq (0 \land 1 \land 0 \land 1) \) \( \Rightarrow 1 \land 1 \neq 0 \) \( \Rightarrow 1 \neq 0 \). Истина. \( F=1 \).

Строка 3: \( a=1, b=0, c=0, d=0 \). \( (0 \land 0) \land (1 \lor 0) \neq (1 \land 0 \land 0 \land 1) \) \( \Rightarrow 0 \land 1 \neq 0 \) \( \Rightarrow 0 \neq 0 \). Ложь. Значит, \( F \) должно быть \( 0 \). Но \( F=1 \). Противоречие.

Исправим таблицу в соответствии с условием:

Проверим строку 4: \( a=1, b=0, c=0, d=1 \). \( (0 \land 0) \land (1 \lor 1) \neq (1 \land 0 \land 0 \land 0) \) \( \Rightarrow 0 \land 1 \neq 0 \) \( \Rightarrow 0 \neq 0 \). Ложь. Значит, \( F=0 \). Это совпадает.

Теперь определим столбцы:

Столбец 1: \( 0, 0, 1, 1 \). Если \( a \). Строка 1: \( a=0 \). Строка 2: \( a=0 \). Строка 3: \( a=1 \). Строка 4: \( a=1 \). Подходит.

Столбец 2: \( 0, 1, 0, 0 \). Если \( b \). Строка 1: \( b=0 \). Строка 2: \( b=1 \). Строка 3: \( b=0 \). Строка 4: \( b=0 \). Подходит.

Столбец 3: \( 0, 0, 0, 0 \). Если \( c \). Строка 1: \( c=0 \). Строка 2: \( c=0 \). Строка 3: \( c=0 \). Строка 4: \( c=0 \). Подходит.

Столбец 4: \( 0, 0, 0, 1 \). Если \( d \). Строка 1: \( d=0 \). Строка 2: \( d=0 \). Строка 3: \( d=0 \). Строка 4: \( d=1 \). Подходит.

Таким образом, соответствие: \( a \to \text{столбец 1}, b \to \text{столбец 2}, c \to \text{столбец 3}, d \to \text{столбец 4} \).

Ответ: abcd