Теоретическое введение
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


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


Payeer

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

В соответствующем задании КИМ ЕГЭ по информатике предложено найти количество решений системы логических уравнений. Несмотря на то, что непосредственные решения определять вроде бы не нужно, зачастую возникает необходимость в их записи с целью последующего подсчёта (но не для внесения в ответ). В этой связи сразу оговорим, как нужно составлять ответ: если в тексте задачи сказано, что в качестве ответа должно выступать число, обозначающее количество решений системы уравнений, то следует записать именно число решений. И ничего кроме!

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

      Как было отмечено выше, в ряде случаев необходимо определить конкретные решения уравнения или системы уравнений, чтобы потом посчитать их. По этой причине в некоторых примерах настоящей статьи формулировка задания и его цель будут отличаться от имеющих место в официальных демо-версиях КИМ.

Решения всякого уравнения или неравенства можно определить в виде множества. Каждое решение при этом является элементом множества, так что даже если решение одно, множество решений просто содержит один элемент. Элемент множества сам может быть множеством. Например, решение уравнения x – 1 = 7 одно (x = 8, т. е. множество решений содержит один элемент), а неравенство x – 1 > 7 имеет бесконечное множество частных решений, описываемое общим решением x > 8 (здесь общее решение — это множество частных решений, включающее бесконечное число возможных значений переменной x, правда, соответствующих известному условию).

Решением является и выражение y = x – 1, ведь оно может быть результатом упрощения какого-нибудь уравнения с двумя переменными. Приведённая запись тоже представляет собой множество решений, как и неравенство, ведь она, по сути, есть уравнение, имеющее бесконечное количество частных решений.

И, наконец, самая большая неожиданность: любое уравнение или неравенство можно называть решением. Только потому, что оно функционально связывает заданные в нём переменные, значения которых всегда можно вывести. Однако, поскольку мы умеем решать не всякое уравнение или неравенство (говоря иначе — упрощать вид решения), сделаем уточнение: будем называть решением такое выражение, очевидным следствием которого являются конкретные значения указанных в нём переменных. Например, одним из очевидных следствий неравенства x > 8 является x = 9, а уравнения y = x – 1 — пара значений (1; 0); она, кстати, может быть записана в виде системы: .

Для начала определимся с тем, что же такое, собственно, система.

    • Система уравнений (и/или неравенств) — решение, являющееся множеством, образованным пересечением всех частных решений, указанных в нём.

    • Нередко пересекаются не все частные решения, указанные в системе. Если система не имеет решений, то она представляет собой пустое множество. В этом случае все вместе частные решения, образующие систему, не пересекаются.

      Если среди частных решений, перечисленных в системе, имеется хотя бы одно пустое множество, то система в целом будет пустым множеством.

Например, система решений есть общее решение, которое выглядит в привычной форме двойного неравенства как 1 ≤ x < 3, а его частным решением может быть x = 1.

Подробнее о пересечении множеств можно прочитать в §5 раздела "Элементы теории множеств".

В процессе решения (упрощения) уравнений и их систем мы столкнёмся не только с системами, но и совокупностями уравнений.

    • Совокупность уравнений (и/или неравенств) — решение, являющееся множеством, образованным объединением всех частных решений, указанных в нём.

    • Если среди частных решений, перечисленных в совокупности, имеется хотя бы одно непустое множество, то совокупность в целом не будет пустым множеством.

Например, совокупность есть общее решение, которое записывается в более простой форме: x < 3. Его частным решением может быть x = 2,9.

Подробнее об объединении множеств можно прочитать в §6 раздела "Элементы теории множеств".

    • Резюмируем вышесказанное. Система и совокупность являются множествами решений, будучи решениями сами по себе. Если такое множество содержит хотя бы один элемент, то говорят, что система или совокупность имеет [частные] решения (хотя бы одно), в противном случае множество — пустое (не содержит частных решений).

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

Покажем некоторые способы обозначения подмножеств решений систем и совокупностей уравнений/неравенств.

Система систем. Если система пересекает несколько частных решений, то их можно произвольно сгруппировать во вложенные системы, и наоборот. В Примере 1 рассмотрена такая ситуация.

  • 1

    • Пусть задана система неравенств:

      Упрощённые неравенства в виде системы записываются так:

      Однако их можно сгруппировать внутри основной системы во вложенные. Вот один из способов группировки:

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

Система совокупностей. Если имеется система, пересекающая несколько совокупностей, её можно представить как совокупность систем, в любую из которых входят по одному элементу каждой исходной совокупности так, чтобы вновь полученные системы вместе обеспечивали все возможные пересечения элементов исходных совокупностей (см. Пример 2).

  • 2

    • Систему совокупностей

      можно представить следующим способом:

      Тогда её решениями являются все перечисленные частные:

      Заметим, что для получения первого частного решения совокупности использовалось правило отбора x < 5, указанное в первой вложенной системе, для получения второго — правило отбора x < 10 из второй вложенной системы. Пустые множества как остальные частные решения тоже получались благодаря соответствующим неравенствам как правилам отбора.

      Понятно, что общим решением является x = 3, и оно одно.

      В данном Примере важнее показать описываемые преобразования, нежели их рациональность.

    • Опять же вспомним, что понятия системы и совокупности связаны с множествами, и тогда преобразования, проведённые в Примере 2, станут более очевидными. Ведь у пересечения есть такое свойство, как дистрибутивность по отношению к объединению.

Совокупность систем. Пусть имеется совокупность нескольких систем. Она может быть записана как система совокупностей, в любую из которых входят по одному элементу каждой исходной системы так, чтобы вновь полученные совокупности вместе обеспечивали все возможные объединения элементов исходных систем (см. Пример 3).

  • 3

    • Совокупность

      может быть записана как система:

      После упрощения эта система представляется компактнее:

      или

      Окончательный ответ (наиболее простой вид решения) можно показать в виде одной маленькой совокупности, которая получена благодаря применению правила отбора 3 ≤ x < 10:

      Это означает, что исходная совокупность (как и любая полученная в процессе преобразования система) имеет 2 частных решения.

      В данном Примере важнее показать описываемые преобразования, нежели их рациональность.

