Interested Article - Логика высказываний

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

Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений .

Язык логики высказываний

Язык логики высказываний (пропозициональный язык ) — формализованный язык , предназначенный для анализа логической структуры сложных высказываний .

Синтаксис логики высказываний

Исходные символы, или алфавит языка логики высказываний :

  • множество пропозициональных переменных (пропозициональных букв):
  • пропозициональные связки (логические союзы):
Символ Значение
Знак отрицания
или & Знак конъюнкции («логическое И»)
Знак дизъюнкции («логическое ИЛИ»)
Знак импликации
  • Вспомогательные символы: левая скобка (, правая скобка ).

Пропозициональные формулы

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

Индуктивное определение множества формул логики высказываний:

  1. Если , то (всякая пропозициональная переменная есть формула);
  2. если — формула, то — тоже формула;
  3. если и — произвольные формулы, то , , — тоже формулы.

Других формул в языке логики высказываний нет.

Форма Бэкуса — Наура , определяющая синтаксис логики высказываний, имеет запись:

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

Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии с пп. 1—3 определения формулы, то она формула, если нет, то не формула .


Соглашения о скобках

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

  • Если опущены внешние скобки, то они восстанавливаются.
  • Если рядом стоят две конъюнкции или дизъюнкции (например, ), то в скобки заключается сначала самая левая часть (то есть эти связки левоассоциативны ).
  • Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: и (от высшего к низшему).

Когда говорят о длине формулы , имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись означает формулу , а её длина равна 12.

Формализация и интерпретация

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

Аксиомы и правила вывода формальной системы логики высказываний

Одним из возможных вариантов ( гильбертовской ) аксиоматизации логики высказываний является следующая система аксиом:

;

;

;

;

;

;

;

;

;

;

.

вместе с единственным правилом:

( Modus ponens )

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

Таблицы истинности основных операций

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

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

,

которое каждую пропозициональную переменную сопоставляет с истинностным значением .

Оценка отрицания задаётся таблицей:

Значения двухместных логических связок (импликация), (дизъюнкция) и (конъюнкция) определяются так:

Тождественно истинные формулы (тавтологии)

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

;
;
;
  • законы поглощения :
;
;
;
.

См. также

Примечания

  1. , с. 203—205.
  2. , статья «Исчисление высказываний».
  3. .
  4. , с. 13.
  5. , с. 91—94.
  6. Ершов Ю. Л. , Палютин Е. А. Математическая логика. — М. , Наука , 1979. — с. 24
  7. , с. 130.
  8. , с. 128.
  9. , с. 32.
  10. , с. 17—19.
  11. , с. 19.

Литература

Источник —

Same as Логика высказываний