DVBogdanov.ru / Тренировочный вариант по информатике, задание 23

Задание №1701/23

Задание

Сколько существует различных наборов значений логических переменных \(x_{1},\ldots,x_{10}\), при которых следующие выражения истинны? \[\begin{array}{l} \left(x_{1}\rightarrow x_{2}\right)\land\left(x_{2}\rightarrow x_{1}\right)\wedge\left(x_{3}\rightarrow x_{4}\right),\\ \left(x_{4}\rightarrow x_{3}\right)\wedge\left(x_{5}\rightarrow x_{6}\right)\wedge\left(x_{6}\rightarrow x_{5}\right),\\ \left(x_{7}\rightarrow x_{8}\right)\wedge\left(x_{8}\rightarrow x_{7}\right)\wedge\left(x_{9}\rightarrow x_{10}\right). \end{array}\]

Решение

Формула вида \(\left(x_{i}\rightarrow x_{i+1}\right)\land\left(x_{i+1}\rightarrow x_{i}\right)\) истинна, если истинны обе входящие в неё импликации. Это возможно только при наборах \(x_i=0\), \(x_{i+1}=0\) или \(x_i=1\), \(x_{i+1}=1\), то есть справедливо равенство \[\left(x_{i}\rightarrow x_{i+1}\right)\land\left(x_{i+1}\rightarrow x_{i}\right) = x_i\equiv x_{i+1}.\]

Обозначим через \(t_j = x_{2j-1}\equiv x_{2j}\) для \(j=1,\ldots,4\) и \(t_5=x_{9}\rightarrow x_{10}\), после чего исходная система примет следующий вид: \[t_1 \wedge t_2 \wedge t_3 \wedge t_4 \wedge t_5.\]

Полученная конъюнкция истинна только в случае, если все конъюнкты \(t_1,\ldots,t_5\) также истинны. Каждому истинному значению переменных \(t_1,\ldots,t_4\) соответствуют ровно два набора в соответствующих исходных переменных \(x_1,\ldots,x_8\), а истинному значению переменной \(t_5\) соответствует ровно три набора в исходных переменных \(x_9\) и \(x_{10}\).

Используя комбинаторное правило произведения, получим искомое количество решений исходной системы: \(2\cdot 2\cdot 2\cdot 2\cdot 3 = 2^4 \cdot 3 = 48\).

Подробнее...

Ответ

48

Подробнее...
Добавить комментарий
Комментарии (0)
#Задачи на логику #Логические уравнения #Подготовка к ЕГЭ по информатике #Правило произведения комбинаторики #Правило суммы комбинаторики