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

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

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

Содержание

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

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

  1. Если P — пропозициональная переменная, то P — формула.
  2. Если A — формула, то \neg A — формула.
  3. Если A и B — формулы, то (A \wedge B), (A \vee B) и (A \to B) — формулы.
  4. Каждая формула может быть получена за конечное число шагов при помощи предыдущих трёх правил.

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

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

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

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

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

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

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

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

Оценка отрицания \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

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

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

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

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 из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

См. также

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


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

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

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

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

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

  • ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ — формализации содержательных логич. теорий; выводимые объекты Л. п. интерпретируются как суждения, составленные из простейших (имеющих, вообще говоря, субъектно предикатную структуру) при помощи пропозициональных связок и кванторов. Чаще всего… …   Математическая энциклопедия

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

  • ИНТУИЦИОНИСТСКОЕ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ — логическое исчисление, описывающее способы вывода высказываний, истинных с точки зрения интуиционизма. Общепринятая (к 1978) формулировка И. и. в. была предложена А. Рейтингом (A. Heyting) в 1930. Основное ее отличие от классич. исчисления… …   Математическая энциклопедия

  • ЛОГИКО-МАТЕМАТИЧЕСКИЕ ИСЧИСЛЕНИЯ — прикладные исчисления, формализации математич. теорий. Л. м. и. задается своим языком и перечнем постулатов (эти элементы образуют синтаксис).и в большинстве случаев снабжается семантикой. Существенными чертами, отличающими Л. м. и. от аксиоматич …   Математическая энциклопедия

  • Логика высказываний — Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники. Логика высказываний (или пропозици …   Википедия

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


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

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