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

Скнф и сднф - что это?

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

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

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

КНФ:

ДНФ:

Совершенно конъюнктивная НФ - конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых, пример:

СКНФ:

 

Совершенно дизьюнктивная НФ - дизьюнкция коньюнкций, причём в каждой коньюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых коньюнкций, в каждой коньюнкции нет одинаковых слагаемых, пример:

СДНФ:

_{Взаимозаменяемые обозначения:}

логика	булева алгебра
∨	+
∧	∙

 

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

Пример: Восстановите логическую функцию по ее таблице истинности:

x	y	z	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

 

 

РЕШЕНИЕ

СДНФ составляется на основе таблицы истинности по следующему правилу:

Для каждого набора переменных, при котором функция равна 1, записывается произведение, в котором с отрицанием берутся переменные, имеющие значение «0».

x	y	z	F
0	0	0	1
0	0	1	1
1	0	0	1
1	0	1	1
1	1	1	1

 

Получаем СДНФ:

СКНФ составляется на основе таблицы истинности по правилу:

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

x	y	z	F
0	1	0	0
0	1	1	0
1	1	0	0

Получаем СКНФ:

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

Решение:

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

Схема устройства

Логические функции и элементы

ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ

Для n - логических переменных (аргументов) существует 2ⁿ их комбинаций или двоичных наборов. На каждом таком наборе может быть определено значение функции 0 или 1. Если значения функции отличаются хотя бы на одном наборе, функции - разные. Общее число переключательных функций (ПФ) от n аргументов равно N=2²ⁿ. Для n=2, N=16. При n=3, N=256 и далее очень быстро растет. Практическое значение имеют 16 функций от 2-х переменных, т.к. любое сложное выражение можно рассматривать как композицию из простейших. В таблице 1 приведены некоторые из ПФ для n=2. i-номер набора входных переменных x1 и x0.

ЗАПОМНИТЕ СЛЕДУЮЩИЕ ОПРЕДЕЛЕНИЯ. Функция "И" равна единице, если равны единице ВСЕ ее аргументы. Функция "ИЛИ" равна единице, если равен единице ХОТЯ БЫ один аргумент. Функция "ИСКЛЮЧАЮЩЕЕ ИЛИ" (XOR) равна единице, если равен единице ТОЛЬКО один ее аргумент.

 

ЛОГИЧЕСКИЙ БАЗИС

Набор простейших ЛФ, позволяющих реализовать любую другую функцию называется логическим базисом (ЛБ). Функции И, ИЛИ, НЕ не являются минимальным ЛБ, т.к. сами могут быть представлены через другие функции, например через F8(ИЛИ -НЕ) или F14(И - НЕ).

Следовательно базис "И - НЕ" является минимальным. Реализацию НЕ,И,ИЛИ в базисе "ИЛИ - НЕ" произвести самостоятельно, используя перечисленные аксиомы.

 

БАЗОВЫЙ ЛОГИЧЕСКИЙ ЭЛЕМЕНТ

На рисунке приведена упрощенная схема И-НЕ и его условное обозначение.

Напряжения на базах транзисторов VT1 и VT2 находятся в противофазе и, если x0*x1=1, то нижний транзистор открыт, а верхний закрыт, так как ~(x0*x1)=0. Потенциал коллектора VT2 в этом случае примерно равен нулю и следовательно y=0. При других значениях x0 и x1 нижний транзистор закрыт, а верхний открыт и на выходе схемы - высокий уровень, т.е. схема работает как элемент И-НЕ. Выходы нескольких БЛЭ категорически нельзя соединять вместе, потому что, если n-1 элементов находятся в состоянии "1", а n-ый в состоянии "0", то n-1 транзисторов VT1 будут "сливать" (sink) токи в единственный транзистор VT2 n-го элемента. Суммарный ток может превысить допустимое значение и VT2 выйдет из строя.

ТРИСТАБИЛЬНЫЕ ЭЛЕМЕНТЫ

Наряду с двумя логическими состояниями существует третье технологическое состояние, когда выход элемента отключается от внутренней схемы. При этом сопротивление между выходом и "землей" становится очень большим и выход микросхемы не оказывает никакого влияния на подключенные к нему выходы других микросхем. Выходы нескольких таких элементов также могут соединяться вместе. Такое включение, разновидность "монтажного И", применяется там, где несколько источников сигналов по очереди подключаются к входам одного или нескольких приемников, не мешая друг другу. Третье состояние называют также высокоимпедансным или Z - состоянием. Схема И-НЕ с Z-состоянием выхода приведена на рис.5. слева, а ее условное обозначение - справа.

Если сигнал ~OE=0, транзистор VT3 закрыт и включенные встречно диоды не оказывают влияния на логические выходы элемента И. Напряжения на базах транзисторов VT1 и VT2 находятся в противофазе и, если x0*x1=1, то верхний транзистор закрыт, а нижний открыт. Потенциал коллектора VT2 примерно равен нулю и следовательно y=0. При других значениях x0 и x1 нижний транзистор заперт, а верхний открыт и на выходе схемы - высокий уровень, т.е. при ~OE=0 схема работает как обычный элемент И-НЕ. Картина существенно изменится при ~OE=1. Транзистор VT3 откроется до насыщения и на базах транзисторов VT1 и VT2 потенциал опустится примерно до нуля, запирая их. Выход "y" окажется отключенным от внутренней логической схемы. На схемах тристабильные элементы обозначаются ромбом с поперечной чертой или буквой Z.

Такие элементы используются там, где необходима передача инфориации по одной линии от нескольких источников к одному или нескольким приемникам. Причем, так как линия одна, то чтобы выходы пассивных источников не искажали информацию на выходе активного источника, они должны переводиться в третье состояние. Z - состояние используется по этой причине в микросхемах памяти, шинных формирователях.

· Дополнительный инверсный вход относится к категории управляющих или функциональных. Функция входа зашифрована в его обозначении (Output Enable - разрешение выхода (~OE)),а значение активного уровня на этом входе,при котором функция выполняется, равно 1, если вход прямой, и равно 0, если вход инверсный, как на схеме.

 

ТАБЛИЦА КАРНО

Таблица Карно (ТК) это видоизмененная запись таблицы истинности. Для функции мажоритарности из последнего примера (ТК) выглядит следующим образом:

Правила построения ТК следующие: 1)Количество клеток ТК равно количеству строк таблицы истинности. 2)Слева и сверху располагаются значения аргументов. Порядок размещения аргументов таков, что в двух соседних по горизонтали и вертикали клетках отличается значение только одного аргумента (поэтому соседними считаются и клетки, находящиеся на противоположных краях таблицы). 3)В клетки заносятся соответствующие значения ЛФ. 4)Единичные клетки объединяются в прямоугольники (импликанты) по 2^i клеток. 5)Для каждого прямоугольника записывается произведение тех аргументов, которые в соседних клетках не изменяют своего значения. 6)Переменные входят в произведение в прямом виде, если их значение в соседних клетках равно 1, в противном случае в инверсном. 7)Полученные произведения складываются по ИЛИ в искомую ЛФ.

В примере имеется 3 прямоугольника - A,B,C, причем Ya = x2*x0 (x1 в соседних клетках меняет свое значение, поэтому в конъюнкцию не входит). Yb = x1*x0 и Yс = x2*x1.

Yмажор = Ya + Yb + Yc = x2*x0 + x1*x0 + x2*x1. (13)

Соответствующая схема (рис.7.) проще, чем на рис.6.

 

1.12 ПРЕОБРАЗОВАНИЕ ЛФ К БАЗИСУ "И-НЕ" И "И-ИЛИ-НЕ"

Применяя к выражению (13) аксиому двойного отрицания (9) получим:

Yмажор =~(~(x2*x0 + x1*x0 + x2*x1)) (14)

Формуле (14) соответствует схема (рис.8,слева) в базисе И-ИЛИ-НЕ.

Применяя к выражению (14) соотношение двойственности (11) получим ~(~(x2*x0) * ~(x1*x0) * ~(x2*x1)). Последнему выражению соответствует схема в базисе И-НЕ (рис.8, справа).

 

Скнф и сднф - что это?

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

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

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

КНФ:

ДНФ:

Совершенно конъюнктивная НФ - конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых, пример:

СКНФ:

 

Совершенно дизьюнктивная НФ - дизьюнкция коньюнкций, причём в каждой коньюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых коньюнкций, в каждой коньюнкции нет одинаковых слагаемых, пример:

СДНФ:

_{Взаимозаменяемые обозначения:}

логика	булева алгебра
∨	+
∧	∙

 

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

Пример: Восстановите логическую функцию по ее таблице истинности:

x	y	z	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

 

 

РЕШЕНИЕ

СДНФ составляется на основе таблицы истинности по следующему правилу: