Лекции - Введение в математическую логику. Части 1 - 2 - файл Лекции - Введение в математическую логику №1.DOC
Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы
Дизъюнктивная нормальная форма
Элементарной конъюнкцией называется конъюнкция переменных высказываний и или их отрицаний. Элементарной дизъюнкцией называется дизъюнкция переменных высказываний и или их отрицаний. Дизъюнктивной нормальной формой ДНФ данной формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций. Конъюнктивной нормальной формой КНФ данной формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций. Для того чтобы построить по данной формуле алгебры логики равносильную ей ДНФ или КНФ необходимо выразить все операции через дизъюнкцию, конъюнкцию и отрицание, воспользоваться законом де Моргана для того, чтобы отрицания стояли лишь над элементарными переменными высказываниями, раскрыть скобки для построения ДНФ или воспользоваться дистрибутивным законом для построения КНФ. Всякая функция алгебры логики может быть представлена в виде формулы, содержащей только операции конъюнкции, дизъюнкции и отрицания. Элементарная конъюнкция дизъюнкция называется правильной, если в нее каждая переменная входит не более одного раза, включая ее вхождение и под знаком отрицания. Элементарная конъюнкция дизъюнкция называется полной относительно переменных x, y, z, если в нее входит каждая из этих переменных не менее одного раза, включая и их вхождение под знаком отрицания. Совершенной дизъюнктивной нормальной формой СДНФ относительно переменных x, y, z, называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильные и полные относительно переменных x, y, z. Совершенная дизъюнктивная нормальная форма СДНФ для булевой функции , не равной тождественно нулю, имеет вид:. В конъюнкции мы записываем , если , и , если. Совершенной конъюнктивной нормальной формой СКНФ относительно переменных x, y, z, называется конъюнктивная нормальная форма, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильные и полные относительно переменных x, y, z. Совершенная конъюнктивная нормальная форма СКНФ для функции , отличной от тождественной единицы, имеет вид:. В дизъюнкции мы записываем , если , и , если. При этом приходится раскрывать скобки с использованием правила поглощения или правила Блейка. Отрицание верхнее полученной ДНФ снова по правилу де Моргана сразу дает нам КНФ:. Таким образом, из КНФ получена СКНФ. Привести выражение к ДНФ. Понижаем отрицания по правилу де Моргана. Построить СДНФ для функции. Построить СКНФ для функции. Привести формулу к СДНФ с помощью эквивалентных преобразований. Аналогично поступают и с другими переменными, поэтому СДНФ для данной функции имеет вид: Таким образом, СКНФ для данной функции имеет вид:. Заметим, что по определению СДНФ и СКНФ, переменные в каждой конъюнкции и дизъюнкции соответственно должны следовать в одинаковом порядке. Привести функцию к ДНФ, затем к СДНФ, с помощью законов алгебры логики: Любую функцию кроме тождественного нуля можно представить в виде СДНФ. На практике наиболее важной представляется нахождение минимальной ДНФ, но алгоритм ее нахождения по существу является вариантом перебора всех равносильных ДНФ. Проще всего находить сокращенную ДНФ по карте Карно. Производится операция обобщенного склеивания по формуле до тех пор, пока это возможно: Операции применяются слева направо: Ко второму столбцу выписываем одну переменную —. К следующим четырем единицам выписываем переменную —. СДНФ функции содержит по числу единиц шесть дизъюнктных слагаемых, но ее сокращенная ДНФ содержит после объединения единиц всего две буквы: С помощью карт Карно по данной таблице истинности для функции четырех переменных и найти ее сокращенную ДНФ: Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию. Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие называемые также вентилями , а также триггер. С помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройств компьютера. Обычно у вентилей бывает от двух до восьми входов и один или два выхода. Переключательная схема — это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подается и с которых снимается электрический сигнал. Каждый переключатель имеет только два состояния: Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю. Всей переключательной схеме также можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю — если не проводит. Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется функцией проводимости. При рассмотрении переключательных схем возникают две основные задачи: Простейшая схема, содержащая один переключатель P , имеет один вход и один выход:. В этом случае схема пропускает ток. Дизъюнкции двух высказываний P Q соответствует схема с параллельным соединением контактов:. Так как любая функция алгебры логики представима в виде ДНФ или КНФ , то для любой булевой функции можно составить соответствующую схему, а каждой схеме соответствует некоторая формула алгебры логики, задающая некую булеву функцию. Организация расчетов на предприятии. Формы способы реализации норм права. Буржуазные реформы гг. В качестве исторической формы розыскной процесс прошел три этапа развития. Вид практики, способы и формы ее проведения Виды и формы государственного кредита Виды и формы денег, особенности их трансформации Виды и формы систематизации нормативных актов. Последнее изменение этой страницы: Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии.
Видно ли на узи метастазы
Play маркет андроид игры
Галакси с4 дуос характеристики
Как утеплить лоджию изнутри своими руками видео
7 класс природные зоны африки презентация
Приказ 222 от 03.08 2016
Тп предпринимателей курган каталог
Блэк десерт рецепты алхимии
Потливость ног у мужчин причины лечение
Третье веко у котенка причины
Скачать торрент игру bio inc
Турникеты официальный сайт
Инструкция по заполнения пу 5
Медведково мытищи 169 расписание
Понятие крупный размер