ЛЕКЦИЯ 1. Лекция 1 введение в математическую логику

• Название: Лекция 1 введение в математическую логику
• Дата: 01.11.2018
• Размер: 64 Kb.
• Имя файла: ЛЕКЦИЯ 1.doc
• Тип: Лекция; #55152

ЛЕКЦИЯ № 1

ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ
Родоначальником науки о логике является греческий философ Аристотель (384-322 г. до н.э.). Он, используя законы человеческого мышления, формализовал известные до него правила рассуждений. Лишь в конце XVII века немецкий математик Г. Лейбниц предложил математизировать формальные рассуждения Аристотеля, вводя символьное обозначение для основных понятий и используя особые правила, близкие к вычислениям. Лейбниц утверждал, что “мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, чтобы облегчить сам процесс нашего мышления”.

Применение математики в логике определило новую науку – математическую логику. Математическая логика — это логика, развиваемая с помощью математических методов.

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

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

Математическое описание логики следует воспринимать, как некую формальную систему, оперирующую с символами по определенным правилам, об­легчающим интерпретацию в реальном мире.

Выделяют несколько типов математических моделей формальной логики.

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

Логика предикатов (predicate calculus) есть модель формальной сис­темы, предметом которой являются повествовательные предложения с учетом их внутренних состава и струк­туры.

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

Логика реляционная (relation calculus) есть модель формальной системы, предметом кото­рой являются отношения в виде множества однородных повествовательных предложений, существенно расширяющие логику предикатов.
Исходным понятием математической логики является “высказывание”. Поэтому любое повествовательное предложение, которое может быть признано истинным или ложным, называют высказыванием. Логическим значением высказывания являются “истина” или “ложь”.

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Например, повествовательное предложение "З есть простое число" является истинным, а “3.14… - рациональное число" - ложным, "Колумб открыл Америку" - истинным, а "Киев - столица Узбекистана" – ложным, “Число 6 делится на 2 и на 3” – истинным, а “Сумма чисел 2 и 3 равна 6” – ложным и т.п.
Такие высказывания называют простыми или элементарными. При формальном исследовании сложных текстов вместо понятия “простые высказывания” замещают понятием “пропозициональные переменные” (от лат. propositio - предложение), которые обозначают прописными буквами латин­ского алфавита “A”, “B”, “C”,… Истинность или ложность высказывания будем отмечать символами “и” – истина или “л” – ложь.

Пример:

1. 
   если A₁:=“3 - простое число”, то A₁ = и;
   
2. 
   если A₂:=“3 - целое число”, то A₂ = и;
   
3. 
   если B₁:=“3, 14…- рациональное число”, то B₁ = л;
   
4. 
   если B₂:=“3, 14…- не рациональное число”, то B₂ = и;
   
5. 
   если С:= “Число 6 делится на 1, 2 и 3”, то С = и;
   
6. 
   если D:=“Число 6 есть сумма чисел 1, 2, 3”, то D = и.
   

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения “ученик десятого класса” и “информатика — интересный предмет”. Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие “интересный предмет”. Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.

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

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

Высказывания, которые получаются из простых предложений с помощью грамматических связок “не”, “и”, “или”, “если…, то…”, “… тогда и только тогда, когда…” и т.п., называют сложными или составными. Для обозначения грамматических связок вводят символы, которые называют логическими(илипропозициональными)связками. Например, :=”или”, &:=“и”, :=”не”, :=“если…, то…”, :=“…тогда и только тогда, когда …”.

Пример:

1. 
   если высказывание “3 – вещественное или целое число”, то формула (A₁A₂) = и;
   
2. 
   если высказывание ”3,14… - рациональное число”, то B₁=л, а ”3,14… - не рациональное число”, то B₁ = и;
   
3. 
   если высказывание “число 6 делится на 1, 2, 3 и представляет сумму делителей 1, 2, 3”, то формула (С&D)= и;
   
4. 
   если высказывание ”если 3 – простое число, то оно целое”, то формула (A₁ A₂)=и;
   