Совокупность совокупностей. Если совокупность объединяет несколько частных решений, то их можно произвольно сгруппировать во вложенные совокупности, и наоборот (что и показано в Примере 4).

  • 4

    • Пусть в ходе решения некоторой задачи получилась совокупность решений

      Её правильно представить и так (если это нужно):

      В любом случае совокупность имеет неограниченное множество частных решений, представляющееся неравенством (общим решением) x < 6.

      Вероятно, аналогичные преобразования вы привыкли выполнять устно.

    • Объединение множеств коммутативно и ассоциативно, поэтому частные решения, приведённые в совокупности, можно произвольно группировать во вложенные совокупности.

Система системы и совокупности. Пусть имеются система и совокупность решений, вложенные в систему (т. е. пересекающиеся). Вся система может быть представлена как совокупность систем, каждая из которых пересекает все частные решения, перечисленные во вложенной исходной системе, и очередное частное решение, взятое из вложенной совокупности (такое преобразование выполнено в Примере 5).

  • 5

    • Пусть задана система, пересекающая систему с совокупностью:

      Она может быть преобразована в совокупность:

      Частные решения, объединяемые этой совокупностью, легко показать явно:

      Понятно, что благодаря правилу отбора 5 < x < 10 частное решение x = 3 первой вложенной системы не было отобрано в выведенную совокупность, а частное решение x = 7 второй системы "прошло" отбор.

      Решением исходной системы, как видно, является x = 7, и оно единственно.

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

Конъюнкция двух аргументов, результатом которой является истина, может быть представлена как система истинных значений этих аргументов. Другими словами, если имеет место логическое уравнение x ⋀ y = 1, то оно может быть заменено системой в соответствии с Правилом (1):

(1)
Истинная конъюнкция представляется системой истинных значений своих аргументов
(1)
    • Отметим возможность записи системы в одну строку. В самом деле, каждая из перечисленных в Правиле (1) переменных равна единице (истине), значит, обе переменные всегда равны друг другу, имея конкретное значение — 1. Подобное представление систем значений логических переменных позволяет экономить, и иногда весьма значительно, место при записи, да и время, на неё затрачиваемое.

Дизъюнкция двух аргументов, результатом которой является истина, есть совокупность истинных значений этих аргументов. Такое логическое уравнение и способ его представления иллюстрируются Правилом (2):

(2)
Истинная дизъюнкция представляется совокупностью истинных значений своих аргументов
(2)

В Примере 6 демонстрируется возможность решения сложного логического уравнения посредством представления его в виде системы, а в Примере 7 — в виде совокупности.

  • 6

    • Задача. Решить логическое уравнение .


      Решение. Введём дополнительные переменные, наличие которых позволит значительно упростить вид уравнения:

      Понятно, что в соответствии с Правилом (1) само уравнение будет записано как система:

      Произведём обратную замену переменных, тогда уравнение выглядит так:

      Последовательно применяя Правила (1) и (2), заменим каждое уравнение этой системы на вложенные систему и совокупность соответственно:

      Чтобы стало проще решить эту систему, запишем явно все решения вложенной совокупности:

      Мы видим, что общее решение вложенных системы и совокупности одно: x = y = 1.

      Последняя запись означает, что уравнение выполняется при единственном условии: x = 1 и y = 1, т. е. при одновременной истинности обеих переменных.

      Ответ. x = y = 1.

  • 7

    • Задача. Решить логическое уравнение .


      Решение. Введём дополнительные переменные, наличие которых позволит значительно упростить вид уравнения:

      Уравнение будет записано по Правилу (2) как совокупность, ведь последнее выполняющееся в нём действие — дизъюнкция:

      Как и в Примере 6, выполним обратную замену переменных, тогда уравнение принимает вид

      Последовательно применяя Правила (1) и (2), заменим каждое уравнение этой совокупности на вложенные систему и совокупность соответственно:

      Чтобы стало проще решить основную совокупность, запишем явно все решения вложенной совокупности:

      Вложенная система имеется среди частных решений вложенной совокупности, поэтому общими решениями основной совокупности являются лишь решения вложенной совокупности:

      Последняя запись означает, что уравнение выполняется при x = 0 и y = 1, при x = 1 и y = 0, а также при x = 1 и y = 1, т. е. при истинном значении хотя бы одного аргумента.

      Ответ.

Если в логическом уравнении инвертируется какая-либо переменная, то при составлении системы или совокупности, описывающей уравнение, достаточно указать инвертированное значение для этой переменной. Так, например, если имеется уравнение A ⋀ ¬B = 1, то его можно представить в виде системы . Это есть то же самое, что и . Если же инвертируется часть выражения, представленного в уравнении, содержащая несколько переменных, то придётся применить правила Моргана (возможно, неоднократно) для преобразования этой части во вложенную систему или совокупность; случай с таким преобразованием описан в Примере 8.

  • 8

    • Задача. Решить логическое уравнение .


      Решение. Введём дополнительные переменные, наличие которых позволит значительно упростить вид уравнения:

      Уравнение будет записано по Правилу (2) как совокупность, ведь последнее выполняющееся в нём действие — дизъюнкция:

      Поскольку введённая нами переменная B инвертируется, её можно приравнять к нулю:

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

      Инвертируем обе части второго уравнения этой совокупности для того, чтобы в его правой части была истина, а не ложь:

      Тогда по правилу Моргана получаем:

      Показанные преобразования дают такие решения:

      Заметьте, что для обоих уравнений совокупности применено Правило (1), ведь теперь во втором её уравнении дизъюнкция заменена конъюнкцией!

      Полученная совокупность означает, что предложенное в задаче уравнение выполняется при равенстве обеих переменных друг другу, т. е. в двух случаях: x = y = 0 и x = y = 1.

      Ответ. x = y.

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

Импликация, как известно, выражается с помощью двух базовых логических операций согласно равенству (3):

(3)
Выражение импликации через базовые логические операции
(3)

Следовательно, уравнение, в котором проверяются условия истинности импликации, x → y = 1, может быть записано в виде совокупности по Правилу (4):

(4)
Истинная импликация как совокупность
(4)

Логическое вычитание может быть заменено выражением, содержащим конъюнкцию, дизъюнкцию и инверсию, в соответствии с равенством (5):

(5)
Выражение логического вычитания через базовые логические операции
(5)

Поэтому уравнение, в котором выясняются условия истинности логического вычитания, может быть записано как совокупность или как система по Правилу (6):

