ЛЕКЦИЯ 3

 

ТЕМА: МАТЕМАТИЧЕСКАЯ ЛОГИКА. ОСНОВНЫЕ ПОНЯТИЯ.

ПЛАН:

1. Задачи и предмет логики.
2. Понятие высказывания.
3. Логические операции над высказываниями.
4. Формулы алгебры логики.

 

 

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.Отрицание.

 Отрицанием высказывания х называ­ется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказы­вание х истинно.

Отрицание высказывания х обозначается и чита­ется «не х» или «неверно, что х».

Логические значения высказывания   можно опи­сать с помощью таблицы.

 

 

Таблицы такого вида принято называть таблицами истинности.

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

Например, для высказывания «Река Волхов вытека­ет из озера Ильмень» отрицанием будет высказывание «Неверно, что река Волхов вытекает из озера Ильмень» или «Река Волхов не вытекает из озера Ильмень», а двой­ным отрицанием будет высказывание «Неверно, что река Волхов не вытекает из озера Ильмень».

 

3.2. Конъюнкция.

 

Конъюнк­цией (логическим умножением) двух высказываний х и у называется новое высказы­вание, которое считается истинным, если оба высказы­вания х и у истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний х и  у обозначается сим­волом х&у  (х  у, ху ), читается «х и. у». Высказывания х и у называются членами конъюнкции.

Логические значения конъюнкции описываются сле­дующей таблицей истинности:

 

 

Например, для высказываний «6 делится на 2», «6 де­лится на 3» их конъюнкцией будет высказывание «6 делит­ся на 2 и 6 делится на 3», которое, очевидно, истинно.

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

Из определения операции конъюнкции и отрицания ясно, что высказывание  всегда ложно.

3.2. Дизъюнкция

Дизъюнкцией  (логическим сложением) двух высказываний х и у называется новое высказывание, которое считается истинным, если хотя бы одно из выс­казываний х, у истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний х, у обозначается сим­волом «x v у», читается «х или у». Высказывания х, у называются членами дизъюнкции.

Логические значения дизъюнкции описываются сле­дующей таблицей истинности:

 

 

Например, высказывание: «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольни­ке DFE угол D острый», «В треугольнике DFE угол Е острый».

В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

Из определения операции дизъюнкции и отрицания ясно, что высказывание  всегда истинно.

 

3.3. Импликация.

 

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

Импликация высказываний х, у обозначается сим­волом х  у , читается «если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у - следствием или заключением, выска­зывание х  у следованием или импликацией.

Логические значения операции импликации описы­ваются следующей таблицей истинности:

 

Например, высказывание «Если число 12 делится на 6, то оно делится на 3», очевидно, истинно, так как здесь истинна посылка: «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

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

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

3.5. Эквиваленция.

 

 Эквиваленцей (или эквивалентно­стью) двух высказываний х и у называется новое выска­зывание, которое считается истинным, когда оба выска­зывания х, у либо одновременно истинны, либо одновре­менно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний х, у обозначается сим­волом х  у , читается «для того, чтобы х, необходимо и достаточно, чтобы у» или «х тогда и только тогда, когда у». Высказывания х, у называются членами эквиваленции.

Логические значения операции эквиваленции опи­сываются следующей таблицей истинности:

 

Например, эквиваленция: «Треугольник SPQ с вер­шиной S и основанием PQ равнобедренный тогда и толь­ко тогда, когда SP = SQ » является истинной, так как высказывания «Треугольник .SPQ с вершиной S и ос­нованием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ  SP = SQ » либо одно­временно истинны, либо одновременно ложны.

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

4.Формулы алгебры логики.

 

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

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

а заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z.

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

Формулы алгебры логики будем обозначать больши­ми буквами латинского алфавита А, В, С, ...

Для упрощения записи формул принят ряд соглаше­ний:

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

- конъюнкция выполняется рань­ше, чем все остальные операции,

- дизъюнкция выполня­ется раньше, чем импликация и эквивалентность

            - если над формулой стоит знак отрицания, то скобки тоже опускаются.

В связи с этим формулы: 

могут быть записаны так:

Логическое значение формулы алгебры логики пол­ностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логичес­ким значением формулы в случае, если х = 1, у = 1, z = 0 будет истина, то есть

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

Например, для формулы  (указан порядок действий) таблица ис­тинности имеет вид:

 

 

Первые два столбца- это всевозможные наборы значений входящих в формулу различных простых высказываний. Легко видеть, что формула принимает 2ⁿ значений, состоящих из нулей и единиц, значит, таблица истинности содержит столько же строк.

 

Рассмотрим еще один пример на составление таблицы истинности:

 

 

. Таблица содержит 2³ = 8 строк:

 

 

 

 

Задачи для самостоятельного решения

 

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.  В какой последовательности выполняются логические операции?