Задание 2 ЕГЭ по информатике 2018

• Внешней операцией в исходном выражении является дизъюнкция: ¬x ∨ y ∨ (¬z ∧ w). Вспомним таблицу истинности для дизъюнкции (сложение):

x1	x2	F
0	0	0
0	1	1
1	0	1
1	1	1

• Чтобы исходное выражение было истинным, нужно, чтобы хотя бы один из операндов равнялся единице. Т.е. ¬x = 1 или 0, y = 1 или 0, ¬z ∧ w = 1 или 0.
• Функция же ложна только в одном случае, — когда все операнды ложны. Поэтому будем искать по признаку лжи.
• В исходной таблице истинности во всех строках функция ложна. Чтобы понять в каком столбце должна находиться та или иная переменная, возьмем за основу строку, в которой только одна единица или только один нуль.
• Строка №1: в ней одна единица — первый столбец. В исходном выражении, чтобы функция была ложна, необходимо, чтобы ¬x = 0, иными словами, x = 1. Значит, первый столбец соответствует переменной x.
• Строка №3: в ней один нуль — четвертый столбец. В исходном выражении, чтобы функция была ложна, необходимо, чтобы y = 0. Значит, четвертый столбец соответствует переменной y.
• Строка №2: в ней второй столбец равен единице, а третий — нулю. В исходном выражении ¬z ∧ w должно равняться 0, чтобы функция была ложной. Конъюнкция истинна только тогда, когда оба операнда истинны (=1); в нашем случае функция должна быть ложной, но пойдем от обратного. Если ¬z = 1, т.е. z = 0, а w = 1, то это неверно для нашего случая. Значит, всё должно быть наоборот: z = 1, а w = 0. Таким образом, столбец второй соответствует z, а столбец третий — w.

x	z	w	y	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

Результат: xzwy

• В первом выражении основная операция — конъюнкция. Соответственно, проверяем выражение по строке второй, там, где функция = 1. Если мы подставим в эту строку все аргументы выражения, то функция действительно возвращает истину. Т.е. это выражение подходит.



• Но проверим на всякий случай остальные.
• Второе выражение проверяем по первой и третьей строке, так как дизъюнкция ложна только в том случае, если все операнды ложны. Проверяя по первой строке, сразу видим, что x1 в ней равен 1. В таком случаем функция будет = 1. Т.е. это выражение не подходит.



• Третье выражение проверяем по второй строке, так как основная операция — конъюнкция — возвратит истину только тогда, когда все операнды равны 1. Видим, что x1 = 0, соответственно функция будет тоже равна 0. Т.е. выражение нам не подходит.



• Четвертое выражение проверяем по первой и третьей строкам. В первой строке x1 = 1, т.е. функция должна быть равна 1. Т.е. выражение тоже не подходит.



• Таким образом, ответ равен 1.

Результат: 1

Результат: cbad

Результат: zyxw

• Преобразуем выражение по закону Де Моргана ¬(a ∨ b) = ¬a ∧ ¬b :

¬(z ∨ (y ∧ ¬x)) = ¬z ∧ ¬(y ∧ ¬x) = 
= ¬z ∧ (¬y ∨ x)

• Так как внешняя операция будет логическое умножение (∧), то проверять следует по строкам, в которых F=1:

0	0	1	1
0	1	1	1

• По второй из двух строк видим, что z не может быть во втором и третьем столбцах (т.к. ¬z вернет 0 и функция станет равной 0). Соответственно, z — первый столбец.
• По первой из двух строк видим, что y не может быть в третьем столбце, т.к. ¬y станет равным 0, и одновременно во втором столбце x равно 0, тогда функция вернет 0. Значит, y — второй столбец, а x — третий.

Результат: zyx

• Так как внешняя (итоговая) операция будет логическое сложение (∨), то разделим выражение на две части: в одной из них оставим одиночную переменную (так легче найти для нее значение), а в другой — две скобки. Приравняем выражение к нулю, т.к. по заданию все строки таблицы истинности возвращают ложь:

          1            2
(x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w = 0

• Для операции логического сложения по таблице истинности имеем только одну строку с результатом равным нулю:

0 ∨ 0 = 0

• Таким образом, получаем две части выражения:

 
1. (x ∧ ¬y) ∨ (y ≡ z) = 0
2. ¬w = 0

• Сразу находим, что в первом столбце может находиться только переменная w, т.к. с отрицанием будет возвращаться 0:

w	Перем. 2	Перем. 3	Перем. 4
???	???	???	???
	0
1	0		0
1		0	0

• Рассмотрим первую часть выражения, в которой внешней операцией также является логическое сложение, которое в результате должно возвратить значение ложь. Таким образом, имеем:

1.1 (x ∧ ¬y) = 0
1.2 (y ≡ z) = 0

• Рассмотрим выражение 1.2. Результатом его является y не эквивалентно х. Т.е. мы должны найти в таблице истинности столбцы, в строках которых нет одинаковых значений. Возьмем столбцы 2 и 4: в них во второй строке значение 0, этого быть не может для y и z. Возьмем столбцы 3 и 4: в них во третьей строке значение 0, этого быть не может для y и z.

w	Перем. 2	Перем. 3	Перем. 4
???	???	???	???
	0
1	0		0
1		0	0

• Значит, в третьем столбце не могут находиться переменные z и y. Там находится x:

w	Перем. 2	Перем. 3	x
???	???	???	???
	0
1	0		0
1		0	0

• Теперь знаем, что во втором и третьем столбцах находятся переменные z и y. Заполним таблицу значениями, исходя из того, что в строках для w должны быть все 1, а для z и y значения построчно должны быть разными:

w	Перем. 2	Перем. 3	x
???	???	???	???
1	0	1
1	0	1	0
1	1	0	0

• В таблице истинности не может быть повторяющихся строк, поэтому для первой строки в столбце x имеем значение 1:

w	Перем. 2	Перем. 3	x
???	???	???	???
1	0	1	1
1	0	1	0
1	1	0	0

• Используя выражение 1.1, имеем y в третьем столбце, т.к. во втором он быть не может, судя по первой строке.

w	z	y	x
???	???	???	???
1	0	1	1
1	0	1	0
1	1	0	0

Результат: wzyx