WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
И.С. Фролов ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Самара 2001 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра алгебры и геометрии И.С. Фролов ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Учебное пособие для студентов математических специальностей Издательство Самарский университет 2001 УДК 517.11 ББК 22.12 Ф 912 Фролов И.С. Элементы математической логики: Учеб. пособие для студентов математических специальностей. Самара: Изд-во Самарский университет, 2001. С. 80.

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

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

ББК 22.12 Рецензент канд. физ.-мат. наук, доц. В.Л. Шур © Фролов И.С., 2001 © Издательство Самарский университет, 2001 Редактор Т.И. Кузнецова Компьютерная верстка, макет И.С. Фролов Л.Р. № 020316 от 04.12.96. Подписано в печать 21.06.2001. Формат 6084/16.

Бумага офсетная. Печать офсетная. Усл. печ. л. 4,65; уч.-изд.л. 5,0.

Тираж 300 экз. Заказ № Издательство Самарский университет.

443011 г. Самара, ул. Акад. Павлова, 1.

УОП СамГУ, ПЛД № 67-43 от 19.02.98.

Введение 1. Традиционная логика Логикой называется наука о законах и формах мышления. Развитие логики на Востоке (Древняя Индия) и на Западе (Древняя Греция) шло различными путями. Одним из важнейших моментов в истории всей западной цивилизации было создание Аристотелем (384–322 гг. до н.э.) формальной логики, изучающей формы правильных рассуждений.

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

английским математиком Джорджем Булем (1815–1864) трактата Математический анализ логики, посвященного алгебраизации формальной логики.

Традиционная логика Аристотеля имеет дело с понятиями, суждениями и умозаключениями. Суждения описывают простейшие взаимоотношения между понятиями. Четыре классических типа суждений:

A(S, P ) общеутвердительное : все S суть P ;

E(S, P ) общеотрицательное : ни одно S не есть P ;

I(S, P ) частноутвердительное : некоторые S суть P ;

O(S, P ) частноотрицательное : некоторые S не суть P в современной символике представляются так:

A : x(S(x) P (x)), I : x(S(x) P (x)), E : x(S(x) ¬P (x)), O : x(S(x) ¬P (x)).

Формальная логика устанавливает ряд свойств суждений. Одно из таких свойств отношение противоречия между суждениями типов A и O (а также между I и E): суждение типа A истинно тогда и только тогда, когда суждение типа O с теми же членами ложно. Например, из истинности суждения Все птицы животные вытекает ложность суждения Некоторые птицы не животные.

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

Во всяком прямоугольнике диагонали равны.

Всякий квадрат есть прямоугольник.

Следовательно, во всяком квадрате диагонали равны.

Этот силлогизм построен по следующей схеме, содержащей три общеутвердительных суждения:

A(M, P ) A(S, M).

A(S, P ) В современных обозначениях ему соответствует схема вывода x(M(x) P (x)) x(S(x) M(x)) x(S(x) P (x)) и даже более короткая логическая формула ((M P ) (S M)) (S P ).

Какие еще существуют аналогичные правила умозаключения Возможны четыре схемы, или, как принято говорить, четыре фигуры силлогизма:

I II III IV ·(M, P ) ·(P, M) ·(M, P ) ·(P, M) ·(S, M) ·(S, M) ·(M, S) ·(M, S).

·(S, P ) ·(S, P ) ·(S, P ) ·(S, P ) В каждой из схем вместо точек можно 43 = 64 способами расставить буквы A, E, I, O. Получается 256 мыслимых правил (в традиционной терминологии модусов силлогизма). Однако не все из них будут правильны, а лишь 19. Им даны следующие названия:

I фигура II фигура III фигура IV фигура Barbara Cesare Darapti Bramantip Celarent Camestres Disamis Camenes Darii Festino Datisi Dimaris Ferio Baroco Felapton Fesapo Bocardo Fresison Ferison Гласные буквы в этих бессмысленных, но служащих мнемонике словах указывают на выбор букв A, E, I, O. Выше уже был приведен пример силлогизма, относящегося к модусу I фигуры bArbArA. Рассмотрим еще один пример. Модус III фигуры fElAptOn имеет вид:

E(M, P ) A(M, S).

O(S, P ) К этому модусу относится умозаключение:

Ни один дельфин не рыба.

Все дельфины морские обитатели.

Следовательно, некоторые морские обитатели не рыбы.

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

2. Логические парадоксы Новый этап в развитии логики, начавшийся с середины XIX в., был связан с возникновением абстрактного аксиоматического метода.



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

Некоторые из них были известны еще с древности.

Парадокс лжеца самый старый и самый известный из логических парадоксов. Легенда приписывает жившему на острове Крит в VI в. до н.э. поэту Эпимениду изречение Все критяне лжецы.

Такое высказывание в устах критянина, конечно, странно, хотя противоречия здесь еще нет: можно просто заключить, что это предложение ложно. Но ситуация изменится, если, как заметил Эвбулид из Милета (IV в. до н.э.), кто-либо скажет: Предложение, которое я сейчас произношу, ложно. Из истинности этой фразы следует, что она ложна, а из ложности что она не ложна, т.е. истинна. Это и есть парадокс лжеца.

Парадокс Рассела. Назовем множество особым, если оно является своим собственным элементом (например, множество всех множеств). Пусть R множество всех неособых множеств. Если R особое множество, то R R по определению особого множества и R R по определению R. Если R неособое множество, то опять R R, но на этот раз по определению R, и R R, т.к. R не является особым. Любое из предположений: R – особое множество, R – неособое множество ведет к противоречию.

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

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

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

§1. Логика высказываний 1. Логические связки В логике высказываний нас интересуют утвердительные предложения, которые могут быть истинными или ложными, но не теми и другими одновременно. Каждое такое утвердительное предложение называется высказыванием. Примеры высказываний: Волга впадает в Каспийское море, Все киты суть рыбы, 5 нечетное число.

Высказывания будем обозначать буквами A, B, C,..., например, A : 15 делится на 3, B : во всяком треугольнике все углы острые.

Буквы, использующиеся для обозначения высказываний, называются логическими атомами. При фиксированном множестве атомов A = {A, B, C,...} интерпретацией называется функция I, отображающая это множество в множество истинностных (логических) значений T = {истина,ложь}, I : A T.

Иными словами, интерпретация это приписывание каждому атому истинностного значения истинаилиложь. Если атом обозначает некоторое конкретное высказывание, например, C : 2 2 = 4, D : 3 < 2, то существует естественная интерпретация этих атомов: I(C) =, I(D) =.

Истинностные значенияистина,ложьсокращенно обозначаются И, Л, или T, F, или 1, 0.

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

Отрицание. ¬A : не-A, неверно, что A. Если A интерпретировано, то ¬A также получит истинностное значение с помощью следующей таблицы истинности (таблицы значений):

A ¬A 0 1 Итак, ¬A ложно, если A истинно, и ¬A истинно, если A ложно.

Конъюнкция. A B : A и B. Смысл этой связки очевиден:

высказывание A B истинно, если A и B одновременно истинны.

Дизъюнкция. A B : A или B. (Лат. Vel соединительное или в отличие от aut разделительного или ). В русском языке слово или используется в двух значениях: соединительном и разделительном. В математической логике эти значения следует строго различать. Высказывание A B истинно, если A истинно, или B истинно, или и A, и B истинны одновременно.

Импликация. A B : если A, то B, из A следует B, A влечет B. Импликация A B истинна, когда A и B истинны, и ложна, когда A истинно, а B ложно. Но нет оснований считать импликацию ложной, если A ложно.

Например, пусть о целом числе x мы делаем высказывание: Если x полный квадрат, то x неотрицательно. Это истинное составное высказывание импликация. Однако и при x = -1, и при x = 5 его первая часть x полный квадрат ложна.

Поэтому высказывание A B считается истинным, и когда A ложно, независимо от логического значения B.

Эквиваленция. A B : A тогда и только тогда, когда B.

Иными словами, высказывание A B истинно, если истинностные значения A и B совпадают.

Таблицы истинности для четырех бинарных1 логических связок можно объединить в одну:

A B A B A B A B A B 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 Каждая строка в таблице истинности соответствует определенной интерпретации.

2. Логические формулы Объекты, конструируемые из атомов с помощью логических связок, называются формулами логики высказываний. Определим более точно понятие логической формулы.

Определение. Формулами называются выражения, сконструированные из атомов A, B, C,... и связок ¬,,,, по следующим правилам:





(1) атом есть формула;

(2) если G и H формулы, то (¬G), (G H), (G H), (G H), (G H) формулы.

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

Пример 1. Формула F1 = ((A (¬B)) C) имеет подформулы:

A, B, C, (¬B), (A (¬B)); сама формула F1 также считается своей подформулой.

т.е. двуместных.

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

( ( A ( ¬B ) ) C ) 1 2 3 3 2 или выделив каждую подформулу (не являющуюся атомом) подчеркиванием от скобки до скобки:

((A (¬B)) C).

Структура формулы, ее конструкция из связок и подформул еще более явно выражена в дереве формулы F1. В каждой вершине такого дерева находится логическая связка, и из нее выходит две (для бинарных связок) или одна (для отрицания) ветвь, ведущая к де C реву соответствующей подформулы. В конA ¬ цевых вершинах (листьях дерева) находятся B атомы.

