Вопросы к зачету часть1 (Вопросы к зачету (ответы)), страница 4

где дизъюнкция берется по всевозможным наборам (σ₁, ...,σ_k) значений аргументов х₁, ..., x_k.

Д о к а з а т е л ь с т в о. Убедимся, что для любого набора (α ₁, ..., α_n) значений аргументов левая и правая части формулы принимают одинаковое значение. Рассмотрим правую часть. Поскольку при (σ₁, α _k =...,σ_k)? (α ₁, ..., α _k) и α ₁, ..., 1, то

Эта величина совпадает со значением левой части. Теорема доказана.

Указанное представление функции задаст разложение по переменным x₁, ..., x_k.Его частный случай при

k=1 имеет вид

и носит название формулы разложения по переменной.

Иногда будем использовать векторную запись формулы (1.5). Набор переменных x₂,.., x_k обозначим через а набор оставшихся переменных х_k+1, ..., x_n — через . Для конъюнкции будем применять обозначение ( , где =(σ₁, ...,σ_k). Тогда разложение (1.5) может быть переписано в виде

(1.6)

где через обозначена функция .

1. Формула разложения по переменной.

10. Доказательство теоремы о представлении двоичной функции в виде СДНФ.

Совершенная дизъюнктивная нормальная форма. Воспользовавшись теоремой 1.1 при k=n, получаем, представление

которое для f(x₁, ..., x_n) ?0 может быть преобразовано к виду

Это представление носит название совершенной дизъюнктивной нормальной формы (с.д.н.ф.). С учетом соглашения, что пустая дизъюнкция равна 0, оно может быть распространено и на функцию, тождественно равную нулю.

В качестве примера выпишем с.д.н.ф. для функции f(x₁,х₂,x₃),заданной таблицей 1.1:

С.д.н.ф. обладает следующими свойствами:

1) является дизъюнкцией некоторых конъюнкций

K₁ K₂ . . . К_S;

2) каждая из конъюнкций K_i, имеет вид

K_i=

где n—число переменных функции;

3) все конъюнкции K_i (i= 1, ...,S) различны.

Т е о р е м а 1.2. Представление логической функции, обладающее свойствами 1)—3) определено однозначно и совпадает с с.д.н.ф. этой функции (однозначность понимается с точностью до перестановки конъюнкций).

Доказательство. Пусть имеется представление функции f(x₁, ..., x_n),обладающее свойствами 1)—3). Запишем его в виде

f(x₁, ..., x_n)= (1.7)

где константа c_{σ1, ...,σn} равна 1 или 0 в зависимости от того, входит конъюнкция в представление или нет. Подставив в обе части (1.7) произвольный набор (α_1,. . .,α_n)значений аргументов, с учетом того, что на этом наборе в 1 обращается единственная конъюнкция приходим к равенству

f(α_1,. . . ,α_n)=

Оно показывает, что коэффициенты однозначно определяются функцией.

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

Способ приведения формул в базисе {0, 1, ,~,&, , —, , } к с.д.н.ф. состоит в следующем. Вначале с использованием представления операций >, ~ через операции -, & и осуществляется перевод в базис {0,1, ,~,& }. Затем на основе законов де Моргана формула преобразуется к виду, при котором отрицания применяются лишь к элементарным переменным x_i. Далее в результате раскрытия скобок с использованием свойства дистрибутивности х(у \/ z) =ху \/ хz получается выражение вида дизъюнкции некоторых конъюнкций (1 считается конъюнкцией пустого множества переменных. При этом можно пред полагать, что все переменные Xi1…Xip , входящие в состав одной конъюнкции, различны, ибо конъюнкция, содержащая переменную одновременно в формах и равна 0 и может быть удалена, а если все вхождения переменной в конъюнкцию одинаковы, то на основе равенства они могут быть заменены одним вхождением. Полученное представление отличается от с. д. н. ф. лишь тем, что в нем конъюнкции могут иметь длину, меньшую n (т. е. содержать не все переменные). Для приведения к с.д.н.ф. каждая конъюнкция Xi1 …Xip домножается на n—р скобок ( \/ ), соответствующих переменным, не входящим в конъюнкцию (напомним, что \/ ? 1). С использованием свойства дистрибутивности осуществляется раскрытие скобок и из множества полученных конъюнкций выбираются все различные.

В качестве примера рассмотрим формулу . Как мы видели, она эквивалентна формуле , которая может быть преобразована так:

Последнее выражение представляет собой с. д. н. ф. функции, реализуемой формулой, и совпадает (с точностью до перестановки конъюнкций) с с. д. н. ф., выписанной выше по таблице 1.1, задающей эту функцию.

11. Представление в виде СКНФ.

. Совершенная конъюнктивная нормальная форма. Всякая функция f(x₁, ..., x_n)?1 может быть выражена также в виде конъюнкции некоторых дизъюнкций . Для того чтобы получить это представление, выпишем с.д.н.ф. функции (x₁, ..., x_n) 0:

Воспользовавшись правилом написания формулы отрицания функции и тем, что , получаем

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

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

В качестве упражнения выпишем с.к.н.ф. функции f(x₁,х₂,x₃),задаваемой таблицей 1.1,

12. Понятие ДНФ булевой функции. Импликанта логической функции. Простой импликант.

Строение м.д.н.ф.

Описание начнем со случая всюду определенных функций.

Дизъюнктивная нормальная форма называется минимальной (сокращенно МДНФ), если она имеет наименьшую длину среди всех равносильных ей ДНФ.

Пусть имеется логическая функция f(x₁, x₂,...,x_n). Логическая функция

g(x₁, x₂,...,x_n) называется импликантом функции f(x₁, x₂,...,x_n), если для всякого набора (σ_1,….,σ_n) значений аргументов выполнено неравенство

f(σ_1,….,σ_n)? g(σ_1,….,σ_n). Это условие может быть эквивалентно переписано в виде

f(x_1,…., x _n) g(x_1,…., x _n) = g(x _1,…., x _n).

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

К качестве примера рассмотрим функцию f ( ) = . Функция является импликантом, ибо

(мы воспользовались соотношением (А \/ В) А = А). Поскольку не есть конъюнкция, импликант не простой. Конъюнкция также является импликантом. Если из нее вычеркнуть переменную , полученная конъюнкция снова будет импликантом, ибо

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

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

Сформулируем теорему о строении м. д. н. ф.

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

Д о к а з а т е л ь с т в о. Рассмотрим произвольную м. д. и. ф. функции f:

f = (2.9)

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

(2.10)

совпадает с f. Для этого достаточно убедиться, что f и f' обращаются в 1 на одних и тех же наборах.

Рассмотрим произвольный набор ( ). Поскольку при укорачивании конъюнкции область ее единичных значений не уменьшается, то на этом наборе выполнено неравенство | и, следовательно,

.

Отсюда вытекает, что если = 1, то и = 1.

Обратно, пусть = 1. Это означает, что на наборе ( ) либо , либо . обращается в 1 (то и другое возможно одновременно). Равенство = 1 в первом случае следует из того, что является импликантом, а во втором- из представления (2.9).