4. Основы логики.

 

Элементы математической логики

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

  Составные высказывания

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

Приведем примеры высказываний.

Пример 1, Волга впадает в Каспийское море.

Пример 2. Два больше трех.

Первое высказывание является истинным, а второе — ложным.

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

Поставим в соответствие высказыванию логическую переменную х, которая принимает значение 1, если высказывание истинно, и 0, если высказывание ложно.

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

Это новое высказывание называется составным, в то время как вы­сказывания, из которых оно образовано, называются его простыми со­ставляющими или компонентами. Любое высказывание, даже такое, ко­торое на самом деле является сложным, может быть использовано в ка­честве одного из простых составляющих какого-то другого составного высказывания.

2. Простейшие связки

Значение истинности составного высказывания определяется значе­ниями истинности его компонент.

Высказывания будем обозначать прописными буквами латинского алфавита X, У, Z ....

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

Пусть даны два произвольных высказывания X и У.

Отрицанием высказывания X называется высказывание X, которое истинно, когда X ложно, и ложно, когда X истинно. Таблица истинности для отрицания.

 

X	X
0	1
1	0

Конъюнкцией двух высказываний X и У называется высказывание X Л У, которое истинно только в том случае, когда X и У оба истинны. Таблица истинности для конъюнкций.

 

X	Y	ХЛУ
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкцией двух высказываний X и У называется высказывание X V Y, которое истинно, когда хотя бы одно из них истинно. Таблица истинности дизъюнкций.

 

X	Y	X>Y
0	0	0
0	1	1
1	0	1
1	1	1

Импликацией двух высказываний X и У называется высказывание X    У, которое ложно тогда и только тогда, когда X истинно, а У ложно. Таблица истинности для импликации.

 

X	Y	Х-У
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентностью высказываний X и У называется высказывание X <-» У, которое истинно тогда и только тогда, когда X и У оба истинны или ложны.

Таблица истинности для эквивалентности.

 

X	Y	Х-У
0	0	1
0	1	0
1	0	0
1	1	1

 

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

Например, составными будут высказывания:

(xay);   x Л X;   (x V У) V x.

Их следует читать «изнутри наружу», подобно алгебраическим вы­ражениям, в которых сначала группируются величины, заключенные в самые внутренние скобки, затем эти скобки в свою очередь группируются и т. д. Если скобок нет, то операции надо выполнять в следующем поряд­ке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрица­ние. Каждое составное высказывание имеет свою таблицу истинности, которая может быть построена стандартным образом.