Автор работы: Пользователь скрыл имя, 26 Ноября 2013 в 17:05, лекция
Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, то есть путем использования законов человеческого мышления. Изучение законов человеческого мышления является предметом логики.
Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384-322 г. до н.э.)- Он систематизировал известные до него сведения, и эта система стала впоследствии называться формальной или Аристотелевой логикой.
Лекция 7. Логические основы информатики
Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, то есть путем использования законов человеческого мышления. Изучение законов человеческого мышления является предметом логики.
Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384-322 г. до н.э.)- Он систематизировал известные до него сведения, и эта система стала впоследствии называться формальной или Аристотелевой логикой. Формальная логика просуществовала без серьезных изменений более двадцати столетий. Естественно, что развитие математики выявило недостаточность Аристотелевой логики и потребовало дальнейшего ее развития.
Главными недостатками формальной логики являлись следующие.
1. Она не сумела привести законы выводов к небольшому количеству надежных логических законов; поэтому подтвердила правильность некоторых выводов на основе экспериментов, которые позже были опровергнуты примерами, доказывающими обратное.
2. Она была неспособна анализировать значительную часть выводов, применяемых в повседневной и научной жизни; доказать правильность или неправильность таких выводов. (Например, не могла доказать, что из правильности предложения «Каждая трапеция является четырехугольником» вытекает правильность предложения «Кто рисует трапецию, тот рисует четырехугольник).
Впервые в истории идеи о построении логики на математической основе была высказаны немецким математиком Г. Лейбницем (1646-1716) в конце XVII века. Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам. Это позволит всякое рассуждение заменить вычислением.
Большинство интерпретаций для математических теорий (и, в частности, для арифметики) строится на базе теории множеств, в связи с этим важно доказать непротиворечивость теории множеств.
Основным (неопределяемым) понятием математической логики является понятие «простого высказывания».
Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».
Приведем примеры высказываний.
1) Новгород стоит на Волхове.
2) Париж - столица Англии.
3) Карась не рыба.
4) Число 6 делится на 2 и на 3.
5) Если юноша окончил среднюю школу, то он получает аттестат зрелости.
Высказывания 1), 4), 5) истинны, а высказывания 2) и 3) ложны.
Высказывания бывают простыми и сложными. Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).
Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
В дальнейшем будем элементарные высказывания обозначать малыми буквами латинского алфавита: х, у, z, .,., а, Ь, с, ...; истинное значение высказывания - буквой и или цифрой 1, а ложное значение - буквой л или цифрой 0.
Если высказывание а истинно, то будем писать а = 1, а если а ложно, то а = 0.
Отрицанием высказывания х называется новое высказывание, которое является истинный, если высказывание х ложно, и ложным, если высказывание x истинно. Отрицание высказывания х обозначается и читается «не х» или «неверно, что х».
Логические значения высказывания х можно описать с помощью таблицы:
x |
|
|
0 |
1 |
1 |
0 |
Таблицы такого вида принято называть таблицами истинности.
Пусть х высказывание. Так как также является высказыванием, то можно образовать отрицание высказывания , то есть высказывание , которое называется двойным отрицанием высказывания х.
2. Конъюнкция (логическое умножение).
Конъюнкцией двух высказываний х, у называется новое высказывание, которое считается истинным, если оба высказывания х, у истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний х, у обозначается символом х&у или (х у), читается «x и у». Высказывания х, у называются членами конъюнкции.
Логические значения конъюнкции описываются следующей таблицей истинности:
x |
y |
х&у |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
Например, для высказываний «6 делится на 2», «б делится на 3» их конъюнкцией будет высказывание «б делится на 2 и 6 делится на 3», которое, очевидно, истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от Друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Из определения операции конъюнкции и отрицания ясно, что высказывание x& всегда ложно.
3. Дизъюнкция (логическое сложение).
Дизъюнкцией двух высказываний х, у называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x, у истинно, и ложным, если они оба ложны.
Дизъюнкция высказываний х, у обозначается символом x y, читается «x или у». Высказывания х, у называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:
х |
y |
| ||
|
1 |
1 |
1 | ||
1 |
0 |
1 | ||
0 |
1 |
1 | ||
0 |
0 |
0 | ||
Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».
В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем (жизнь или смерть). В алгебре логики союз «или» всегда употребляется в не исключающем смысле.
4. Импликация.
Импликацией двух высказываний х, у называется новое высказывание, которое считается ложным, если х истинно, а у - ложно, и истинным во всех остальных случаях.
Импликация высказываний х, у обозначается символом х у, читается «если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у — следствием или заключением, высказывание х у - следованием или импликацией.
Логические значения операции импликации описываются следующей таблицей истинности:
x |
x |
х y |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
Например, высказывание «Если число 12 делится на 6, то оно делится на 3», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3». «Если 2 x 2=5, то существует баба яга »
Употребление слов «если .,., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание «Если х, то у» вообще не имеет смысла. Кроме того, строя предложение вида «если х, то у» в обыденной речи, мы всегда подразумеваем, что предложение у вытекает из предложения х. Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
5. Эквивалеация.
Эквиваленцией (или эквивалентностью) двух высказываний х, у называется новое высказывание, которое считается истинным, когда оба высказывания д:, у либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.
Эквиваленция высказываний х, у обозначается символом х у, читается «для того, чтобы х, необходимо и достаточно, чтобы y» или «х тогда и только тогда, когда у». Высказывания х, у называются членами эквиваленции. Логические значения операции эквиваленцин описываются следующей таблицей истинности:
х |
y |
х у |
*1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда SP=SQ» является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ SP = SQ » либо одновременно истинны, либо одновременно ложны. Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.
Функция сложения по модулю два истинна тогда и только тогда, когда значения переменных различны.
(8)
x |
y |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Запись читается как «x стрелка Пирса y». Функция истина тогда и только тогда, когда ложны обе её переменные.
x |
y |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
Cтрелка Пирса противоположна дизъюнкции, и для неё справедливо:
(9)
Запись x|y читается как «x штрих Шеффера y». Функция ложна тогда и только тогда, когда оба значения переменных истинны.
x |
y |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Штрих Шеффера противоположна конъюнкции, и для неё справедливо:
С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний х, у, г можно построить высказывания: