Элементы логики

Тот факт, что формула B является логическим выводом формул AB и A, играет в математике очень важную роль. Он позволяет из уже известных истинных утверждений AB и A получить новое истинное утверждение B. Заметим, что такой способ получения, или выведение новых утверждений в математической логике является одним из основных. Такое выведение задается специальным правилом выведения, которое имеет вид и название modus ponens (правило отделения). Оно позволяет получить вывод B утверждения AB как отдельное высказывание, то есть отделить его вид предпосылки A. В математической логике существуют и другие правила выведения, но здесь мы их не рассматриваем.

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

Второй способ получения новых истинных высказываний заключается в применении упомянутых правил выведения к уже известным истинным высказываниям. При этом формулируется система высказываний-тавтологии, которая составляет основу для выведения других. Они называются аксиомами, а высказывания, которые выводятся, - теоремами. Примером аксиомы может служить высказывание AA, которое называется законом исключенного третьего. Такой способ порождения высказываний называется исчислением высказываний.

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

5. Неформальное знакомство с кванторами

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

Каждый человек смертен.

Сократ - человек.

Отсюда выплывает, что Сократ смертен.

Очевидно, что высказывание "Сократ смертный" не является логическим выводом предпосылок "Каждый человек смертен" и "Сократ - человек". Однако корректность приведенных рассуждений ни у кого не вызывает сомнения. Очевидно, что она предопределена каким-то особенным содержанием слова "каждая".

Введем дополнительные обозначения. Пусть x помечает некоторую переменную, значения которой могут иметь некоторое свойство P. Такие переменные называются предметными. Высказывание "x имеет свойство P" обозначим P(x). Например, высказывание "Целое число x является парным" обозначим E(x). Значение такого высказывания зависит от значения этой переменной. При x=1 высказывание E(x) ошибочное, при x=2 - истинное. Вместо буквы x можно записать ее значение, например, E(2).

Предложение "Каждое значение x имеет свойство P", или "Все значения x имеют свойство P", или "Все x имеют свойство P", или "При всех x исполняется свойство P" обозначим записью x P(x). В этой записи часть x называется квантором всеобщности. Слово "квантор" происходит от слова "квантификация", которое означает "количественное выражение". Продолжая пример о парных числах, заметим, что утверждение x E(x) является ошибочным.

Предложение "Существует значение x, что имеет свойство P", или "Некоторые значения x имеют свойство P", или "При некотором значении x исполняется свойство P", или "Некоторые x имеют свойство P" обозначим записью x P(x). В этой записи часть x называется квантором существования. Очевидно, что в примере о парных числах утверждения x E(x) является истинным.

Очевидно, что

x P(x)  x P(x),



Вернуться назад