(6)
Истинное логическое вычитание как совокупность или система
(6)
    • Отметим возможность записи совокупности (6) одной строкой. Первая её система может быть записана как x ≠ y = 1, вторая — x ≠ y = 0. Левые части данных равенств (x ≠ y) совпадают, а правые вместе содержат все возможные значения, которые только можно присвоить логическим переменным. Это говорит о том, что можно совсем обойтись без этих значений, а оставить лишь главное условие: x ≠ y. Ведь из этой записи видно, что переменные не равны друг другу, но какие они при этом имеют значения — не важно.

Эквиваленция — операция, противоположная логическому вычитанию, значит, выражается она так, как показано в равенстве (7):

(7)
Выражение эквиваленции через базовые логические операции
(7)
    • Операция эквиваленции иногда обозначается знаком "≡", который в математике имеет значение "тождественно равно".

Уравнение, позволяющее определить условия истинности эквиваленции, записывается совокупностью по Правилу (8):

(8)
Истинная эквиваленция как совокупность
(8)
    • Совокупность (8), по аналогии с Правилом (6), здесь тоже может быть записана одной строкой. Ведь истинная эквиваленция показывает, что аргументы x и y равны друг другу, но совсем не важно, чему именно они равны — лжи или истине.

    • В Примере 8 фактически было проведено доказательство Правила (8).

      Правило (8) можно записать и в виде системы.

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

Наличие системы значений логических переменных указывает на то, что все эти значения должны быть присвоены соответственным переменным одновременно и без исключений. Система, в которой указаны только значения неповторяющихся логических переменных, не содержащая вложенных совокупностей, имеет строго одно решение для определённых в ней переменных, т. е. одно частное решение. Если такая система содержит не все переменные уравнения, то количество частных решений описываемого ею уравнения вычисляется как 2n – m, где n — общее количество логических переменных уравнения, m — количество логических переменных, упомянутых в этой системе (разумеется, m ≤ n).

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

  • 9

    • Задача. Найти число решений логического уравнения .


      Решение. Прежде чем решать это уравнение, упростим его. Поскольку (тождественно равно, т. е. равно при любых значениях x3), то оно принимает вид . Теперь можно представить его маленькой системой x1 = x2 = 1.

      Мы получили систему значений неповторяющихся логических переменных, которая имеет одно решение для переменных x1 и x2. Но в исходном уравнении три переменные: x1, x2 и x3. Значит, n = 3, m = 2 и уравнение имеет 2 различных решения. Покажем это на фрагменте таблицы истинности.

      x1x2x3
      000
      001
      010
      011
      100
      101
      110
      111

      В таблице выделены те значения логических переменных x1 и x2, которые вместе являются решениями системы, а эти пары содержатся в двух строках. Значит, и решений у уравнения всего два.

      Можно рассуждать быстрее, не записывая все строки таблицы истинности. Приведём лишь одну строку, в которой укажем пару значений переменных системы:

      x1x2x3
      11 

      В этой строке осталась незаполненной одна ячейка, в которой может быть одно из двух различных значений переменной x3. Значит, уравнение имеет два решения.

      Ответ. 2.

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

Последовательность действий при расчёте числа частных решений совокупности в простейших случаях можно увидеть из Примеров 10 и 11.

  • 10

    • Задача. Найти число решений логического уравнения .


      Решение. Составим совокупность:

      Имеем два множества значений логических переменных, одно из них образуется при u = 1 (назовём это множество A), второе — при v = 0 (пусть это множество называется B). Всего в исходном уравнении две логические переменные, значит, при u = 1 существует два решения уравнения (т. е. |A| = 2), при v = 0 тоже два (|B| = 2). Теперь представим, что наши множества пересекаются: и вправду, пересечение наблюдается при u ≠ v = 0, а это — система значений неповторяющихся переменных. Заключаем, что |A ⋂ B| = 1. Подставляя эти значения в формулу для расчёта мощности объединения двух множеств, получаем: |A ⋃ B| = 2 + 2 – 1 = 3 (решения уравнения).

      Ответ. 3.

  • 11

    • Задача. Найти число решений логического уравнения .


      Решение. Составим совокупность значений логических переменных:

      Решениями уравнения являются все, в комбинациях значений переменных которых x1 = 1 (множество A) или одновременно x2 = 0 и x3 = 1 (множество B). Имеем: |A| = 4, |B| = 2, |A ⋂ B| = 1. Подставляя вычисленные значения в формулу для расчёта мощности объединения двух множеств, получаем: |A ⋃ B| = 4 + 2 – 1 = 5 (решений уравнения).

      Ответ. 5.

Чтобы не пользоваться формулами для расчёта мощности объединения при анализе совокупностей, включающих большое число частных решений, прибегают к модификации совокупности, целью которой является получение эквивалентной совокупности, включающей исключительно непересекающиеся решения. Такая модификация проводится в соответствии с Правилом (9), в котором a и b — не переменные, но логические значения:

(9)
Модификация совокупности
(9)

Задачи Примеров 10 и 11 решены с помощью Правила (9) в Примерах 12 и 13 соответственно.

  • 12

    • Задача. Найти число решений логического уравнения .


      Решение. Составим совокупность и модифицируем её по Правилу (9):

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

      Первое решение совокупности, u = 1, имеет два частных решения для обеих переменных u и v. Это легко доказать, построив таблицу:

      uv
      1 

      Незаполненная ячейка в этой таблице говорит о том, что переменная v может иметь любое значение — одно из двух возможных, естественно. Значит, система, записанная в строке таблицы (в подобных таблицах строка — это именно система значений), имеет 2 решения.

      Второе решение совокупности, u = v = 0, представляет собой систему, имеющую одно решение (ведь система всегда имеет одно решение для своих переменных, а переменные в ней представлены все; эта система тоже показана в виде таблицы ниже).

      uv
      00

      Таким образом, предложенное в задаче уравнение имеет 2 + 1 = 3 решения.

      Ответ. 3.

  • 13

    • Задача. Найти число решений логического уравнения .


      Решение. Составим и модифицируем по Правилу (9) совокупность значений логических переменных:

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

      Первое решение совокупности, x1 = 1, имеет 4 частных решения для всех трёх переменных уравнения. Построим таблицу и докажем это:

      x1x2x3
      1  

      Второе её решение, x1 = x2 ≠ x3 = 1, предлагает лишь одно частное решение:

      x1x2x3
      001

      Итого предложенное в задаче уравнение имеет 4 + 1 = 5 решений.

      Ответ. 5.

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

    • Обратное уравнение по отношению к данному логическому — такое логическое уравнение, одна из частей которого (правая или левая) представляет собой инвертированное выражение той же части данного уравнения.

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

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

