Теорема Поста (значения)

Теорема Поста может означать:

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

Примечания

Похожие исследовательские статьи

Компа́ктное простра́нство — определённый тип топологических пространств, обобщающий свойства ограниченности и замкнутости в евклидовых пространствах на произвольные топологические пространства.

Булевой алгеброй называется непустое множество A с двумя бинарными операциями $\text{[math]}$ , $\text{[math]}$ , одной унарной операцией $\text{[math]}$ и двумя выделенными элементами: 0 и 1 такими, что для любых a, b и c из множества A верны следующие аксиомы:

Логи́ческий тип да́нных, или булев тип, или булевый тип — примитивный тип данных в информатике, принимающий два возможных значения, иногда называемых истиной (true) и ложью (false). Присутствует в подавляющем большинстве языков программирования как самостоятельная сущность или реализуется через численный тип данных. В некоторых языках программирования за значение истина полагается 1, за значение ложь — 0.

Зада́ча выполни́мости бу́левых фо́рмул — важная для теории вычислительной сложности алгоритмическая задача.

Замкнутый класс в теории булевых функций — такое множество $\text{[math]}$ функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: $\text{[math]}$ . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества $\text{[math]}$ , снова входит в это же множество.

Гу́рвиц — еврейская фамилия. Производная от фамилии Горовиц.

Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

Бу́лева фу́нкция от $\text{[math]}$ аргументов — в дискретной математике — отображение $\text{[math]}$ , где $\text{[math]}$ — булево множество. Элементы булева множества $\text{[math]}$ обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число $\text{[math]}$ , обозначающее количество аргументов, называется арностью или местностью функции, в случае $\text{[math]}$ булева функция превращается в булеву константу. Элементы декартова произведения $\text{[math]}$ называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается $\text{[math]}$ , а от $\text{[math]}$ аргументов — $\text{[math]}$ . Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.

Таблица истинности — таблица, описывающая логическую функцию.

Полином Жегалкина — многочлен над полем $\text{[math]}$ , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция $\text{[math]}$ называется самодвойственной, если для любых значений $\text{[math]}$ верно

\text{[math]}

Метаматематика — раздел математической логики, изучающий основания математики, структуру математических доказательств и математических теорий с помощью формальных методов. Термин «метаматематика» буквально означает «за пределами математики».

Принцип двойственности — наименование различных вариантов и проявлений феномена двойственности в разных разделах математики.

Принцип двойственности в проективной геометрии — двойственность между понятиями точки и прямой.
Принцип двойственности в теории множеств — двойственность, выражаемая в возможности перехода к эквивалентным утверждениям взаимозаменой объединения и пересечения с дополнением аргументов и взаимозаменой пустого множества и универсума, проявление законов де Моргана, имеющего место во всех булевых алгебрах.
Принцип двойственности для булевых формул — возможность перейти к формуле, задающую двойственную функцию, заменой всех функций, непосредственно входящих в формулу, на двойственные. Также, такая двойственность позволяет переходить к эквивалентному тождеству, заменой всех функций в тождестве на двойственные.
Двойственность в топологии:
- Двойственность Александера
- Двойственность Понтрягина
- Двойственность Колмогорова

Логическая функция:

Двоичная логическая функция — Булева функция;
Троичные логические функции

Лавинный эффект — понятие в криптографии, обычно применяемое к блочным шифрам и криптографическим хеш-функциям. Важное криптографическое свойство для шифрования, которое означает, что изменение значения малого количества битов во входном тексте или в ключе ведет к «лавинному» изменению значений выходных битов шифротекста. Другими словами, это зависимость всех выходных битов от каждого входного бита.

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

Карно́ — французская фамилия, а также объекты, образованных от этой фамилии. Известные носители:

Карно, Ипполит Лазар (1801—1888) — сын Лазара, политик.
Карно, Лазар (1753—1823) — деятель Великой французской революции, «Организатор победы», член Директории, математик и физик.
Карно, Луи — французский футболист.
Карно, Морис (1924—2022) — американский физик, создатель метода минимизации булевых функций, известного как «карта Карно».
Карно, Рано — индонезийский актёр и политик.
Карно, Стефан — французский футболист.
Карно, Фред (1866—1941) — сценическое имя английского антрепренёра Фредерика Джона Уэсткотта.

Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция. Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:

\text{[math]}

\text{[math]}

В математике, термин «нормированная алгебра» может указывать на одну из трёх алгебраических структур:

Нормированная ассоциативная алгебра
- Банахова алгебра, важнейший частный случай
Нормированная алгебра с делением
- Теорема Гурвица о нормированных алгебрах с делением, классификация одного из частных случаев
Нормированная булева алгебра

Теорема Стоуна — название математических результатов, принадлежащих американскому математику Маршаллу Стоуну.

Теорема Стоуна об аппроксимации — обобщение, данное Стоуном для теоремы Вейерштрасса о равномерном приближении многочленами функций, непрерывных на отрезке.
Теорема Стоуна о группах унитарных операторов в гильбертовом пространстве — результат функционального анализа о стандартном представлении сильно непрерывных однопараметрических групп унитарных операторов, имеющий важные приложения в квантовой механике.
Теорема Стоуна о представлении булевых алгебр — утверждение об изоморфности всякой булевой алгебры некоторому полю множеств.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.