ЛОГИКА ВЫСКАЗЫВАНИЙ

Математическая логика изучает базовые понятия синтак­сиса (формы) и семантики (содержания) естественного языка. Рассмотрим три крупных направления исследований в матема­тической логике — логику высказываний, логику предикатов и теорию доказательств. Эти направления потребуются при изучении кибернетических и интеллектуальных систем.

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

 

Определения

Определение 1. Высказыванием называется повество­вательное предложение (текст) естественного языка, о котором имеет смысл говорить истинно оно или ложно.

 

Например, «студент Петров присутствует на лекции», «эта стена белая», «3³ = 28» и т.д.

 

Предложение «Город х стоит на реке у» не явля­ется высказыванием, пока не заданы х и у, так как здесь нельзя определить истина это или ложь.

Из данных высказываний можно составлять новые, сложные высказывания с помощью так называемых логических опера­ций.

Истинность значений сложных высказываний определяет­ся только истинностью значений составляющих высказываний, а не их смыслом. Простейшие высказывания, в которых не вы­деляются части, являющиеся высказываниями, будем обозна­чать прописными латинскими буквами А, В, ..., Р, ... и называть атомарными.

Определение 2. Отрицанием высказывания Р называ­ется высказывание, истинное тогда и только тогда, когда Р лож­но. Отрицание Р обозначается ]Р или Р и читается «не Р».

Отрицание высказывания определяется табл. 1.

Таблица истинности отрицания

P
И	Л
Л	И

В естественном языке отрицание соответствует составлению из высказывания Р нового высказывания «неверно, что Р», или «не Р».

Определение 3. Конъюнкцией двух высказываний Р и Q называется высказывание, истинное тогда и только тогда, ко­гда истинны оба высказывания. Конъюнкция Р и Q обозначается Р & Q или Р Q и читается «Р и Q».

Конъюнкция определяется

Таблица истинности конъюнкции

P	Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

В естественном языке конъюнкция соответствует соединению высказываний союзом «и».

Определение 4. Дизъюнкцией двух высказываний Р и Q называется высказывание ложное тогда и только тогда, когда ложны оба эти высказывания.

Дизъюнкция высказываний Р и Q обозначается Р V Q и читается «Р или Q».

Дизъюнкция определяется табл. 3.

Таблица 3.

Таблица истинности конъюнкции

P	Q
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

В естественном языке дизъюнкция соответствует соединению высказываний союзом «или» в неразделительном смысле.

Рассмотрим теперь сложное высказывание, которое в есте­ственном языке выражают, например, фразой «если Р, то Q» (или «из Р следует Q», или «Р влечет Q»). Жизненный опыт подсказывает, что истинность этого высказывания должна обо­значать следующее:

если Р истинно, Q «обязано» быть истин­ным (следовать из Р);

если же Р ложно, то на Q нет ограниче­ний, оно может быть как истинным, так и ложным (из ложного утверждения ничего не следует).

Значит, «из Р следует Q» ложно в единственном случае: Р истинно, Q ложно.

Следующие высказывания служат примерами:

1) если 0 = 0, то 1 = 1;

2) если 0 = 1, то 0 = 0;

3) если 0 = 0, то 0 = 1;

4) если 0 = 1, то 1 = 2.

Первое утверждение истинно, так как, используя равенство 0 = 0 и другие свойства чисел, можно вывести 1 = 1, прибавляя по единице к обеим частям равенства 0 = 0.

Второе утверждение тоже естественно считать истинным, так как, умножая на нуль обе части равенства 0 = 1, получим 0 = 0.

Третье приходится считать ложным, так как исходя из ис­тинного равенства 0 = 0 с помощью умозаключений никогда не придем к ложному.

Четвертое естественно считать истинным. Прибавляя к обе­им частям равенства 0 = 1 по 1, получим 1 = 2.

Используя оборот «если Р, то Q» как логическую операцию, определим ее следующим образом.

Определение 5. Импликацией двух высказываний Р и Q называется высказывание ложное тогда и только тогда, когда Р истинно, a Q ложно.

Импликация высказываний обозначается Р => Q, или Р Q и читается: «Р влечет Q», или «если Р то Q», или «из Р следует Q», или «пусть Р, тогда Q», или «Р является достаточным для Q», или «Q является необходимым для Р».

