На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Rust
  
> ЕГЭ по информатике 2020, часть 1, № 23
    ЕГЭ по информатике 2020, вариант Москва
    Часть 1, № 23
    Математическая логика
    Задание взято с сайта
    http://kotolis.ru/realegeinf_2020

    user posted image

    Вот здесь эта задача решена, только для 5 иксов и 6 игреков.
    https://vk.com/@inform_web-23-zadacha-2020

    В записи местами отсутствуют индексы, но догадаться можно.

    Можно прорешать эту задачу по предложенной схеме. Схема вроде правильная.
    Сообщение отредактировано: swf -
      Решение.
      Упростим выражение, избавившись от импликаций.
      a → b = not(a) V b

      xi & yj → xi & yj+1 = not(xi & yj) V xi & yj+1
      xi & yj → xi+1 & yj = not(xi & yj) V xi+1 & yj+1
      (xi & yj → xi & yj+1) & (xi & yj → xi+1 & yj) =
      (not(xi & yj) V xi & yj+1) & not(xi & yj) V xi+1 & yj+1
      not(xi & yj) V (xi+1 & yj+1)
      not(xi & yj) V (xi+1 & yj+1) = 1 для всех i = 1…5, j = 1…6.
      Или xi & yj = 0, или xi+1 & yj+1 = 1, или и то, и другое.

      Подсчитаем количество наборов для
      xi & yj = 0, i = 1…4, j = 1…5.

      1) Все xi и yj равны 0
      xi =0, yj = 0, i = 1…4, j = 1…5 – означенные переменные.
      x5 и y6 – свободные переменные, могут принимать любые значения 2^2 = 4 способами.
      4 набора.

      2)Все xi равны 0, среди yj есть хотя бы одна 1, i = 1…4, j = 1…5 – означенные переменные.
      У yj, j = 1…5, 2^5 = 32 возможных набора.
      Из них один нулевой набор (все yj = 0), в оставшемся 31 наборе есть хотя бы одна 1.
      x5 и y6 – свободные переменные.
      31 * 4 = 124 набора

      3) Теперь наоборот, все yj равны 0, среди xi есть хотя бы одна 1, i = 1…4, j = 1…5 – означенные переменные.
      У xi, i = 1…4, 2^4 = 16 возможных наборов.
      Из них один нулевой набор (все xi = 0), в оставшихся 15 наборах есть хотя бы одна 1.
      x5 и y6 – свободные переменные.
      15 * 4 = 60 наборов

      И остаётся самый сложный случай.

      4) Среди xi есть хотя бы одна 1 и среди yj есть хотя бы одна 1, i = 1…4, j = 1…5 – означенные переменные.
      В каком-то уравнении эти единицы должны встретиться:
      xi =1, yj = 1, i = 1…4, j = 1…5.
      Тогда xi & yj = 1, поэтому, чтобы выражение всё же имело значение 1,
      xi+1 & yj+1 должно быть равно 1.
      Но, если xi+1 = 1 и yj+1 = 1, то xi+2 = 1 и yj+2 = 1 и так далее.
      Поэтому, если в наборе x1...x5 какое-то xi = 1, то для всех номеров κ > i xk тоже должны быть равны 1.
      Аналогично, если в наборе y1...y6 какой-то yj = 1, то все игреки с большими номерами тоже равны 1.

      Эти наборы (для x1...x5 и y1...y6) удобно представить в виде двух таблиц.

      x1x2x3x4x5
      00001
      00011
      00111
      01111
      11111


      y1y2y3y4y5y6
      000001
      000011
      000111
      001111
      011111
      111111


      Получилось 5 наборов для x1 ... x5.
      Но самый первый набор x1 = x2 = x3 = x4 = 0 и для игреков с хотя бы одной 1, и для всех нулевых игреков уже был подсчитан ранее.

      Аналогично, получается 6 наборов для y1 ... y6.
      Самый первый набор y1 = y2 = y3 = y4 = y5 = 0 и для иксов с хотя бы одной 1, и для всех нулевых иксов уже был подсчитан.

      Остаются 4 набора для x1 ... x5 и 5 наборов для y1 ... y6, которые можно соединять друг с другом всеми способами:
      4 * 5 = 20 наборов
      Итого 4 + 124 +60 + 20 = 208.

      Ответ: 208 .
      Сообщение отредактировано: swf -
      1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
      0 пользователей:


      Рейтинг@Mail.ru
      [ Script execution time: 0,0154 ]   [ 14 queries used ]   [ Generated: 25.07.21, 02:30 GMT ]