Схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ
Схема И реализует конъюнкцию двух или более логических значений.
Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.
Схема НЕ (инвертор) реализует операцию отрицания. Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0.
Схема И—НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: 
, где 
читается как "инверсия (x и y)".
Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: 
, где 
, читается как "инверсия (x или y)".
Основные законы в алгебре логики
В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:
Составление таблицы истинности
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:
(0, 0), (0, 1), (1, 0), (1, 1).
|
|
|
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Пример:
1. Составим таблицу истинности для формулы 
, которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.
Упрощение логической формулы.
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Под упрощением формулы, не содержащей операций импликации и эквивалентности, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
|
|
|
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры.
Примеры:
1. 
.
Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами;
2. 
.
Применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);
3. 
Повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);
Дата добавления: 2018-04-05; просмотров: 803; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!