Полная система функций алгебры логики

Дата добавления: 2015-07-23 ; просмотров: 2292 ; Нарушение авторских прав

Система функций алгебры логики F=<f1, f2,…, fs,…>Í P2 называется полной или функционально полной, если любая функция алгебры логики может быть записана в виде формулы через функции этой системы (или, как говорят, выражена формулой над F).

В соответствии с этим определением системы функций <Ø,&,Ú>, <Ø,&>, <Ø,Ú>, <Ø,®>, а также <¯>и <½>являются функционально полными.

Имеются и другие полные системы функций. Определить полноту некоторой системы функций можно с помощью следующей теоремы.

Теорема. О полных системах функций алгебры логики

Пусть имеются две системы функций алгебры логики: F=<f1, f2,…, fp,…> и G=<g1, g2,…, gr,…>, относительно которых известно, что система F полна и каждая её функция может быть выражена формулой через функции системы G. Тогда система функций G – является полной.

Пример: покажем функциональную полноту следующих систем: (1) G1=<º,Ú,0>, (2) G2= <Å,&,º>и (3) G3=<1,·,Å>, где «·» – это обычное умножение.

(1) Известно, что система функций <Ø,Ú>является полной. Поскольку «Ú» имеется в G1, а «Ø» выражается формулой , то G1 тоже полна.

(2) Известно, что система функций <Ø,&>является полной. Поскольку «&» имеется в G2, а «Ø» выражается формулой , то G2 тоже полна.

(3) Т.к. система <Ø,&>является полной и х·у = х&у, а , то G3 – полная система функций. Система G3 играет особую роль в алгебре логики, т.к. формула, сконструированная из функций <1,·,Å>и скобок, после раскрытия скобок и несложных алгебраических преобразований переходит в полином Жегалкина(СПНФ).

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

Пусть М Í Р2 – некоторое подмножество множества всех функций алгебры логики. Замыканием М называется множество тех истинностных функций, которые могут быть выражены формулой над М.

Замыкание М обозначается [M].

Класс функций М называется функционально замкнутым или просто замкнутым, если его замыкание совпадает с ним самим, т.е. [M] = М.

Определение полной системы функций можно сформулировать в терминах замыканий: система функций М является функционально полной, если её замыкание совпадает с множеством всех функций алгебры логики, т.е. [M]=P2.

Содержание

Полные системы функций [ править ]

Определение:
Если любая булева функция, являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым (англ. closed set).
Определение:
Замыканием (англ. сlosure) множества функций называется минимальное по включению замкнутое подмножество всех функций, содержащее данное множество функций.
Определение:
Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций.
Определение:
Полная система функций называется безызбыточной (англ. irredundant functions), если она перестает быть полной при исключении из неё любого элемента.

Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

  • функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
  • самодвойственныые функции [math]S[/math] ,
  • монотонные функции [math]M[/math] ,
  • линейные функции [math]L[/math] .

Замкнутые классы булевых функций [ править ]

Класс функций сохраняющих ноль [math]T_0[/math] .

Определение:
Говорят, что функция сохраняет ноль, если [math]f(0, 0, ldots, 0) = 0[/math] .
Читайте также  Почему не работает рутрекер сегодня

Класс функций сохраняющих единицу [math]T_1[/math] .

Определение:
Говорят, что функция сохраняет единицу, если [math]f(1, 1, ldots, 1) = 1[/math] .

Класс самодвойственных функций [math]S[/math] .

Определение:
Говорят, что функция самодвойственна (англ. self-dual), если [math]f(overline,ldots,overline)=overline[/math] . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.

Класс монотонных функций [math]M[/math] .

Определение:
Говорят, что функция монотонна (англ. monotonic function) , если [math]forall i (a_i leqslant b_i) Rightarrow f(a_1,ldots,a_n)leqslant f(b_1,ldots,b_n)[/math] .

Класс линейных функций [math]L[/math] .

Определение:
Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, ldots, a_n[/math] , где [math]a_i in <0, 1>, forall i=overline<1,n>[/math] , что для любых [math]x_1, x_2, ldots, x_n[/math] имеет место равенство: [math]f(x_1, x_2, ldots, x_n) = a_0oplus a_1cdot x_1oplus a_2cdot x_2 oplusldotsoplus a_ncdot x_n[/math] .

Количество линейных функций от [math]n[/math] переменных равно [math]

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

Формулировка и доказательство критерия Поста [ править ]

Теорема:
Доказательство:
[math] riangleright[/math]
Необходимость.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным.

