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

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

Литералы можно разделить на два типа:

• Положительный литерал — это просто атом (например, $x$).
• Отрицательный литерал — это отрицание атома (например, $\lnot x$).

Полярность . литерала может быть положительной или отрицательной в зависимости от того, является ли он положительным или отрицательным литералом

В логике с устранением двойного отрицания (где $\lnot \lnot x\equiv x$) дополнительный литерал или дополнение литерала $l$ можно определить как литерал, соответствующий отрицанию $l$. Мы можем написать ${\bar {l}}$ для обозначения дополнительного литерала $l$. Точнее, если $l\equiv x$ затем ${\bar {l}}$ является $\lnot x$ и если $l\equiv \lnot x$ затем ${\bar {l}}$ является $x$. Устранение двойного отрицания происходит в классической логике, но не в интуиционистской логике .

В контексте формулы в конъюнктивной нормальной форме литерал считается чистым , если в формуле не встречается дополнение к литералу.

В логических функциях каждое отдельное вхождение переменной, как в обратной, так и в незаполненной форме, является литералом. Например, если $A$, $B$ и $C$ являются переменными, то выражение ${\bar {A}}BC$ содержит три литерала и выражение ${\bar {A}}C+{\bar {B}}{\bar {C}}$ содержит четыре литерала. Однако выражение ${\bar {A}}C+{\bar {B}}C$ также можно было бы сказать, что он содержит четыре литерала, поскольку, хотя два литерала идентичны ( $C$ появляется дважды), это квалифицируется как два отдельных события.

Примеры

В исчислении высказываний литерал — это просто пропозициональная переменная или ее отрицание.

В исчислении предикатов литерал — это атомарная формула или ее отрицание, где атомарная формула — это символ предиката, применяемый к некоторым терминам . $P(t_{1},\ldots ,t_{n})$ терминами, с рекурсивно определенными начиная с постоянных символов, переменных символов и функциональных символов. Например, $\neg Q(f(g(x),y,2),x)$ является отрицательным литералом с постоянным символом 2, переменными символами x , y функциональными символами f , g и символом предиката Q. ,

Ссылки

• Бен-Ари, Мордехай (2001). Математическая логика для информатики (2-е изд.). Спрингер. ISBN  1-85233-319-7 .

• Басс, Сэмюэл Р. (1998). «Введение в теорию доказательств» (PDF) . В Бассе, Сэмюэл Р. (ред.). Справочник по теории доказательств . Амстердам: Эльзевир. стр. 1–78. ISBN  0-444-89840-9 .

• Годзе, Атул П.; Годзе, Дипали А. (2008). Цифровые логические схемы . Технические публикации. ISBN  9788184314250 .

• Раутенберг, Вольфганг (2010). Краткое введение в математическую логику . Университетский текст (3-е изд.). Спрингер. дои : 10.1007/978-1-4419-1221-3 . ISBN  978-1-4419-1220-6 .