Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2020-12-06 | 189 |
5.00
из
|
Заказать работу |
|
|
1) В алгебре логики имеют место следующие соотношения:
2) В алгебре логики имеют место следующие законы:
Закон отрицания (инверсия)
а) отрицание конъюнкции
Отрицание от конъюнкции равно дизъюнкции отрицаний.
б) отрицание дизъюнкции
Отрицание от дизъюнкции равно конъюнкции отрицаний.
Переместительный закон
Логические функции «И» и «ИЛИ» подчиняются переместительному закону:
(«И»)
(«ИЛИ»)
Сочетательный закон
Логические функции «И» и «ИЛИ» подчиняются сочетательному закону:
(«И»)
(«ИЛИ»)
Дистрибутивный (распределительный) закон
Непосредственной проверкой можно убедиться, что операции логического сложения и логического умножения подчиняются дистрибутивному (распределительному) закону: одинаковые переменные в конъюнкциях и дизъюнкциях можно выносить за скобку.
а) дистрибутивный закон умножения по отношению к сложению имеет такой же вид, как и для алгебраического сложения и умножения, например:
(распределение конъюнкции по дизъюнкции),
б) дистрибутивный закон сложения по отношению к умножению является специфичным для алгебры логики и не имеет аналогов в обычной алгебре:
(распределение дизъюнкции по конъюнкции).
Доказательство:
Согласно основным соотношениям алгебры логики выражение в скобках
равно1.
Непосредственно из дистрибутивного закона вытекают следующие правила, которые используются при преобразовании функций, при их минимизации, т.е. приведении их к виду с наиме ньшим числом конъюнкций минимально возможного ранга. После этого функция не поддается дальнейшему упрощению.
3) Из первой формы дистрибутивного закона вытекают следующие правила:
|
Правило склеивания для ДНФ
а) (для двух переменных)
Доказательство:
,
б) (для трех переменных)
Доказательство:
Это правило позволяет заменить два члена, имеющие общую часть (а) – X и б) - ) и аргумент (а) – Y и б) -X) с инверсией в одном члене, одним общим членом (а) – X и б) - ) – т.е. произвести склеивание.
Правило поглощения для ДНФ.
а) (для двух переменных)
Доказательство:
б) (для трех переменных)
Доказательство:
.
Это правило позволяет заменять 2 (или больше – 3) члена, один из которых входит в другой (конъюнкция) в качестве сомножителя, одним этим членом, т.е. произвести «поглощение» члена конъюнкции общим членом.
Из второй формы дистрибутивного закона вытекает правило свертки.
Правило свертки для ДНФ
Доказательство:
Из второй формы дистрибутивного закона имеем:
или
Доказательство:
Это правило позволяет упростить один из членов дизъюнктивной нормальной формы.
Аналогичные формулы существуют для преобразования конъюнктивных нормальных форм.
Правило склеивания для КНФ
Доказательство:
Правило поглощения для КНФ
Доказательство:
Правило свертки для КНФ
Доказательство:
Рассмотрим следующий пример:
Пусть задана логическая функция:
F(A, B, C, D) =
1) Преобразуем член с инверсией
Доказательство:
=
2) Раскрываем скобки:
(конъюнкция ).
3) Преобразуем член с конъюнкцией
4) Подставляем преобразованные выражения в исходную формулу:
F(A, B, C, D) =
Это нормальная дизъюнктивная форма. Применяя к формулы склеивания и поглощения, можно ее упростить:
1) к 1-му и 2-му членам применим формулу склеивания:
2) к 3-ему и 5-му членам применим формулу поглощения:
Получим: F(A, B, C, D) =
Результат:
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!