Применение основ.равносильностей ал-ры выск-й

Р!две обл-ти прим-я ф-л (А.В.)

I. Анализ рассуждений.При док-ве теорем разл.мат-х теорий мы помимо фактов этих теорий используем некот. лог. рассуждения.Эти лог.рассуждения на языке логики м.выраж-ся некот.ф-ми.Чтобы некот. рассуждение б.лог.оправданным в прим-и, нужно, чтобы соответств.ему ф-ла была тождественно истинной.Способ док-ва от противного:Пусть требуется доказать теорему вида p . Полагаем, что q неверно, т.е. верно . Учитывая это предположение, пытаемся придти к противоречию, т.е. док-ть, что нек.факт p выполняется и, одновp-но, не выпол-ся, а значит справедливо . Если мы это сумеем сделать, то делаем заключение: q– истинно. На языке логики выск-й это способ рассуждений м.записать ф-лой:

Проверим, явл-ся ли эта ф-ла тождественно ист-й:

~ ~ ~ ~ ~ ~1.

Т.к. ф-ла тождественно истинна, то применение метода от противного при док-ве логически оправдано.2) Метод рассм-я частных случаев. Это способ док-ва м.выразить ф-лой:

Проверим ее:

(17)~

~ (12)~

~ (13,16)~

~ (1)~

~ ~

~ ~

~ ~ … ~

~ ~

~ ~

~ ~

~ ~

~ ~ …~ ~

~ (21)~ (23)~1.

II. Логические цепи.В лог.устр-вах исп-ся 3 основ-х элемента «И» – конъюнктор, «ИЛИ» – дизъюнктор и инвертор «НЕ». Они представлены на рис. 1.

Эл-нты И и ИЛИ м.иметь несколько входов, на каждый из кот-х подается двоичный сигнал, принимающий значения 0 или 1. Выход элемента И равен нулю всегда, кроме случая, когда все входы равны единице; в этом случае выход элемента И тоже равен единице. Выход элемента ИЛИ равен единице всегда, кроме случая, когда все его входы равны нулю. Инвертор в противоп-сть элем-м И и ИЛИ имеет только один вход, сигнал на его выходе противоположен сигналу на входе: если вход.сигнал имеет значение 0, то сигнал на выходе приним-т знач-е 1; если входной сигнал приним-т знач-е 1, то сигнал на выходе равен 0.Практические схемы, реализующие логич.св-ва этих 3-х элем-в, м.б.построены из транзисторов, сопротивлений, диодов и др. компонентов. Естест-но полагать, что математические модели этих схем (комбинационные схемы) реализуют одну или несколько булевых ф-ций, к-е однозначно опр-ся структурой схемы.Так как дизъюнкция, конъюнкция и отрицание образуют полную с-му булевых ф-ций, то любую булеву ф-цию м.реализовать схемой из дизъюнкторов, конъюнкторов и инверторов с n входами и одним выходом. Для

этого м., н-р, для данной булевой ф-кции найти СДНФ или СКНФ, выполнить упрощение и затем синтезировать полученную ф-улу в виде комбинационной схемы из элементов И, ИЛИ и НЕ.Пр-р: построить комбинационную схему, реализующую ф-цию F, зад.таблицей истинности:

CДНФ: – 10 элементов;

F ~ ~ ~ ~ ~ ~ ~ ~ – получена после упрощения из СДНФ – 6 элементов (рис.2);

СКНФ: – 6 элементов;

~ – получена из СКНФ по принципу двойственности – 7 элементов (рис. 3).

Полезной комбинацией элементов И, ИЛИ и НЕ явл-ся двоичный сумматор с двумя входами, изображенный на рис.4. Этот элемент обозначается символом Å.

С пом-ю разл. способов каскадного соединения двоичных сумматоров с двумя входами м.построить двоичный сумматор с N входами.