5. 
   если высказывание “3 есть простое число тогда и только тогда, когда оно целое”, то формула (А₁А₂)=и.
   

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

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

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

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

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний. Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Джоржем Булем, прежде чем в 1938 году выдающийся американский математик и инженер Клод Шеннон показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе и для функционирования релейно-контактных и электронно-ламповых схем.

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

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

Упражнения:

1. 
   Установите, какие из следующих предложений являются логическими высказываниями, а какие — нет (объясните почему):
   

а) “Солнце есть спутник Земли”;

б) “2+3ґ4”;

в) “сегодня отличная погода”;

г) “в романе Л.Н. Толстого “Война и мир” 3 432 536 слов”;

д) “Санкт-Петербург расположен на Неве”;

е) “музыка Баха слишком сложна”;

ж) “первая космическая скорость равна 7.8 км/сек”;

з) “железо — металл”;

и) “если один угол в треугольнике прямой, то треугольник будет тупоугольным”;

к) “если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный”

2. 
   Укажите, какие из высказываний предыдущего упражнения истинны, какие — ложны, а какие относятся к числу тех, истинность которых трудно или невозможно установить
   

3. 
   Сформулируйте отрицания следующих высказываний или высказывательных форм:
   

а) “Эльбрус — высочайшая горная вершина Европы”;

б) “2>=5”;

в) “10<7”;

г) “все натуральные числа целые”;

д) “через любые три точки на плоскости можно провести окружность”;

е) “теннисист Кафельников не проиграл финальную игру”;

ж) “мишень поражена первым выстрелом”;

з) “это утро ясное и теплое”;

и) “число n делится на 2 или на 3”;

к) “этот треугольник равнобедренный и прямоугольный”;

л) "на контрольной работе каждый ученик писал своей ручкой".

4. 
   Сформулируйте отрицания следующих высказываний или высказывательных форм:
   

а) “Эльбрус — высочайшая горная вершина Европы”;

б) “2>=5”;

в) “10<7”;

г) “все натуральные числа целые”;

д) “через любые три точки на плоскости можно провести окружность”;

е) “теннисист Кафельников не проиграл финальную игру”;

ж) “мишень поражена первым выстрелом”;

з) “это утро ясное и теплое”;

и) “число n делится на 2 или на 3”;

к) “этот треугольник равнобедренный и прямоугольный”;

л) "на контрольной работе каждый ученик писал своей ручкой".

5. 
   Определите, какие из высказываний (высказывательных форм) в следующих парах являются отрицаниями друг друга, а какие нет:
   

а) “5<10”, “5>10”;

б) “10>9”, “10<=9”;

в) “мишень поражена первым выстрелом”, “мишень поражена вторым выстрелом”;

г) “машина останавливалась у каждого из двух светофоров”, “машина не останавливалась у каждого из двух светофоров”,

д) “человечеству известны все планеты Солнечной системы”, “в Солнечной системе есть планеты, неизвестные человечеству”;

е) “существуют белые слоны”, “все слоны серые”;

ж) “кит — млекопитающее”, “кит — рыба”;

з) “неверно, что точка А не лежит на прямой а”, “точка А лежит на прямой а”;

и) “прямая а параллельна прямой b”, “прямая a перпендикулярна прямой b”;

к) “этот треугольник равнобедренный и прямоугольный”, “этот треугольник не равнобедренный или он не прямоугольный”.

6. 
   Определите значения истинности высказываний: реднем образовании достаточно для поступления в институт”;
   

б) “наличие аттестата о среднем образовании необходимо для поступления в институт”;

в) “если целое число делится на 6, то оно делится на 3”;

г) “подобие треугольников является необходимым условием их равенства”;

д) “подобие треугольников является необходимым и достаточным условием их равенства”;

е) “треугольники подобны только в случае их равенства”;

ж) “треугольники равны только в случае их подобия”;

з) “равенство треугольников является достаточным условием их подобия”;

и) “для того, чтобы треугольники были неравны, достаточно, чтобы они были неподобны”;

к) “для того, чтобы четырёхугольник был квадратом, дт ьостаточно, чтобы его диагонали были равны и перпендикулярны”.