Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством: замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все . Множество предполных классов булевых функций исчерпывается списком: класс функций, сохраняющих константу 0:; класс функций, сохраняющих константу 1:; класс самодвойственных функций:; класс монотонных функций:; класс линейных функций — представимых полиномом Жегалкина первой степени:.
Также говорят о предполноте одного замкнутого класса в другом. Класс предполон в классе , если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс предполон в классах и .
В многозначной логике предполные классы аналогично определяются как замкнутые классы, обладающие свойством — замыкание объединения этого класса с любой функцией из , не принадлежащей ему, порождает все . В случае структура предполных классов описывается теоремой Розенберга.
Литература
Категория:Теория функциональных систем Категория:Математическая логика Категория:Теория дискретных функций Категория:Булева алгебра