Литерал (математическая логика)

Литерал в теории булевых функций и логике высказываний — булева формула, имеющая вид $x$ или ${\overline {x}}$ для некоторой переменной $x$ . Разделяют два типа литералов:

Положительный литерал — формула вида $x$ ;
Отрицательный литерал — формула вида ${\overline {x}}$ .

Литералы иногда обозначаются $x^{\sigma }$ , где $\sigma$ принимает значение $1$ или $0$ . Это обозначение определяется следующим образом:

x^{\sigma }={\begin{cases}x&\sigma =1\\{\overline {x}}&\sigma =0\end{cases}}

В логике первого или высших порядков литералом называют либо атомарную формулу, (логические константы атомарной формулой не считаются), либо её логическое отрицание. Соответственно, разделяют два типа литералов:

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

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

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

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

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

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

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

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

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

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

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

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

Многозначная логика — это логика высказываний, в которой существует более двух истинностных значений логического выражения. Традиционно, в классической логике Аристотеля, мы имеем дело только с двумя возможными значениями — «истиной» или «ложью». Однако данная двухзначная логика может быть дополнена до n — значной с n > 2. Наиболее популярными в литературе являются трехзначная логика, конечнозначная и бесконечнозначная логики.

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

Конъюнкти́вный одночле́н — булева формула, представляющая собой конъюнкцию литералов:

\text{[math]}

Дизъюнкти́вный одночле́н — дизъюнкция литералов :

\text{[math]}

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

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

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

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций
в каждой дизъюнкции нет одинаковых пропозициональных переменных
каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

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

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

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

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