logo

Скнф и сднф

Мы знаем 2 способа задания логических функций: формулой и таблицей истинности. По формуле легко составляется таблица. На практике при конструировании различных электронных устройств часто возникает обратная задача - от таблицы истинности перейти к формуле.

Предварительно введём следующие определения.

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

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

Всякую дизъюнкцию элементарных конъюнкций, назовём дизъюнктивной нормальной формой, то есть ДНФ.

Всякую конъюнкцию элементарных дизъюнкций, назовём конъюнктивной нормальной формой, то есть КНФ.

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

Например, для переменных X, Y, Z

Название

Соответствует определению

Не соответствует определению

Элементарная дизъюнкция

X V X

X V Z

X V Y V Z

X V Y  X

Элементарная конъюнкция

X X

X Z

X YX

X V Y  X

ДНФ

XX V XYZ

XY V Y V XZ

XY

Но ДНФ можно построить для всякой формулы путем ее преобразования

КНФ

(X V Y V X)(X V Z)

X (X V Y)(Y VZ)

XY

Но КНФ можно построить для всякой формулы путем ее преобразования

СДНФ

XYZ V XYZ

XY VY V XZ

СКНФ

(X V Y V Z)(X VY V Z)

(X V Y V X)(X V Z)

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4