Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Конспекты / Подготовка к ЕГЭ: Задание 23

Подготовка к ЕГЭ: Задание 23

  • Информатика

Поделитесь материалом с коллегами:

Подготовка к ЕГЭ: Задание 23

1. Условие задачи.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, x10, которые удовлетворяют всем перечисленным ниже условиям?

 ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) =1

((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) =1

((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) =1

((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) =1

 В ответе не нужно перечислять все различные наборы значений x1, x2, ... x9, x10, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

 2. Набросок решения.  

Решение состоит из двух этапов. Сначала попытаемся описать, как устроены все наборы значений переменных, удовлетворяющие данной системе. Далее подсчитаем число таких наборов.

            2.1. Как устроено множество решений

           А. Предварительный этап – упрощаем уравнения.

В системе фигурируют логические функции от следующих выражений:

(x1 ≡ x2),   (x3 ≡ x4),  (x5 ≡ x6),  (x7 ≡ x8),   (x9 ≡ x10)

Подобно тому, как это делается при решении алгебраических уравнений, сделаем замену переменных:

t1 =    x1 ≡ x2

t2 =    x3 ≡ x4

t3 =     x5 ≡ x6

t4 =     x7 ≡ x8

t5 =     x9 ≡ x10

 Общая формула замены (k=1, 2, 3, 4, 5):

tk = (x2k-1 ≡ x2k)

После замены получим:

(t1  \/  t2) /\ (¬t1  \/ ¬ t2 ) =1

(t2  \/  t3) /\ (¬t2  \/ ¬ t3 ) =1

(t3  \/  t4) /\ (¬t3  \/ ¬ t4 ) =1

(t4  \/  t5) /\ (¬t4  \/ ¬ t5 ) =1

Уравнения полученной системы имеют вид (k=1, 2, 3, 4):

(tk  \/  tk+1) /\ (¬tk  \/ ¬ tk+1 ) =1

            Это означает, что из каждых двух переменных tk  и  tk+1 ровно одна равна 1 и ровно одна равна нулю, т.е. эти переменные имеют разные значения. Таким образом, систему можно еще немного упростить и записать ее так:

 ¬(t1  ≡   t2 ) =1

¬(t2  ≡   t3 ) =1

¬(t3  ≡   t4 ) =1

¬(t4  ≡   t5 ) =1

            Б. Анализ системы.

В любом решении последней системы значения переменных чередуются. Поэтому такая система имеет ровно два решения: 01010 и 10101 (первая цифра – значение переменной t1 вторая - значение   tи т.д.).

Далее, вспоминаем, что

tk = x2k-1 ≡ x2k

(здесь k=1, 2, 3, 4, 5).

Поэтому каждому значению tk соответствуют две пары значений переменных  x2k-1 и x2k:

 tk = 1 в двух случаях: { x2k-1 = x2k=1 } и { x2k-1 = x2k=0 },

 tk = 0 в двух случаях: { x2k-1 = 1; x2k=0 } и { x2k-1 = 0; x2k=1 }.

 

             2.2. Подсчет числа решений

Каждому из двух решений системы для переменных соответствует 25 = 32 решения исходной системы. Поэтому исходная система имеет 2∙32 = 64 решения.

Ответ:64

Упражнение. Выпишите все решения. Это немного утомительно, но полезно.

 

 









Выберите курс повышения квалификации со скидкой 50%:

Краткое описание документа:

Подготовка к ЕГЭ: Задание 23

1. Условие задачи.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, x10, которые удовлетворяют всем перечисленным ниже условиям?

 ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) =1

((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) =1

((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) =1

((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) =1

 В ответе не нужно перечислять все различные наборы значений x1, x2, ... x9, x10, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

 2. Набросок решения.  

Решение состоит из двух этапов. Сначала попытаемся описать, как устроены все наборы значений переменных, удовлетворяющие данной системе. Далее подсчитаем число таких наборов.

            2.1. Как устроено множество решений

           А. Предварительный этап – упрощаем уравнения.

В системе фигурируют логические функции от следующих выражений:

(x1 ≡ x2),   (x3 ≡ x4),  (x5 ≡ x6),  (x7 ≡ x8),   (x9 ≡ x10)

Подобно тому, как это делается при решении алгебраических уравнений, сделаем замену переменных:

t1 =    x1 ≡ x2

t2 =    x3 ≡ x4

t3 =     x5 ≡ x6

t4 =     x7 ≡ x8

t5 =     x9 ≡ x10

 Общая формула замены (k=1, 2, 3, 4, 5):

tk = (x2k-1 ≡ x2k)

После замены получим:

(t1  \/  t2) /\ (¬t1  \/ ¬ t2 ) =1

(t2  \/  t3) /\ (¬t2  \/ ¬ t3 ) =1

(t3  \/  t4) /\ (¬t3  \/ ¬ t4 ) =1

(t4  \/  t5) /\ (¬t4  \/ ¬ t5 ) =1

Уравнения полученной системы имеют вид (k=1, 2, 3, 4):

(tk  \/  tk+1) /\ (¬tk  \/ ¬ tk+1 ) =1

            Это означает, что из каждых двух переменных tk  и  tk+1 ровно одна равна 1 и ровно одна равна нулю, т.е. эти переменные имеют разные значения. Таким образом, систему можно еще немного упростить и записать ее так:

 ¬(t1  ≡   t2 ) =1

¬(t2  ≡   t3 ) =1

¬(t3  ≡   t4 ) =1

¬(t4  ≡   t5 ) =1

            Б. Анализ системы.

В любом решении последней системы значения переменных чередуются. Поэтому такая система имеет ровно два решения: 01010 и 10101 (первая цифра – значение переменной t1,  вторая - значение   t2 и т.д.).

Далее, вспоминаем, что

tk = x2k-1 ≡ x2k

(здесь k=1, 2, 3, 4, 5).

Поэтому каждому значению tk соответствуют две пары значений переменных  x2k-1 и x2k:

 tk = 1 в двух случаях: { x2k-1 = x2k=1 } и { x2k-1 = x2k=0 },

 tk = 0 в двух случаях: { x2k-1 = 1; x2k=0 } и { x2k-1 = 0; x2k=1 }.

 

             2.2. Подсчет числа решений

Каждому из двух решений системы для переменных t соответствует 25 = 32 решения исходной системы. Поэтому исходная система имеет 2∙32 = 64 решения.

Ответ:64

Упражнение. Выпишите все решения. Это немного утомительно, но полезно.

 

 

 

 

 

Автор
Дата добавления 11.06.2015
Раздел Информатика
Подраздел Конспекты
Просмотров290
Номер материала 563554
Получить свидетельство о публикации
Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх