Алгебра логики

Логика – наука о правильном мышлении, о законах вывода одних суждений из других, в то время как психология – наука об общих закономерностях мышления.

Основателем логики принято считать Аристотеля (384-322гг.до н.э.). Он в виде силлогизмов построил формальную логику, которая была названа Аристотелевой логикой.

Идея о построении логики на математической основе принадлежит Лейбницу (1646-1716), и была сформулирована в конце 17-го века. Понятия должны заменяться символами, которые соединяются по особым правилам. Тогда рассуждения можно заменить вычислениями. «Мы употребляем знаки не только для того, чтобы передать наши мысли другим людям, но и для того, чтобы облегчить сам процесс мышления»(Лейбниц).

Первая реализация математической логики была сделана Булем (1815-1864), который разработал алгебру высказываний. Фреге (1848-1925) и Пеано(1858-1932) применили логику для обоснования арифметики и теории множеств.

Основное понятие алгебры логики – высказывание. По Аристотелю, высказывание – это утверждение или отрицание чего-либо о чём-либо. В современной интерпретации высказывание – мысль о событии.

Высказывание – суждение, о котором имеет смысл говорить, соответствует или не соответствует оно действительности. Если высказывание соответствует действительности, то оно истинно. Если высказывание не соответствует действительности, то оно ложно.

В речи высказывания выражаются повествовательными предложениями.

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

Высказываниям приписываются значения истинности. Если высказывание истинно, ему приписывается значение истинности «истина». Если высказывание ложно, ему приписывается значение истинности «ложь».

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

Истина – логическая единица, обозначается 1, И (если русскими буквами), Т( от Тruth). Ложь – логический нуль, обозначается 0, Л, F (от False).

В математической логике принят тезис экстенсиональности, все высказывания рассматриваются только с точки истинности, высказывания, имеющие одинаковые значения истинности, рассматриваются как эквивалентные. Вся математическая логика экстенсиональна.

Двух значений истинности достаточно для большинства рассуждений. Разработаны так же и другие логики: многозначные, модальные,… Этими логиками мы пока не занимаемся.

Высказывания делятся на простые и сложные. Простые высказывания – не разложимые на другие высказывания, не содержат в себе других высказываний. Сложные высказывания – те, которые состоят из простых, и значения истинности которых определяются значениями истинности входящих в них простых высказываний. Сложные высказывания, значения истинности которых не зависят от входящих в них простых, математическая логика не изучает (например, я сказала, что дважды два – пять. Значение истинности этого высказывания не зависит от значения истинности высказывания «дважды два – пять», а только от того, было ли произнесено это утверждения).

Итак, поскольку высказывания рассматриваются только с точки зрения значения истинности, то высказывания, имеющие одинаковые значения истинности, рассматриваются как тождественные. Таким образом введено отношение равенства высказываний. Обозначения равенства высказываний: а=b, ab, a≡b, a~b. Читается эквивалентно, равносильно, тогда и только тогда, когда. Отношение равенства высказываний является отношением эквивалентности (является рефлексивным, симметричным и транзитивным, что легко доказать).

Отличие отношений между высказываниями от отношений на множествах состоит в том, что и область определения, и область изменения отношений между высказываниями – истинностные значения. Т.е. отношение может рассматриваться как операция над высказываниями. Если отношение имеет место, то значение операции 1, в противном случае – значение 0.

Операции над высказываниями могут быть заданы таблицей истинности.

Можно записать суждение (а=1)=а – читается «от убеждения в истинности истины не прибудет». Если а – истинно , то а=1 – тоже истина, и 1=1 – истина. Если а – ложно, то а=1 – ложь, и ложь эквивалентна лжи.

Обозначения в алгебре высказываний используются двух типов: алгебраические (введённые Булем), чтобы подчеркнуть сходство с алгеброй, и логические (Пеано, Рассел), чтобы подчеркнуть отличия.

Рассмотрим операции сравнения высказываний. Каждая операция может быть определена двумя способами: от истины (определяем, когда сложное высказывание истинно) и от лжи (определяем, когда оно ложно). Будут приводиться оба определения.

1. Эквивалентность, или равенство высказываний. Эквивалентность истинна тогда и только тогда, когда оба высказывания одновременно истинны, или оба одновременно ложны. Эквивалентность ложна тогда и только тогда, когда одно из исходных высказываний истинно, а другое ложно.

a	b	а=b
0 0 1 1	0 1 0 1	1 0 0 1

