И.А. Пушкарев логика

CDxyCNxz = С(Dxy, CNxz ).

(4) Эта запись, являясь вариантом так называемой«польской записи»,

свойствами (1) – (4) существуют. Например, таковым является множество всех слов над рассматриваемым алфавитом, или – над любым бòльшим алфавитом.

Пусть X ¹ Æ – множество всех формальных языков, удовлетворяющих этим

свойствам (это опять не совсем«правильное» множество, но мы не будем обращать на это внимания).

Далее, заметим, что "Q Í X формальный язык IM , состоящий из тех

D uv Î IM . Очевидно, что в случае остальных условий, которые необходимо

MÎQ

проверить, рассуждения абсолютно аналогичны. В частности, свойствами (1) –

(4) обладает формальный язык L = IM .

MÎX

Покажем, что этот язык обладает также и свойством (5). Пусть это не так,

формальный язык, удовлетворяющий свойствам (1) – (5). Тогда он, в частности,

удовлетворяет свойствам (1) – (4), поэтому L Í L¢ (по свойству (5) языка L).

Симметричным образом, L¢ Í L , откуда L = L¢.

вид DAB , где A = N z и B = CCN x yD x z являются формулами (свойство (4)).

Выражение А, в свою очередь является формулой потому, что имеет вид NR ,

где R = z является формулой в силу свойства(2). Тот факт, что выражение В тоже является формулой также следует из , тогочто свойства (3) и (4)

позволяют свести его к тому, что формулами являются x, y, и z.

(2) Почему формулой не является никакое выражение, содержащее некоторый символ, не входящий в V È {C, D, N , O, I}? Потому что существует

формальный язык, удовлетворяющий условиям (1) – (4) и не содержащий ни одного слова, в который входит этот «лишний» символ (например – множество

Определение 1.2. (1) Пусть u Î L . Слово u называется тавтологией, если булева функция, реализуемая соответствующей формулой, тождественно равна

1.

(2)Множество всех тавтологий обозначим буквой Т.

(3)Пара (L, T ), а также (менее точно) множество Т, называется

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

Ω рассмотреть хорошее и простое множество В = {0, 1}.

Следовательно, таблицу истинности сложного высказывания, зависящего

от n простых (кстати, не вполне ясно, что это такоеJ), можно составить

Проведём непосредственное вычисление:

D(N 1)CC(N 1)0(D11)= D0C(C00)1 = D0(C01)= D00 = 0 .

5. Общая картина

Какое место в общей картине занимают рассмотренные объекты? В

рассматриваемой модели они играют роль реального мира, в котором есть вещи мыслимые, но неизвестно, верные ли (язык L), а есть – «правда жизни» (язык

Т). Теории, заданные ссылкой на«объективную реальность», называются

15

семантическими. В следующем параграфе будет сформулировано понятие,

играющее в рассматриваемой модели роль мышления.

16

§2. Исчисление высказываний 1. Предварительное обсуждение

Простой алгоритм проверки принадлежности

пропозициональной теории, приведённый в §1, хорош не во всех отношениях.

Если вспомнить основную цель исследования– изучение человеческого мышления, то недостаток алгоритма становится понятен: люди думают не так.

Они используют умозаключения, а не полный перебор различных вариантов (он

«несолиден» и обычно нереален из-за высокой трудоёмкости). Формальный аналог умозаключения называетсяправилом вывода, а система, позволяющая

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

аксиоматики не то, чтобы потребуется, но – окажется очень удобна – ещё одна

рассматриваемый алфавит, добавив к нему новый символJ, заменяющий буквосочетание DN: J uv Û (u Þ v)Û ((Øu)Ú v)Û DN uv .

2. Аксиоматика

Определение 2.1. Аксиомой исчисления высказываний называется любая формула, имеющая один из тринадцати видов:

(А1) JaJba ,

(А2) JJaJbcJJabJac ,

(А3) JCaba ,

17

(А4) JCabb ,

(А5) JaJbCab,

(А6) JaDab ,

(А7) JbDab ,

(А8) JJacJJbcJDabc ,

(А9) JNaJab,

(А10) JJabJJaNbNa ,

(А11) DaNa ,

(А12) JOa ,

(А13) JaI ,

где а, b, с – произвольные формулы.

Замечания. (1) Почему приведённая аксиоматика разрешима? Потому

конечное число. Конкретные аксиомы получаются из схем заменой переменных

а, b, с на конкретные формулы, поэтому множество всех аксиомбесконечно.

Соответственно, и количество аксиом бесконечно. Важно также отметить, что

а, b, с – не пропозициональные переменные, они принимают значения не из множества высказываний, а из множестваформул. Такие переменные можно назвать формульными.

(3)От вхождения «лишнего» символа J можно избавиться, заменив все его вхождения «обратно» на DN. Например, аксиома (А8) превратится при этом

в«настоящую» формулу DNDNacDNDN bcDNDabc .

(4)С другой стороны, использование символа J упрощает аксиомы, но

ещё не делает их интуитивно понятными(что было бы крайне желательным)

L. В этом смысле определение2.1. представляет собой самый настоящий

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

Это превратит список схем аксиом (А1) – (А13) в следующий список:

(А1) a ® (b ® a),

(А2) (a ® (b ® c))® ((a ® b)® (a ® c)),

(А3) (a Ù b)® a ,

(А4) (a Ù b)® b ,

(А5) a ® (b ® (a Ù b)),

(А6) a ® (a Ú b),

(А7) b ® (a Ú b),

(А8) (a ® c)® ((b ® c)® ((a Ú b)® c)),

(А9) (Øa)® (a ® b),

(А10) (a ® b)® ((a ® (Øb))® (Øa)),

(А11) a Ú (Øa),

(А12) O ® a ,

(А13) a ® I .

В таком виде аксиомы действительно являются интуитивно очевидными

J.

(5) Список схем аксиом из определения2.1. не является единственно возможным для построения исчисления высказываний. Он даже не является минимальным! В действительности можно, основываясь на полном наборе булевых функций, состоящем из импликации и тождественного , нуля построить аксиоматику, основанную всего на трёх схемах аксиом.

19

Определение 2.1'. Аксиомой исчисления высказываний называется любая формула, имеющая один из трёх видов:

(В1) a ® (b ® a),

(В2) (a ® (b ® c))® ((a ® b)® (a ® c)),

(В3) ((а ® O)® O)® a .

При этом аксиомы вида(А3) – (А13) станут теоремами (что бы ни означало это слово).

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

Закончив обсуждение аксиоматики, перейдём к правилам вывода. В

исчислении высказываний такое правило всего одно, но называется modus ponens. Его обычно записывают в форме

(МР) a, a ® b . b

Фактически оно является тернарным отношением на множестве формул,

но эту формальность можно отдельно не обсуждать, поместив её «внутри» определений формального вывода и теоремы.

правила (МР)).

(2) Формула, имеющая доказательство, называется теоремой исчисления высказываний.

20

Пример. Покажем, что для любой формулыp формула p ® p является теоремой. Её доказательством может, например, служить следующая последовательность:

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

доказательства. Конкретное доказательство формулыq ® q для каждой

доказательство отнюдь не просто придумать! К сожалению, это – характерная для рассматриваемого предмета трудность(вдохновляющая на некоторую мыслительную деятельность J).