Модальная алгебра

Модальная алгебра — структура $\langle A,\land ,\lor ,-,0,1,\Box \rangle$ , где:

$\langle A,\land ,\lor ,-,0,1\rangle$ — булева алгебра,
$\Box$ — унарная операция над $A$ , удовлетворяющая $\Box 1=1$ и $\Box (x\land y)=\Box x\land \Box y$ для всех $x,y\in A$ .

Модальные алгебры являются моделями логики высказываний модальной логики, подобно тому, как булевы алгебры являются моделями классической логики. В частности, многообразие всех модальных алгебр обеспечивает алгебраическую семантику модальной логики $\mathrm {K}$ , а решётка его подмногообразий дуально изоморфна решётке нормальных модальных логик.

Теорема Стоуна о представлении булевых алгебр может быть обобщена до двойственности Йоунсcона — Тарского^[англ.], согласно которой каждая модальная алгебра может быть представлена как алгебра допустимых множеств в модальном общем фрейме^[англ.].

Алгебра Магари (диагонализируемая алгебра) — модальная алгебра, удовлетворяющая условию $\Box (-\Box x\lor x)=\Box x$ ; алгебры Магари соответствуют логике доказуемости^[англ.].

Литература

Chagrov, A. Modal Logic / A. Chagrov, M. Zakharyaschev. — Oxford University Press, 1997. — Vol. 35. — ISBN 0-19-853779-4.

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

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

<span class="mw-page-title-main">Импликация</span>

Имплика́ция — бинарная логическая связка, по своему применению приближенная к союзам «если…, то…».

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

Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ. Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Замкнутый класс в теории булевых функций — такое множество $\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]}$ . Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.

Семантика Крипке является распространенной семантикой для неклассических логик, таких как интуиционистская логика и модальная логика. Она была создана Солом Крипке в конце 1950-х — начале 1960-х годов. Это было большим достижением для развития теории моделей для неклассических логик.

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

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

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

Топологическая семантика является естественной семантикой для неклассических логик, таких как интуиционистская логика и модальная логика. Исторически топологическая семантика появилась раньше более распространённой на данной момент семантики Крипке. Основы топологической семантики были заложены в работах Куратовского.

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

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

\text{[math]}

\text{[math]}

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

S5 — одна из пяти систем модальной логики, предложенных Льюисом и Лэнгфордом в книге «Символическая логика». Является нормальной модальной логикой и одной из старейших систем модальной логики. Будучи простейшей модельной логикой, образуется формулами логики высказываний, тавтологиями, аппаратом вывода с подстановками и modus ponens. Синтаксис при этом дополнен модальным оператором необходимости $\text{[math]}$ и двойственным ему оператором возможности $\text{[math]}$ .

Алгебра Жегалкина — множество булевых функций, на котором определены нульарная операция взятия единицы $\text{[math]}$ , бинарная операция конъюнкции $\text{[math]}$ и бинарная операция суммы по модулю два $\text{[math]}$ . Константа ноль вводится как $\text{[math]}$ . Операция отрицания вводится соотношением $\text{[math]}$ . Операция дизъюнкции следует из тождества $\text{[math]}$ .

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

Нормальная модальная логика — множество формул L, содержащее:

Все пропозициональные тавтологии;
$\text{[math]}$ ;
$\text{[math]}$ .

Алгебра Гейтинга — импликативная решётка с наименьшим элементом $\text{[math]}$ .

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