ТЕМА 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. Значит, для каждой цепочки существует 2⁷ = 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 строк):

Получили общее количество решений: 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 строк):

Теперь можно определить общее количество всех решений для исходных равенств, составив таблицу отображений:

Значит, количество наборов переменных, при которых справедлива исходная система равенств, равно: 128 + 128 + 128 + 128 = 512

Ответ: 512

• Примеры, рассмотренные на этой странице в формате pdf: скачать
• Решенные задачи по теме других авторов: скачать
• Смотреть видеоуроки по теме: видео 1, видео 2, видео 3, видео 4

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу