ТЕМА: МАТЕМАТИЧЕСКАЯ ЛОГИКА. ОСНОВНЫЕ ПОНЯТИЯ.
ПЛАН:
1.
Задачи и
предмет логики.
Математика является наукой, в которой все утверждения
доказываются с помощью умозаключений, то есть путем использования законов
человеческого мышления. Изучение законов человеческого мышления является
предметом логики.
Как самостоятельная наука логика оформилась в трудах
греческого философа Аристотеля (384-322 г. до в.э.). Он систематизировал
известные до него сведения, и эта система стала впоследствии называться формальной
или Аристотелевой логикой.
Формальная логика просуществовала без серьезных изменений
более двадцати столетий. Естественно, что развитие математики выявило
недостаточность Аристотелевой логики и потребовало дальнейшего ее развития.
Впервые в истории идеи о построении логики на математической
основе были высказаны немецким математиком Г. Лейбницем (1646-1716) в конце ХVII века. Он считал, что основные понятия логики должны
быть обозначены символами, которые соединяются по особым правилам. Это позволит
всякое рассуждение заменить вычислением.
«Мы употребляем знаки
не только для того, чтобы передать наши мысли другим лицам, но и для того,
чтобы облегчить сам процесс нашего мышления» (Лейбниц).
Первая
реализация идеи Лейбница принадлежит английскому ученому Д. Булю (1815-1864).
Он создал алгебру, в которой буквами обозначены высказывания, и это привело к
алгебре высказываний. Введение символических обозначений в логику имело для
этой науки такое же решающее значение, как введение буквенных
обозначений для математики. Именно благодаря введению символов в логику была
получена основа для создания новой науки - математической логики.
Применение
математики к логике позволило представить логические теории в новой удобной
форме и применить вычислительный аппарат к решению задач,малодоступных
человеческому мышлению, и это, конечно, расширило область логических
исследований. К концу XIX столетия актуальное значение для математики
приобрели вопросы обоснования ее основных понятий и идей. Эти задачи имели
логическую природу и, естественно, приведи к дальнейшему развитию математической
логики.
Особенности математического мышления объясняются
особенностями математических абстракций и многообразием их взаимосвязей. Они
отражаются в логической систематизации математики, в доказательстве математических
теорем. В связи с этим современную математическую логику определяют как раздел
математики, посвященный изучению математических доказательств и вопросов
оснований математики.
Одной из основных причин развития математической логики является широкое распространение аксиоматического метода в построении различных математических теорий, в первую очередь, геометрии, а затем арифметики, теории групп и т. д.
В аксиоматическом построении математической теории предварительно выбирается некоторая система неопределяемых понятий и отношения между ними. Эти понятия и отношения называются основными. Далее без доказательства принимаются основные положения рассматриваемой теории - аксиомы. Все дальнейшее содержание теории выводится логически из аксиом. Впервые аксиоматическое построение математической теории было предпринято Евклидом в построении геометрии.
Изложение этой теории в «Началах» Евклида не безупречно. Евклид здесь пытается дать определение исходных понятия (точки, прямой, плоскости). В доказательстве теорем используются нигде явно не сформулированные положения, которые считаются очевидными. Таким образом, в этом построении отсутствует необходимая логическая строгость. Отметим, что такой подход к аксиоматическому построению теории оставался единственным до XIX века. Большую роль в изменении такого подхода сыграли работы Н. И. Лобачевского (1792-1856).
Лобачевский впервые в явном виде высказал убеждение в невозможности доказательства пятого постулата Евклида (через точку, не лежащую на прямой проходит одна и только одна прямая, параллельная данной прямой) и подкрепил это убеждение созданием новой геометрии. Позже немецкий математик Ф. Клейн (1849-1925) доказал непротиворечивость геометрии Лобачевского, чем фактически была доказана и невозможность доказательства пятого постулата Евклида.
Так возникли и были решены в работах Н. И. Лобачевского и Ф. Клейна впервые в истории математики проблемы невозможности доказательства и непротиворечивости в аксиоматической теории.
2. Понятие высказывания.
Основным (неопределяемым) понятием математической логики является понятие «простого высказывания».
Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».
Приведем примеры высказываний.
1) Санкт –Петербург стоит на Неве.
2) Париж — столица Англии.
3) Карась не рыба.
4) Число 6 делится на 2 и на 3.
5) Если юноша окончил среднюю школу, то он получает аттестат зрелости.
Высказывания 1), 4), 5) истинны, а высказывания 2) и 3) ложны.
Очевидно, предложение «Да здравствуют наши спортсмены!» не является высказыванием.
Различают два вида высказываний.
Высказывание,
представляющее собой одно утверждение, принято называть простым или
элементарным.
Примерами элементарных высказываний могут служить высказывания 1) и 2).
Высказывания,
которые получаются из элементарных с помощью грамматических связок «не», «и»,
«или», «если .... то ...», «тогда и только тогда», принято называть
сложными или составными.
Так, высказывание 3) получается из простого высказывания «Карась - рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на З», соединенных союзом «и». Высказывание 5) получается из простых высказываний «Юноша окончил среднюю школу», «Юноша получает аттестат зрелости» с помощью грамматической связки «если ..., то ...». Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».
В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
Элементарные высказывания обозначаются малыми буквами латинского алфавита: х, у, z, ..., а, b, с, ...; истинное значение высказывания цифрой 1, а ложное значение - буквой цифрой 0.
Если высказывание а истинно, то будем писать а = 1, а если а ложно, то а = 0.
3. Логические операции над высказываниями
3.1.Отрицание.
Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.
Отрицание высказывания х обозначается и читается «не х» или «неверно, что х».
Логические значения высказывания можно описать с помощью таблицы.
х |
|
0 |
1 |
1 |
0 |
Таблицы такого вида принято называть таблицами истинности.
Пусть х высказывание. Так как также является высказыванием, то можно образовать отрицание высказывания , то есть высказывание , которое называется двойным отрицанием высказывания х. Ясно, что логические значения высказываний х и совпадают.
Например, для высказывания «Река Волхов вытекает из озера Ильмень» отрицанием будет высказывание «Неверно, что река Волхов вытекает из озера Ильмень» или «Река Волхов не вытекает из озера Ильмень», а двойным отрицанием будет высказывание «Неверно, что река Волхов не вытекает из озера Ильмень».
3.2. Конъюнкция.
Конъюнкцией (логическим
умножением) двух высказываний х и у называется новое высказывание,
которое считается истинным, если оба высказывания х и у истинны, и
ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний х и у обозначается символом х&у (х у, ху ), читается «х и. у». Высказывания х и у называются членами конъюнкции.
Логические значения конъюнкции описываются следующей таблицей истинности:
х |
у |
ху |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Например, для высказываний «6 делится на 2», «6 делится на 3» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Из определения операции конъюнкции и отрицания ясно, что высказывание всегда ложно.
3.2.
Дизъюнкция
Дизъюнкцией (логическим сложением) двух высказываний х и
у называется новое высказывание, которое считается истинным, если хотя
бы одно из высказываний х, у истинно, и ложным, если они оба ложны.
Дизъюнкция высказываний х, у обозначается символом «x v у», читается «х или у». Высказывания х, у называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:
х |
у |
хvу |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Например, высказывание: «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».
В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.
Из определения операции дизъюнкции и отрицания ясно, что высказывание всегда истинно.
3.3. Импликация.
Импликацией двух высказываний х и у называется
новое высказывание, которое считается ложным, если х истинно, а у -
ложно, и истинным во всех остальных случаях.
Импликация высказываний х, у обозначается символом х у , читается «если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у - следствием или заключением, высказывание х у следованием или импликацией.
Логические значения операции импликации описываются следующей таблицей истинности:
х |
у |
ху |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
Например, высказывание «Если число 12 делится на 6, то оно делится на 3», очевидно, истинно, так как здесь истинна посылка: «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».
Употребление слов «если .... то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание «Если х, то у» вообще не имеет смысла. Кроме того, строя предложение вида «если х, то у» в обыденной речи, мы всегда подразумеваем, что предложение у вытекает из предложения х. Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «Если х, то у». Если при этом известно, что х истинно и доказана истинность импликации х у, то мы вправе сделать вывод об истинности заключения у.
3.5.
Эквиваленция.
Эквиваленцей (или эквивалентностью) двух
высказываний х и у называется новое высказывание, которое считается истинным,
когда оба высказывания х, у либо одновременно истинны, либо одновременно
ложны, и ложным во всех остальных случаях.
Эквиваленция высказываний х, у обозначается символом х у , читается «для того, чтобы х, необходимо и достаточно, чтобы у» или «х тогда и только тогда, когда у». Высказывания х, у называются членами эквиваленции.
Логические значения операции эквиваленции описываются следующей таблицей истинности:
х |
у |
ху |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Например, эквиваленция: «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда SP = SQ » является истинной, так как высказывания «Треугольник .SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ SP = SQ » либо одновременно истинны, либо одновременно ложны.
Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.
4.Формулы
алгебры логики.
С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний х, у, z можно построить высказывания:
Первое из них есть дизъюнкция конъюнкции х и у и отрицания выказывания z, а второе высказывание есть импликация, посылкой которой является высказывание х,
а заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z.
Всякое сложное высказывание, которое может быть получено из
элементарных высказываний посредством применения логических операций отрицания,
конъюнкции, дизъюнкции, импликации и эквиваленции, называется формулой
алгебры логики.
Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В, С, ...
Для упрощения записи
формул принят ряд соглашений:
скобки можно
опускать, придерживаясь следующего порядка действий:
- конъюнкция выполняется раньше, чем все остальные операции,
- дизъюнкция выполняется раньше, чем импликация и эквивалентность
- если над формулой стоит знак отрицания, то скобки тоже опускаются.
В связи с этим формулы:
могут быть записаны так:
Логическое значение формулы алгебры логики полностью определяется
логическими значениями входящих в нее элементарных высказываний. Например,
логическим значением формулы в случае, если х = 1,
у = 1, z = 0 будет истина, то есть
Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности.
Например, для формулы (указан порядок действий) таблица истинности имеет вид:
х |
у |
1 |
2 |
3 |
4 |
5 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
Первые два столбца- это всевозможные
наборы значений входящих в формулу различных простых высказываний. Легко
видеть, что формула принимает 2n значений, состоящих из нулей и единиц, значит, таблица истинности
содержит столько же строк.
Рассмотрим еще один пример на составление таблицы истинности:
. Таблица содержит 23 = 8 строк:
x |
y |
z |
1 |
2 |
3 |
4 |
5 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
Задачи
для самостоятельного решения
1. Какие из следующих предложений являются высказываниями:
а)Москва - столица России;
б)
в) студент физико-математического факультета;
г) 5+3 – 6;
д)
Луна есть спутник Марса;
е) а>0.
2. Приведите примеры предложений, а) являющихся
высказываниями; б) не являющихся высказываниями.
3. Установите, истинно или ложно высказывание:
а)
б)
4. Среди следующих высказываний указать элементарные (простые) и составные (сложные). В составных высказываниях выделить грамматические связки:
1) число 27 не делится на 3;
2) число 15 делится на 5 и на 3;
3) если число 126 делится на 9, то оно делится на 3;
4) число 7 является делителем числа 42;
5)
число 1269 делится на 9 тогда и только тг когда 18 делится на 9.
5. Обозначьте элементарные высказывания буквами
и запишите следующие высказывания с помощью
символов алгебры логики:
1)
45 кратно 3 и 42 кратно 3;
2)
45 кратно 3 и 12 не кратно 3;
3)
или
4)
2<5;
5) если число 212 делится на 3 и 4, то оно делится 12;
6) число 212 - трехзначное и кратно 3 или 4.
6. Какие из следующих импликаций истинны:
1) если 2х2=4, то 2<3;
2) если 2х2=4, то 2>3;
3) если 2х2=5, то 2<3;
4) если 2х2=5, то 2>3?
7. Найдите логические значения х и у, при которых выполняются равенства:
8. Известно, что импликация х у истинна, а эквивалентность х у ложна. Что можно сказать о значении импликации у х ?
9. Известно, что эквивалентность х у истинна. Что можно сказать о значении и ?
10. Известно, что х имеет значение 1. Что можно сказать о значениях импликации
11. Известно, что х у имеет значение 1. Что можно сказать о значениях
12. Пусть х = 0, у = 1, z = 1 Определить логические значения нижеследующих сложных высказываний:
13. Составить таблицы истинности для формул:
7)
8)
Контрольные
вопросы
1.
Что называется высказыванием?
Обозначения высказываний.
2.
Определения простого (элементарного)
и сложного (составного) высказываний.
3.
Логические значения высказываний.
4.
Что называется отрицанием простого высказывания? Привести таблицу
истинности.
5.
Что называется дизъюнкцией двух
простых высказываний? Привести таблицу истинности.
6.
Что называется конъюнкцией двух
простых высказываний? Привести таблицу истинности.
7.
Что называется импликацией двух
простых высказываний? Привести таблицу истинности.
8.
Что называется эквиваленцией двух
простых высказываний? Привести таблицу истинности.
9.
Определение формулы алгебры
логики.
10.
В какой последовательности
выполняются логические операции?