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

(перенаправлено с «Исчисление высказываний»)

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

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

Язык логики высказыванийПравить

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

Алфавит языка логики высказыванийПравить

Исходные символы, или алфавит языка логики высказываний, разделены на следующие три категории[1][5]:

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

Некоторые авторы вместо строгой дизъюнкции и эквивалентности используют знак выводимости  .[6]

  • Вспомогательные символы: левая скобка (, правая скобка ), запятая ,.[6]

Пропозициональные переменныеПравить

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

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

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

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

  1. пропозициональная переменная есть формула;
  2. если   — произвольная формула, то   — тоже формула;
  3. если   и   — произвольные формулы, то  ,  ,  ,   и   — тоже формулы. Некоторые авторы считают: если   и   — произвольные формулы, то  ,  ,   и   — тоже формулы.[6]

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

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

Соглашения о скобкахПравить

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

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

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

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

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

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

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

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

 ;

 ;

 ;

 ;

 ;

 ;

 ;

 ;

 ;

 ;

 .

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

  (Modus ponens)

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

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

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

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

 ,

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

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

   
 
 
 
 

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

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

См. такжеПравить

ПримечанияПравить

  1. 1 2 3 4 5 6 7 Чупахин, Бродский, 1977, с. 203—205.
  2. 1 2 Кондаков, 1971, статья «Исчисление высказываний».
  3. 1 2 НФЭ, 2010.
  4. 1 2 3 Герасимов, 2011, с. 13.
  5. Войшвилло, Дегтярев, 2001, с. 91—94.
  6. 1 2 3 Ершов Ю. Л., Палютин Е. А. Математическая логика. — М., Наука, 1979. — с. 24
  7. Эдельман, 1975, с. 130.
  8. Эдельман, 1975, с. 128.
  9. Игошин, 2008, с. 32.
  10. 1 2 Герасимов, 2011, с. 17—19.
  11. Герасимов, 2011, с. 19.

ЛитератураПравить