Чтобы составить представление обратного уравнения в виде системы или совокупности, поступают следующим образом:

все системы (являющиеся основной и вложенными) заменяются на совокупности, а совокупности — на системы;

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

Так, например, обратным уравнением и его представлением в виде системы по отношению к показанному в Правиле (4) будет следующее:

    • Правила (6) и (8) содержат взаимно обратные решения друг по отношению к другу.

    • Первое решение вложенной системы Правила (9) — ни что иное, как обратное уравнение по отношению к первому решению исходной совокупности. Теперь, познакомившись с понятием обратного уравнения, можно сформулировать Правило (9) так: чтобы получить совокупность двух непересекающихся решений из исходной совокупности, нужно второе решение записать в виде системы второго решения исходной совокупности и уравнения, обратного первому её решению, а само первое решение оставить неизменным. Понятно, что слова "первый" и "второй" взаимозаменяемы.

    • Если исходная совокупность содержит более двух решений и её требуется привести к виду, в котором она содержит непересекающиеся решения, то:

      два последних решения объединяются вложенной совокупностью, которая модифицируется по Правилу (9), затем модифицированная вложенная совокупность становится вторым решением ещё одной вложенной совокупности, и т. д.;

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

В Примере 14 показано, как на основе Правила (9) выполняется модификация совокупности, объединяющей более двух уравнений. Описанные в этом Примере действия придётся выполнять весьма часто при анализе уравнений и их систем.

  • 14

    • Задача. Найти число решений логического уравнения .


      Решение. Составим совокупность уравнений, соответствующую исходному уравнению:

      Модифицируем её по Правилу (9). Для этого выделим вложенную совокупность, включающую 2 решения (снизу); тогда, согласно Правилу (9), в получаемую вложенную систему должны входить обратное уравнение по отношению к x2 = x3 = 1 и собственно уравнение x3 = x4 = 1:

      Обратное системе x2 = x3 = 1 решение — совокупность, которую тоже нужно модифицировать по Правилу (9):

      Превратим вложенную систему во вложенную совокупность:

      Теперь осталось проделать аналогичные действия со всей совокупностью в целом, которую и модифицируем. Оставим первое её уравнение без изменений, а вместо вложенной совокупности запишем систему, пересекающую обратное первому уравнение и эту вложенную совокупность:

      Модифицируем по Правилу (9) решение, обратное первому уравнению совокупности:

      Осталось пересечь вложенные в систему совокупности:

      Преобразуем, чтобы результат не выглядел столь громоздко:

      Все выполненные действия были направлены на одну цель: конечная совокупность должна содержать непересекаемые решения для того, чтобы можно было узнать число частных решений для каждого из них, а затем просто сложить и получить ответ (проверьте, что решения действительно не пересекаются, построив таблицу значений переменных). Первая система этой совокупности, x1 = x2 = 1, имеет 4 частных решения. Вторая, x1 ≠ x2 = x3 = 1, — 2 частных решения. Наконец, третья, x2 ≠ x3 = x4 = 1, предоставляет тоже 2 частных решения. Итого 8 частных решений имеет исходное уравнение.

      Ответ. 8.

Число решений некоторого логического уравнения и число решений обратного ему уравнения связаны между собой. Пусть в этих уравнениях использовано n логических переменных, а количество решений одного из них равно k. Тогда количество решений обратного ему уравнения составляет 2n – k.

    • Частные решения взаимно обратных уравнений никогда не совпадают. Более того, все комбинации значений логических переменных, при которых логическое уравнение не выполняется, обязательно являются частными решениями обратного ему уравнения.

На основе знаний о взаимно обратных логических уравнениях можно значительно быстрее находить число их частных решений (как, кстати, и сами решения), что видно из Примеров 15 и 16.

  • 15

    • Задача. Найти число решений логического уравнения:


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

      Уравнение можно представить в виде совокупности двух систем:

      В ней первые уравнения вложенных систем можно записать в виде системы и совокупности соответственно, а вторые дополнительно упростить:

      Теперь можно сказать, что вложенные в совокупность системы имеют непересекающиеся решения (если, конечно, эти решения у них есть): дело здесь в том, что система x1 ≠ x2 = 0 и совокупность являются друг по отношению к другу взаимно обратными решениями, следовательно, можно не применять формулы для расчёта числа элементов объединения и не модифицировать совокупность с помощью Правила (9), но напрямую складывать количество решений первой и второй систем.

      Рассмотрим системы этой совокупности по-отдельности.

      Первая её система должна быть представлена так, чтобы в ней все логические операции были заменены на вложенные (в т. ч. друг в друга) системы и совокупности. Сделаем это и упростим её:

      Со второй системой поступим аналогично:

      Эта маленькая совокупность может быть заменена ещё меньшей системой: x2 = x3 = 1.

      Вот что теперь представляет собой всё предложенное в задаче уравнение:

      Заметим, что первая вложенная система даёт два частных решения, вторая — тоже два, которые, как мы заметили выше, не пересекаются с решениями предыдущей (проверьте это самостоятельно). Поэтому уравнение имеет всего 4 несовпадающих частных решения.

      Ответ. 4.

  • 16

    • Задача. Найти число решений логического уравнения:


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

      Тогда уравнение можно представить в виде совокупности двух систем так:

      Первые уравнения её вложенных систем можно записать в виде системы и совокупности соответственно, а вторые дополнительно упростить:

      Как и в предыдущем Примере, вложенные в совокупность системы имеют непересекающиеся решения, ведь опять же система x1 ≠ x2 = 0 и совокупность являются друг по отношению к другу взаимно обратными решениями. Напомним, что это значит: можно не применять формулы для расчёта числа элементов объединения и не модифицировать совокупность с помощью Правила (9), но напрямую складывать количество решений первой и второй систем.

      Рассмотрим системы этой совокупности по-отдельности.

      Первая её система должна быть представлена так, чтобы в ней все логические операции были заменены на вложенные (в т. ч. друг в друга) системы и совокупности:

      Перейдём к подсчёту её частных решений. Вложенная система x1 ≠ x2 = 0 — единственное уравнение, содержащее переменные x1 и x2, и только для них она предоставляет, естественно, лишь одно частное решение.

      Обе системы вложенной совокупности не пересекаются хотя бы потому, что система x5 = x6 = 0 и совокупность являются взаимно обратными решениями.

      Вложенная в совокупность система

      имеет для своих переменных x3, x4, x5 и x6 2 различных решения.

      Вложенная в ту же совокупность система

      имеет для своих переменных x3, x4, x5 и x6 6 несовпадающих решений.

      Итого вложенная совокупность для своих переменных x3, x4, x5 и x6 имеет 2 + 6 = 8 решений, значит, вся первая система тоже имеет 8 решений: 1 × ( 2 + 6 ) = 8.

      Со второй системой совокупности нужно поступить аналогично. Заменим в ней все логические операции на системы и совокупности в соответствии с Правилами (2), (6) и (8):

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

      Обе системы вложенной совокупности не пересекаются, поскольку совокупность и система x5 = x6 = 0 являются взаимно обратными решениями.

      Вложенная в совокупность система

      имеет для своих переменных x3, x4, x5 и x6 2 × 3 = 6 решений.

      Ещё одна вложенная в совокупность система

      имеет для своих переменных x3, x4, x5 и x6 2 × 1 = 2 решения.

      Итого вложенная совокупность для своих переменных x3, x4, x5 и x6 имеет 6 + 2 = 8 решений, значит, вторая система полученной совокупности имеет 3 × 8 = 24 решения.

      Исходное же уравнение имеет, таким образом, 8 + 24 = 32 решения.

      Ответ. 32.

