Примеры формальных систем

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

Эта формальная система называется еще логикой высказываний, или пропозициональной логикой. Формальные системы, как определено выше, представляют собой систему четырех объектов М=: Т— алфавит, Р — множество синтаксических правил, А — множество аксиом, В — множество правил вывода. Следовательно, задать формальную систему — это задать эти четыре объекта.

Определение исчисления высказываний

Логика высказываний определяется следующим образом.

• 1. Алфавит
• — пропозициональные символы — это буквы латинского алфавита (прописные и строчные) или те же буквы с индексами, например: А, А_ь …, Р, Q, а, Ь, х_ьх₂,…; эти символы используются для обозначения высказываний, т. е. утверждений о свойствах или взаимосвязях объектов предметной области;
• — логические связки:

отрицание (читается «не», «отрицание», «неверно, что»); используется для обозначения частицы «не» и всех ее синонимов, импликация —> (читается «если …, то…», «влечет», «следует», «импликация», «имплицирует»); используется для обозначения словосочетаний «если …, то …», «потому что», «так как» ит.п.;

• — круглые скобки (и); используются для правильного написания и правильной интерпретации формул.
• 2. Синтаксические правила
• — любой пропозициональный символ есть формула;
• — если т есть формула, то (т) тоже является формулой;
• — если т, /и, и т₂ являются формулами, то выражения —>т и т,—>т₂ тоже являются формулами.
• 3. Аксиомы

В этих аксиомах символы т_ьт₂и т, обозначают произвольные формулы.

4. Правило вывода (правило modus ponens, или правило отделения)

Правило modus ponens означает: если имеются две формулы т_] и т^т_ъ то можно записать формулу т₂. Другими словами, формула т₂ является логическим выводом из формул /и, и /и,—>/Изданное определение довольно экономно, так как использует лишь две связки (-1 и —") и всего три аксиомы. Однако существует еще более экономное определение этой формальной системы, использующее одну связку (штрих Шеффера) и одну аксиому. Об этом подробнее будет идти речь ниже.

В любой формальной системе, если необходимо, можно определять новые связки и правила образования формул на основе заданных в определении формальной системы. Например, в логике высказываний, как правило, в алфавит вводятся новые логические связки л (конъюнкция), v (дизъюнкция) и = (эквивалентность), которые определяются через заданные связки и следующим образом:

алЬ обозначает формулу —.(дг—>—, й), avb обозначает формулу (^а—>Ь), а=Ь обозначает формулу (а—>Ь) л (Ь->а).

Введение

новых логических связок в алфавит логики высказываний сопровождается дополнением списка синтаксических правил новым правилом: — если т_х и т₂ являются формулами, то выражения т^т₂, m_{vm₂ и т_х=т₂ тоже являются формулами.

К правилу вывода (МР) при этом добавляются следующие правила переписывания:

Правила переписывания применяются как ко всей формуле в целом, так и к отдельным ее частям. Символ |=> указывает на то, что соответствующее правило вывода является именно правилом переписывания. Правило вывода (МР) применяется только к формулам в целом, к частям формул его применять нельзя.

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

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

• 1. Алфавит
• — пропозициональные символы — это буквы латинского алфавита (прописные и строчные) или те же буквы с индексами, например: А, А, …, Р, Q, а, Ь, х_ьх₂,…; эти символы используются для обозначения высказываний, т. е. утверждений о свойствах или взаимосвязях объектов предметной области;
• — логическая связка: | (штрих Шеффера);
• — круглые скобки (и); используются для правильного написания и правильной интерпретации формул.
• 2. Синтаксические правила
• — любой пропозициональный символ есть формула;
• — если т есть формула, то (т) тоже является формулой;
• — если т_: и т₂ являются формулами, то выражение т, |т₂ тоже является формулой.
• 3. Аксиома
• (р|(0И)1(ЖФ))1((*1?)1((НОМ?))) —

Здесь символы p, q, r, snt обозначают произвольные формулы.

4. Правило вывода

Эквивалентность описанной формальной системы логике высказываний следует понимать в том смысле, что если во всех теоремах этой формальной системы записи аЬ заменить формулой (-.av-,/;), то полученное множество формул полностью исчерпывает все теоремы логики высказываний.

Этот факт был установлен Ж. Нико в 1917 г. Заметим, что пять логических связок логики высказываний могут быть выражены через штрих Шеффера: ->р соответствует формуле р |р, pvq соответствует формуле ((pp)(qq)), p/q соответствует формуле ((/;|с/)|(/;|с/)), p^>q соответствует формуле (p (qq)), р = q соответствует ({p (qq)) (q (pp)))(((p (qq))(q (pp))) —

Имеется еще один экономный вариант определения логики высказываний в сравнении с данным в начале. Он был предложен Я. Лукасевичем и Б. Собочинским и основан на тех же двух связках и —но на одной единственной аксиоме при использовании правила вывода modus ponens. Этот вариант определения приводит к тому же множеству формул, что и первоначальное определение логики высказываний.

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

• — закон тождества р^>р,
• — закон исключенного третьего pv-, p,
• — закон противоречия ~^(рл^р).

В качестве примера доказательства в исчислении высказываний рассмотрим доказательство закона тождества /?-«/?.

• 1 • р-> ((/?—>/?)—>/?) аксиома (А 1) при /и, = р, т₂ = (р->р)
• 2. (р—> ((/?—>/?)—>/?))—> ((/?—> (/?—"/?))—> (/?—>/?)) аксиома (А2) при т_] = т₃=р, Щ = (р^р)
• 3. (р-> (р^>р))^> (р^р) правило (МР), примененное к формулам (1) и (2)
• 4. /?-> (/?->/?) аксиома (AI) при т_] = т₂ = р
• 5. р^р правило (МР), примененное к формулам (3) и (4)

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

I. Законы коммутативности.

II. Законы ассоциативности.

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

IV. Законы идемпотентности.

V. Законы де Моргана (законы двойственности)

VI. Закон двойного отрицания.

VII. Закон исключенного третьего.

VIII. Закон противоречия

В законах логики высказываний символами я, b и с обозначены произвольные формулы, поэтому законы рассматриваются как схемы теорем: подстановка в закон любых формул вместо символов а, Ьмс приводит к формуле, которая сама является теоремой.