Разбор 2 задания ЕГЭ по информатике про таблицы истинности

• Отобразим перебор всех значений использующихся в выражении переменных (всю таблицу истинности). Поскольку в выражении используются 4 переменных, то строк таблицы будет 2⁴=16:



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

xwzy

✎ Способ 2. Программирование:
Язык python:

print('x y z w') for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (not(x) or y or z) and (x or not(z) or not(w)) if not(F): print(x, y, z, w)

print('x y z w') for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (not(x) or y or z) and (x or not(z) or not(w)) if not(F): print(x, y, z, w)

• В результате будут выведены значения для F=0:

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

• Сопоставив их с исходной таблицей, получим результат:

xwzy

  Язык pascalAbc.net:

begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not x or y or z) and (x or not z or not w)) then writeln(x:7, y:7, z:7,w:7); end.

begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not x or y or z) and (x or not z or not w)) then writeln(x:7, y:7, z:7,w:7); end.

• В результате будут выведены значения для F=0:

      x      y      z      w
  False  False   True   True
  False   True   True   True
   True  False  False  False
   True  False  False   True

• Где false = 0, True = 1
• Сопоставив их с исходной таблицей, получим результат:

Ответ:

xwzy

✎ Способ 3. Логические размышления:
• Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:

(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w) = 1 когда:
1. (¬x ∨ y ∨ z) = 1 
И 
2. (x ∨ ¬z ∨ ¬w) = 1

• Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
• Разобьём исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
• Для сомножителя (¬x ∨ y ∨ z):

x	y	z	результат
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

• Получили ложь в одном наборе, так как дизъюнкция (∨) ложна только тогда, когда ложны все операнды.
• Для сомножителя (x ∨ ¬z ∨ ¬w):

x	z	w	результат
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

• Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
• Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ∧) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):



• Выпишем только пересеченные наборы:

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

• Сравнив вторую строку заданной таблицы и вторую строку получившейся таблицы, находим, что x находится в первом столбце.

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

x	???	???	???	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

• Сравнив первую и четвертую одинаковые строки получившейся таблицы, находим, что y в обоих случаях равен 0. Значит он находится в 4-м столбце.

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

x	???	???	y	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

• Сравнив предпоследнюю и последнюю строки получившейся таблицы, там где x = 1, находим, что z в обоих случаях равен 0, тогда как w принимает значение и 1 и 0. Значит z находится в 3-м столбце.

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

• Для w остается второй столбец:

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

Результат: xwzy

• Решим задание методом построения полной таблицы истинности.
• Посчитаем общее количество строк в таблице истинности и построим ее:

4 переменных -> 24 = 16 строк



• Для начала упростим выражение и выделим в нем две основные части относительно внешней операции (операция, которая выполняется последней).

(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)
1. Избавимся от импликации:
¬(¬z ∧ ¬(x ≡ y)) ∨ ¬(y ∨ w)
2. Внесем знак отрицания в скобки (закон Де Моргана):
(z ∨ (x ≡ y)) ∨ (¬y ∧ ¬w) = 0
   1 часть = 0     2 часть = 0

* Исходное выражение должно быть = 0. Дизъюнкция = 0, когда оба операнда равны 0.

• Разбили исходное выражение на две части, теперь добавим столбцы для двух частей в таблицу истинности:



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

(z ∨ (x ≡ y)) = 0 когда z = 0 и x ≡ y = 0

¬y ∧ ¬w = 0 когда:
1. ¬y = 0  ¬w = 0
2. ¬y = 1  ¬w = 0
3. ¬y = 0  ¬w = 1

• В результирующей таблице истинности получили только три набора значений переменных при которых выражение возвратит ложь.

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

• Сравнив их с исходной таблицей истинности, имеем:

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

• Таким образом, ответ: ywxz

Результат: ywxz

Язык PascalAbc.net:

begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not z and (x xor y)) <= not(y or w)) then writeln(x:7, y:7, z:7,w:7); end.

begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not z and (x xor y)) <= not(y or w)) then writeln(x:7, y:7, z:7,w:7); end.

• В результате будут выведены значения для F=0:

      x      y      z      w
  False   True  False  False
  False   True  False   True
   True  False  False   True

• Где false = 0, True = 1

Сопоставив их с исходной таблицей, получим результат: ywxz

Язык Python:

print ('x y z w') for x in 0,1: for y in 0,1: for z in 0,1: for w in 0,1: F=(not z and not(x==y))<=(not(y or w)) if not F: print (x,y,z,w)