Высказывание Р называется посылкой импликации, a Q -заключением.

Таблица 4. Таблица истинности импликации и эквивалентности

P	Q
И	И	И	И
И	Л	Л	Л
Л	И	И	Л
Л	Л	И	И

Определение 6. Эквивалентностью двух высказыва­ний Р и Q называется высказывание, истинное тогда и только тогда, когда истинности Р и Q совпадают. Эквивалентность обо­значается Р ~ Q и читается: «Р эквивалентно Q», или «Р тогда и только тогда, когда Q», или «Р является необходимым и доста­точным для Q».

 

Формулы логики высказываний

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

Определение 7. Алфавитом называется любое непустое множество. Элементы этого множества называются символа­ми (буквами) данного алфавита.

Определение 8. Словом в данном алфавите называется произвольная конечная последовательность символов (возмож­но, пустая).

Слово а называется подсловом слова b, если b = b₁ a b₂ для некоторых слов b₁ и b₂.

Всякое подмножество слов данного алфавита называется языком в этом алфавите.

Рассмотрим язык логики высказываний, т. е. подмножество слов в некотором выделенном алфавите. Слова в языке логики высказываний принято называть формулами логики высказыва­ний. Эти формулы используются для моделирования высказы­ваний.

Определение 9. Пусть известно.

1. Алфавит логики высказываний содержит следующие символы: высказывателъные переменные Х₁, Х₂, логи­ческие связки &, , , =>, ~; символы скобок (, ), которые в дальнейшем будут играть разные роли.

2. Всякая высказывательная переменная есть формула, кото­рая называется атомарной.

3. Если а — формула, то (а) — формула. Если а и b — форму­лы, то (а&b), (а V b), (а => b), (а ~ b) — формулы.

4. Других правил образования формул нет.

Замечание 1. Вместо высказывательных переменных Х₁, . . ., Х_п, ... иногда удобно пользоваться прописными латинскими буквами без индексов.

Пример 1. Слово (((А)&В) => (BА)) — формула.

Слово (А & В) => В A не является формулой (нет скобок).

Слово ((АВ) => (В A)) — не формула, так как знак не бинарная связка.

Замечание 2. Удобно при записи формул по умолчанию опус­кать внешние скобки и скобки при отрицании высказывательных пере­менных, например формула из примера 1:

(А&В) => (В A).

Определение 10. Логические связки в логике высказыва­ний задают алгебраические операции на множестве Ф всех вы­сказываний.

Отрицание — унарная алгебраи­ческая операция, остальные четыре логические связки: конъ­юнкция, дизъюнкция, импликация, эквивалентность - бинар­ные алгебраические операции.

В связи с этим логика высказыва­ний — алгебра с пятью алгебраическими операциями (Ф, &, V, =>, ~, ), которая называется алгеброй логики высказываний.

 

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

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

Семантика языка логики высказываний изучает смысл фор­мул (слов языка) с точки зрения их оценивания на истинность. Вопросы семантики часто решаются с помощью таблиц истин­ности формул.

 

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

 

Правила преобразования формул

Определение 11. Пусть а и b — две формулы, зависящие от одного и того же множества высказывательных переменных.

Эти формулы называются равносильными, если на любой оценке переменных они принимают одинаковые значения.

Равносильность формул а и b логики высказываний будем обозначать a ≡ b, так же как равносильность формул в элемен­тарной алгебре, например a³ — b³ ≡ (a - b)(a² + ab + b ).

Пояснение. Оценка переменных — набор истинностных зна­чений данных переменных.

Равносильность формул имеет свой алгебраический аналог в тождественном равенстве алгебраических выражений.

Замечание. Нужно различать символы «≡» и «~».

Символ «~» является символом логической операции формального языка (это необходимо и достаточно).

Символ «≡» является метасимволом. Он не принадлежит алфавиту языка логики высказываний и говорит о равносильности слов с точки зрения их семантики.

 

Основные равносильности.

Для любых формул a, b, c справедливы следующие равносильности.

1. a&b=b&a (коммутативность операции &).

2. a&a = а (идемпотентность операции &).

3. а & (b & с) = (а & b) & с (ассоциативность операции &).