Достаточность.

Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.

  1. Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math] ). Тогда [math] f_0(1)[/math] может принимать два значения:
  1. [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, ldots, x) = 1[/math] .
  2. [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, ldots, x) =
    eg x[/math] .
  • Рассмотрим функцию, не сохраняющую один — [math]f_1[/math] (то есть функцию, для которой [math]f_1(1) = 0[/math] ). Тогда [math]f_1(0)[/math] может принимать два значения:
    1. [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, ldots, x) = 0[/math] .
    2. [math]f_1(0) = 1[/math] , тогда [math]f_1(x, x, x, ldots, x) = lnot x[/math] .
    3. Таким образом, возможны четыре варианта:

      • Мы получили функцию [math] eg [/math] .

      Используем несамодвойственную функцию [math]f_s[/math] . По определению, найдется такой вектор [math]x_0[/math] , что [math]f_s(x_0) = f_s(lnot x_0)[/math] . Где [math]x_0 = (x_<01>, x_<02>, ldots, x_<0k>)[/math] .

      Рассмотрим [math]f_s(x^<01>>, x^<02>>, ldots, x^<0k>>)[/math] , где либо [math]x^<0i>> = x[/math] , при [math]x_ <0i>= 1[/math] . Либо [math]x^<0i>> = lnot x[/math] , при [math]x_ <0i>= 0 [/math] . Нетрудно заметить, что [math]f_s(0) = f_s(1) Rightarrow f_s = operatorname [/math] . Таким образом мы получили одну из констант.

      • Мы получили [math] eg [/math] и [math]0 Rightarrow[/math] имеем константу, равную [math]1[/math] , поскольку [math]lnot 0 = 1[/math] .
      • Мы получили [math] eg [/math] и [math]1 Rightarrow[/math] имеем константу, равную [math]0[/math] , поскольку [math]lnot 1 = 0[/math] .
      • Мы получили [math]1[/math] и [math]0[/math] .

      Рассмотрим немонотонную функцию [math]f_m[/math] . Существуют такие [math]x_1, x_2, ldots, x_n[/math] , что [math]f_m(x_1, x_2, ldots, x_, 0 , x_, ldots, x_n) = 1[/math] , [math]f_m(x_1, x_2, ldots, x_, 1 , x_, ldots, x_n) = 0[/math] , зафиксируем все [math]x_1, x_2, ldots, x_n[/math] , тогда [math]f_m(x_1, x_2, ldots, x_, x, x_, ldots, x_n)= lnot x[/math] .

      В итоге имеем три функции: [math] eg [/math] , [math]0[/math] , [math]1[/math] .

      Используем нелинейную функцию [math]f_l[/math] . Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math] . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 land x_2 [ oplus x_1] [oplus x_2][ oplus

      1][/math] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

      Рассмотрим несколько вариантов:

        Присутствует член [math]oplus

      1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]oplus

      1[/math] исчезнет.
      Присутствуют три члена, без [math]oplus

      1[/math] : [math]g_l= x_1 land x_2 oplus x_1 oplus x_2[/math] . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] vee [/math] .
      Присутствуют два члена, без [math]oplus

      1[/math] . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] wedge [/math] через [math] eg [/math] и [math]g_l[/math] . Например, если функция [math]g_l(x_1, x_2, ldots, x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, ldots, i_m[/math] ложны, а все остальные истины, то функцию [math] wedge [/math] можно выразить как [math]g_l([lnot]x_1, [lnot]x_2, ldots, [lnot]x_n)[/math] , где [math]lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, ldots, i_m[/math] .

    4. Присутствует один член. Выразим [math] wedge [/math] через [math] eg [/math] и [math]g_l[/math] аналогично пункту 3.
    5. В итоге получим функцию [math] eg [/math] , а также либо функцию [math] wedge [/math] , либо функцию [math] vee [/math] . Поскольку функцию [math] wedge [/math] можно выразить через [math] vee [/math] и [math] eg [/math] , а функцию [math] vee [/math] через [math] wedge [/math] и [math] eg [/math] , то мы получили базис [math] wedge [/math] , [math] vee [/math] , [math] eg [/math] . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x land lnot x[/math] .

      Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.

      [math] riangleleft[/math]
      Читайте также  Рисунки девочек для срисовки карандашом легкие

      Примеры [ править ]

      Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math] , [math]T_1[/math] , [math]S[/math] , [math]M[/math] , [math]L[/math] .

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

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

      • [math]left<land,lor,
        eg
        ight>[/math] (конъюнкция, дизъюнкция, отрицание);
      • [math]left<land,oplus,1
        ight>[/math] (конъюнкция, сложение по модулю два, константа один).

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

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

      Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

      Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]left<oplus,1
      ight>[/math] можно назвать базисом класса линейных функций.

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

      Читайте также  Северный мост как проверить исправность

      Функционально полной системойбулевых функций (ФПСБФ) называется совокупность таких булевых функций (f1, f2, . fk), посредством которых можно записать произвольную булеву функцию f.

      Это обусловливает целесообразность постановки задачи определения свойств, которыми должны обладать функции, составляющие ФПСБФ.

      Решение этой задачи основано на понятии замкнутого относительно операции суперпозиции класса функций. Класс булевых функций, функционально замкнутый по операции суперпозиции, есть множество функций, любая суперпозиция которых дает функцию, также принадлежащую этому множеству. Среди функционально замкнутых классов выделяют классы обычного типа, называемые предполными, которые обладают следующими свойствами. Предполный класс S не совпадает с множеством Р всех возможных булевых функций, однако, если в него включить любую, не входящую в S, булеву функцию, то новый функционально замкнутый класс будет совпадать с множеством Р. Проведенные исследования показали, что предполных классов пять, а для построения ФПСБФ необходимо и достаточно, чтобы ее функции не содержались полностью ни в одном из пяти предполных классов.

      Наряду с нормальными формами представления функций алгебры логики в вычислительной технике широко используются логические полиномиальные формы. Преобразования над формулами булевых функций иногда удобно выполнять в алгебре Жегалкина. Алгебра Жегалкина включает две двухместные операции: конъюнкцию и сложение по модулю 2, а также константу 1.

      Теорема Жегалкина. Любая функция алгебры логики может быть представлена многочленом вида:

      где кi – коэффициент, принимающие значения 0 или 1.

      Теорема позволяет представить любую ФАЛ в виде полиномов различной степени.

      Задача построения полинома Жегалкина сводится к нахождению коэффициентов ki, Для любых конституент единицыk1иk2имеет место следующее соотношениеk1Vk2=k1k2. Оно позволяет выполнить переход от СДНФ к полиному Жегалкина. Для этого достаточно заменить в СДНФ символ(дизъюнкции) на символ, выполнить подстановку вида х=х 1 с последующими преобразованиями в алгебре Жегалкина.

      Перечислим предполные классы булевых функций:

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

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

      Существует 8 линейных функций от 2 переменных.

      Ссылка на основную публикацию
      Adblock
      detector