Четверг, 02.04.2020, 14:27

Сайт учителя информатики Людмилы Шогеновой

Меню сайта
Категории раздела
Мои статьи [7]
Наш опрос
Оцените мой сайт
Всего ответов: 3
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Вход на сайт
Поиск
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Главная » Статьи » Мои статьи

    Решение систем логических уравнений методом отображения
    МОУ Инженерная школа №6
    Шогенова Л. И.

    РЕШЕНИЕ СИСТЕМ ЛОГИЧЕСКИХ УРАВНЕНИЙ МЕТОД ОТОБРАЖЕНИЯ

    Задание на решение системы логических уравнений остается в ЕГЭ одним из самых сложных. Но решение этой системы не только проверяет знание логических операций и умение считать у наших школьников, но и учит рассуждать, строить логические цепочки. Конечно, оно незаслуженно находится в части B. При оценке ответа нет возможности квалифицировать ошибку, так как ответ, как и логическое высказывание, бывает либо истинным, либо ложным. А поводов дать неверный в этом случае ответ много: можно написать наугад, а можно решить все от начала до конца, проделать все логические преобразования, выстроить верную цепочку рассуждений и в последнем действии допустить арифметическую ошибку.»
    Практическая часть

    Задание 1. (23.208) Сколько различных решений имеет система логических уравнений
    x1  x2  y1  y2  x1  y1 = 0
    x2  x3  y2  y3  x2  y2 = 0
    ...
    x5  x6  y5  y6  x5  y5 = 0
    x6  x7  y6  y7  x6  y6 = 0
    x7  y7 = 0
    где x1,x2,…,x7 и y1,y2,…,y7 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение: Можем заметить, что все кроме последнего уравнения являются однотипными. Поэтому пока будем рассматривать систему без последнего уравнения.
    Построим таблицу истинности для первого уравнения.

    х1 у1 х2 у2 x1  x2 y1  y2 x1  y1 x1  x2  y1  y2  x1  y1
    0 0 0 0 0 0 1 1
    0 0 0 1 0 0 1 1
    0 0 1 0 1 0 1 1
    0 0 1 1 1 0 1 1
    0 1 0 0 0 1 0 1
    0 1 0 1 0 0 0 0
    0 1 1 0 1 1 0 1
    0 1 1 1 1 0 0 1
    1 0 0 0 0 0 0 0
    1 0 0 1 0 0 0 0
    1 0 1 0 0 0 0 0
    1 0 1 1 0 0 0 0
    1 1 0 0 0 1 0 1
    1 1 0 1 0 0 0 0
    1 1 1 0 0 1 0 1
    1 1 1 1 0 0 0 0
    Так как значение уравнение = 0, то вычеркиваем те строки, в которых результатом получилась истина (1).
    После преобразования получается следующая таблица:
    х1 у1 х2 у2 x1  x2 y1  y2 x1  y1 x1  x2  y1  y2  x1  y1
    0 1 0 1 0 0 0 0
    1 0 0 0 0 0 0 0
    1 0 0 1 0 0 0 0
    1 0 1 0 0 0 0 0
    1 0 1 1 0 0 0 0
    1 1 0 1 0 0 0 0
    1 1 1 1 0 0 0 0
    Строим непосредственно само отображение пары х1у1 в пару х2у2.
    х1у1 х2у2
    00
    00 = 10
    01
    01 =01+10+11
    10
    10 =10
    11
    11 =10+11

    Все пары х1у1 =00 были исключены в первой таблице истинности, поэтому столбце х1у1 количество таких пар как 00 равно 0:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7
    00 0 1 1 1 1 1 1
    01 1 3 6 10 15 21 28
    10 1 1 1 1 1 1 1
    11 1 2 3 4 5 6 7
    Если бы в системе не было последнего уравнения x7  y7 = 0, то такая система имела бы 37 решений (1+28+1+7). Но вернемся к последнему уравнению системыx7  y7 = 0. Данное равенство НЕ выполняется, если х1=0 и у1 = 0. Следовательно, исключаем количество решений для пары 00, то есть количество решений в первой строке. Тем самым, получаем 37-1=36 решений.
    Ответ: 36 решений.
    Задание 2. (23.207) Сколько различных решений имеет система логических уравнений
    ((x1  y1)  (x2  y2))  (x1  x2) = 1
    ((x2  y2)  (x3  y3))  (x2  x3) = 1
    ...
    ((x7  y7)  (x8  y8))  (x7  x8) = 1
    (x8  y8) = 1
    где x1,x2,…,x8 и y1,y2,…,y8 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

    Решение: Аналогично предыдущей системе рассмотрим первое уравнение ((x1  y1)  (x2  y2))  (x1  x2) = 1 и построим таблицу истинности:

    x1 y1 x2 y2 x1  y1 x2  y2 ((x1  y1)  (x2  y2)) x1  x2 ((x1  y1)  (x2  y2))  (x1  x2)
    0 0 0 0 1 1 1 0 0
    0 0 0 1 1 0 0 0 0
    0 0 1 0 1 0 0 1 0
    0 0 1 1 1 1 1 1 1
    0 1 0 0 0 1 1 0 0
    0 1 0 1 0 0 1 0 0
    0 1 1 0 0 0 1 1 1
    0 1 1 1 0 1 1 1 1
    1 0 0 0 0 1 1 1 1
    1 0 0 1 0 0 1 1 1
    1 0 1 0 0 0 1 1 1
    1 0 1 1 0 1 1 1 1
    1 1 0 0 1 1 1 1 1
    1 1 0 1 1 0 0 1 0
    1 1 1 0 1 0 0 1 0
    1 1 1 1 1 1 1 1 1

    Так как значение уравнение = 1, то вычеркиваем те строки, в которых результатом получилась ложь (0).
    После преобразования получается следующая таблица:

    x1 y1 x2 y2 x1  y1 x2  y2 ((x1  y1)  (x2  y2)) x1  x2 ((x1  y1)  (x2  y2))  (x1  x2)
    0 0 1 1 1 1 1 1 1
    0 1 1 0 0 0 1 1 1
    0 1 1 1 0 1 1 1 1
    1 0 0 0 0 1 1 1 1
    1 0 0 1 0 0 1 1 1
    1 0 1 0 0 0 1 1 1
    1 0 1 1 0 1 1 1 1
    1 1 0 0 1 1 1 1 1
    1 1 1 1 1 1 1 1 1
    Строим непосредственно само отображение пары х1у1 в пару х2у2.
    х1у1 х2у2
    00
    00 = 10+11
    01
    01 =10
    10
    10 =01+10
    11 11 =00+01+10+11
    Строим таблицу количества решений:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7 х8у8
    00 1 2 6 12 25 48 91 168
    01 1 1 2 3 5 8 13 21
    10 1 2 3 5 8 13 21 34
    11 1 4 9 20 40 78 147 272

    Если бы в системе не было последнего уравнения (x8  y8) = 1, то такая система имела бы 495 решений. Но вернемся к последнему уравнению системы (x8  y8) = 1. Данное равенство НЕ выполняется, если х1=0 и у1 = 0. Следовательно, исключаем количество решений для пары 00, то есть количество решений в первой строке. Тем самым, получаем 495-168=327 решений.
    Ответ: 327 решений.
    Задание 3 (23.180) Сколько различных решений имеет система логических уравнений
    (x1  x2)  (x3  x4) = 1
    (x3  x4)  (x5  x6) = 1
    (x5  x6)  (x7  x8) = 1
    (x7  x8)  (x9  x10) = 1
    x1  x3  x5  x7  x9 = 1
    где x1, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

    Решение: Рассмотрим первое уравнение (x1  x2)  (x3  x4) = 1
    Строим таблицу истинности для переменных х1, х2, х3, х4:
    x1 х2 х3 х4 (x1  x2) (x3  x4) (x1  x2)  (x3  x4)
    0 0 0 0 1 1 1
    0 0 0 1 1 1 1
    0 0 1 0 1 0 0
    0 0 1 1 1 1 1
    0 1 0 0 1 1 1
    0 1 0 1 1 1 1
    0 1 1 0 1 0 0
    0 1 1 1 1 1 1
    1 0 0 0 0 1 1
    1 0 0 1 0 1 1
    1 0 1 0 0 0 1
    1 0 1 1 0 1 1
    1 1 0 0 1 1 1
    1 1 0 1 1 1 1
    1 1 1 0 1 0 0
    1 1 1 1 1 1 1
    Вычеркнем строки, в которых результатом получился ноль. Получим следующую таблицу истинности:

    x1 х2 х3 х4 (x1  x2) (x3  x4) (x1  x2)  (x3  x4)
    0 0 0 0 1 1 1
    0 0 0 1 1 1 1
    0 0 1 1 1 1 1
    0 1 0 0 1 1 1
    0 1 0 1 1 1 1
    0 1 1 1 1 1 1
    1 0 0 0 0 1 1
    1 0 0 1 0 1 1
    1 0 1 0 0 0 1
    1 0 1 1 0 1 1
    1 1 0 0 1 1 1
    1 1 0 1 1 1 1
    1 1 1 1 1 1 1
    Получим следующую зависимость:

    х2у2 х1у1
    00 =00+01+10+11
    01 =00+01+10+11
    10 =10
    11 =00+01+10+11

    Строим таблицу количества решений для каждой пары:

    х1х2 х3х4 х5х6 х7х8 х9х10
    00 1 4 13 40 121
    01 1 4 13 40 121
    10 1 1 1 1 1
    11 1 4 13 40 121

    Последнее уравнение x1  x3  x5  x7  x9 = 1 влияет на количество решений всей системы, следовательно, х1=1, х3=1, х5=1, х7=1, х9=1.
    Следовательно, меняется полностью вся таблица

    х1х2 х3х4 х5х6 х7х8 х9х10
    00 0 0 0 0 0
    01 0 0 0 0 0
    10 1 1 1 1 1
    11 1 2 3 4 5
    Получается, 6 решений системы.
    Ответ: 6 решений.

    Задание 4. (23.173) Сколько различных решений имеет система логических уравнений
    (x1  (x2  y1))  (y1  y2) = 1
    (x2  (x3  y2))  (y2  y3) = 1
    ...
    (x8  (x9  y8))  (y8  y9) = 1
    x9  y9 = 1
    где x1,x2,…,x9 и y1,y2,…,y9, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    Рассмотрим первое уравнение
    (x1  (x2  y1))  (y1  y2) = 1
    Строим таблицу истинности для переменных х1, у1,х2,у2:

    x1 у1 х2 у2 x2  y1 x1  (x2  y1) y1  y2 (x1  (x2  y1))  (y1  y2)
    0 0 0 0 0 1 1 1
    0 0 0 1 0 1 1 1
    0 0 1 0 1 1 1 1
    0 0 1 1 1 1 1 1
    0 1 0 0 1 1 0 0
    0 1 0 1 1 1 1 1
    0 1 1 0 1 1 0 0
    0 1 1 1 1 1 1 1
    1 0 0 0 0 0 1 0
    1 0 0 1 0 0 1 0
    1 0 1 0 1 1 1 1
    1 0 1 1 1 1 1 1
    1 1 0 0 1 1 0 0
    1 1 0 1 1 1 1 1
    1 1 1 0 1 1 0 0
    1 1 1 1 1 1 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнение равно 1.
    x1 у1 х2 у2 x2  y1 x1  (x2  y1) y1  y2 (x1  (x2  y1))  (y1  y2)
    0 0 0 0 0 1 1 1
    0 0 0 1 0 1 1 1
    0 0 1 0 1 1 1 1
    0 0 1 1 1 1 1 1
    0 1 0 1 1 1 1 1
    0 1 1 1 1 1 1 1
    1 0 1 0 1 1 1 1
    1 0 1 1 1 1 1 1
    1 1 0 1 1 1 1 1
    1 1 1 1 1 1 1 1

    Получим следующую зависимость:

    х2у2 х1у1
    00 =00
    01 =00+01+11
    10 =00+10
    11 =00+01+10+11
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7 х8у8 х9у9
    00 1 1 1 1 1 1 1 1 1
    01 1 3 8 19 42 89 184 375 758
    10 1 2 3 4 5 6 7 8 9
    11 1 4 10 22 46 94 190 382 766

    Всего решений 1534 =1+758+9+766, но в системе присутствует последнее уравнение x9  y9 = 1 , которое исключает 9 решений. Так как при x9  y9 = 1 исключается пара х9у9=10. Таким образом, исходная система имеет 1525 решения.
    Ответ: 1525 решений.
    Задание 5 (23.118). Сколько различных решений имеет система логических уравнений
    (x1  y1)  ((x1  y1) (x2  y2)) = 1
    (x2  y2)  ((x2  y2) (x3  y3)) = 1
    (x3  y3)  ((x3  y3) (x4  y4)) = 1
    (x4  y4)  ((x4  y4) (x5  y5)) = 1
    (x5  y5)  ((x5  y5) (x6  y6)) = 1
    (x6  y6)  ((x6  y6) (x7  y7)) = 1
    (x7  y7)  ((x7  y7) (x8  y8)) = 1
    x8  y8 = 1
    где x1, …, x8, y1, …, y8, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

    Решение: В данной системе все уравнения, кроме последнего, однотипны. Поэтому можно применить метод отображения.
    Рассмотрим первое уравнение (x1  y1)  ((x1  y1) (x2  y2)) = 1 и построим таблицу истинности для левой части данного логического уравнения
    x1 у1 х2 у2 x1  y1 x1  y1 x2  y2 (x1  y1) (x2  y2) x1  y1)  ((x1  y1) (x2  y2))
    0 0 0 0 0 1 1 1 0
    0 0 0 1 0 1 1 1 0
    0 0 1 0 0 1 1 1 0
    0 0 1 1 0 1 0 0 0
    0 1 0 0 1 1 1 1 1
    0 1 0 1 1 1 1 1 1
    0 1 1 0 1 1 1 1 1
    0 1 1 1 1 1 0 0 0
    1 0 0 0 1 1 1 1 1
    1 0 0 1 1 1 1 1 1
    1 0 1 0 1 1 1 1 1
    1 0 1 1 1 1 0 0 0
    1 1 0 0 1 0 1 1 1
    1 1 0 1 1 0 1 1 1
    1 1 1 0 1 0 1 1 1
    1 1 1 1 1 0 0 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнение равно 1.

    x1 у1 х2 у2 x1  y1 x1  y1 x2  y2 (x1  y1) (x2  y2) x1  y1)  ((x1  y1) (x2  y2))
    0 1 0 0 1 1 1 1 1
    0 1 0 1 1 1 1 1 1
    0 1 1 0 1 1 1 1 1
    1 0 0 0 1 1 1 1 1
    1 0 0 1 1 1 1 1 1
    1 0 1 0 1 1 1 1 1
    1 1 0 0 1 0 1 1 1
    1 1 0 1 1 0 1 1 1
    1 1 1 0 1 0 1 1 1
    1 1 1 1 1 0 0 1 1

    Получим следующую зависимость:

    х2у2 х1у1
    00 =01+10+11
    01 =01+10+11
    10 =01+10+11
    11 =11
    Обратим внимание на то, что пары х1у1=00 нет в наборе, поэтому в первой строке и первом столбце значение будет равно 0.
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7 х8у8
    00 0 3 7 15 31 63 127 255
    01 1 3 7 15 31 63 127 255
    10 1 3 7 15 31 63 127 255
    11 1 1 1 1 1 1 1 1
    Всего решений 766=255*3+1, но в системе присутствует последнее уравнение x8  y8 = 1, которое исключает 255 решений. Так как при x8  y8 = 1 исключается пара х8у8=00. Таким образом, исходная система имеет 511 решения.
    Ответ: 511 решений.

    Задание 6 (23.117).Сколько различных решений имеет система логических уравнений
    (x1  y1)  ((x1  y1) (x2  y2)) = 1
    (x2  y2)  ((x2  y2) (x3  y3)) = 1
    (x3  y3)  ((x3  y3) (x4  y4)) = 1
    (x4  y4)  ((x4  y4) (x5  y5)) = 1
    (x5  y5)  ((x5  y5) (x6  y6)) = 1
    (x6  y6)  ((x6  y6) (x7  y7)) = 1
    x7  y7 = 1
    где x1, …, x7, y1, …, y7, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    Эта система совершенно такая же, как предыдущая, но количество переменных в ней не 8, а семь, поэтому решение будет идентичным. В данной системе все уравнения, кроме последнего, однотипны. Поэтому можно применить метод отображения.
    Рассмотрим первое уравнение (x1  y1)  ((x1  y1) (x2  y2)) = 1 и построим таблицу истинности для левой части данного логического уравнения
    x1 у1 х2 у2 x1  y1 x1  y1 x2  y2 (x1  y1) (x2  y2) x1  y1)  ((x1  y1) (x2  y2))
    0 0 0 0 0 1 1 1 0
    0 0 0 1 0 1 1 1 0
    0 0 1 0 0 1 1 1 0
    0 0 1 1 0 1 0 0 0
    0 1 0 0 1 1 1 1 1
    0 1 0 1 1 1 1 1 1
    0 1 1 0 1 1 1 1 1
    0 1 1 1 1 1 0 0 0
    1 0 0 0 1 1 1 1 1
    1 0 0 1 1 1 1 1 1
    1 0 1 0 1 1 1 1 1
    1 0 1 1 1 1 0 0 0
    1 1 0 0 1 0 1 1 1
    1 1 0 1 1 0 1 1 1
    1 1 1 0 1 0 1 1 1
    1 1 1 1 1 0 0 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.

    x1 у1 х2 у2 x1  y1 x1  y1 x2  y2 (x1  y1) (x2  y2) x1  y1)  ((x1  y1) (x2  y2))
    0 1 0 0 1 1 1 1 1
    0 1 0 1 1 1 1 1 1
    0 1 1 0 1 1 1 1 1
    1 0 0 0 1 1 1 1 1
    1 0 0 1 1 1 1 1 1
    1 0 1 0 1 1 1 1 1
    1 1 0 0 1 0 1 1 1
    1 1 0 1 1 0 1 1 1
    1 1 1 0 1 0 1 1 1
    1 1 1 1 1 0 0 1 1

    Получим следующую зависимость:

    х2у2 х1у1
    00 =01+10+11
    01 =01+10+11
    10 =01+10+11
    11 =11
    Обратим внимание на то, что пары х1у1=00 нет в наборе, поэтому в первой строке и первом столбце значение будет равно 0.
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7
    00 0 3 7 15 31 63 127
    01 1 3 7 15 31 63 127
    10 1 3 7 15 31 63 127
    11 1 1 1 1 1 1 1
    Всего решений 382=127*3+1, но в системе присутствует последнее уравнение x7  y7 = 1, которое исключает 127 решений. Так как при x7  y7 = 1 исключается пара х7у7=00. Таким образом, исходная система имеет 255 решений.
    Ответ: 255 решений.

    Задание 7 (23.53).Сколько различных решений имеет система уравнений
    (X1  X2)  (¬X1  ¬X2)  (X1  X3) = 1
    (X2  X3)  (¬X2  ¬X3)  (X2  X4) = 1
    ...
    (X7  X8)  (¬X7  ¬X8)  (X7  X9) = 1
    (X8  X9)  (¬X8  ¬X9)  (X8  X10) = 0
    где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

    Решение:
    Эта система интересна тем, что все уравнения однотипны по структуре, но последнее уравнение имеет значение не 1, как все предыдущие, а 0. В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение ((X1  X2)  (¬X1  ¬X2)  (X1  X3) = 1 и построим таблицу истинности для левой части данного логического уравнения
    x1 х2 х3 (¬X1  ¬X2 X1  X3 X1  X2 (X1  X2)  (¬X1  ¬X2)  (X1  X3)
    0 0 0 1 1 0 1
    0 0 1 1 0 0 1
    0 1 0 0 1 0 1
    0 1 1 0 0 0 0
    1 0 0 0 0 0 0
    1 0 1 0 1 0 1
    1 1 0 0 0 1 1
    1 1 1 0 1 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.

    x1 х2 х3 (¬X1  ¬X2 X1  X3 X1  X2 (X1  X2)  (¬X1  ¬X2)  (X1  X3)
    0 0 0 1 1 0 1
    0 0 1 1 0 0 1
    0 1 0 0 1 0 1
    1 0 1 0 1 0 1
    1 1 0 0 0 1 1
    1 1 1 0 1 1 1

    Получим следующую зависимость:

    х2х3 х1х2
    00 =00
    01 =00+10
    10 =01+11
    11 =11
    Строим таблицу количества решений для каждой пары, кроме х9х10. Для них зависимость будет другая, так как значение последнего уравнения равно 0:

    х1х2 х2х3 х3х4 х4х5 х5х6 х6х7 х7х8 х8х9
    00 1 1 1 1 1 1 1 1
    01 1 2 3 4 5 6 7 8
    10 1 2 3 4 5 6 7 8
    11 1 1 1 1 1 1 1 1

    Так как последнее уравнение имеет значение 0, то из первой таблицы истинности нужно вычеркнуть строки с конечным значением 1(«истина»).

    x1 х2 х3 (¬X1  ¬X2 X1  X3 X1  X2 (X1  X2)  (¬X1  ¬X2)  (X1  X3)
    0 1 1 0 0 0 0
    1 0 0 0 0 0 0

    Последнее уравнение устанавливает следующую зависимость:

    х2х3 х1х2
    00 =10
    01 -
    10 -
    11 =01

    Тогда получим такой последний столбец таблицы количества решений:

    х1х2 х2х3 х3х4 х4х5 х5х6 х6х7 х7х8 х8х9 х9х10
    00 1 1 1 1 1 1 1 1
    8
    01 1 2 3 4 5 6 7 8
    0
    10 1 2 3 4 5 6 7 8 0
    11 1 1 1 1 1 1 1 1 8

    Суммируем последний столбец и получаем 16 решений.
    Ответ: 16 решений.
    Задание 8 (23.56).Сколько различных решений имеет система уравнений
    ((X1  X2)  (X3  X4))  (¬(X1  X2)  ¬(X3  X4)) = 1
    ((X3  X4)  (X5  X6))  (¬(X3  X4)  ¬(X5  X6)) = 1
    ((X5  X6)  (X7  X8))  (¬(X5  X6)  ¬(X7  X8)) = 1
    ((X7  X8)  (X9  X10))  (¬(X7  X8)  ¬(X9  X10)) = 1
    ((X9  X10)  (X11  X12))  (¬(X9  X10)  ¬(X11  X12)) = 1
    где x1, x2, …, x12 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение ((X1  X2)  (X3  X4))  (¬(X1  X2)  ¬(X3  X4)) = 1 и построим таблицу истинности для левой части данного логического уравнения


    x1 х2 х3 х4 x1  x2 x3  x4 ((x1  x2)  (x3  x4)) ¬(x1  x2) ¬(x3  x4) (¬(x1  x2)  ¬(x3  x4)) ((x1  x2)  (x3  x4))  (¬(x1  x2)  ¬(x3  x4))
    0 0 0 0 1 1 1 0 0 0 0
    0 0 0 1 1 0 1 0 1 1 1
    0 0 1 0 1 0 1 0 1 1 1
    0 0 1 1 1 1 1 0 0 0 0
    0 1 0 0 0 1 1 1 0 1 1
    0 1 0 1 0 0 0 1 1 1 0
    0 1 1 0 0 0 0 1 1 1 0
    0 1 1 1 0 1 1 1 0 1 1
    1 0 0 0 0 1 1 1 0 1 1
    1 0 0 1 0 0 0 1 1 1 0
    1 0 1 0 0 0 0 1 1 1 0
    1 0 1 1 0 1 1 1 0 1 1
    1 1 0 0 1 1 1 0 0 0 0
    1 1 0 1 1 0 1 0 1 1 1
    1 1 1 0 1 0 1 0 1 1 1
    1 1 1 1 1 1 1 0 0 0 0

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.

    x1 х2 х3 х4 x1  x2 x3  x4 ((x1  x2)  (x3  x4)) ¬(x1  x2) ¬(x3  x4) (¬(x1  x2)  ¬(x3  x4)) ((x1  x2)  (x3  x4))  (¬(x1  x2)  ¬(x3  x4))
    0 0 0 1 1 0 1 0 1 1 1
    0 0 1 0 1 0 1 0 1 1 1
    0 1 0 0 0 1 1 1 0 1 1
    0 1 1 1 0 1 1 1 0 1 1
    1 0 0 0 0 1 1 1 0 1 1
    1 0 1 1 0 1 1 1 0 1 1
    1 1 0 1 1 0 1 0 1 1 1
    1 1 1 0 1 0 1 0 1 1 1

    Получим следующую зависимость:

    х3х4 х1х2
    00 =01+10
    01 =00+11
    10 =01+11
    11 =01+10
    Строим таблицу количества решений для каждой пары:

    х1х2 х3х4 х5х6 х7х8 Х9х10 Х11х12
    00 1 2 4 8 16 32
    01 1 2 4 8 16 32
    10 1 2 4 8 16 32
    11 1 2 4 8 16 32

    Суммируем последний столбец и получаем 128 решений.
    Ответ: 128 решений.

    Задание 9 (23.64).Сколько различных решений имеет система уравнений
    x1  x2  x3  x4 = 1
    x3  x4  x5  x6 = 1
    x5  x6  x7  x8 = 1
    x7  x8  x9  x10 = 1
    где x1,x2,…,x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение x1  x2  x3  x4 = 1 и построим таблицу истинности для левой части данного логического уравнения

    x1 х2 х3 х4 x3  x4 x2  x3  x4 x1  x2  x3  x4
    0 0 0 0 0 1 1
    0 0 0 1 1 1 1
    0 0 1 0 0 1 1
    0 0 1 1 0 1 1
    0 1 0 0 0 0 0
    0 1 0 1 1 1 1
    0 1 1 0 0 0 0
    0 1 1 1 0 0 0
    1 0 0 0 0 1 1
    1 0 0 1 1 1 1
    1 0 1 0 0 1 1
    1 0 1 1 0 1 1
    1 1 0 0 0 0 1
    1 1 0 1 1 1 1
    1 1 1 0 0 0 1
    1 1 1 1 0 0 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.

    x1 х2 х3 х4 x3  x4 x2  x3  x4 x1  x2  x3  x4
    0 0 0 0 0 1 1
    0 0 0 1 1 1 1
    0 0 1 0 0 1 1
    0 0 1 1 0 1 1
    0 1 0 1 1 1 1
    1 0 0 0 0 1 1
    1 0 0 1 1 1 1
    1 0 1 0 0 1 1
    1 0 1 1 0 1 1
    1 1 0 0 0 0 1
    1 1 0 1 1 1 1
    1 1 1 0 0 0 1
    1 1 1 1 0 0 1

    Получим следующую зависимость:

    х3х4 х1х2
    00 =00+10+11
    01 =00+01+10+11
    10 =00+10+11
    11 =00+10+11
    Строим таблицу количества решений для каждой пары:

    х1х2 х3х4 х5х6 х7х8 х9х10
    00 1 3 9 27 81
    01 1 4 13 40 121
    10 1 3 9 27 81
    11 1 3 9 27 81

    Суммируем последний столбец и получаем 364 решения.
    Ответ: 364 решения.

    Задание 10 (23.140).Сколько различных решений имеет система уравнений
    (x1  y1)  (x2  y2)
    (x2  y2)  (x3  y3)
    ...
    (x5  y5)  (x6  y6)
    (x6  y6)  (x7  y7)
    где x1, …, x7, y1, …, y7, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение (x1  y1)  (x2  y2) и построим таблицу истинности для левой части данного логического уравнения

    x1 y1 x2 y2 x1  y1 x2  y2 (x1  y1)  (x2  y2)
    0 0 0 0 0 1 0
    0 0 0 1 0 0 1
    0 0 1 0 0 0 1
    0 0 1 1 0 0 1
    0 1 0 0 1 1 1
    0 1 0 1 1 0 0
    0 1 1 0 1 0 0
    0 1 1 1 1 0 0
    1 0 0 0 1 1 1
    1 0 0 1 1 0 0
    1 0 1 0 1 0 0
    1 0 1 1 1 0 0
    1 1 0 0 1 1 1
    1 1 0 1 1 0 0
    1 1 1 0 1 0 0
    1 1 1 1 1 0 0

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.
    x1 y1 x2 y2 x1  y1 x2  y2 (x1  y1)  (x2  y2)
    0 0 0 1 0 0 1
    0 0 1 0 0 0 1
    0 0 1 1 0 0 1
    0 1 0 0 1 1 1
    1 0 0 0 1 1 1
    1 1 0 0 1 1 1

    Получим следующую зависимость:

    х2у2 х1у1
    00 =01+10+11
    01 =00
    10 =00
    11 =00
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7
    00 1 3 3 9 9 27 27
    01 1 1 3 3 9 9 27
    10 1 1 3 3 9 9 27
    11 1 1 3 3 9 9 27

    Суммируем последний столбец и получаем 108 решений.
    Ответ: 108 решений.

    Задание 11 (23.155). Сколько различных решений имеет система уравнений?
    ((x1y1)(x2y2))  (x1x2)  (y1y2) =1
    ((x2y2)(x3y3))  (x2x3)  (y2y3) =1

    ((x8y8)(x9y9))  (x8x9)  (y8y9) =1
    где x1,x2,…,x9, у1,у2,…,у9 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение ((x1y1)(x2y2))  (x1x2)  (y1y2) =1 и построим таблицу истинности для левой части данного логического уравнения
    x1 y1 x2 y2 x1y1 x2y2 (x1y1)(x2y2) x1x2 y1y2 ((x1y1)(x2y2))  (x1x2)  (y1y2)
    0 0 0 0 1 1 1 1 1 1
    0 0 0 1 1 0 0 1 1 0
    0 0 1 0 1 0 0 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 1 0 0 0 1 1 1 0 0
    0 1 0 1 0 0 1 1 1 1
    0 1 1 0 0 0 1 1 0 0
    0 1 1 1 0 1 1 1 1 1
    1 0 0 0 0 1 1 0 1 0
    1 0 0 1 0 0 1 0 1 0
    1 0 1 0 0 0 1 1 1 1
    1 0 1 1 0 1 1 1 1 1
    1 1 0 0 1 1 1 0 0 0
    1 1 0 1 1 0 0 0 1 0
    1 1 1 0 1 0 0 1 0 0
    1 1 1 1 1 1 1 1 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.
    x1 y1 x2 y2 x1y1 x2y2 (x1y1)(x2y2) x1x2 y1y2 ((x1y1)(x2y2))  (x1x2)  (y1y2)
    0 0 0 0 1 1 1 1 1 1
    0 0 1 1 1 1 1 1 1 1
    0 1 0 1 0 0 1 1 1 1
    0 1 1 1 0 1 1 1 1 1
    1 0 1 0 0 0 1 1 1 1
    1 0 1 1 0 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1

    Получим следующую зависимость:

    х2у2 х1у1
    00 =00
    01 =01
    10 =10
    11 =00+01+10+11
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7 х8у8 х9у9
    00 1 1 1 1 1 1 1 1 1
    01 1 1 1 1 1 1 1 1 1
    10 1 1 1 1 1 1 1 1 1
    11 1 4 7 10 13 16 19 22 25

    Суммируем последний столбец и получаем 28 решений.
    Ответ: 28 решений.

    Задание 12 (23.157). Сколько различных решений имеет система уравнений?
    (x1  x2)  (x2  x3) = 0
    (x2  x3)  (x3  x4) = 0
    ...
    (x7  x8)  (x8  x9) = 0
    где x1,x2,…,x9 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение (x1  x2)  (x2  x3) = 0 и построим таблицу истинности для левой части данного логического уравнения

    x1 x2 x3 x1  x2 x2  x3 (x1  x2)  (x2  x3)
    0 0 0 0 0 0
    0 0 1 0 1 0
    0 1 0 1 1 1
    0 1 1 1 0 0
    1 0 0 1 0 0
    1 0 1 1 1 1
    1 1 0 0 1 0
    1 1 1 0 0 0

    Вычеркнем строки с единичными значениями, так как значение уравнения равно 0.
    x1 x2 x3 x1  x2 x2  x3 (x1  x2)  (x2  x3)
    0 0 0 0 0 0
    0 0 1 0 1 0
    0 1 1 1 0 0
    1 0 0 1 0 0
    1 1 0 0 1 0
    1 1 1 0 0 0

    Получим следующую зависимость:
    х2х3 х1х2
    00 =00+10
    01 =00
    10 =11
    11 =01+11
    Строим таблицу количества решений для каждой пары:

    х1х2 х2х3 х3х4 х4х5 х5х6 х6х7 х7х8 х8х9
    00 1 2 3 5 8 13 21 34
    01 1 1 2 3 5 8 13 21
    10 1 1 2 3 5 8 13 21
    11 1 2 3 5 8 13 21 34

    Суммируем последний столбец и получаем 110 решений.
    Ответ: 110 решений.

    Задание 13 (23.158). Сколько различных решений имеет система уравнений?
    (x1  x2)  (x1  x3) = 0
    (x2  x3)  (x2  x4) = 0
    ...
    (x7  x8)  (x7  x9) = 0
    где x1,x2,…,x9 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение (x1  x2)  (x1  x3) = 0 и построим таблицу истинности для левой части данного логического уравнения

    x1 x2 x3 x1  x2 x1  x3 (x1  x2)  (x1  x3)
    0 0 0 0 0 0
    0 0 1 0 1 0
    0 1 0 1 0 0
    0 1 1 1 1 1
    1 0 0 1 1 1
    1 0 1 1 0 0
    1 1 0 0 1 0
    1 1 1 0 0 0

    Вычеркнем строки с единичными значениями, так как значение уравнения равно 0.

    x1 x2 x3 x1  x2 x1  x3 (x1  x2)  (x1  x3)
    0 0 0 0 0 0
    0 0 1 0 1 0
    0 1 0 1 0 0
    1 0 1 1 0 0
    1 1 0 0 1 0
    1 1 1 0 0 0

    Получим следующую зависимость:

    х2х3 х1х2
    00 =00
    01 =00+10
    10 =01+11
    11 =11
    Строим таблицу количества решений для каждой пары:

    х1х2 х2х3 х3х4 х4х5 х5х6 х6х7 х7х8 х8х9
    00 1 1 1 1 1 1 1 1
    01 1 2 3 4 5 6 7 8
    10 1 2 3 4 5 6 7 8
    11 1 1 1 1 1 1 1 1

    Суммируем последний столбец и получаем 18 решений.
    Ответ: 18 решений.

    Задание 14 (23.159). Сколько различных решений имеет система уравнений?
    (x1  (x2  y2))  (y1  y2) = 1
    (x2  (x3  y3))  (y2  y3) = 1
    ...
    (x6  (x7  y7))  (y6  y7) = 1
    где x1,x2,…,x7 и y1,y2,…,y7, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    В данной системе все уравнения однотипны, поэтому можно применить метод отображения.
    Рассмотрим первое уравнение (x1  (x2  y2))  (y1  y2) = 1 и построим таблицу истинности для левой части данного логического уравнения

    x1 y1 x2 y2 x2  y2 x1  (x2  y2) (y1  y2) (x1  (x2  y2))  (y1  y2)
    0 0 0 0 0 1 1 1
    0 0 0 1 0 1 1 1
    0 0 1 0 0 1 1 1
    0 0 1 1 1 1 1 1
    0 1 0 0 0 1 0 0
    0 1 0 1 0 1 1 1
    0 1 1 0 0 1 0 0
    0 1 1 1 1 1 1 1
    1 0 0 0 0 0 1 0
    1 0 0 1 0 0 1 0
    1 0 1 0 0 0 1 0
    1 0 1 1 1 1 1 1
    1 1 0 0 0 0 0 0
    1 1 0 1 0 0 1 0
    1 1 1 0 0 0 0 0
    1 1 1 1 1 1 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.

    x1 y1 x2 y2 x2  y2 x1  (x2  y2) (y1  y2) (x1  (x2  y2))  (y1  y2)
    0 0 0 0 0 1 1 1
    0 0 0 1 0 1 1 1
    0 0 1 0 0 1 1 1
    0 0 1 1 1 1 1 1
    0 1 0 1 0 1 1 1
    0 1 1 1 1 1 1 1
    1 0 1 1 1 1 1 1
    1 1 1 1 1 1 1 1
    Получим следующую зависимость:

    х2у2 х1у1
    00 =00
    01 =00+01
    10 =00
    11 =00+01+10+11
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7
    00 1 1 1 1 1 1 1
    01 1 2 3 4 5 6 7
    10 1 1 1 1 1 1 1
    11 1 4 8 13 19 26 34

    Суммируем последний столбец и получаем 43 решения.
    Ответ: 43 решения.

    Задание 15 (23.164). Сколько различных решений имеет система уравнений?
    (x1  (x2  y2))  (y1  y2) = 1
    (x2  (x3  y3))  (y2  y3) = 1
    ...
    (x7  (x8  y8))  (y7  y8) = 1
    x8  y8 = 1
    где x1,x2,…,x8 и y1,y2,…,y8, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Решение:
    В данной системе все уравнения, кроме последнего, однотипны, поэтому можно применить метод отображения. Последнее уравнение стоит учесть в конце решения.
    Рассмотрим первое уравнение (x1  (x2  y2))  (y1  y2) = 1 и построим таблицу истинности для левой части данного логического уравнения

    x1 y1 x2 y2 x2  y2 (x1  (x2  y2)) (y1  y2) (x1  (x2  y2)) (y1  y2)
    0 0 0 0 0 1 1 1
    0 0 0 1 1 1 1 1
    0 0 1 0 1 1 1 1
    0 0 1 1 1 1 1 1
    0 1 0 0 0 1 0 0
    0 1 0 1 1 1 1 1
    0 1 1 0 1 1 0 0
    0 1 1 1 1 1 1 1
    1 0 0 0 0 0 1 0
    1 0 0 1 1 1 1 1
    1 0 1 0 1 1 1 1
    1 0 1 1 1 1 1 1
    1 1 0 0 0 0 0 0
    1 1 0 1 1 1 1 1
    1 1 1 0 1 1 0 0
    1 1 1 1 1 1 1 1

    Вычеркнем строки с нулевыми значениями в последнем столбце, так как значение уравнения равно 1.
    x1 y1 x2 y2 x2  y2 (x1  (x2  y2)) (y1  y2) (x1  (x2  y2)) (y1  y2)
    0 0 0 0 0 1 1 1
    0 0 0 1 1 1 1 1
    0 0 1 0 1 1 1 1
    0 0 1 1 1 1 1 1
    0 1 0 1 1 1 1 1
    0 1 1 1 1 1 1 1
    1 0 0 1 1 1 1 1
    1 0 1 0 1 1 1 1
    1 0 1 1 1 1 1 1
    1 1 0 1 1 1 1 1
    1 1 1 1 1 1 1 1

    Получим следующую зависимость:
    х2у2 х1у1
    00 =00
    01 =00+01+10+11
    10 =00+10
    11 =00+01+10+11
    Строим таблицу количества решений для каждой пары:

    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7 х8у8
    00 1 1 1 1 1 1 1 1
    01 1 4 11 26 57 120 247 502
    10 1 2 3 4 5 6 7 8
    11 1 4 11 26 57 120 247 502

    Последнее уравнение x8  y8 = 1 исключает пару 10, то есть х8=1, у8=0. Таким образом вычеркиваем третью строку.
    х1у1 х2у2 х3у3 х4у4 х5у5 х6у6 х7у7 х8у8
    00 1 1 1 1 1 1 1 1
    01 1 4 11 26 57 120 247 502
    10
    1 2 3 4 5 6 7 8
    11 1 4 11 26 57 120 247 502

    Суммируем последний столбец и получаем 1005 решений.
    Ответ: 1005 решений.
    Список литературы:
    1. Е.А.Мирончик. Метод отображения // Информатика, № 10, 2013, с. 18-26
    2. Е.А. Мирончик. Люблю ЕГЭ за В15, или Ещё раз про метод отображения // Информатика, № 7-8, 2014, с. 26-32.
    3. К.Ю. Поляков. Преподавание, наука и жизнь. [Электронный ресурс],-
    4. http://kpolyakov.spb.ru/school/ege.htm
    Категория: Мои статьи | Добавил: L-Shog543507 (27.12.2018) | Автор: Людмила Шогенова
    Просмотров: 111 | Рейтинг: 0.0/0
    Всего комментариев: 0
    avatar