История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-06-11 | 303 |
5.00
из
|
Заказать работу |
|
|
Тема: Решение задач по теме «Булева алгебра»
Цель: научитьсяприменять законы алгебры логики.
Общие теоретические сведения
Операции над высказываниями.
Отрицанием высказывани я х называется новое высказывание, которое истинно, если высказывание ложное и наоборот. Таблица истинности операции отрицания имеет вид:
Дизъюнкцией двух высказываний x и y(логическое «или») называется новое высказывание, которое будет истинным тогда когда, когда хотя бы одно из высказываний будет истинным.
Конъюнкцией двух высказываний x и y(логическое «и») называется новое высказывание, которое будет истинным тогда когда, когда оба высказывания истины. Обозначение операции конъюнкция - & (
Импликацией двух высказываний x и y(«если – то») называется новое высказывание, которое ложно тогда, когда х(предпосылка) - истинно, а у(следствие) - ложно.
Эквивалентностью двух высказываний x и y(«тогда и только тогда») называется новое высказывание, которое будет истинно, если высказывания х и у будут одновременно истинны или ложны.
Неодназночностью (суммой по модулю два) двух высказываний x и y(«тогда и только тогда») называется новое высказывание, которое будет истинно тогда когда одно из высказываний х или у истинно, а другое ложно.
Штрих Шеффера (логическое «и - не») высказываний x и y - это новое высказывание, которое будет ложно тогда и только тогда когда оба высказывания истинны.
|
Стрелка Пирса (логическое «или - не») высказываний x и y - это новое высказывание, которое будет истинно тогда и только тогда когда оба высказывания ложны.
Для операций справедливы следующие приоритеты: ù, &, Ú, ®, «.
Формулы равносильности.
1) Коммутативность
АVВ º ВVА А&В º В&А
2) Ассоциативность
АV(ВVС) º (АVВ)VС А&(В&С) º (А&В) &С
3) Дистрибутивность
АV(В&С) º (АVВ)&(АVС) А&(ВVС) º (А&В)V(А&С)
4) Идемпотентность
АVА º А А&А º А
5) Поглощение
АV(А&В) º А А&(АVВ) º А
6) Закон де Моргана
º & º V
7) Закон исключающий третьего
АV1 º 1 А&1 º A
8) Закон противоречия
AVÆ º A A&Æ º Æ
9) Закон двойного отрицания
º A
10) º 1, º 0
11) A®B º VB
12) A«B º (A®B)&(B®A)
13) AÅB º A& V &B
14) A | B º º V
15) A¯B º º &
Дизъюнктивной нормальной формой (ДНФ) формулы называется выражение вида:
, (2.4)
где - элементарная конъюнкция.
Конъюнктивной нормальной формой (КНФ) формулы называется выражение вида:
, (2.5)
где - элементарная дизъюнкция.
Любую формулу можно представить в виде ДНФ или КНФ.
ПРИМЕР
Пусть дана формула
Требуется получить ДНФ и КНФ данной формулы.
Применяя формулы равносильности, получаем КНФ :
Применяя формулы равносильности, получаем ДНФ :
Совершеннойдизъюнктивной нормальной формой(СДНФ) формулы называется такая ДНФ, для которой выполняются следующие условия:
1. Все элементарные конъюнкции, входящие в ДНФ , различны.
2. Все элементарные конъюнкции, входящие в ДНФ , содержат литеры, соответствующие всем переменным.
3. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит двух одинаковых литер.
|
4. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит переменную и ее отрицание.
СДНФ можно получить двумя способами:
1. по таблице истинности;
2. с помощью равносильных преобразований.
Совершеннойконъюнктивной нормальной формой(СКНФ) формулы называется такая КНФ, для которой выполняются следующие условия:
1. Все элементарные дизъюнкции, входящие в КНФ , различны.
2. Все элементарные дизъюнкции, входящие в КНФ , содержат литеры, соответствующие всем переменным.
3. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит двух одинаковых литер.
4. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит переменную и ее отрицание.
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!