print ('x y z w') for x in 0,1: for y in 0,1: for z in 0,1: for w in 0,1: F=(not z and not(x==y))<=(not(y or w)) if not F: print (x,y,z,w)

• В результате будут выведены значения для F=0:

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

Сопоставив их с исходной таблицей, получим результат:

Результат: ywxz

Результат: cbad

✎ Логические размышления (бескомпьютерный вариант):
• Внешним действием (последним выполняемым) в исходном выражении является дизъюнкция:

¬x ∨ y ∨ (¬z ∧ w)

• Вспомним таб. ист-ти для дизъюнкции (логическое сложение):

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

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

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
x	???	???	???	F
1	0	0	0	0

• Строка №3: в ней один нуль — четвертый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы y = 0. Значит четвертый столбец соответствует переменной y.

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
x	???	???	y	F
1	1	1	0	0

• Строка №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

✎ Способ 2. Программирование:
Язык pascalABC.NET:

begin
  writeln('x  ','y  ','z  ','w  ');
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not(not x or y or(not z and w)) then
            writeln(x:7,y:7,z:7,w:7);
end.

Результат: xwzy

• Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 2⁵=32, т.е. 32 строки.
• Из этих 32 строк и для F и для G мы знаем наверняка только о 5 строках: 4 из них истинны (=1), а одна ложна (=0).
• Вопрос стоит о количестве строк = 1 для таб. истинности F ∨ G. Данная операция — дизъюнкция, которая ложна только в одном случае — если F = 0 и одновременно G = 0
• В исходных таблицах для F и G мы знаем о существовании только одного 0, т.е. в остальных строках может быть 1. Т.о., и для F и для G в 31 строке могут быть единицы (32-1=31), а лишь в одной — ноль.
• Тогда для F ∨ G только в одном случае будет 0, когда и F = 0 и G = 0:

№	F	G	F ∨ G
1	0	0	0
2	0	1	1
…	…	…	1
32	…	…	1

• Соответственно, истинными будут все остальные строки:

32 - 1 = 31

Результат: 31

• Полная таблица истинности для каждого из выражений A и B состоит из 2⁷ = 128 строк.
• В четырех из них результат равен единице, значит в остальных — 0.
• A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
• Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:

A	B
1	0
1	0
1	0
1	0
0	1
0	1
0	1
0	1
0	0
…	…

• Итого получаем 8 строк.
• Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.

Результат: 8

• Полная таблица истинности для каждого из выражений A и B состоит из 2⁸ = 256 строк.
• В шести из них результат равен единице, значит в остальных — 0.
• A ∧ B ложно в том случае, когда:

  A ∧ B = 0 если:
  
  1. A = 0, B = 1 
  2. B = 0, A = 1
  3. A = 0 и B = 0
  

• Во всех случаях там где А=1 может стоять B=0, и тогда результат F = 0. Поскольку нам необходимо найти максимально возможное число нулей, то как раз для всех шести А=1 сопоставим B=0, и наоборот, для всех шести возможных B=1 сопоставим A=0

A	B	F
1	0	0
1	0	0
1	0	0
1	0	0
0	1	0
0	1	0
0	1	0
0	1	0
0	0	0
…	…	…

• Поскольку строк всего 256, то вполне возможно, что все 256 из них возвратят в результате 0

Результат: 256

• В первом внешняя операция (выполняется последней) — конъюнкция. Начнем рассмотрение с нее. Соответственно, проверяем по второй строке таб. ист-ти, там где F = 1, так как в таком случае все аргументы должны быть истинными (см. таб. истинности для конъюнкции).
• Если мы подставим в нее все аргументы выражения, то функция действительно возвращает истину. Т.е. пункт первый подходит:



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



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



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



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

Результат: 1

• Поскольку выражение включает 5 переменных, то таб. ист-ти состоит из 2⁵ = 32 строк.
• Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
• Обозначим первую скобку за А, а вторую скобку за B. Получим A ∧ B.
• Найдем сколько нулей существует для таб. истинности:

   A  B  F
1. 0  0  0
2. 0  1  0
3. 1  0  0

Теперь рассмотрим каждый случай отдельно:

• 1 случай. 0 0 : A = 0 и B = 0, то есть:

¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.

• Обратим внимание, что во вторых скобках везде стоит инверсия переменных, которые находятся в первых скобках. Таким образом, это невозможно, так как дизъюнкция равна нулю, когда все операнды равны нулю. А если в первых скобках все 0, то из-за инверсий во вторых скобках все 1. То есть этот случай нам не подходит.
• 2 случай. 0 1 : нам он подходит, так как если первая скобка возвратит 0, то вторая вернет 1.
• 3 случай. 1 0 : нам он подходит, так как если вторая скобка возвратит 0, то первая вернет 1.
• Итого получаем два случая, когда исходное выражение вернет 0, т.е. две строки таблицы истинности.
• Тогда получим количество строк, с результатом равным 1:

32 - 2 = 30, что соответствует номеру 2

Результат: 2

• Полная таблица истинности будет иметь 2⁶ = 64 строк (т.к. 6 переменных).
• 4 из них нам известны: в них x3 два раза не совпадает с F.
• Неизвестных строк:

 
64 - 4 = 60

• В неизвестных x3 может не совпадать с F, кроме того, в двух известных x3 не совпадает с F. Соответственно максимально возможное число строк с несовпадающими x3 и F, будет:

60 + 2 = 62

Результат: 62

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

1 пункт:

(((x1 ∧ (x2 → x3) ∧  ¬x4) ∧ x5) ∧ x6)  ∧ ¬x7

• Внешняя операция — конъюнкция. Ее проще проверять по строке, в которой F = 1 (значит все сомножители должны быть равны 1).
• Возьмем 3-ю строку, в ней x4=1. В нашем выражении х4 с отрицанием, т.е. = 0. Для конъюнкции, когда хоть один из сомножителей равен нулю, выражение вернет в результате 0, а у нас в строке 1. Т.е. этот пункт не подходит:


2 пункт:

(((x1 ∨ (¬x2 → x3) ∨  ¬x4) ∨ ¬x5) ∨ x6)  ∨ ¬x7

• Последняя выполняющаяся операция (внешняя) — дизъюнкция. Ее легче проверять по строке, в которой F = 0 (значит все слагаемые должны быть равны 0).
• Смотрим по первой строке: х4 = 0, в рассматриваемом пункте он с отрицанием, т.е. = 1. Соответственно все выражение вернет единицу, а в таблице в строке 0. Т.е. этот пункт не подходит:


3 пункт:

(((¬x1 ∧ (x2 → ¬x3) ∧  x4) ∧ ¬x5) ∧ x6) ∧ x7

• Последняя операция — конъюнкция. Ее проще проверять по строке, в которой F = 1 (значит все сомножители должны быть равны 1).
• Возьмем 2-ю строку: в ней х7 = 0, в рассматриваем пункте х7 без отрицания, т.е. так и остается равным нулю. При умножении выражение вернет в результате 0. В таблице — 1. Т.е. пункт тоже не подходит:



• Единственным подходящим вариантом остался пункт под номером 4 (на всякий случай всегда стоит проверить и его).

Результат: 4

• Сначала необходимо рассмотреть логическую операцию, которую мы будем выполнять в последнюю очередь — это логическое И (конъюнкция) или ∧. То есть внешнюю операцию:

(y → x) ∧ (y → z) ∧ z

• Конъюнкцию легче рассматривать по тем строкам таб. ист-ти, в которых F = 1, т.е. №3, №4, и №8
• Поскольку для конъюнкции функция истинна только тогда, когда все переменные истинны, то необходимо чтобы отдельно каждая скобка была истинна ((y → x) = 1 и (y → z)=1) и переменная z тоже была истинной (=1)

(y → x) ∧ (y → z) ∧ z = 1
   если: 
1. (y → x) = 1
2. (y → z) = 1
3. z = 1

• Поскольку с выражениями в скобках сложней работать, определим сначала какому столбцу соответствует z. Для этого выберем строку (№3), где F = 1, а в остальных ячейках только одна единица, остальные — нули.

№	Перем. 1	Перем. 2	Перем. 3	F
3	0	1	0	1

• Таким образом, делаем вывод, что z находится во втором столбце (отсчет ведем слева):

№	Перем. 1	Перем. 2	Перем. 3	F
_	???	z	???	F

• Дальше нам необходимо рассмотреть две скобки, в которых находится операция импликации: (y → x) и (y → z). Обе эти скобки должны возвращать истину (=1). В таб. истинности для импликации, функция возвращает в результате 1 тогда, когда:
• вторая переменная (заключение) равна 1 (первая при этом может быть любой),
• вторая переменная (заключение) равна 0, а первая обязательно должна быть равна тоже 0.
• Рассмотрим скобку (y → x) и строку 4 таблицы:

№	Перем. 1	z	Перем. 3	F
4	0	1	1	1

• Для этой строки только y может быть равен 0, т.к. если x = 0, тогда y=1, и скобка в результате возвратит ложь (1 → 0 = 0). Соответственно, y находится в первом столбце. А x значит должен стоять в третьем:

y

z

x

F

Результат: yzx