Частичные булевы функции — различия между версиями

Версия 18:48, 31 октября 2013

Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович. Курс читается в осеннем семестре 2007-2008 учебного года.

Программа курса

Понятие частичной булевой функции. Операция суперпозиции над частичными булевыми функциями. Примеры полных систем в классе Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): P_2^* . Определение предполных в Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): P_2^*

классов. Критерий функциональной полноты в классе Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): P_2^*

. Континуальность числа замкнутых классов в Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): P_2^* .

Оператор позитивного замыкания. Простейшие свойства позитивно замкнутых классов. Принцип двойственности для позитивной выразимости. Порождение позитивно замкнутых классов булевых функций функциями от двух переменных. Перечисление всех позитивно замкнутых классов булевых функций.

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

Оператор замыкания с разветвлением по предикату равенства (Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -оператор). Порождение Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -замкнутых классов частичных булевых функций функциями от двух переменных. Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -замкнутые классы булевых функций, построение Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -базисов в этих классах.

Определение и Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -замкнутость классов Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): T_0^*, T_1^*, S^*, I^* . Построение Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -базисов в классах Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): P_2^*, T_0^*, T_1^*, S^*, I^* . Критерий Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -полноты в классе Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): P_2^* . Минимальные Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E -замкнутые классы частичных булевых функций.

Оператор Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): S -замыкания. Континуальность числа Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): S -замкнутых классов частичных булевых функций.

Литература

1. Алексеев В.Б., Вороненко А.А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. Т. 6, № 4. С. 58—79.
2. Марченков С.С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика. 1999. Т. 11, № 4. С. 110—126.
3. Марченков С.С. Замкнутые классы булевых функций. М.: Физматлит, 2000.
4. Марченков С.С. Операторы замыкания с разветвлением по предикату // Вестник МГУ. Серия 1. 2003. № 6. С. 37—39.
5. Марченков С.С. Оператор замыкания с разветвлением по предикату равенства на множестве частичных булевых функций // Дискретная математика. 2008. Т. 20, № 2.
6. Марченков С.С, Попова А.А. Позитивно замкнутые классы частичных булевых функций // Вестник МГУ. Серия 15. 2008. № 2.
7. Фрейвалд Р.В. Функциональная полнота для не всюду определённых функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55—68.

Ссылки

• Программа курса (pdf)