Часто принимается соглашение о приоритетах логических связок:

¬,,,, (в порядке убывания приоритета), позволяющее сократить число скобок. Мы тогда можем записать: F1 = A ¬B C.

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

Пример 2. Построим таблицу значений для формулы F2 = ¬A B C:

A B C ¬A ¬A B F 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0 1 Другой способ вычисления логических значений состоит в следующем. Будем обозначать |F |I или просто |F | значение формулы F при заданной интерпретации I. В предположении, что логические значения формул суть числа 0 или 1, легко проверить, что |¬A| = 1 - |A|, |A B| = |A| · |B| = min(|A|, |B|), |A B| = |A| + |B| - |A| · |B| = max(|A|, |B|), 1, если |A| |B|, |A B| = 1 - |A| + |A| · |B| = 0, если |A| > |B|, 1, если |A| = |B|, |A B| = 1 - - |B| = |A| 0, если |A| = |B|.

Пример 3. Найдем логическое значение формулы F3 = (A B) (¬A B):

|F3| = 1 - |A B| - |¬A B| = 1 - - |A| + |A| · |B|) - ((1 - |A|)+ (+|B| - (1 - |A|) · |B|) = 1 - - |A| + |A| · |B|) - (1 - |A| + |A| · |B|) = 1, (т.е. формула F3 всегда истинна.

Формула называется тождественно истинной (или общезначимой) формулой, если она получает значениеистинапри любой интерпретации. Другое название общезначимой формулы тавтология.

Общезначимость формулы G обозначается |= G.

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

Пример 4. Формула A A является тавтологией, формула A¬A противоречием, как показывает следующая таблица значений:

A A A A ¬A 0 1 1 1 Формула называется выполнимой, если существует интерпретация, при которой она истинна (такая интерпретация называется моделью формулы), и опровержимой, если найдется интерпретация, при которой она ложна. Например, для формулы F2 (см. пример 2) имеется пять моделей, соответствующих строкам с единицей в последней колонке одна из них представляет собой интерпретацию I(A, B, C) = (0, 0, 1); остальные: (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 1).

Упражнение 1. Что является отрицанием высказываний: Формула F общезначима, Формула F выполнима Упражнение 2. Докажите, что если формула не общезначима и не противоречива, то она выполнима и опровержима одновременно.

3. Логические эквивалентности Необходимо знать простые примеры общезначимых формул и уметь применять их для получения других общезначимых формул.

Теорема 1. Следующие формулы тождественно истинны:

(1) A B B A A B B A (коммутативность) (2) (A B) C A (B C) (A B) C A (B C) (ассоциативность) (3) (A B) C (A C) (B C) (A B) C (A C) (B C) (дистрибутивность) (4) ¬(A B) (¬B ¬A) ¬(A B) (¬B ¬A) (законы Де М органа) (5) ¬¬A A (закон двойного отрицания) (6) ¬(A ¬A) (закон отрицания противоречия) (7) A ¬A (закон исключенного третьего) (8) A A (закон тождества) (9) A A A A A A (законы идемпотентности) (10) A B ¬A B (закон импликации) (11) (A B) (A B) (B A) (закон эквиваленции).

Доказательство проводится с помощью построения таблиц истинности. Например, для 1-го закона Де Моргана (4):

A B A B F1 ¬A ¬B F2 F 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 Обозначения F, F1, F2 использованы для всей формулы и ее подформул, стоящих слева и справа от символа : F1 = ¬(A B), F2 = (¬B ¬A), F = ¬(A B) (¬B ¬A).

Формулы F и G называются (логически) эквивалентными, если |= F G. Будем обозначать (логическую) эквивалентность формул следующим образом: F G. Мы уже имеем некоторый запас эквивалентных формул, с помощью которых можно производить эквивалентные преобразования, аналогичные принятым в алгебре: переставлять члены в конъюнкции и дизъюнкции, опускать скобки в выражениях вида (A B) C и A (B C), раскрывать скобки и т.д. Рассмотрим теперь средства получения новых эквивалентностей.

Теорема 2. Если |= F и |= F G, то |= G.

Зафиксируем произвольную интерпретацию I. По условию |F | = 1 и |F G| = 1, т.е. |F | |G|. Отсюда заключаем, что |G| = 1.

Теорема 3. F G тогда и только тогда, когда формулы F и G имеют одинаковые таблицы значений.

Если F G, то при любой интерпретации I имеем |F G|I = 1, т.е. |F |I = |G|I. Справедливо и обратное.

Пример 5. Запишем закон импликации в виде A B ¬A B. Для его доказательства, согласно теореме 3, достаточно проверить совпадение таблиц истинности формул A B и F = ¬A B:

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.