logo
Лекции_по_ДМ_2часть

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

Рассмотрим ещё два понятия: замыкания и замкнутого класса, которые тесно связаны с понятием полноты.

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

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

Примеры:

Пусть М = Р2, тогда [M] = Р2.

Пусть М = {}, тогда [M] = Р2.

Пусть М = {1,}, тогда [M] = {f(x1,…,xn)P2: f(x1,…,xn) = c0c1x1cnxn, где сi0 или 1}. Т.е. [M] – это множество функций, представимых линейным выражением или класс всех линейных функций.

Свойства замыкания:

Для всякого множества функций алгебры логики М замыкание «шире» самого множества М. Или [M]  М.

Для всякого множества функций М замыкание замыкания М есть само замыкание М. Или [[M]] = [М].

Если множество функций М1 является подмножеством множества функций М2, то замыкание М1 является подмножеством замыкания М2. Или если М1  М2, то [М1]  [М2].

Объединение замыканий двух множеств является подмножеством замыкания объединения этих множеств. Или [М1]  [М2]  [М1  М2].

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

Так, например, множество всех функций алгебры логики – функционально замкнутый класс. А множества {Ø,&}, {Ø,Ú}, {Ø,®} не являются замкнутыми классами, поскольку их замыканием является множество всех функций алгебры логики. То же можно сказать и о других полных системах функций. Тем самым, определение полной системы функций можно сформулировать в терминах замыканий: система функций М является функционально полной, если её замыкание совпадает с множеством всех функций алгебры логики, т.е. [M]=P2.

    1. Yandex.RTB R-A-252273-3
      Yandex.RTB R-A-252273-4