Теперь можно перейти, наконец, к решению систем логических уравнений. Хотя мы их уже вовсю решаем (упрощаем)! И не только системы, но и совокупности. Дело в том, что всякое логическое уравнение представляется в виде системы или совокупности сравнительно небольших (по количеству переменных и действий с ними) уравнений, а изначально предложенную систему (или совокупность) логических уравнений можно считать одним большим уравнением; в этом можно лишний раз убедиться, благодаря Правилам (1), (2), (4), (6) и (8).

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

системы, логические уравнения которых содержат разные действия с переменными и разные константы, и…

системы, пересекающие логические уравнения, имеющие одинаковую структуру.

    • В уравнениях, имеющих одинаковую структуру, одни и те же действия выполняются над разными переменными. Константы однотипных уравнений (например, истина или ложь, т. е. 1 или 0), расположенные в соответственных позициях, должны совпадать.

Назовём уравнения с одинаковой структурой однотипными.

    • Чаще всего приходится иметь дело с системами смешанного типа: в них есть несколько однотипных уравнений и несколько отличающихся способом организации или константами.

Процесс нахождения числа решений системы однотипных уравнений виден из Примера 17.

  • 17

    • Задача. Найти число решений системы уравнений:


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

      Итак, одно любое уравнение предложенной в задании системы представляется в виде такого решения (разумеется, 1 ≤ i ≤ 4):

      Как видно, каждое уравнение исходной системы имеет по три частных решения для своих переменных. Так, например, частные решения первого можно представить таблицей:

      x1x2
      00
      10
      11

      Найдём частные решения первых двух уравнений вместе.

      Запишем частные решения первого и частные решения второго рядом:

      x1x2
      00
      10
      11
      x2x3
      00
      10
      11

      Первое решение первого уравнения пересекается с одним (первым) решением второго; второе решение первого — с одним (первым) решением второго; наконец, третье решение первого — с двумя решениями второго. Итого имеем 4 частных решения первых двух уравнений системы вместе. Они могут быть отображены в виде таблицы значений так:

      x1x2x3
      000
      100
      110
      111

      Замечаем, что, пересекая вновь получаемые совместные решения одного или нескольких первых уравнений с решениями последующего, количество совместных решений возрастает на единицу, поскольку последняя переменная в таблице всегда будет иметь истинное значение в одном случае, ложное — в остальных. А ведь именно истинное её значение приводит к увеличению количества совместных со следующим уравнением решений! Значит, если первое уравнение имеет 3 собственных частных решения, а всего уравнений четыре, то общее число частных решений системы составляет 3 + ( 4 – 1 ) × 1 = 6.

      Ответ. 6.

Чаще всего уравнения системы, включая однотипные, должны быть преобразованы к более простому виду. Упрощение вида логических уравнений до решения их и системы в целом продемонстрировано в Примере 18.

  • 18

    • Задача. Найти число решений системы уравнений:


      Решение. Данная система включает в себя 4 однотипных уравнения, на что указывает многоточие. Каждое её уравнение можно упростить следующим образом (считать i ∊ {1, 3, 5, 7}):


      (по правилам поглощения)
      (по правилу эквиваленции инвертированных значений)
      (по определениям эквиваленции и логического вычитания).

      Оказывается, что любое уравнение системы не просто содержит лишь одну бинарную логическую операцию: его частные решения зависят от двух переменных, а не трёх, как можно было подумать сразу.

      Итак, решения любого уравнения системы при i ∊ {1, 3, 5, 7} описываются простой совокупностью в соответствии с Правилом (6):

      Таким образом, одно любое уравнение системы при i ∊ {1, 3, 5, 7} имеет два решения для переменных xi и xi+1, причём они и решения другого уравнения при j ∊ {1, 3, 5, 7}, i ≠ j, всегда пересекаются в непустое множество решений, ведь переменные одного уравнения не содержатся в другом. В этом случае, чтобы рассчитать количество решений системы в целом, нужно количество решений одного уравнения возвести в степень, показателем которой является число уравнений системы. Тогда 24 = 16 (частных решений).

      Ответ. 16.

    • Если предложено найти количество частных решений системы однотипных уравнений, то конкретные решения этих уравнений имеет смысл записывать и затем пересекать (находить общие) в том случае, когда переменные одного уравнения содержатся в другом. В противном случае делать это совсем не обязательно, — сравните ещё раз решения задач, выполненные в Примерах 17 и 18.

Нахождение числа частных решений системы логических уравнений, не являющихся однотипными, нередко требует записи частных решений каждого уравнения и их последующего пересечения. Это же касается и систем смешанного типа. Однако бывают и исключения, которые желательно вовремя заметить ради экономии времени. Решения двух систем — не содержащей однотипные уравнения и имеющей смешанный тип, — приведены в Примерах 19 и 20 соответственно.

  • 19

    • Задача. Найти число решений системы уравнений:


      Решение. Оба уравнения системы не являются однотипными, поэтому придётся решать каждое по-отдельности. Запишем её в виде системы значений переменных, пересекающей вложенные систему и совокупность:

      Так, первое уравнение исходной системы теперь представляется верхней вложенной совокупностью, а второе — нижней вложенной системой.

      Весьма просто убедиться в том, что первое уравнение является тождеством, т. е. выполняется при любых значениях логических переменных. Действительно, вложенная совокупность равносильна совокупности, объединяющей восемь несовпадающих систем, каждая из которых представляет собой тройку значений переменных x1, x2 и x3. Поэтому при дальнейшем анализе мы не будем упоминать о верхнем уравнении исходной системы, ведь оно никак не влияет на её частные решения и их количество.

      Запишем вложенную систему (второе уравнение исходной системы) как систему совокупностей всех возможных пар соответственных переменных и упростим её (преобразуем в совокупность систем):

      Никакие вложенные системы полученной совокупности не пересекаются, поскольку для преобразований использовалось Правило (9). Поэтому достаточно сложить число частных решений каждой из её систем. Первая и последняя системы имеют по два частных решения (в них не указана переменная x3, значит, она может иметь любое значение), вторая — одно решение. Итого второе уравнение имеет 2 + 1 + 2 = 5 решений, значит, столько же частных решений имеет и предложенная в задании система в целом.

      Ответ. 5.

  • 20

    • Задача. Найти число решений системы уравнений:


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

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

      Полученную совокупность можно представить, разумеется, проще:

      Отсюда видны все частные решения первого уравнения, которые можно оформить в виде таблицы:

      x1x2x3
      000
      001
      011
      111

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

      y1y2y3
      000
      001
      011
      111

      Два только что решённых нами уравнения не имеют совпадающих переменных, значит, они вместе имеют 42 = 16 решений. Из них нужно выбрать такие, которые удовлетворяют третьему уравнению. Для этого запишем частные решения второго и первого рядом и выделим столбцы, переменные которых имеются в третьем уравнении:

      y1y2y3
      000
      001
      011
      111
      x1x2x3
      000
      001
      011
      111

      Если y2 = 0, то из четырёх наборов значений x1 … x3 можно выбирать любые. Значение y2 = 0 повторяется в таблице два раза, следовательно, мы уже нашли 8 частных решений исходной системы в целом.

      Для каждого истинного значения переменной y2 можно выбрать лишь по одному набору значений переменных x1 … x3. Значение y2 = 1 повторяется в таблице тоже два раза, и потому можно говорить, что найдено ещё два частных решения всей системы.

      Итого предложенная в задании система имеет 4 + 4 + 1 + 1 = 10 частных решений.

      Ответ. 10.

В Примерах 2, 3 и 5 настоящей статьи было показано, как разрешать или запрещать к записи в ответ отдельные значения переменных системы благодаря правилам отбора решений. Примеры эти были наибанальнейшими, но акцент на правила отбора был сделан не просто так. При решении систем логических уравнений некоторые из них тоже полезно определять как правила отбора, а не включать преобразования с ними в упрощение основного уравнения (или основных уравнений), ведь это очень экономит время. Правила отбора решений следует применять к уравнению, процесс преобразования которого для получения частных решений в контексте всей системы и их подсчёта можно сделать максимально эффективным: не громоздким и быстрым.

    • Прежде чем решать систему логических уравнений, нужно выбрать, какие её уравнения считать правилами, а какие — основными. Скорее всего, основным уравнением может быть какое-нибудь одно, тем более для системы (а не совокупности).

    • Иногда для выделения правил и основного уравнения отдельные решения исходной системы нужно перегруппировать.

Уравнение системы, которое можно воспринимать как правило отбора решений, определяется хотя бы по одному из следующих критериев:

оно имеет слишком много или, наоборот, слишком мало частных решений относительно других;

оно содержит, кроме прочих, переменные, которые не упоминаются вообще или упоминаются редко в других уравнениях;

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

    • Система не может состоять только из правил, иначе эти правила будет не к чему применить!

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

Покажем, как можно рассматривать отдельные уравнения, входящие в предлагаемую к анализу систему, в качестве правил отбора решений других её уравнений без подробного анализа. Подобная практика приведена в Примерах 21 — 23; они очень похожи друг на друга, но отличаются тонкостями преобразований и анализа.

  • 21

    • Задача. Найти число решений системы уравнений:


      Решение. Прежде чем приступать к записи системы, заменяя логические операции системами и совокупностями, приглядимся к её уравнениям, чтобы определить, какие можно истолковать как правила отбора решений, а какие — упрощать, используя эти правила.

      Первое уравнение представляется системой совокупностей, переменные которых упоминаются в ней и в других уравнениях исходной системы не однажды:

      По этой причине данное уравнение не будем считать правилом отбора.

      Запишем второе уравнение. Если бы в его правой части была истина (единица), то уравнение выглядело бы так:

      Но в правой его части ложь (нуль), значит, нужно составить обратное решение по отношению к только что записанной системе:

      Мы видим, что каждая из переменных y1, y2 и y3 присутствует только во втором уравнении исходной системы и больше ни в каком. Таким образом, будем считать это уравнение правилом отбора. Это правило можно сформулировать на математическом языке ещё короче:

      Такая запись означает буквально следующее: "хотя бы в одной паре (потому что совокупность) переменных x и y с равными индексами одна переменная не равна другой при том, что переменная y пары ложна". Можно продолжить: "соответственно переменная x пары истинна". Поскольку мы уже выбрали основное уравнение, — самое первое в системе, не содержащее ни одной переменной y, — то переформулируем это правило специально для него:

      Это означает: "среди переменных x1, x2 и x3 должна быть хотя бы одна истинная".

      И третье уравнение: y4 ≠ x1 = 0. Это тоже правило (ведь переменная y4 есть только в нём), гласящее, что "переменные y4 и x1 не равны друг другу при том, что x1 = 0". Данное правило влияет на предыдущее, упрощая его:

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

      Теперь все уравнения по-отдельности разобраны. Запишем первое уравнение исходной системы совместно с двумя выведенными правилами и перегруппируем вложенные совокупности для удобства последующих преобразований:

      Заметили, что верхняя вложенная совокупность фактически исчезла? Это — результат влияния правила номер 2: x1 = 0, а x2 может принимать любое значение.

      Выделим вложенную систему и преобразуем её отдельно:

      Вы видите, что она превратилась… нет, даже не в совокупность, но равенство x3 = 1! Тогда вот чему равна вся исходная система без учёта переменных y1 … y4:

      Если бы не было других переменных, можно было формулировать ответ прямо сейчас. А так придётся составлять таблицу значений переменных x1 … x4:

      x1x2x3x4
      0 11

      что эквивалентно

      x1x2x3x4
      0011
      0111

      Как видно, системы значений переменных, показанные в таблице, не пересекаются. Впрочем, так и должно быть. Допишем к этой таблице ещё одну — со значениями y1 … y4, пока не заполненную:

      x1x2x3x4
      0011
      0111
      y1y2y3y4
          
          

      В обоих случаях y4 = 1 (потому что x1 = 0, второе правило):

      x1x2x3x4
      0011
      0111
      y1y2y3y4
         1
         1

      В первой строке значений среди переменных x1 … x3 только x3 = 1, следовательно, y3 = 0 (см. первое правило):

      x1x2x3x4
      0011
      0111
      y1y2y3y4
        01
         1

      Во второй строке значений среди переменных x1 … x3 уже две истинны. По первому правилу должна быть хотя бы одна пара переменных x и y с одинаковыми индексами, в которой xi ≠ yi = 0 (1 ≤ i ≤ 3). Поэтому расширим таблицу, перечислив все допустимые значения y1 и y2:

      x1x2x3x4
      0011
      0111
      0111
      0111
      y1y2y3y4
        01
       001
       011
       101

      Система, представленная первой строкой значений, имеет 4 частных решения; системы второй, третьей и четвёртой строк — по 2. Итого вся исходная система имеет 10 частных решений.

      Ответ. 10.

  • 22

    • Задача. Найти число решений системы уравнений:


      Решение. Прежде чем приступать к записи системы, заменяя логические операции системами и совокупностями, приглядимся к её уравнениям, чтобы определить, какие можно истолковать как правила отбора решений, а какие — упрощать, используя эти правила.

      Первое уравнение представляется системой совокупностей, переменные которых упоминаются в ней и в других уравнениях исходной системы не однажды:

      По этой причине данное уравнение не будем считать правилом отбора.

      Запишем второе уравнение:

      Почему оно выглядит в виде совокупности, см. предыдущий Пример. Мы видим, что каждая из переменных y1, y2 и y3 присутствует только во втором уравнении исходной системы и больше ни в каком. Таким образом, будем считать это уравнение правилом отбора. Это правило можно сформулировать на математическом языке ещё короче:

      Такая запись означает буквально следующее: "хотя бы в одной паре переменных x и y с равными индексами одна переменная не равна другой при том, что переменная y пары ложна, а переменная x пары истинна". Поскольку мы уже выбрали основное уравнение, — самое первое в системе, не содержащее ни одной переменной y, — то переформулируем это правило специально для него: "среди переменных x1, x2 и x3 должна быть хотя бы одна истинная" (см. предыдущий Пример).

      И третье уравнение: y4 ≠ x2 = 0. Это тоже правило (ведь переменная y4 есть только в нём), гласящее, что "переменные y4 и x2 не равны друг другу при том, что x2 = 0". Данное правило влияет на предыдущее, упрощая его:

      И оно может быть применено в виде совсем маленькой совокупности:

      А при этом, напоминаем, x2 = 0!

      Теперь все уравнения по-отдельности разобраны. Запишем первое уравнение исходной системы совместно с двумя выведенными правилами и перегруппируем вложенные совокупности для удобства последующих преобразований:

      Мы применили правило x2 = 0 к верхней вложенной совокупности, а правило — ко второй. Так можно, потому что всё равно нужно пересекать все совокупности первого уравнения.

      Вот как преобразуется теперь первая полученная только что система:

      Тогда первое уравнение исходной системы с применёнными к нему правилами выглядит совсем просто:

      И ещё проще:

      И ещё: x1 = x2 ≠ x3 = x4 = 1.

      Если бы не было других переменных, можно было формулировать ответ прямо сейчас. А так придётся составлять таблицу значений переменных x1 … x4:

      x1x2x3x4
      0011

      Допишем к этой таблице ещё одну — со значениями y1 … y4. Пока занесём в неё лишь одно значение — y4 = 1 (оно выделено из второго правила):

      x1x2x3x4
      0011
      y1y2y3y4
         1

      А вот по первому правилу среди переменных x1 и x3 должна быть хотя бы одна истинная. Действительно, x3 = 1, значит, по тому же первому правилу, y3 = 0:

      x1x2x3x4
      0011
      y1y2y3y4
        01

      Очевидно, исходная система имеет 4 частных решения.

      Ответ. 4.

  • 23

    • Задача. Найти число решений системы уравнений:


      Решение. Понятно, что первое уравнение системы выглядит так (см. оба предыдущих Примера):

      Его неудобно назначать правилом отбора по сравнению с другими уравнениями.

      Второе уравнение тоже было представлено как совокупность в двух предыдущих Примерах:

      Оно было истолковано как правило:

      Напомним, как формулируется это правило: "хотя бы в одной паре переменных x и y с равными индексами одна переменная не равна другой при том, что переменная y пары ложна, а переменная x пары истинна". Оно же по отношению к первому уравнению: "среди переменных x1, x2 и x3 должна быть хотя бы одна истинная" (см. предыдущий Пример).

      Третье уравнение (правило): y4 ≠ x4 = 0 (переменные y4 и x4 не равны друг другу при том, что x4 = 0). Данное правило не влияет на первое, в отличие от продемонстрированного в обоих предыдущих Примерах.

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

      Мы видим, что система несовместна, ведь среди x1, x2 и x3 должна быть хотя бы одна истинная переменная, что отрицает первая её вложенная система. Вот так мы, даже не анализируя значения переменных y1 … y4, добрались до ответа.

      Ответ. 0.

Среди критериев выделения правила из решений системы (см. выше) есть такой: "уравнение имеет слишком много или, наоборот, слишком мало частных решений относительно других". Зададимся вопросом: как уравнение со множеством частных решений может быть правилом, т. е. зависимостью, упрощающей жизнь? Оказывается, может. Ведь всегда есть обратное уравнение, которое, как было подробно описано в настоящей статье, тогда будет иметь очень мало частных решений. Но: если обычное правило разрешает использование установленных им зависимостей, то обратное уравнение по правилу (обратное правило) запрещает их использование.

