1.6. Решение систем логических уравнений

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

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

Системы логических уравнений с одним неизвестным. Пусть задана система логических уравнений с одним неизвестным у

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

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

Возьмем теперь в качестве операции операцию Из равенства следует, что Используем еще раз эту операцию:

т. е. из равенства следует, что Итак,

а значит, логические связи, выражаемые уравнениями, не нарушаются при преобразовании последних с помощью операции (в качестве можно взять и любую из переменных х или На основании (1.42) уравнения (1.40) можно привести к виду

где Используя аксиомы (1.2) и (1.3), легко убедиться, что если то а: и наоборот: если то т. е.

а значит, операцию V можно использовать для преобразования уравнений, правая часть которых равна нулю. На основании (1.44) систему логических уравнений (1.43) можно представить в виде

т. е. любую систему логических уравнений можно свести к одному уравнению решение которого относительно у и нужно найти.

Разложив левую часть уравнения (1.45) по у, будем иметь

где

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

произвольная (полностью неопределенная) функция;

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

Из сказанного следует, что решение можно представить в виде мультиплексной функции (1.35):

Если положить то

причем решение (1.47) существует лишь при выполнении условия

Подстановка решения (1.47) в уравнение (1.46) дает

т. е., действительно, при выполнении условия (1.48) левая часть уравнения (1.46) обращается в нуль, и решение некоторая функция переменных

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

В общем случае решение где — 0 или 1 в точках, в которых функция а в остальных точках т.е. решением является неполностью определенная функция, которой соответствут целый класс полностью определенных функций.

Несмотря на кажущуюся сложность выражения (1.47), его достаточно просто применять при решении многих практических задач. Это связано с тем, что при решении вместо неизвестных в уравнения подставляются константы 0 и 1.

Пример 1. Доказать тождество Решим уравнение относительно

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

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

Пример 2. Найдем решение уравнения

следовательно, решение отсутствует.

Пример 3. Найдем решение уравнения

т. е. имеется единственное решение

Пример 4. Докажем высказанное в начале данного раздела утверждение, что из равенства не следует, что Для этого решим первое равенство относительно у:

поэтому т. е.

Пример 5. Докажем теорему, утверждающую, что если Для этого решим систему двух логических уравнений относительно у:

так как Действительно, получили, что

Алгебраическое представление логических уравнений. Если символы 0 и 1 считать числами, то все логические операции можно заменить на арифметические операции или алгебраические формулы на основании очевидных соотношений

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

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

На основании приведенных соотношений логическое уравнение (1.46) преобразуется в алгебраическое

решением которого будет Легко заметить, что при решения не существует и при

Системы логических уравнений с более чем одним неизвестным. Решение систем логических уравнений с двумя неизвестными

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

Решив систему (1.49) относительно у в соответствии с (1-47) и (1.48), получим:

где

Если функция это означает, что решение системы (1.49) относительно у существует независимо от значений Поэтому можно взять Тогда, подставив это значение в (1.50), получим:

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

которое существует только в том случае, если выполняется условие

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

В результате получены функции не зависящие от неизвестных

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

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

Пример 1. Решим относительно неизвестных у и 2 уравнение

Найдем решение уравнения сначала относительно у:

поэтому решаем уравнение относительно z:

Значит, и

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

Пример 2. Найдем решение уравнения

относительно у.

Легко убедиться, что поэтому решаем уравнение

относительно

Так как то решение исходного уравнения существует.

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

Если решить исходное уравнение относительно неизвестных в другом порядке, то функции будут иметь вид:

Сравнив решения (1.52) и (1.53), легко заметить, что полностью определенные части у них одинаковые. Решения для зависимые, Так как полностью неопределенная функция входит в оба решения. Поэтому решением уравнения (1-51) будет зависимая пара функций По выражениям (1.52) или (1.53) (результат получается один и тот же) легко вычислить значения этой пары в точках

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

Пример 3. Найдем решение уравнения относительно у:

Далее решаем уравнение

относительно

Так как то логическое уравнение решений не имеет.

Приложения систем логических уравнений. Разработанный метод решения систем логических уравнений является мощным инструментом для анализа (см. гл. 2) и синтеза (см. гл. 3) логических схем, широко используемых на практике при проектировании цифровых устройств. Так, он был применен при разработке общего метода структурного синтеза цифровых автоматов на триггерах типов и др. [10, 11]. Перечисленные триггеры описываются функциями переходов

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

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

Триггер типа Решение уравнения (1-54) относительно Т:

Для отыскания данной функции возбуждения можно воспользоваться и более простым методом — применить операцию к левой и правой частям уравнения относительно переменной

Триггер типа Решение уравнения (1.55) относительно

Приравняв последнее уравнение нулю, находим:

Подставив найденное значение К в функцию для получим:

Триггер типа Решение системы уравнений (1.56) относительно

Приравняв последнее уравнение нулю, находим:

Подставив найденное значение в функцию для получим:

Триггер типа Решение уравнения (1-57) сначала относительно а затем относительно дает:

Наиболее часто для проектирования цифровых автоматов формальными методами используются триггеры типов и функции возбуждения которых

Функции возбуждения -триггера (1.58) использовать значительно сложнее, чем функции (1.59) - (1.61), так как они взаимозависимы (полностью неопределенная функция входит и в Методика синтеза автоматов на -триггерах изложена в [10].

Триггер типа Рассмотрим пример решения уравнения

с тремя неизвестными и которое представляет собой функцию переходов D-L-триггера. Решение относительно дает

Решив уравнение

относительно получим:

Из этого следует уравнение

решением которого является Подставив найденное значение в функцию а затем в функцию окончательно получим:

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

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

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