Предполные классыПредполный класс в теории булевых функций - замкнутый класс булевых функций, обладающий следующим свойством - замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все . Множество предполных классов булевых функций исчерпывается списком:
Также говорят о предполноте одного замкнутого класса в другом. Класс A предполон в классе B, если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс предполон в классах и . В многозначной логике предполные классы аналогично определяются как замкнутые классы, обладающие свойством - замыкание объединения этого класса с любой функцией из , не принадлежащей ему, порождает все . Но в случае k>2 на данный момент нет общего описания структуры предполных классов в отличие от двузначной логики. Литература
Категории:
Источник: Русская википедия 2012 | ||||||
Вы можете разместить ссылку на этот материал у себя на сайте, блоге или форуме
Похожие статьи Предполные классыПредполные классы Предполный класс в теории булевых функций - замкнутый класс булевых функций, обладающий следующим свойством - замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все . Множество предполных классов булевых функций исчерпывается списком: Класс функций, сохраняющих константу 0: . Класс функций, сохраняющих константу 1: . Класс самодвойственных функций: . Класс монотонных функций: . Класс линейных функций: . Также говорят о предполноте одного замкнутого класса в другом. Класс A классы кл'ассы, -ов (игра) Классы L и NL Классы L и NL Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl. Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры: Пусть язык — ориентированный граф в котором есть путь от s до t, тогда NL-полные задачи Преобразователь, требующий логарифмической Классы Классы Классы общественные, «... большие группы людей, различающиеся по их месту в исторически определенной системе общественного производства, по их отношению (большей частью закрепленному и оформленному в законах) к средствам производства, по их роли в общественной организации труда, а, следовательно, по способам получения и размерам той доли общественного богатства, которой они располагают. Классы, это такие группы людей, из которых одна может себе присваивать труд другой, благодаря различию их места в определенном укладе Классы L и NL Классы L и NL Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl. Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры: Пусть язык — ориентированный граф в котором есть путь от s до t, тогда NL-полные задачи Преобразователь, требующий логарифмической Искать все статьи, похожие на текущую (Предполные классы) |
| Универсальная энциклопедия 2012 Карта сайта Страница создана за 0.03087 сек. Всего документов включено в базу знаний: 5150576 |