СДАМ ГИА






Задания
Версия для печати и копирования в MS Word

Сколько су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже условиям?

 

(x1→x2) ∧ (x2→x3) ∧ (x3→x4) ∧ (x4→x5) = 1

(x1→y1) ∧ (x2→y2) ∧ (x3→y3) ∧ (x4→y4) ∧ (x5→y5) = 1

 

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма равенств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких наборов.

Задание 23 № 6967

Пояснение.

Рас­смот­рим пер­вое уравнение. Ло­ги­че­ское «И» истинно, когда ис­тин­ны все высказывания. Для того, чтобы ра­вен­ство выполнялось, необходимо, чтобы каж­дая скоб­ка была истинной. Им­пли­ка­ция ложна толь­ко тогда, когда по­сыл­ка истинна, а след­ствие ложно. Пред­ста­вим ре­ше­ния этого урав­не­ния в виде дерева:

 

 

Рас­смот­рим остав­шиее­ся урав­не­ния для пер­во­го на­бо­ра x1, x2, x3, x4, x5: 11111. Им­пли­ка­ция ложна тогда, когда из ис­тин­ны сле­ду­ет ложь. В дан­ном слу­чае, все x равны 1, сле­до­ва­тель­но все y также долж­ны быть равны 1.

Рас­смот­рим вто­рой набор пе­ре­мен­ных x1, x2, x3, x4, x5: 01111. Заметим, что все y, кроме пер­во­го могут при­ни­мать толь­ко зна­че­ния 1, y1 может быть равен 0 или 1. Таким об­ра­зом вто­ро­му на­бо­ру x со­от­вет­ству­ет 2 · 1 = 2 на­бо­ра y.

Рас­смот­рим тре­тий набор пе­ре­мен­ных x1, x2, x3, x4, x5: 00111. Заметим, что все y, кроме пер­во­го и вто­ро­го могут при­ни­мать толь­ко зна­че­ния 1, y1 и y2 может быть равен 0 или 1. Таким об­ра­зом вто­ро­му на­бо­ру x со­от­вет­ству­ет 2 · 2 · 1 = 4 на­бо­ра y.

Про­ве­дя ана­ло­гич­ные рас­суж­де­ния для на­бо­ров x 00011, 00001, 00000, получаем, со­от­вет­ствен­но 8, 16 и 32 на­бо­ра y.

 

Таким образом, по­лу­ча­ем 1 + 2 + 4 + 8 + 16 +32 = 63 на­бо­ра пе­ре­мен­ных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма равенств.

 

Ответ: 63.


Аналоги к заданию № 6967: 6999



Источник: МИОО: Ди­а­гно­сти­че­ская ра­бо­та по ин­фор­ма­ти­ке 19.03.2014 Ва­ри­ант ИНФ10801.




     О проекте

© Гущин Д. Д., 2011—2017


СПб ГУТ! С! Ф! У!