ГДЗ по информатике, 10 класс, Босова, номер 20.11: Преобразование логических выражений

Первое уравнение: x₁&x₂→x₃&x₄=1.

Вспомним определение импликации (a→b): она ложна только в одном случае — когда посылка a истинна, а следствие b ложно. Во всех остальных случаях импликация истинна.

Значит, условие x₁&x₂→x₃&x₄=1 нарушается (становится равным 0) только тогда, когда:

• x₁&x₂=1 (то есть x₁=1 и x₂=1);
• x₃&x₄=0 (то есть хотя бы одна из переменных x_3,x₄ равна 0).

Нам нужно посчитать количество наборов, где это не происходит . Всего переменных в этом уравнении 4 (x_1,x_2,x_3,x₄). Общее число комбинаций для них равно 2⁴=16.

Посчитаем «плохие» комбинации (где уравнение не выполняется): 1. Условие x₁=1,x₂=1 фиксирует две переменные. 2. Условие x₃&x₄=0 означает, что пара (x_3,x₄) может быть (0,0),(0,1),(1,0). Это 3 варианта. Итого плохих комбинаций: 1·1·3=3.

Количество хороших комбинаций для первых четырех переменных: 16-3=13.

Второе уравнение: x₃lorx₄lorx₅&x₆=1.

Это дизъюнкция (логическое ИЛИ). Она ложна только если все слагаемые ложны. Значит, чтобы уравнение было истинным, нам нужно исключить случай, когда:

• x₃=0⇒x₃=1;
• x₄=0⇒x₄=1;
• x₅&x₆=0.

То есть «плохой» случай — это когда x₃=1,x₄=1 и одновременно x₅&x₆=0.

Однако переменные x₃ и x₄ уже участвовали в первом уравнении. Мы не можем просто умножить количества решений, так как переменные связаны. Нужно рассмотреть систему целиком или использовать метод перебора/таблицы истинности для связанных групп.

Давайте перегруппируем задачу. Переменные x_1,x₂ влияют только на первое уравнение через конъюнкцию. Переменные x_5,x₆ влияют только на второе уравнение. Связующее звено — x_3,x₄.

Рассмотрим возможные значения пары (x_3,x₄):

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

• Для (0,0): 3(для x_1,x₂)×4(для x_5,x₆)=12.
• Для (0,1): 3×4=12.
• Для (1,0): 3×4=12.
• Для (1,1): 4×1=4.

Общее количество решений для системы №1: 12+12+12+4=40.

Система состоит из 4 уравнений с 10 переменными. Заметим структуру: каждое следующее уравнение связывает предыдущую пару переменных со следующей парой.

Уравнения: 1) x₁lorx₂lorx₃&x₄=1 2) x₃lorx₄lorx₅&x₆=1 3) x₅lorx₆lorx₇&x₈=1 4) x₇lorx₈lorx₉&x₁₀=1

Рассмотрим первое уравнение. Оно ложно только если x₁=0,x₂=0 и x₃x₄=0. То есть x₁=1,x₂=1 и (x_3,x₄)≠(1,1). Если же x₁=1,x₂=1, то для выполнения уравнения обязательно должно быть x₃=1,x₄=1. Если хотя бы один из x_1,x₂ равен 0, то x₁lorx₂=1, и уравнение выполнено при любых x_3,x₄.

Эту логику можно применить рекурсивно. Давайте посчитаем количество допустимых переходов между парами переменных.

Обозначим состояние пары (x_2k-1,x_2k). Нас интересует, сколько способов выбрать следующую пару (x_2k+1,x_2k+2) так, чтобы уравнение x_2k-1lorx_2klorx_2k+1x_2k+2=1 выполнялось.

Рассмотрим два случая для текущей пары (u,v):

• Случай А: Пара (u,v) не является (1,1). Тогда ulorv=1. Уравнение истинно автоматически, независимо от следующей пары (w,z). Количество вариантов для следующей пары: 2²=4.
• Случай Б: Пара (u,v) является (1,1). Тогда ulorv=0. Чтобы уравнение стало истинным, необходимо w&z=1, то есть следующая пара должна быть строго (1,1). Количество вариантов для следующей пары: 1.

Теперь применим это к цепочке из 5 пар переменных: P₁=(x_1,x₂),P₂=(x_3,x₄),P₃=(x_5,x₆),P₄=(x_7,x₈),P₅=(x_9,x₁₀).

Начнем с первой пары P₁. Она может быть любой из 4 возможных комбинаций. Разобьем их на группы: - Группа 1: P₁≠(1,1). Таких комбинаций 3 ((0,0),(0,1),(1,0)). - Группа 2: P₁=(1,1). Таких комбинаций 1.

Ветвь 1: Если P₁≠(1,1) (3 варианта выбора), то для P₂ доступно 4 варианта (так как ограничение снимается). Но теперь мы должны смотреть на P₂, чтобы определить ограничения для P₃. Здесь удобнее считать динамически или построить дерево состояний.

Давайте определим количество путей длины N (пар) в графе состояний, где вершины — это пары (0,0),(0,1),(1,0),(1,1). Из любой вершины, кроме (1,1), есть ребра во все 4 вершины следующего уровня. Из вершины (1,1) есть ребро только в вершину (1,1) следующего уровня.

Пусть a_k — количество способов закончить k-ю пару значением (1,1). Пусть b_k — количество способов закончить k-ю пару значением, отличным от (1,1). Всего способов для k-й пары: S_k=a_k+b_k.

Рекуррентные соотношения: Чтобы получить a_k+1 (следующая пара (1,1)): - Можно прийти из любого состояния k-го уровня, если оно было (1,1)? Нет, из (1,1) можно перейти только в (1,1). Вклад: a_k·1. - Можно прийти из состояния k-го уровня, отличного от (1,1)? Да, из таких состояний можно перейти в любую пару, включая (1,1). Вклад: b_k·1 (выбираем конкретно (1,1) из 4 вариантов). Итого: a_k+1=a_k+b_k=S_k. Чтобы получить b_k+1 (следующая пара не (1,1)): - Из состояния (1,1) нельзя перейти в не-(1,1). Вклад: 0. - Из состояния не-(1,1) можно перейти в любые 3 варианта не-(1,1). Вклад: b_k·3. Итого: b_k+1=3b_k.

Начальные условия для k=1 (первая пара x_1,x₂): a₁=1 (пара (1,1)) b₁=3 (пары (0,0),(0,1),(1,0))

Вычислим для k=2: a₂=a₁+b₁=1+3=4 b₂=3b₁=3·3=9 S₂=13

Вычислим для k=3: a₃=a₂+b₂=4+9=13 b₃=3b₂=3·9=27 S₃=40

Вычислим для k=4: a₄=a₃+b₃=13+27=40 b₄=3b₃=3·27=81 S₄=121

Вычислим для k=5 (последняя пара x_9,x₁₀): a₅=a₄+b₄=40+81=121 b₅=3b₄=3·81=243 S₅=121+243=364

Таким образом, общее количество решений системы №2 равно 364.