И совершенная конъюнктная нормальная форма (СКНФ)

В некоторых случаях бывает удобно выразить булеву функцию только через конъюнкцию, дизъюнкцию и отрицание.

Например, это удобно из-за того, что выражения с этими операциями удобно подставлять одно в другое.

Для вычисления СКНФ и СДНФ нам пригодится только что построенная таблица.

x	y	z			f	СДНФ	СКНФ

Правило построения СДНФ: выбрать те и только те строки, в которых значение функции равно 1, затем в этих строках записать конъюнкцию x, y, z по следующему правилу:

Если соответствующая переменная равна 0, то пишем её с отрицанием, если она равна 1, то пишем без отрицания.

Например, во второй строке мы пишем , поскольку в соответствующей строке были значения x = 0, y = 0, z = 1.

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

В итоге получаем: СДНФ = .

Построение СКНФ в некотором смысле двойственно к построению СКНФ.

Вместо строк со значением 1 берём строки со значением 0, вместо дизъюнкции – конъюнкция, а вместо конъюнкции дизъюнкцию.

И одно принципиальное отличие – там, где значение переменной равно 0, мы берём её без отрицания, а там, где это значение равно 1, берём с отрицанием. Сравните первую и третью строки, выражения в которых равны соответственно и .

Выражение для СКНФ можно получить, перемножив все эти дизъюнкции.

СКНФ = .

Следующее важное действие – упростить СДНФ.

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

Итак, упрощённая форма СДНФ в данном случае равна .

Показать логическую схему, причём написать, что для первоначальной записи потребовалось бы очень много элементов: импликация, эквивалентность, и так далее. А для СКНФ достаточно трёх элементов: И, ИЛИ и НЕ.

Привести пример составления схемы для СДНФ и для упрощённой ДНФ.

Но, как во многих задачах на упрощение, возникает вопрос: можно ли упростить выражение дальше? Точнее сказать – можно ли получить выражение, содержащее ещё меньше букв и равное данному?

Ответ даёт метод минимизирующих карт.

Для его применения составьте таблицу такого вида.

f	Значения переменных	x	y	z	xy	xz	yz	xyz
				z
			y
			y	z			yz
		x
		x		z		xz
		x	y		xy
		x	y	z	xy	xz	yz	xyz

Каждую переменную, x, y и z, мы снабжаем или не снабжаем отрицанием в соответствии со значениями переменных.

Например, если во втором столбце 001, то x и y с отрицаниями, а z – без отрицания.

А в остальных столбцах переменные сопровождаются отрицаниями в соответствии с третьим, четвёртым и пятым столбцами.

Теперь производим вычёркивание по следующему принципу.

Сначала вычёркиваем все строки, в которых значение функции равно нулю. В данном примере вычёркиваются строки с номерами 1, 3, 4 и 5.

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

Теперь из оставшихся элементов, взяв по одному элементу из строки, составим самое короткое выражение.

В данном примере из второй и шестой строк имеет смысл взять два одинаковых выражения , а из седьмой и восьмой строк – два одинаковых выражения xy, поскольку при вычислении дизъюнкции получим: .

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

Если преобразования дали такой же ответ, что и метод минимизирующих карт, это добавляет уверенности в ответе.

Если они дали ответ длиннее, то, возможно, вы не до конца использовали возможности упрощения.

А если преобразования дали ответ короче, чем метод минимизирующих карт, то такая ситуация теоретически противоречива: метод минимизирующих карт даёт самую короткую форму записи.

В качестве упражнения на булевы функции можно рассматривать вычисление функции , где f – функция от трёх переменных.

Задачу можно решать двумя способами.

Первый способ: найти значения выражений для всех значений пары x, y. Затем подставить полученные значения в функцию от трёх переменных.

Например: если x = y = 0, то (по таблице истинности для функции f).

Дополнительное условие для этой задачи: по таблице истинности необходимо определить формулу для полученной функции от двух переменных. Например, xy или x XOR y.

Второй способ: подставить в исходную формулу для функции (например, ) вместо переменной y выражение , а вместо переменной z выражение , затем упростить выражение.

Многочлен Жегалкина

Многочлен Жегалкина – это представление булевой функции в виде арифметического выражения, а точнее – в виде многочлена , причём значения переменных x, y, z и значения полученных выражений рассматриваются в кольце вычетов по модулю 2. При этом каждое чётное число заменяют 0, а каждое нечётное – 1.

Есть несколько способов вычисления этих коэффициентов, мы рассмотрим два способа.

Первый способ: метод неопределённых коэффициентов.

Подставим в многочлен все возможные наборы x, y, z и получим 8 условий на 8 коэффициентов. При этом матрица системы будет содержать много нулей.

Например, f (0, 0, 0) = a₀ = 0 (значение берём из таблицы истинности).

Далее, f (0, 0, 1) = a₀ + a₃ = 1, поэтому a₃ = 1. И так далее, на каждом уравнении будем получать новый коэффициент.

В итоге получим: a₃ = 1, a₁₂ = 1, a₂₃ = 1.

Тогда многочлен Жегалкина имеет вид: z + xy + yz.

Второй способ: использование СДНФ.

Как и следовало ожидать, ответ для второго способа вычисления многочлена Жегалкина совпал с ответом для первого способа.

Если эти ответы различаются, необходимо проверить выкладки.

В ответе с многочленом Жегалкина принято записывать слагаемые в лексикографическом порядке.

Двойственная функция

Определение. Пусть f – некоторая булева функция. Тогда двойственной к f (обозначается f*) называют функцию, таблица истинности которой получается из таблицы истинности f заменой всех 0 на 1, а всех 1 на 0.

Такую операцию называют инвертированием таблицы истинности.

Примечание.

Инвертирование происходит не только со значениями функции, но и со значениями x и y. Поэтому после построения таблицы её нужно будет «перевернуть», то есть переставить все строки в обратном порядке.

Посмотрим, например, что произойдёт с дизъюнкцией при такой замене.

x	y

После инвертирования таблицы

x	y	*

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

x	y	*

Из полученной таблицы видно, что значения функции, двойственной к конъюнкции, совпали со значениями дизъюнкции.

Следовательно, .

Аналогично можно обосновать такие равенства.

Не нашли, что искали? Воспользуйтесь поиском по сайту: