Образовательный блог – всё для учебы

Пусть F – есть некоторое подмножество функций из P2.

Определение: Суперпозиция функций (булева формула) над F определяется индуктивно следующим образом:

1. Всякая функция f(x₁, x₂,…,x_n) из F есть суперпозиция (формула) над F.

2. Если А(x₁, x₂,…,x_m) (m – шаг индукции) – есть суперпозиция над F и каждое из выражений A₁, A₂,…,A_m есть либо суперпозиция над F, либо переменная, то функция A(A₁, A₂,…,A_n) – есть суперпозиция над F.

Замечание: Суперпозиция функций над F есть обычная подстановка функций из F.

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

Замечание: Одна и та же функция может быть записана разными формулами.

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

Определение: Замыкание класса F – множество всех суперпозиций над F. Обозначается [F] – замыкание класса F.

Замечание: Класс F – замкнутый, если F = [F].

Замечание:
1. F?[F]
2. [[F]] = [F] идемпотентность
3. F1?F2 ? [F1] ? [F2]

Определение: Система G функций из замкнутого класса F полна в F (является порождающей системой для F), если [G] = F. Система функций H полна в P2, если [H] = P2.

Полная в F система функций G называется базисом для F, если всякая собственная подсистема системы F полной для G уже не является.

1. Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности
2. Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
3. Функции и отношения, их свойства
4. Класс функций, сохраняющих константу
5. Класс монотонных функций и его замкнутость относительно суперпозиции
6. Примеры универсальных алгебр, подалгебры, гомоморфизм и изоморфизм алгебр
7. Класс линейных функций и его замкнутость относительно суперпозиции
8. Теорема Поста о функциональной полноте
9. Фундаментальная система решений, общее решение однородного и неоднородного ЛРУ с помощью ФСР
10. Определение ?(?) – функций, кусочно-линейной функции
11. Исключения в Delphi, классы исключений
12. Описание систем с помощью передаточных функций
13. Построения функционально-структурной модели
14. Рекуррентные уравнения, порядок уравнения, частное и общее решение
15. Целые числа, сравнения – дискретная математика
16. СДНФ и СКНФ
17. Функции алгебры логики