Материал: Diskretnaya_matematika

Если f(х₁, х₂, ..., х_n) ≢ 1, то соотношение (4) можно переписать в форме

(5)

Эта форма называется совершенной конъюнктивной нормальной формой (СКНФ).

Следствие. Для произвольной логической функции также существует взаимнооднозначное соответствие между ее СКНФ и таблицей истинности:

а) СКНФ содержит ровно столько элементарных дизъюнкций, сколько нулевых наборов у функции;

б) каждому нулевому набору σ = (σ₁, …, σ_n) соот­вет­ствует элементарная дизъюнкция всех переменных функции, в которой для σ_i = 1 переменная х_i берется с отрицанием и для σ_i = 0 – без отрицания.

Рассмотрим построение СКНФ по таблице истинности функ­ции f(x₁, х₂,..., x_n). Для каждого набора σ = (σ₁, …, σ_n) из нулевого множества [0] (такого, что f(σ₁, …, σ_n) = 0), составляется выражение ЭД: . Затем эти дизъюнкции соединяются знаком конъ­юнкции.

Пример 2. Построим СКНФ для функции неэкви­ва­лентности f₇(x₁, х₂) = (х₁  х₂). Исходя из нулевого мно­жества этой функции [0] = {(0, 0), (1, 1)} формула СКНФ будет иметь вид: F_СКНФ = (х₁  х₂) • (х₁  х₂).

2.3. Полные системы логических функций

Система функций  = {f₁(x₁₁,...,x_1p1), ..., f_s(x_s1, ...,x_sps),…} на­зываетсяполной, если любую логическую функциюf(x₁, ...,x_n) мож­но представить в виде супер­позиции функций {f₁, ...,f_s, ...} и переменных х₁, ..., х_n.

Функции, входящие в полную систему, называются базисными, а сама полная система функций –базисом.

Примеры полных систем функций (базисов)

1. Булевый базис ₀= {х₁• х₂,x₁х₂,х}.

Полнота булева базиса следует из того, что для любой логической функ­ции можно построить СДНФ или СКНФ.

2. Конъюнктивный булевый базис₁= {х₁• х₂,х}. Полнота этого базиса следует из п. 1 и представления дизъюнкции в виде:

x₁ х₂=х₁•х_2.

3. Дизъюнктивный булевый базис ₂= {x₁ х₂,х }.

Полнота этого базиса следует из п. 1 и представления конъюнкции в виде:

х₁ • х₂ =х₁ х₂.

4. Базис Жегалкина ₃ = {х₁ • х₂, х₁  х₂, 1}.

Полнота этого базиса следует из п. 2 и представления отрицания в виде:х = х  1.

Теорема 3. Любую логическую функциюf(x₁, ...,x_n) можно предста­вить в виде полинома Жегалкина:

f(x₁, ...,x_n) = а₀а₁x₁а₂x₂…а₂ⁿ_-1x₁…x_n, (6)

где а_i  {0,1}, i = 0, 1, ..., 2ⁿ - 1.

Доказательство.Система функций= {х₁• х₂, х₁х₂, 1, 0} полна. Из формулы СДНФ (3), пользуясь свойствами:

xx= 0,x•x=x,x0 =x,

x• 0 = 0,x• 1 =x,x₁•x₂=x₂•x₁,

x₁  x₂ = x₂  x₁, (x₁  x₂) • x₃ = (x₁ • x₃)  (x₂ • x₃),

получим представление функции в виде полинома (6).

Следствие. Для любой логической функции, наряду с СДНФ и СКНФ в случае булева базиса, существует единственный полином Жегалкина вида (6).

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

Теорема 4 (о полноте). Для того чтобы система функ­ций {f₁(x_l1 ..., х_1р1), ...,f_s(x_s1, ...,x_sps), ...} была полна, необ­хо­димо и достаточно, чтобы она содер­жала функцию, не сохраняющую 0; функцию, не сохраняющую 1; несамо­двой­ственную функцию; немо­нотонную функцию; нелинейную функцию.

