Решение заданий №2 КЕГЭ по информатике

2-е задание: «Таблицы истинности»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
  
Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы

Типичные ошибки и рекомендации по их предотвращению:

"Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковых строк. Это приводит к внешне правдоподобному, но на самом деле неверному решению"

ФГБНУ "Федеральный институт педагогических измерений

Задание 2_11: Решение 2 задания ЕГЭ по информатике (Задание № 169 К. Поляков): https://kpolyakov.spb.ru/school/ege.htm

Логическая функция F задается выражением (¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w)

Ниже приведен фрагмент таблицы истинности функции F, содержащей все наборы аргументов, при которых функция F ложна.

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

Решение:

✎ Способ 1. Электронные таблицы Excel + Логические размышления:

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

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

 Выделите таблицу и отсортируйте строки по столбцу с результатом функции. Для этого в меню Главная = Настраиваемая сортировка =:

 Получили верхние строки таблицы — с которыми сравним исходную таблицу и найдем результат:

 Получаем следующий порядок переменных:

xwzy

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

• В результате будут выведены значения для 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:

• В результате будут выведены значения для 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 находится в первом столбце.

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

• Сравнив предпоследнюю и последнюю строки получившейся таблицы, там где 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 остается второй столбец:

Результат: xwzy

Задание 2_4: 2 задание. ГВЭ 11 класс по информатике 2018 (ФИПИ):

Дан фрагмент таблицы истинности выражения F.

Каким из приведённых ниже выражений может быть F?
1) ¬x1 ∧ x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
4) x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7

 Решение:

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

• Если мы подставим в нее все аргументы выражения, то функция действительно возвращает истину. Т.е. пункт первый подходит:

• Но проверим на всякий случай остальные.

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

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

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

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

Результат: 1

Раздел кодификатора ФИПИ: 1.5.1 Высказывания, логические операции, кванторы, истинность высказывания

Каждое из логических выражений F и G содержит 5 переменных. В таблицах истинности выражений F и G есть ровно 5 одинаковых строк, причём ровно в 4 из них в столбце значений стоит 1.

Сколько строк таблицы истинности для выражения F ∨ G содержит 1 в столбце значений?

Решение.

На 4 наборах входных переменных оба выражения равны 1, на 1 наборе оба равны 0, а на всех остальных одно из них равно 0, а другое 1. Поэтому если взять логическое или от этих двух выражений, то на том наборе, на котором они оба были равны 0, полученное выражение будет равно 0, на всех же остальных наборах хотя бы одно из них будет равно 1, поэтому и итоговое выражение будет равно 1. Всего различных наборов 32, из них на одном 0, то есть на 31 оставшихся наборах будет 1.

Ответ: 31.

Каждое из логических выражений F и G содержит 7 переменных. В таблицах истинности выражений F и G есть ровно 7 одинаковых строк, причём ровно в 6 из них в столбце значений стоит 0.

Сколько строк таблицы истинности для выражения F ∧ G содержит 0 в столбце значений?

Решение.

На 6 наборах входных переменных оба выражения равны 0, на 1 наборе оба равны 1, а на всех остальных одно из них равно 0, а другое 1. Поэтому если взять логическое и от этих двух выражений, то на том наборе, на котором они оба были равны 1, полученное выражение будет равно 1, на всех же остальных наборах хотя бы одно из них будет равно 0, поэтому и итоговое выражение будет равно 0. Всего различных наборов 2⁷ = 128, из них на одном 1, то есть на 127 оставшихся наборах будет 0.

Ответ: 127.

https://inf-ege.sdamgia.ru/test?theme=355