Задание 23

1. Общие сведения
2. Пример задания
3. Еще один пример
4. Обсуждение
5. Разбор еще трех задач
6. Задачи для самостоятельного решения
7. Задачи с решениями (с сайта ege.yandex.ru и другие)

8. История


1. Общие сведения

Сложность: высокая.

Примерное время решения (для тех, кто будет выполнять часть 2):  5-10 минут

Тема: Основы логики

Подтема: Анализ логических выражений

Что проверяется: Умение анализировать логические выражения. Умение описать на естественном языке множество значений логических переменных, при которых заданный набор логических выражений истинен.

Как может выглядеть задание:

Например, так.

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

2. Пример задания

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

Задача 2012-B15-1.

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

 

((x1x2) \/ (x3x4)) /\ (¬(x1x2) \/ ¬(x3x4)) =1

((x3x4) \/ (x5x6)) /\ (¬(x3x4) \/ ¬(x5x6)) =1

((x5x6) \/ (x7x8)) /\ (¬(x5x6) \/ ¬(x7x8)) =1

((x7x8) \/ (x9x10)) /\ (¬(x7x8) \/ ¬(x9x10)) =1

 

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

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

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

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

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

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

(x1x2),  (x3x4), (x5x6), (x7x8),  (x9x10)

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

t1 =    x1x2

t2 =    x3x4

t3 =     x5 ≡ x6

t4 =     x7 ≡ x8

t5 =     x9x10

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

tk = (x2k-1x2k)

Получим:

(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-1x2k

(здесь k=1, 2, 3, 4, 5), то каждому значению tk соответствуют две пары значений переменных  x2k-1 иx2k. Например, tk = 1 в двух случаях: { x2k-1 = x2k=1 } и { x2k-1 = x2k=0 }.

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

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

Ответ:64

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

3. Пример из открытого сегмента банка заданий ФИПИ

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

Задача 2012-B15-2 (открытый сегмент, зачёт 3:2011)

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

¬(x1 ≡ x2) /\  (x1 \/ x3) /\ (¬x1 \/ ¬x3) =0

¬(x2 ≡ x3) /\  (x2 \/ x4) /\ (¬x2 \/ ¬x4) =0

...

¬(x8 ≡ x9) /\  (x8 \/ x10) /\ (¬x8 \/ ¬x10) =0

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

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

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

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

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

Заметим, что выражение (a \/ b) /\ (¬a \/ ¬b) равносильно тому, что ровно одна из переменных a и b равна 1, то есть равносильно выражению ¬(a ≡ b). Поэтому каждое выражение вида (xk \/ xk+2) /\ (¬xk \/ ¬xk+2), где k=1, …, 8, в наших уравнениях можно заменить выражением   ¬(xk ≡ xk+2).

Таким образом, наша система эквивалентна системе

¬(x1 ≡ x2) /\  ¬(x1 ≡ x3) =0

¬(x2 ≡ x3) /\  ¬(x2 ≡ x4) =0

...

¬(x8 ≡ x9) /\  ¬(x8 ≡ x10) =0

Далее,  ¬a  /\  ¬b = 0 означает, что, если  ¬a   истинно, то ¬b  истинным быть не может. Т.е. ¬a  /\  ¬b = 0 эквивалентно ¬a  b = 1.

Поэтому систему можно записать в следующем виде

¬(x1 ≡ x2 (x1 ≡ x3) =1

¬(x2 ≡ x3 (x2 ≡ x4) =1

...

¬(x8 ≡ x9) (x8 ≡ x10) =1

 

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

Каждое из уравнений полученной системы имеет вид (k = 1, …, 8):

¬(xk ≡ xk+1 (xk ≡ xk+2) =1

            Иными словами, если два соседних элемента набора xk и xk+1 не равны между собой, то xk=xk+2, то есть элементы xk+1 и xk+2 также не равны между собой. Таким образом, набор удовлетворяет системе, тогда и только тогда, когда он обладает следующими свойствами. В начале набора стоит несколько (может быть, одно) одинаковых значений (назовем это"головой" набора). Затем (после первого появления нового числа) значения в наборе чередуются ("хвост" набора).

Пример решения: 1111010101 (в  этой последовательности первая цифра – значение переменной x1, вторая цифра – значение переменной x2, и т.д.)

Здесь голова набора состоит из четырех единиц, а хвост – это последовательность  01010101. в данном примере длина головы равна 4.

            Важное наблюдение. Для каждой непустой головы есть ровно один хвост, образующий вместе с ней решение. Действительно, первая цифра такого хвоста – это цифра, противоположная цифрам головы. А дальше цифры в хвосте чередуются.

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

В соответствии с важным наблюдением, количество решений совпадает с количеством возможных голов. Очевидно, существует 10 голов, состоящих из единиц (1, 11, 111, …, 1111111111) и столько же голов, состоящих из нулей.

Ответ: 20.

Замечание. Как видим, сложность решения задачи не зависит от числа переменных и уравнений. Если понятно, как устроено множество решений, подсчитать количество решений для аналогичной системы, скажем, с 20-ю переменными, не сложнее, чем в уже рассмотренном случае.

4. Обсуждение

4.1. Какие знания/умения/навыки нужны ученику, чтобы решить эту задачу

Эта задача – одна из самых сложных в экзамене, если не самая сложная. Для ее решения ученик должен уметь

- преобразовывать логические выражения (включая выполнение замены переменных);

- переводить формальное описание, в виде системы логических условий, на нормальный, "человеческий" язык и

- подсчитать число двоичных наборов, удовлетворяющих заданным условиям.

После того, как выяснено, что за наборы удовлетворяют системе, подсчет их числа относительно прост.

Наиболее трудным для усвоения, видимо, является второе из перечисленных требований – оно не формализуется, от ученика, как правило, требуется догадка.

4.2 Рекомендации для учителей: как разбирать задачу с учениками

Эти рекомендации – не догма, а попытка сделать выводы из собственного опыта и опыта коллег. Ждем комментариев и Ваших рекомендаций.

Придумывайте свои подходы, применяйте их и сообщайте нам!

4.2.1. Разбирать эту задачу стоит только с учениками, которые достаточно свободно владеют преобразованиями логических выражений. Отметим несколько полезных преобразований (они встречались в разобранных примерах):

¬a \/ b равносильно a b

(a b) /\ (b a) равносильно a ≡ b

(¬a \/ b) /\ (a\/¬b) равносильно a ≡ b

(a \/ b) /\ (¬a \/ ¬b) равносильно ¬(a ≡ b).

Подробнее о преобразованиях логических выражений написано здесь [см. logic01.doc]

Кроме того, полезно потренироваться в выполнении замен в логических выражениях. Отметим, что это делается точно так же, как и замены в уравнениях, которые встречаются в курсе математики.

4.2.2. Самое трудное – сообразить, что из себя представляет множество решений. В разделах 5 и 6 разобрано несколько примеров. Другие полезные примеры и рекомендации можно найти на сайте К.Ю.Полякова.

4.2.3. Подсчет количества решений – несложная комбинаторная задача. Сильные ученики могут сообразить, как провести подсчет, даже не обладая специальными знаниями. Стоит повторить формулы произведения возможностей и формулу суммы арифметической прогрессии.

4.2.4. Таким образом, план подготовки может быть примерно таким.

1) Повторить логические преобразования и элементы комбинаторики.

2) Порешать задачи и попрактиковаться в переводе формального описания, в виде системы логических условий, на нормальный, "человеческий" язык.

4.3. Рекомендации для учеников: как решать подобные задачи

Точного алгоритма действий, гарантированно приводящего к успеху здесь нет. Первая цель – понять, что собой представляет множество решений системы. Для этого систему бывает полезно преобразовать (упростить) систему, используя тождественные преобразования и замены переменных. Затем – подсчитать количество элементов во множестве решений.

Во многих случаях система состоит из однотипных уравнений, каждое из которых связывает небольшое число переменных (две-три-четыре), при том, что в системе может быть 10 и более переменных. Обычно, количество переменных не является источником сложности, оно является параметром решения. Если не получается решить задачу в общем виде, можно попробовать перебрать все решения для системы с небольшим количеством переменных. Это может подсказать, как выглядит решение в общем виде.

5. Другие задачи

Задача 2012-B15-3

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

(x1 x2) /\  (x2 x3) /\ (x3 x4) /\ (x4 x5) = 1

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

Решение. Очевидно, выполнены следующие соотношения:

 (x1 x2) = 1

 (x2 x3) = 1

 (x3 x4) = 1

 (x4 x5) = 1

Допустим, что набор {a1, a2, a3. a4, a5} – решение нашего уравнения. Допустим, что  a4 = 1. Тогда, из уравнения

(x4 x5) = 1

следует, что a5 = 1 (напомним: 1 → 0  ложно!). Допустим теперь, что а3=1. Из условия

(x3 x4) = 1

следует, что a4=1 и, значит, по доказанному, a5 = 1.

Аналогично можно показать (проверьте сами!), что если в решении встречается 1, то далее идут только единицы.

Таким образом, решения уравнения – это наборы, в которых сначала идут нули, а потом – единицы.

!!! Важно не забыть про «особые» наборы – 00000 и 11111. Они тоже годятся.

Таким образом, вот все решения уравнения:

00000, 00001, 00011, 00111, 01111, 11111

Каждое решение полностью описывается количеством единиц в нем. Это количество может быть от 0 до 5. Количество решений – 6.

Задача 2012-B15-4

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

(x1 x2) /\  (x2 x3) /\ (x3 x4) /\ (x4 x5) = 1 (1)

(z1 z2) /\  (z2 z3) /\ (z3 z4)  = 1 (2)

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

Решение. Про такие системы говорят, что переменные в них «разделенные»: x1, …, x5 встречаются только в уравнении (1), а z1, …, z4  - только в уравнении (2). Из решения задачи 3 следует, что уравнению (1) удовлетворяют 6 наборов значений переменных x1, x2, ..., x5, а уравнению (2) – 5 наборов значений переменных z1, …, z4  Каждый из этих наборов для {xi } может образовать решение с любым из наборов для {zi }. Поэтому общее количество решений равно 6∙5 = 30.

Ответ: 30

6. Задачи для самостоятельного решения

Задача 2012-B15-Т1

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

(x1 x2) /\  (x2 x3) /\ … /\ (x499 x500) = 1

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

  Задача 2012-B15- Т2

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

(x2 x1) /\  (x3 x2) /\ … /\ (x1000 x999) = 1

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

Задача 2012-B15- Т3

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

(x1 x3) /\  (x3 x5) /\ … /\ (x9 x11) = 1

(x2 x4) /\  (x4 x6) /\ … /\ (x8 x10) = 1

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

 

Задача 2012-B15- Т4

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

(x1 x3) /\  (x3 x5) /\ … /\ (x99 x101) = 1

(x2 x4) /\  (x4 x6) /\ … /\ (x98 x100) = 1

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

Ответы: Т1. 501; Т2. 1001; Т3. 42; Т4. 2652.


 
 

9 комментариев

  1. Т.С.:

    Опечатка: в Т4 ответ не 2562, а 2652

  2. Светлана:

    Доброго времени суток. В условии примера из демо-версии в третьем уравнении пара второго сомножителя ¬(x5 ≡ x7)верна ли. Если это так, то решение дано не верно.

    • editor:

      Вы, конечно, правы. Спасибо, исправили.
      PS Смотрели задачу недели на главной странице? 🙂

  3. Скорее всего в формуле ошибка:
    (a→ b) /\ (a→ b) равносильно a ≡ b
    Надо:
    (a→ b) /\ (b→ a) равносильно a ≡ b
    Верно?

  4. Ольга Владимировна:

    Нет ли ошибок в ответах? На форуме несколько учителей обсуждыли эти задания. У нас получаются следующие ответы:
    Т1 -501, Т2 - 1001, Т3 - 42, Т4 - 2652.
    Где получить консультацию?

    • ege-go:

      Уважаемая Ольга Владимировна!
      Вы совершенно правы. Это опечатка, приносим свои извинения. Текст исправлен

    • ege-go:

      Уважаемая Ольга Владимировна!
      Да, в файле ошибка. Исправили.
      Спасибо за сообщение!

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика