Совершенные формы записи логических функций СКНФ и СДНФ

Формы логических функций.

Дизъюнктивная и конъюнктивная.

Элементарная конъюнкция - такая конъюнкция, в которую входят только переменные и их отрицания, например,

Элементарной называется дизъюнкция, представляющая собой логическую сумму переменных и их отрицаний, например,

Элементарные конъюнкции (дизъюнкции) могут характеризоваться рангом, равным количеству переменных в конъюнкции (дизъюнкции).

ДНФ

КНФ

Эти формы имеют две основные отличительные способности:

1. Все элементарные конъюнкции и дизъюнкции имеют одинаковый ранг.
2. В элементарные конъюнкции (дизъюнкции) входят все те переменные или их отрицания, от которых зависит функция.

Функция F=x1x2+ x1x3+x1x2x3содержит конъюнкции одинакового ранга, но записана в ДНФ, а не в СДНФ. Это объясняется тем, что элементарные конъюнкции не содержат всех тех переменных или их отрицаний, от которых зависит функция. Функция записана в СДНФ.

Функция в СКНФ

Следствия из законов:

1. Правило поглощения.

Данное правило является следствием из распределительного закона. Оно может быть записано в следующем виде:

х1+х1х2+х1х2х3=х1

Видно, что в каждую из элементарных конъюнкций входит переменная х1

и суть поглощения заключается в том, чтобы функция с меньшим рангом, если она входит в элементарные конъюнкции с меньшим рангом, поглотила те, что с большим.

2. Правило свертки.

Правило является следствием второго распределительного закона:

а)

б)

Правило свертки говорит о том, что при наличии переменной высшего ранга и переменной с отрицанием, которая входит в один ранг больше (случай а)), мы можем сократить это отрицание и х1свертывается.

1. Правило расширения:

Понятие расширения объясняется возможностью добавления к правой части конъюнкции х2х3

1. Правило склеивания.

Правило склеивания базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлениями одной переменной. Например, конъюнкции 58.08 являются попарно соседними. В первой паре конъюнкции отличаются представлением х2, а во второй представлением х1.

При решении логических задач следует строго соблюдать порядок выполнения логических операций, согласно их приоритету:

1. Вычисляется инверсия
2. Конъюнкция
3. Дизъюнкция
4. Равнозначность

Дата добавления: 2014-12-08