В Примерах 24 и 25 показано, как используются прямые и обратные правила. Кроме того, в Примере 25 выполняется перегруппировка входящих в систему решений с целью определения единственного основного уравнения для наиболее удобного применения к нему правил.

  • 24

    • Задача. Найти число решений системы уравнений:


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

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

      Второе уравнение системы встречалось нам раньше, в Примерах 21 — 23. Напомним, что оно представляется такой системой:

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

      Данная запись, будь она основным правилом, означала бы следующее: "хотя бы одна пара, состоящая из соседних переменных xi и xi+1, должна отвечать требованию, что первая переменная в ней истинна, а вторая ложна". Но это — обратное правило, значит, формулироваться оно должно так: "не может быть ни одной пары, состоящей из соседних переменных xi и xi+1, такой, что первая переменная в ней истинна, а вторая ложна". Вот как это коротко записать:

      Третье уравнение предложенной в задаче системы тоже встречалось в трёх предыдущих Примерах, но с другим значением в правой части. Здесь оно представляется системой, а не совокупностью:

      На основе такого решения не создать удобное правило, поэтому составим на его основе обратное правило — уже второе:

      Поскольку правило именно обратное, то формулироваться оно будет так: "не может быть ни одной пары, состоящей из переменных с равными индексами xj и yj, такой, что первая переменная в ней истинна, а вторая ложна". Формулировка напоминает предыдущее правило, но ведь и соответствующие уравнения однотипны! Запишем коротко:

      Четвёртое уравнение исходной системы можно было бы добавить в конъюнкт третьего, в любом случае оно расширяет область действия второго правила, никак не уточняя его. Вот как теперь выглядит второе правило:

      Второе правило применим при осуществлении заключительных действий по поиску частных решений. Пока же запишем пересечённые основное уравнение системы и применяемое к нему первое правило, выделим в совокупности первого решения вложенную совокупность и проведём модификации совокупностей (для того, чтобы конечная совокупность содержала исключительно непересекающиеся решения) по Правилу (9):

      Заметьте, как, благодаря первому правилу, в процессе преобразований выпадали решения, противоречащие ему. Скоро наступит черёд второго правила. Для его применения занесём полученные решения в таблицу:

      x1x2x3x4
      1111
      0111
      0011

      Присоединим рядом таблицу возможных значений переменных y1 … y4, пока ещё пустую:

      x1x2x3x4
      1111
      0111
      0011
      y1y2y3y4
          
          
          

      Настало время применить второе правило. Оно говорит фактически о том, что если xj = 1, то yj = 1 (1 ≤ j ≤ 4).

      Так что в первой строке любая из переменных yj истинна:

      x1x2x3x4
      1111
      0111
      0011
      y1y2y3y4
      1111
          
          

      В оставшихся двух строках некоторые из этих переменных могут принимать любые значения — в соответствии с записью:

      x1x2x3x4
      1111
      0111
      0011
      y1y2y3y4
      1111
       111
        11

      Осталось посчитать частные решения. Система значений переменных первой строки предполагает одно частное решение, второй — два, третьей — четыре. Всего семь.

      Ответ. 7.

  • 25

    • Задача. Найти число решений системы уравнений:


      Решение. Система пересекает 7 логических уравнений, 5 из которых являются однотипными (на это указывает многоточие). Упрощать её (т. е. решать) из такого представления было бы достаточно проблематичным занятием. Заметим, что однотипные уравнения — конъюнкты, а это говорит о том, что каждое из них само по себе является системой. Поэтому не возникнет сложности перегруппировать их содержимое и сделать вместо пяти однотипных уравнений два разных. Тогда исходная система будет иметь такое представление:

      Первое и второе уравнения в этом представлении — это все однотипные уравнения изначально предложенного представления.

      Первое уравнение полученной системы можно записать так:

      Его сложно упрощать, потому оно претендует на роль основного уравнения. Однако попробуем создать на его основе обратное правило, для чего запишем обратное уравнение:

      Что ж, обратное правило говорит о том, что "не может быть ни одной пары, состоящей из соседних переменных xi и xi+1, такой, что обе переменные в ней ложны". Вот короткая запись этого правила:

      Теперь запишем как систему второе уравнение:

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

      Его формулировка: "не может быть ни одной пары переменных с равными индексами xj и yj, такой, что первая переменная в ней истинна, а вторая ложна". Его тоже можно записать короче:

      Третье уравнение — совокупность:

      Вот оно, наше основное уравнение! Значит, первое уравнение мы не напрасно оформили в качестве правила.

      Наконец, четвёртое уравнение (явно — правило): y6 ≠ x1 = 0 (переменные y6 и x1 не равны друг другу при том, что x1 = 0). Это наше третье правило.

      Что ж, запишем третье уравнение с применёнными к нему первым и третьим правилами (вторым правилом воспользуемся позже) и сразу немного упростим получившуюся систему:

      Далее проведём обычные преобразования, включая модификацию совокупностей по Правилу (9), — чтобы они содержали исключительно непересекающиеся решения:

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

      Значения переменных вложенных систем этой совокупности занесём в таблицу:

      x1x2x3x4x5x6
      01101 
      011101
      01111 
      01011 

      Если бы в исходной системе не было других переменных, то уже можно было думать об ответе. Но переменные есть, есть и пока не использованное второе правило. Припишем к имеющейся таблице значений ещё одну справа, она будет содержать значения переменных y1 … y6. Сразу учтём в ней третье правило, таким образом, во всех случаях y6 = 1:

      x1x2x3x4x5x6
      01101 
      011101
      01111 
      01011 
      y1y2y3y4y5y6
           1
           1
           1
           1

      Второе правило говорит о том, что если xj истинна, то yj может быть только истинной (1 ≤ j ≤ 5).

      x1x2x3x4x5x6
      01101 
      011101
      01111 
      01011 
      y1y2y3y4y5y6
       11 11
       111 1
       11111
       1 111

      Посчитаем количество частных решений исходной системы. Решения эти не пересекаются, ведь при преобразованиях к совокупностям применялось Правило (9); в этом можно убедиться, глядя в таблицу. Значит, для расчёта достаточно сложить число частных решений всех четырёх её систем. Первая и последняя системы дают по 8 частных решений, вторая и третья — по четыре, что в сумме составляет 24 решения.

      Ответ. 24.

Далее имеет смысл рассмотреть конкретные примеры решения нескольких задач этого типа, заимствованных из открытых официальных демо-версий. См. Оглавление рассматриваемой темы.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика