СДАМ ГИА






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

Сколько су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x6, y1, y2, … y6, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже условиям?

 

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

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1

(¬x1 ∨ y1) ∧ (¬x2 ∨ y2) ∧ (¬x3 ∨ y3) ∧ (¬ x4 ∨ y4) ∧ (¬x5 ∨ y5) ∧ (¬x6 ∨ y6) = 1

 

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, … x6, y1, y2, … y6, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма равенств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких наборов.

Задание 23 № 11124

Пояснение.

Заметим, что пер­вое и вто­рое урав­не­ния не свя­за­ны между собой ни через какие переменные.

 

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

 

 

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

 

 

Теперь рас­смот­рим тре­тье уравнение. Конъ­юнк­ция ис­тин­на только, если все опе­ран­ды истинны. Каж­дое урав­не­ния вида ¬xN ∨ yN = 1 имеет три решения: 01, 00, 11. То есть для каж­дой пары xN, yN за­пре­ще­ны ре­ше­ния вида 10.

Будем пред­став­лять ре­ше­ния урав­не­ний в виде на­бо­ра нулей и единиц, например, ре­ше­ние x1 = 0, x2 = x3 =x4, = x5= x6 = 1 имеет вид 011 111. Заметим, что для пер­вых двух урав­не­ний в на­бо­рах ре­ше­ний после еди­ни­цы могут сто­ять толь­ко единицы. То есть раз­ре­ше­ны ре­ше­ния вида 001 111.

Также заметим, что если yN = 0, то xN обя­за­тель­но равно единице.

Таким образом, получаем, что на­бо­ру yN 111 111, могут со­от­вет­ство­вать на­бо­ры xN: 111 111, 011 111, 001 111, 000 111, 000 011, 000 001, 000 000. Всего семь наборов.

Аналогично, на­бо­ру yN 011 111 со­от­вет­ству­ет шесть на­бо­ров и так далее. Всего по­лу­ча­ем:

 

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 наборов.

Ответ: 28.



Источник: ЕГЭ по ин­фор­ма­ти­ке 23.03.2016. До­сроч­ная волна




     О проекте

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


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