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

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

Логика высказываний (или пропозициональная логика от англ. propositional logic, или исчисление высказываний[1]) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка.

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

Содержание

Основные понятия

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, и (пропозициональная) формула, определяемой индуктивно следующим образом[2]:

  1. Если P — пропозициональная переменная, то P — формула.
  2. Если A — формула, то \neg A — формула.
  3. Если A и B — формулы, то (A \to B), (A \wedge B) и (A \vee B) — формулы.
  4. Других формул нет.

Множество пропозиционных формул называется языком логики высказываний (англ. propositional language, PL)[2].

Знаки \neg, \wedge, \vee и \to (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

Правила построения формул логики высказываний

  1. Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное логическое высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
  2. Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1)\vee(Ф2)), ((Ф1)\wedge(Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

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

Пример

Пусть элементарными высказываниями являются А, В, С. Записи

¬ A\wedge BC и (B)\wedge(B\veeA→C)

c формальной точки зрения не являются формулами, так как мы натыкаемся при их разборе на нарушение правил построения формул. (В первом случае отсутствует логическая связка между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи

(¬ A)\wedge(B\veeC) и B\wedge((B\veeA)→C)

вполне соответствуют требованиям построения формулы. В процессе анализа формулы (¬ A)\wedge(B\veeC) выделяются следующие её части:

               ( ¬A ) \wedge ( B\veeC )
                      \wedge                     | Связующее действие
                 ¬A       B \vee C             | Разделённые части (формулы первого уровня)
                 ¬          \vee               | Связующее действие
                 A        B    C             | Разделённые части (формулы нулевого уровня)
                                             | Все разделённые части являются элементарными высказываниями; разбор закончен.

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

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

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

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

Например: запись A \vee B \wedge \neg C означает формулу (A \vee (B \wedge ( \neg C))), а её длина равна 12.

Истинностное значение

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

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

p\! \neg p
0\!
1\!
1\!
0\!

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

p\! q\! p\rightarrow q p \wedge q p \vee q
0
0
1
0
0
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1

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

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

Законы де Моргана:

1)  \neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q);

2)  \neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q);

Закон контрапозиции:

(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p);

Законы поглощения:

1) p\vee(p\wedge q)\leftrightarrow p;

2) p\wedge(p\vee q)\leftrightarrow p;

Законы дистрибутивности:

1) p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r);

2) p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r).

Исчисление высказываний

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

A_1 : A \rightarrow (B \rightarrow A);

A_2 : ((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)));

A_3 : A \wedge B \rightarrow A;

A_4 : A \wedge B \rightarrow B;

A_5 : A \rightarrow (B \rightarrow (A \wedge B));

A_6 : A \rightarrow (A \vee B);

A_7 : B \rightarrow (A \vee B);

A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C));

A_9 : \neg A \rightarrow (A \rightarrow B);

A_{10} : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A);

A_{11} : A\vee\neg A.

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

\frac{A \rightarrow B, A}{B} (Modus ponens)

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

См. также

Примечания

  1. 1 2 Кондаков, 1971, статья «Исчисление высказываний»
  2. 1 2 Герасимов, 2011, с. 13
  3. Герасимов, 2011, с. 17-19
  4. Герасимов, 2011, с. 19

Литература



Wikimedia Foundation. 2010.

Нужно решить контрольную?

Полезное


Смотреть что такое "Логика высказываний" в других словарях:

  • ЛОГИКА ВЫСКАЗЫВАНИЙ — раздел логики, в котором изучаются истинностные взаимосвязи между высказываниями. В рамках данного раздела высказывания (пропозиции, предложения) рассматриваются только с т.зр. их истинности или ложности, безотносительно к их внутренней субъектно …   Философская энциклопедия

  • логика высказываний —         ЛОГИКА ВЫСКАЗЫВАНИЙ, пропозициональная логика раздел символической логики, изучающий         сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, простые высказывания при этом выступают как… …   Энциклопедия эпистемологии и философии науки

  • ЛОГИКА ВЫСКАЗЫВАНИЙ — раздел логики, в котором вопрос об истинности или ложности высказываний рассматривается и решается на основе изучения способа построения высказываний из т. н. элементарных (далее не разлагаемых и не анализируемых) высказываний с помощью… …   Большой Энциклопедический словарь

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

  • логика высказываний — раздел логики, в котором вопрос об истинности или ложности высказываний рассматривается и решается на основе изучения способа построения высказываний из так называемых элементарных (далее не разлагаемых и не анализируемых) высказываний с помощью… …   Энциклопедический словарь

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

  • ЛОГИКА ВЫСКАЗЫВАНИЙ — раздел логики, в к ром вопрос об истинности или ложности высказываний рассматривается и решается на основе изучения способа построения высказываний из т.н. элементарных (далее не разлагаемых и не анализируемых) высказываний с помощью логич.… …   Естествознание. Энциклопедический словарь

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

  • ЛОГИКА ВЫСКАЗЫВАНИЙ, или ПРОПОЗИЦИОНАЛЬНАЯ ЛОГИКА — раздел дедуктивной логики, в котором вопрос об истинности (или ложности) высказываний (т. е. суждений, рассматриваемых без их субъектно предикатной структуры) в умозаключениях рассматривается на основе изучения следующего средства их выражения т …   Современный философский словарь

  • ЛОГИКА — (от греч. logos слово, понятие, рассуждение, разум), или Формальная логика, наука о законах и операциях правильного мышления. Согласно основному принципу Л., правильность рассуждения (вывода) определяется только его логической формой, или… …   Философская энциклопедия

Книги

Другие книги по запросу «Логика высказываний» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»