Класс функций, сохраняющих ноль

Функция f(х₁, ..., х_n) называется сохраняющей ноль, если она на нулевом наборе принимает значение 0, то естьf(0, ..., 0) = 0.

Пример.f(х) = 0,f(х) = х,f(х₁, х₂) = х₁• х₂,f(х₁, х₂) = х₁Úх₂ сохраняют ноль;f(х) = 1,f(х) =х,f(х₁, х₂) = х₁® х₂ не сохраняют ноль.

Лемма 1. Из функций, сохраняющих ноль, супер­позицией можно получить только функции, сохраняющие ноль.

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

Ф(х₁, ..., х_n) = f(f₁(х₁, ..., х_n), ..., f_m(х₁, ..., х_n))

сохраняет ноль, если функции f, f_l, …, f_m сохраняют ноль. Последнее следует из

f(f₁(0, ..., 0), ... f_m(0, ..., 0)) = f(0, ..., 0) = 0.

Следствие. Полная система функций должна содер­жать хотя бы одну функцию, не сохраняющую ноль.

Класс функций, сохраняющих единицу

Функция f(х₁, ..., х_n) называется сохраняющей едини­цу, если она на единичном наборе принимает значение 1, то естьf(1, ..., 1) = 1.

Пример.Функцииf(х) = 1,f(х) = х – сохраняют единицу; функцииf(х) = 0,f(х) =х,f(х₁, х₂) =х₁ Å х₂ – не сохраняют единицу.

Лемма 2. Из функций, сохраняющих единицу, суперпози­цией можно получить только функции, сохраняющие единицу. Доказательство очевидно.

Следствие. Полная система функций должна содер­жать хотя бы одну функцию, не сохраняющую единицу.

Класс самодвойственных функций

Функция f(х₁,..., х_n) называется самодвойственной, еслиf(х₁, ..., х_n) =f(х₁, ...,х_n).

Пример.f(х) = х,f(х) =х – самодвойствен­ные функ­ции;f(х₁, х₂) = х₁• х₂,f(х₁, х₂) = х₁Úх₂– несамо­двой­ственные.

Лемма 3. Из самодвойственных функций суперпози­цией можно получить только самодвойственные функции.

Следствие. Полная система функций должна содер­жать хотя бы одну несамодвойственную функцию.

Класс монотонных функций

Набор  = (₁, ..., _n) предшествует набору  = (₁, ..., _n), если _i  _i (i = l, 2, ..., n). Это обозначаем как   . Наборы, которые находятся в отношении  называются сравнимыми.

Функция f(х₁, ..., х_n) называется монотонной, если для любой пары наборов a и b таких, что при   : f()  f().

Пример.f(х) = х,f(х₁, х₂) = х₁ • х₂,f(х₁, х₂) = х₁Úх₂– монотонные функции, аf(х) =х – немо­нотонная функция.

Лемма 5. Из монотонных функций суперпозицией мож­но получить только монотонные функции.

Следствие. Полная система функций должна содер­жать хотя бы одну немонотонную функцию.

Класс линейных функций

Функция f(х₁, ..., х_n) называется линейной, если полином Жегалкина этой функции имеет линейный вид:

f(х₁, ..., х_n) = а₀Åа₁x₁Å…Åа_n x_n,

где а_i  {0,1} (i = 0, l, ..., n).

Пример.f(х) = х,f(х) =х = хÅ 1 – линейные функции;f(х₁, х₂) = х₁ Úх₂= х₁Å х₂Å х₁•х₂– нелинейная функция.

Лемма 7. Из линейных функций суперпозицией можно полу­чить только линейные функции.

Следствие. Полная система функций должна содержать хотя бы одну нелинейную функцию.

Таблица 2.6. Свойства функций двух переменных

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