Частичные булевы функции
Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович.
Программа курса
Понятие частичной булевой функции. Операция суперпозиции над частичными булевыми функциями. Примеры полных систем в классе P_2^*. Определение предполных в P_2^* классов. Критерий функциональной полноты в классе P_2^*. Континуальность числа замкнутых классов в P_2^*.
Оператор позитивного замыкания. Простейшие свойства позитивно замкнутых классов. Принцип двойственности для позитивной выразимости. Порождение позитивно замкнутых классов булевых функций функциями от двух переменных. Перечисление всех позитивно замкнутых классов булевых функций.
Определение и позитивная замкнутость десяти классов частичных булевых функций, построение позитивных базисов в этих классах. Теорема о перечислении всех позитивно замкнутых классов частичных булевых функций. Построение диаграммы включений.
Оператор замыкания с разветвлением по предикату равенства (E-оператор). Порождение E-замкнутых классов частичных булевых функций функциями от двух переменных. E-замкнутые классы булевых функций, построение E-базисов в этих классах.
Определение и E-замкнутость классов T_0^*, T_1^*, S^*, I^*. Построение E-базисов в классах P_2^*, T_0^*, T_1^*, S^*, I^*. Критерий E-полноты в классе P_2^*. Минимальные E-замкнутые классы частичных булевых функций.
Оператор S-замыкания. Континуальность числа S-замкнутых классов частичных булевых функций.
Литература
- Алексеев В.Б., Вороненко А.А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. Т. 6, № 4. С. 58—79.
- Марченков С.С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика. 1999. Т. 11, № 4. С. 110—126.
- Марченков С.С. Замкнутые классы булевых функций. М.: Физматлит, 2000.
- Марченков С.С. Операторы замыкания с разветвлением по предикату // Вестник МГУ. Серия 1. 2003. № 6. С. 37—39.
- Марченков С.С. Оператор замыкания с разветвлением по предикату равенства на множестве частичных булевых функций // Дискретная математика. 2008. Т. 20, № 2.
- Марченков С.С, Попова А.А. Позитивно замкнутые классы частичных булевых функций // Вестник МГУ. Серия 15. 2008. № 2.
- Фрейвалд Р.В. Функциональная полнота для не всюду определённых функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55—68.
Ссылки
- Программа курса (pdf)
