4.10. Представление логической функции в виде сднф и скнф

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

- гдеfфункция 3х переменных.

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

- гдеfфункция 3х переменных.

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

- гдеfфункция 3х переменных.

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

- гдеfфункция 3х переменных.

Логическая функция конъюнктивной нормальной формы (КНФ): - форма представления конъюнктивной функции, в которой инверсия применяется лишь непосредственно к аргументам (переменным), но не к более сложным функциям от этих аргументов.

- гдеfфункция трех переменных.

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

- гдеfфункция 3х переменных.

4.10.1. Первичные термы

Терм- это переменные, инверсии переменных, их конъюнкция и дизъюнкция.

Первичные термы:- переменные и их инверсии.

Для первичных термов будем использовать обозначение - гдеe_p = 0или1. В общем случае- подставляем сюда значенияe_p = 0или1 получим:

при e_p = 0 то

при e_p = 1 то

Такое обозначение облегчает формализацию общих соотношений для логических функций:

4.10.2. Минтермы и макстермы

Минтерм: - конъюнкция всех переменных, которые входят в прямом виде, если значение данной переменной в точке определения равно1, либо в инверсном виде, если значение переменной равно0.

Обозначение термов позволяет в общем виде записать конъюнкцию любого числа аргументов.

Минимальным термом – минтермом: - называется функция n переменных:

Vi	x1,x0
0	0 0
1	0 1
2	1 0
3	1 1

где v=(x_n-1,…,x₀), e_p = 0или1

Из данного определения следует, что имеется 2ⁿ – различных минтермовnпеременных т.к. минтерм представляетnразрядное двоичное число от0до2ⁿ –1.

Запишем все минтермы двух переменных

Макстерм- это дизъюнкция всех переменных, которые входят в прямом виде, если значение данной переменной в точке области определения равно0, либо в инверсном виде, если значение переменной равно1.

Vi	x1,x0
0	0 0
1	0 1
2	1 0
3	1 1

Максимальным термом – макстермом: - называетсяфункцияnпеременных

где v=(x_n-1,…,x₀), e_p = 0или1

Запишем все макстермы двух переменных

4.10.3. Запись функции в виде сднф и скнф

Возьмем функцию двух переменныхx₁x₀. Применим к ней терему разложения для переменнойx₁.

Далее каждую из функций иразложим по переменнойx₀.

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

В общем виде представление функции в СДНФ:

Так как значение функциитоеслииеслиотсюда СДНФ можно представить в виде:

гдеi₁ – номера точек, в которых функция.

СДНФ можно получить аналогичным способом с помощью теоремы разложения. Но можно пойти более легким путем.

Возьмем инверсию СДНФ: из данного соотношения на основании закона двойственности получим:а так какобщий вид СКНФ:

Так как значение функции тоеслииеслиотсюда СКНФ можно представить в виде:

гдеi₀ – номера точек, в которых функция.