Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 46 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

То есть, с точ ки зре ния функ цио наль ной пол но ты, сис те му S
0
мож но счи тать из бы точ ной, так как она со хра ня ет свой ст ва пол но ты и
при уда ле нии из нее дизъ юнк ции или конъ юнк ции. Од на ко, как вид но
из при ме ров, за не из бы точ ность сис тем S
1
и S
2
при хо дит ся пла тить из -
бы точ но стью фор мул (боль шое чис ло от ри ца ний).
Мно же ст во М ло ги че ских функ ций на зы ва ет ся замк ну тым клас -
сом, ес ли лю бая су пер по зи ция функ ций из мно же ст ва М сно ва при над -
ле жит М. Вся кая сис те ма S ло ги че ских функ ций по ро ж да ет не ко то рый
замк ну тый класс, со стоя щий из всех функ ций, ко то рые мож но по лу -
чить су пер по зи ция ми из S. Та кой класс на зы ва ет ся за мы ка ни ем S и обо -
зна ча ет ся [S]. Замк ну тый класс об ра зу ет, так на зы вае мые, мо но тон ные
функ ции.
Функ ция f(x
1
… x
n
) на зы ва ет ся мо но тон ной, ес ли для лю бых дво ич -
ных на бо ров s и t дли ны n, из то го, что s £ t , сле ду ет, что f(s) £ f(t) .
На при мер, рас смот рим две ло ги че ские функ ции f
1
и f
2
:
x
1
x
2
x
3
f
1
f
2
0 0 0 0 0
0 0 1 1 0
0 1 0 0 1
0 1 1 1 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Функ ция f
1
не мо но тон на, так как 001< 101, а f
1
(001) > f
1
(101).
Функ ция f
2
мо но тон на, так как 001< 101 и f
2
(001) < f
2
(101).
Мно же ст во всех мо но тон ных функ ций яв ля ет ся замк ну тым
клас сом.
Для то го, что бы сис те ма функ ций S бы ла функ цио наль но пол ной,
не об хо ди мо и дос та точ но что бы она со дер жа ла хо тя бы од ну не мо но -
тон ную и хо тя бы од ну не ли ней ную функ цию. По ня тие не ли ней ной
функ ции мы рас смот рим в раз де ле, по свя щен ном ал геб ре Же гал ки на.
46
      То есть, с точки зрения функциональной полноты, систему S0
можно считать избыточной, так как она сохраняет свойства полноты и
при удалении из нее дизъюнкции или конъюнкции. Однако, как видно
из примеров, за неизбыточность систем S1 и S2 приходится платить из-
быточностью формул (большое число отрицаний).

      Множество М логических функций называется замкнутым клас-
сом, если любая суперпозиция функций из множества М снова принад-
лежит М. Всякая система S логических функций порождает некоторый
замкнутый класс, состоящий из всех функций, которые можно полу-
чить суперпозициями из S. Такой класс называется замыканием S и обо-
значается [S]. Замкнутый класс образует, так называемые, монотонные
функции.
      Функция f(x1 … xn) называется монотонной, если для любых двоич-
ных наборов s и t длины n, из того, что s £ t , следует, что f(s) £ f(t) .
      Например, рассмотрим две логические функции f1 и f2:

                x1        x2        x3        f1        f2
                0         0         0         0         0
                0         0         1         1         0
                0         1         0         0         1
                0         1         1         1         1
                1         0         0         1         0
                1         0         1         0         1
                1         1         0         0         1
                1         1         1         1         1

     Функция f1 немонотонна, так как 001< 101, а f1(001) > f1(101).
     Функция f2 монотонна, так как 001< 101 и f2(001) < f2(101).
     Множество всех монотонных функций является замкнутым
классом.
     Для того, чтобы система функций S была функционально полной,
необходимо и достаточно чтобы она содержала хотя бы одну немоно-
тонную и хотя бы одну нелинейную функцию. Понятие нелинейной
функции мы рассмотрим в разделе, посвященном алгебре Жегалкина.
46

Страницы