Задание 23
ТЕМА 23
"Логические уравнения"
Пример 1
Сколько существует различных наборов значений логических переменных x1, x2,… x7, y1, y2… y7, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ≡ y1) ≡ (x2 ≡ y2)
(x2 ≡ y2) ≡ (x3 ≡ y3)
...
(x6 ≡ y6) ≡ (x7 ≡ y7)
В ответе не нужно перечислять все наборы значений переменных x1, x2,… x7, y1, y2… y7, при которых справедлива данная система равенств. В качестве ответа нужно указать количество таких наборов переменных.
Решение
В исходной системе 6 равенств, в каждом из которых присутствуют различные переменные не связанные между собой. Значит можно переписать эти равенства, обозначив каждую скобку новой переменной:
(x1 ≡ y1) = A
(x2 ≡ y2) = B
(x3 ≡ y3) = C
(x4 ≡ y4) = D
(x5 ≡ y5) = E
(x6 ≡ y6) = F
(x7 ≡ y7) = G, тогда можно записать:
A ≡ B
B ≡ C
C ≡ D
D ≡ E
E ≡ F
F ≡ G
Каждое равенство представляет собой эквиваленцию (тождество) двух переменных. Тождество принимает значение истинности в двух случаях:
1) 0 ≡ 0 = 1
2) 1 ≡ 1 = 1
Значит, каждая переменная, может принимать значения 0 или 1. Так как все переменные тождественны друг другу, то существует всего две цепочки значений:
A (0 или 1)
B (0 или 1)
…
G (0 или 1)
Все переменные A - G являются скобками, внутри которых тождество. Поэтому на каждый 0 в цепочке решений должно существовать 2 набора переменных (x, y), и на каждую 1 также должно существовать 2 набора переменных (x, y). Каждая цепочка состоит из семи элементов, каждый из которых может принимать два значения и при 0, и при 1. Значит, для каждой цепочки существует 27 = 128 наборов значений переменных (x, y). Всего таких цепочек две, поэтому общее количество наборов переменных равно: 128 · 2 = 256
Ответ: 256
Пример 2
(демоверсия ЕГЭ по информатике 2019 г)
Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?
(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1
(y2 → (y3 ∧ x2)) ∧ (x2 → x3) = 1
…
(y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1
y7 → x7 = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x7, y1, y2, … y7, при которых выполнена данная система равенств. В качестве ответа нужно указать количество таких наборов.
Решение
Для решения исходной системы равенств можно использовать способ отображения, так как первые 6 равенств подобны. На решение первых 6 равенств далее нужно наложить ограничение, записанное в 7 равенстве.
Результат решения первого равенства можно применить к другим равенствам.
Уравнение: (y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1 – истинно в случае, когда
(y1 → (y2 ∧ x1)) = 1 и (x1 → x2) = 1.
Необходимо построить таблицу истинности для первого равенства и выявить количество верных решений (таблица для 4 переменных будет содержать 16 строк):
Обозначим x1 и y1 через xi и yi, а x2 и y2 через xi+1 и yi+1. В соответствии с полученной таблицей нужно указать стрелками на схеме все истинные решения для первых 6 уравнений.
Теперь можно определить общее количество всех решений для первых 6 исходных равенств, составив таблицу отображений:
Получили общее количество решений: 1 + 1 + 7 + 28 = 37.
Теперь осталось только применить 7 уравнение к полученному количеству решений:
y7 → x7 = 1 – ложно при y7 = 1, а x7 = 0. Такой набор значений для (x7,y7) равен 1 и соответствует второй строке в таблице отображений. Это решение необходимо исключить из общего количества решений!
Значит, количество наборов переменных, при которых справедлива исходная система равенств, равно: 37 – 1 = 36
Ответ: 36
Пример 3
(демоверсия ЕГЭ по информатике 2020 г)
Сколько существует различных наборов значений логических переменных x1, x2, … x8, y1, y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?
(¬(x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬(x2 ≡ y2)) ≡ (x3 ≡ y3)
…
(¬(x7 ≡ y7)) ≡ (x8 ≡ y8)
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8, y1, y2, … y8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Решение
Для решения исходной системы равенств можно использовать способ отображения, так как равенства однотипны.
Результат решения первого равенства можно применить к другим равенствам.
Тождество принимает значение истинности в двух случаях:
1) 0 ≡ 0 = 1
2) 1 ≡ 1 = 1
Необходимо построить таблицу истинности для первого равенства и выявить количество истинных решений (таблица для 4 переменных будет содержать 16 строк):
Обозначим x1 и y1 через xi и yi, а x2 и y2 через xi+1 и yi+1. В соответствии с полученной таблицей нужно указать стрелками на схеме все истинные решения для всех уравнений.
Теперь можно определить общее количество всех решений для исходных равенств, составив таблицу отображений:
Значит, количество наборов переменных, при которых справедлива исходная система равенств, равно: 128 + 128 + 128 + 128 = 512
Ответ: 512
Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу