Применение к переключательным схемам

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

Пример 1. Схема

соответствует формуле .

Схемы, которым соответствуют равносильные формулы, обладают одинаковыми переключательными свойствами.

Укажем метод (Квайна), позволяющий для формулы , заданной в СДНФ, найти равносильную в ДНФ и содержащую наименьшее число знаков .

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

Дизъюнктивные члены, не допускающие сокращения, называются простыми импликантами ранга n. С членами, полученными после первого сокращения, проводим повторно сокращения, а не допускающие сокращения члены назовем простыми импликантами ранга n – 1, и т.д.

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

Пример 2. Цепи

отвечает пропозициональная формула , которая равносильна

При получении этой цепочки эквивалентных формул использовалась теорема об эквивалентной замене и некоторые логические законы.

Таким образом, рассматриваемая цепь эквивалентна более простой цепи

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

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

А	В	С
и	и	и
и	и	л
и	л	и
и	л	л
л	и	и
л	и	л
л	л	и
л	л	л

Составим таблицу истинности, описывающую булеву функцию, реализуемую искомой схемой. Функция описывается формулой

.

Цепь, удовлетворяющая условиям задачи

или

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

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

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

Контрольные вопросы и упражнения

1. Какими переключательными свойствами обладает схема, соответствующая тавтологии; тождественно ложной формуле?

2. Доказать, что .

3. Почему дизъюнкция всех простых импликант равносильна исходной формуле?

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

а) ;

б) ;

в) ;

г) .

5. Для данной схемы написать соответствующую формулу алгебры высказываний:

а)

б)

6. Построить схему голосования для комитета из 4 членов (один из них - председатель). Решение принимается прямым большинством. В случае равенства голосов вопрос решает председатель.

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

8. Минимизировать формулы по методу Квайна:

а) ;

б) ;

в) ;

г) .

ТЕМА IV

Дата добавления: 2015-11-14