4. а b = b а (коммутативность операции ).

5. а а = а (идемпотентность операции ).

6. а (b с) = (а b) с (ассоциативность операции ).

7. a(b&с) = (аb)&(aс) (дистрибутивность операции относительно операции &).

8. a&(bс) = (a&b)(а&с) (дистрибутивность операции & относительно операции ).

9. а & (а b) = а (первый закон поглощения).

10. а (а&b) = а (второй закон поглощения).

11. а = а (снятие двойного отрицания).

12. (a&b) = ab (первый закон де Моргана).

13. (а b) = а &b (второй закон де Моргана).

14. а = (a&b)(а& b) (первая формула расщепления).

15. а = (ab)&(аb) (вторая формула расщепления).

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

Еще одна группа равносильностей показывает, что одни связ­ки могут быть выражены через другие.

16. а ~ b ≡ (а b)&(bа) ≡ (a&b) (a&b).

17. a=>b≡ab≡(a&b).

18. ab≡ab≡(a&b).

19. a&b≡(a =>b) ≡(a&b).

Рассмотрим доказательство приведенных равносильностей на примерах тождеств 8, 10, 15. При этом в методических целях приведем три различных способа доказательства.

Пусть в тождестве 8 формулы a, b, с — атомарные, т. е. a = А, b = B, с = С.

Таблица 6

Таблица истинности равносильных формул

A	B	C
И	И	И	И	И	И	И	И
И	И	Л	И	И	Л	И	И
И	Л	И	И	И	Л	И	И
И	Л	Л	Л	Л	Л	Л	Л
Л	И	И	И	Л	Л	Л	Л
Л	И	Л	И	Л	Л	Л	Л
Л	Л	И	И	Л	Л	Л	Л
Л	Л	Л	Л	Л	Л	Л	Л

 

Рассмотрим табл. 6. Пятый и восьмой столбцы в таблице совпадают, следовательно, тождество доказано. Этот способ до­казательства равносильности назовем табличным.

 

Теперь докажем тождество 10 (второй закон поглощения) пу­тем логических рассуждений. Этот способ называется логиче­ским. Он имеет два хода рассуждения: «слева—направо» и «справа — налево».

Ход «слева —направо». Пусть в тождестве 10 слева будет ложь, т.е. а (а&b) = Л. Тогда по определению дизъюнкции будет: а = Л и (а&b) = Л. Тем самым получили, что справа в тождестве 10 имеем ложь: а = Л.

Ход «справа— налево». Пусть в тождестве 10 справа будет ложь, т. е. a = Л. Тогда для левой части тождества 10 имеем ложь. В самом деле (а&b) = Л. Тем самым а (а&b) = Л.

Тождество 10 полностью доказано. Рассматривать отдельно случай, когда слева и справа в данном тождестве истина нет необходимости, так как его доказательство можно провести рас­суждением от противного и использованием уже доказанного.

Например, пусть слева в тождестве — истина, тогда и спра­ва будет истина, так как в противном случае, если справа бу­дет ложь, то, по доказанному, слева будет ложь. А это проти­воречит предположению. Аналогично рассматривается случай «справа- налево».

Итак, в логическом способе доказательства равносильности достаточно рассматривать один случай — или для истины, или для лжи, но обязательно в два хода: «слева — направо» и «спра­ва— налево».

 

Теперь докажем тождество 15 (вторая формула расщепле­ния) третьим способом, который назовем алгебраическим.

Суть способа состоит в использовании уже доказанных равносильностей для преобразования левой и правой частей тожде­ства к одному и тому же виду.

Рассмотрим правую часть тождества 15. Воспользуемся тож­деством 7, которое предполагаем доказанным. Тогда вынесем а за скобки, будем иметь (ab)&(аb)≡а(b&b) ≡ а, так как (b&b) ≡Л.

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

 

Рассмотрим правила, с помощью которых удобно переходить от одних равносильностей к другим.

Теорема 1 (правило равносильных добавлений и удалений формул).

Если а, b и с — произвольные формулы, то следующие равносильности выполняются и не выполняются одновременно:

a ≡ b; a ≡ b;

a&с ≡ b&с; с&a ≡с&b;

aс≡bс; сa≡ cb;

a => с≡ b => с; с => a ≡ с =b;