Нормальные формы логических функций

а) КНФ - конъюнктивная нормальная форма: y = ( v v v...) & (x1 v v v...) &...

б) ДНФ - дизъюнктивная нормальная форма: y = x₁&x₂&x₃&... v &x₂&x₃&... v...

Каждая группа, входящая в ДНФ, называется ДИЗЪЮНКТ (ЛЕКСЕМА, ТЕРМ).

Если в каждой группе присутствуют все имеющиеся переменные (с отрицаниями или без), то такая форма называется СОВЕРШЕННОЙ (сДНФ – все ТЕРМЫ имеют максимальный порядок).

ДНФ - более наглядна и удобна. У нее допускается более компактная запись: y = x₁x₂x₃ v x₂x₃ v...

Преобразование: ДНФ <=> Таблица истинности

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

Разбиваем ее на термы и последовательно заполняем результирующий столбец таблицы.

Сначала ставим единицы в тех строках, где первый терм (x₁&x₂&x₃) возвращает единицу:

x1	x2	x3	Y

Затем, то же самое проделываем и для второго ( ):

x1	x2	x3	y

Когда все термы исчерпаны, оставшиеся пустые ячейки заполняем нулями:

x1	x2	x3	y

Обратная задача: логическая функция задана таблицей истинности, записать ее формулу.

Пример в виде ДНФ:

Помечаем все строки, где функция y = 1, и выписываем соответствующие им термы:

x1	x2	Y
			-
			- x2

Ответ: = {сДНФ обычно упрощается по формулам склейки} =

Пример в виде КНФ:

Помечаем все строки, где функция y = 0, аналогично выписываем соответствующие им термы, делаем общее отрицание функции (чтобы перейти от 0 к 1) и далее – по де Моргану:

x1	x2	Y
			-
			- x2

Ответ: = {сКНФ}

Преобразование ДНФ ç КНФ – достаточно раскрыть скобки по правилу перемножения.

Преобразование ДНФ è КНФ – через построение таблицы истинности.