Построение СКНФ и СДНФ по таблице истинности

СДНФ и СКНФ — описание⚠️. Правила построения дизъюнктивной и конъюнктивной формы☑️ по таблице истинности. Алгоритм, примеры и решение

Что такое СДНФ 

Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.

Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).

ДНФ выглядит следующим образом:

((A;wedge;overline B;wedge;C);vee;(B;wedge;C))

СДНФ обладает некоторыми определенными свойствами:

• включает различные элементарные конъюнкции;
• все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
• ни в одном логическом слагаемом не содержится переменная и её отрицание.

К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.

Источник: http://wiki.fenix.help/informatika/sdnf

Основные правила при построении СДНФ

СДНФ является дизъюнкцией конституента единицы, соответствующей входящей совокупности логических переменных, при которых функция достигает показателя «1». Она удовлетворяет 3 условия:

• Включает разные элементарные конъюнкции.
• Конъюнкции включают разные переменные.
• Все из элементарных конъюнкций включают в одной и той же последовательности все имеющиеся логические переменные этой ДНФ.

Привести к СДНФ можно всякую булеву формулу за исключением той, что не выступает тождественно ложной. Получению СДНФ предшествует создание таблицы истинности. Чтобы построить СДНФ следует записать произведение для каждой совокупности присутствующих переменных. Важно учесть, что логические переменные со значением «0» нужно брать с отрицанием.

Реклама

Реклама

Не каждый студент может себе позволить за семестр в ВУЗе отдать100 000 ₽. Но круто, что естьгрантына учебу.Грант-на-вуз.рф–этовозможность учиться на желанной специальности.По ссылкекаждый получит бонус от300 ₽до100 000 ₽–грант-на-вуз.рф

Источник: http://zen.yandex.ru/media/studystudent/sdnf-sknf-kak-postroit-s-ispolzovaniem-tablicy-5e8596abd421bb7d8627fe9e

Совершенная дизъюнктивная нормальная форма (СДНФ)

Для реализации таблицы истинности при помощи логических элементов «И» (СДНФ) достаточно рассмотреть только те строки таблицы истинности, которые содержат логические «1» в выходном сигнале. Строки, содержащие в выходном сигнале логический 0 в построении цифровой схемы не участвуют. Каждая строка, содержащая в выходном сигнале логическую «1», реализуется схемой логического элемента «И» с количеством входов, совпадающим с количеством входных сигналов в таблице истинности.

Входные сигналы, описанные в таблице истинности логической единицей, подаются на вход этого логического элемента непосредственно, а входные сигналы, описанные в таблице истинности логическим нулем, подаются на вход этого же логического элемента «И» через инверторы. Объединение сигналов с выходов логических элементов «И», реализующих отдельные строки таблицы истинности, производится при помощи логического элемента «ИЛИ». Количество его входов определяется количеством строк в таблице истинности, в которых в выходном сигнале присутствует логическая единица.

Рассмотрим конкретный пример. Пусть цифровому устройству необходимо реализовать таблицу истинности, приведенную на рисунке 1:

Рисунок 1. Произвольная таблица истинности

Для синтеза цифровой схемы, реализующей сигнал Out0, достаточно рассмотреть строки, выделенные красным цветом. В таблице истинности три строки, содержащие единицу в выходном сигнале Out0, поэтому в формуле СДНФ будет содержаться три произведения входных сигналов — термов, а точнее минтермов:

Так как количество переменных в каждом терме (ранг терма) данного логического выражения равно, то такое логическое выражение называется совершенным. (Совершенная Дизъюнктивная Нормальная Форма — СДНФ)

Полученное логическое выражение реализуются микросхемой D2 в схеме, приведенной на рисунке 2. Как и в формуле, каждая строка (терм) реализуется своим логическим элементом «И», затем выходы этих логических элементов объединяются при помощи логического элемента «ИЛИ». Количество входов логического элемента «И» (ранг минтерма) в СДНФ однозначно определяется количеством входных сигналов в таблице истинности. Количество этих элементов, а значит и количество входов в логическом элементе «ИЛИ» определяется количеством строк с единичным сигналом на реализуемом выходе цифровой схемы.

Рисунок 2. Принципиальная схема цифрового устройства, реализующая таблицу истинности, приведенную на рисунке 1

Для построения принципиальной схемы, реализующей сигнал Out1, достаточно рассмотреть строки, выделенные зеленым цветом. Эти строки реализуются микросхемой D3. Принцип построения этой схемы не отличается от примера, рассмотренного выше. В таблице истинности присутствуют всего три строки, содержащие единицу в выходном сигнале Out1, поэтому в формуле СДНФ выхода Out1 будет содержаться три произведения входных сигналов:

Обычно при построении цифровых схем после реализации таблицы истинности производится минимизация схемы по законам алгебры логики, но для упрощения понимания материала сейчас минимизация производиться не будет. Это оправдано еще и с той точки зрения, что неминимизированные схемы обычно обладают максимальным быстродействием. При реализации схемы на ТТЛ микросхемах быстродействие всего узла будет равно быстродействию одиночного инвертора (см. описание ТТЛ микросхем).

По СДНФ форме логического выражения обычно строятся современные микросхемы большой интеграции — программируемые логические интегральные схемы (ПЛИС), такие как программируемые логические матрицы (ПЛМ), программируемые матрицы логики ПМЛ или CPLD.

Источник: http://digteh.ru/digital/SintSxem.php

Как пользоваться калькулятором

1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
2. Укажите действия, которые необходимо выполнить с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем «С решением»
4. Нажмите на кнопку «Построить»

Источник: http://hd01.ru/info/kak-najti-sknf-i-sdnf/

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.

Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

• И (AND): & • ∧ *
• ИЛИ (OR): ∨ +
• НЕ (NOT): ¬ !
• Исключающее ИЛИ (XOR): ⊕ ^
• Импликация: -> → =>
• Эквивалентность: =

Что умеет калькулятор

• Строить таблицу истинности по функции
• Строить таблицу истинности по двоичному вектору
• Строить совершенную конъюнктивную нормальную форму (СКНФ)
• Строить совершенную дизъюнктивную нормальную форму (СДНФ)
• Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
• Определять принадлежность функции к каждому из пяти классов Поста
• Строить карту Карно
• Минимизировать ДНФ и КНФ
• Искать фиктивные переменные

Источник: http://hd01.ru/info/kak-najti-sknf-i-sdnf/

Правила построения по таблице истинности

Дизъюнктивная форма

Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.

Конъюнктивная форма

Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.

Источник: http://wiki.fenix.help/informatika/sdnf

Что такое таблица истинности?

Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n – число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.

Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.

Источник: http://hd01.ru/info/kak-najti-sknf-i-sdnf/

См. также

• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма
• Совершенная конъюнктивная нормальная форма

Источник: http://wiki2.org/ru/Совершенная_дизъюнктивная_нормальная_форма

Примечания

1. ↑ Виноградова М.С., Ткачев С.Б. Булевы функции. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. — 32 с.
2. ↑ Математическая логика. — Пермь: Изд-во ПГТУ, 1998. — 17 с.

Эта страница в последний раз была отредактирована 11 апреля 2021 в 13:20.

Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.

Источник: http://wiki2.org/ru/Совершенная_дизъюнктивная_нормальная_форма