2. Неравенства.

   1. Слабое неравенство, или импликация. Символизирует логическое следование. Обозначается аb; ab.Читается «если a, то b», «из a следует b». При этом a называют посылкой, b – заключением импликации. Импликация истинна тогда и только тогда, когда посылка ложна или заключение истинно. Импликация ложна тогда и только тогда, когда посылка истинна, а заключение ложно.

Следует обратить внимание, что из лжи следует всё, что угодно.

a	b	ab
0 0 1 1	0 1 0 1	1 1 0 1

2. Слабое неравенство, или обратная импликация. Обозначается ab; ab. Читается «а следует из b». Обратная импликация ab истинна тогда и только тогда, когда a истинно или b ложно. Обратная импликация aÜb ложна тогда и только тогда, когда а ложно, а b – истинно.

a	b	aÜb
0 0 1 1	0 1 0 1	1 0 1 1

3. Сильное неравенство, или антиимпликация. Обозначается ab, . Читается «а не следует из b». Антиимпликация истинна тогда и только тогда, когда а ложно, а b – истинно. Антиимпликация ложна тогда и только тогда, когда а истинно или b ложно. Таблица истинности антиимпликации:

a	b
0 0 1 1	0 1 0 1	0 1 0 0

4. Обратная антиимпликация. Обозначается a>b, . Обратная антиимпликация истинна тогда и только тогда, когда а истинно, а b – ложно. Обратная антиимпликация ложна тогда и только тогда, когда а ложно или b истинно.

a	b
0 0 1 1	0 1 0 1	0 0 1 0

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

Основные операции алгебры логики - конъюнкция, дизъюнкция и отрицание.

Определим эти операции.

Дизъюнкция. Семантика операции приближённо передается словом «или», юристы в этих случаях пишут или/и, чтобы подчеркнуть, что дизъюнкция истинна при истинности обоих операндов, «или» является включительным. Обозначение дизъюнкции - . Дизъюнкция истинна, тогда и только тогда, когда истинен хотя бы один из её аргументов. Дизъюнкция ложна тогда и только тогда, когда ложны оба её аргумента. Таблица истинности дизъюнкции:

a	b	ab
0 0 1 1	0 1 0 1	0 1 1 1

Конъюнкция. Конъюнкция в речи передается союзами и, а , но, так же. В тексте она может быть представлена просто точкой или запятой. Конъюнкция обозначается &, . Конъюнкция истинна тогда и только тогда, когда истинны оба аргумента. Конъюнкция ложна тогда и только тогда, когда ложен хотя бы один из её аргументов. Таблица истинности конъюнкции:

a	b	a&b
0 0 1 1	0 1 0 1	0 0 0 1

Отрицание. Отрицание суждения а в речи передаётся словами «не а», «не верно, что а». Обозначается отрицание суждения a - . а. Отрицание истинно тогда и только тогда, когда исходное суждение ложно. Отрицание ложно тогда и только тогда, когда исходное суждение истинно. Таблица истинности для отрицания:

a
0 1	1 0

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

Формулы исчисления высказываний строится с использованием логических связок из логических констант и пропозициональных переменных. Более точно:

1. Пропозициональные переменные и константы – формулы.

2. Если А и В – формулы, то (), (А&В), (АÚВ), (АÞВ), (АÛВ) – формулы.

3. Других формул нет.

Для того, чтобы при записи формул не писать лишние скобки, установлено, что самой сильной связкой считается отрицание, далее – конъюнкция, затем – дизъюнкция, ещё более слабой связкой является импликация, и самой слабой – эквивалентность , т.о. получаем список связок в порядке убывания их силы: ^, &,Ú,Þ,=. Соотношение силы для других связок обычно не рассматривается.

Если рассмотреть два множества {AВ, А, В, АВ} c отношением частичного порядка , и множество {a&b, a, b, aÚb} с отношением частичного порядка Þ, то легко установить, что эти множества изоморфны.

Изоморфными являются и алгебры множеств и логики. Логические законы можно получить из законов алгебры множеств заменой обозначений множеств на обозначения пропозициональных переменных, знака  на знак &, знака  на знак Ú, и прочтением как отрицания. Однако обратное неверно, не всякой формуле алгебры логики соответствует формула алгебры множеств. Это обусловлено тем, что любое отношение между высказываниями является высказыванием, т.е. имеет некоторое значение истинности, как и исходные высказывания. Отношение же между множествами множеством не является (оно может быть только истинно- если такое отношение имеет место, или ложно – в противном случае).