Элементы математической логики

                   
Элементы математической логики
    Логика как искусство рассуждений зародилась в глубокой древности.Начало науки о законах и формах рассуждений связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в позапрошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики.     Главная цель применения в логике математической символики заключалась в том, чтобы свести операции с логическими заключениями к формальным действиям над символами. При этом исходные положения записываются формулами, которые преобразуются по определенным законам, а полученные результаты истолковываются в соответствующих понятиях.     Бурное развитие математической логики связано, прежде всего, с задачами обоснования математики, где она используется для доказательства непротиворечивости исходных понятий и правильности рассуждений и выводов математических теорий.     Во второй половине ХХ века логика получила широкое применение в технике при исследовании и разработке релейно-контактных схем, вычислительных машин, дискретных автоматов. Ее методы используются в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Математическая логика внедряется в такие области как экономика, биология, медицина, психология, языкознание, право. Столь интенсивный выход математической логики за пределы математики объясняется тем, что ее аппарат легко распространяется на объекты самой общей природы, лишь бы они только характеризовались конечным числом состояний.     С расширением областей применения и дальнейшим развитием математической логики изменяется и взгляд на нее. Объектами математической логики являются любые конечные дискретные системы, а ее главная задача – структурное моделирование таких систем. Понятие высказывания.    Основным объектом, изучаемым математической логикой является высказывание. Высказывание – это повествовательное предложение, относительно которого известно, является оно истинным (И) или ложным (Л). Примеры:
«Наталья – мужское имя» – ложное высказывание
«Пять больше трех» – истинное высказывание
«Луна – спутник земли» – истинное высказывание
«Как дела?» – не является высказыванием
«Соблюдайте технику безопасности!» – не является высказыванием
«Белые медведи живут в Африке» – ложное высказывание
«25>10» – истинное высказывание
«С Новым Годом!» – не является высказыванием
«Стой! Куда идешь?» – не является высказыванием
    Мы не будем исследовать внутреннюю структуру высказываний, потому что такое исследование относится скорее к лингвистике, чем к математике. Высказывание, в котором невозможно выделить более простые высказывания, будем называть простым, а все остальные составными. Сложное высказывание можно образовать, выполняя над простыми высказываниями те или иные действия (в терминах математической логики – операции). В разговорном языке операциям над высказываниями соответствуют логические связки "если , то ", " и ", " или ", "не " и др.     Рассмотрим высказывание «Если завтра будет хорошая погода, мы поедем на дачу», это высказывание состоит из двух элементарных высказываний «завтра будет хорошая погода» и «мы поедем на дачу», которые соединены логической связкой «если, то». Примеры:
"a"Напряжение в сети 220 В", "частота 50 Гц" – простые высказывания; "напряжение в сети  220 В и частота 50 Гц" – сложное высказывание.
"Если начальная скорость равна нулю и ускорение а – постоянная величина, то пройденный за время t путь S вычисляется по формуле S=at2/2" – сложное высказывание. Выделим простые высказывания, составляющие данное сложное высказывание: "начальная скорость равна нулю", "ускорение а – постоянная величина", "пройденный за время t путь S вычисляется по формуле S=at/2".
Основные логические операции
Название
Прочтение
Обозначение

Отрицание
не
¬

Конъюнкция
и


Дизъюнкция
или


Импликация
если ... то


Эквивалентность
тогда и только тогда, когда


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

   0
   1

1
0

Конъюнкцией двух высказываний Х и У называется высказывание , которое истинно только в том случае, когда Х и У оба истинны. Таблица истинности для конъюнкций.
Х
Y


0
0
0

0
1
0

1
0
0

1
1
1

Дизъюнкцией двух высказываний Х и У называется высказывание , которое истинно, когда хотя бы одно из них истинно. Таблица истинности дизъюнкций.
Х
Y


0
0
0

0
1
1

1
0
1

1
1
1

Импликацией двух высказываний Х и У. называется высказывание , которое ложно тогда и только тогда, когда Х истинно, а У ложно. Таблица истинности для импликации.
Х
Y


0
0
1

0
1
1

1
0
0

1
1
1

Эквивалентностью высказываний Х и У называется высказывание , которое истинно тогда и только тогда, когда Х и У оба истинны или ложны. Таблица истинности для эквивалентности.
Х
Y


0
0
1

0
1
0

1
0
0

1
1
1

Понятие формулы логики высказываний.
Пусть p, q – переменные, которые принимают значения истина или ложь. Тогда
если p – логическая переменная, то p – формула,
если p – формула, ¬p – формула,
если p, q – формулы, то (pq), (pvq), (pq), (pq),
других формул не существует.
    Другими словами запись сложного высказывания в виде простых высказываний, соединенных логическими операциями, называется логической формулой. Приоритет операций
Отрицание
Конъюнкция
Дизъюнкция
Импликация
Эквиваленция
  Пусть А – формула, содержащая n переменных, тогда присвоив каждой переменной значение или ложь, мы получим некоторый набор истинностных значений переменных, таких наборов 2n.     Для каждого конкретного набора переменных формула принимает определенные истинностные значения. Как правило, нахождение истинностных значений формулы при различных наборах переменных находится с помощью таблицы истинности. Пример: Построить таблицы истинности для следующих формул логики высказывания,
p
q
r
(p->q)
(q->r)
(p->r)
¬(p->r)
(p->q)/\(q->r)
(q->r)/\¬(p->r)

0
0
0
1
1
1
0
1
0

0
0
1
1
1
1
0
1
0

0
1
0
1
0
0
1
0
0

0
1
1
1
1
1
0
1
0

1
0
0
0
1
1
0
0
0

1
0
1
0
1
1
0
0
0

1
1
0
1
0
0
1
0
0

1
1
1
1
1
1
0
1
0

        Если при всех наборах переменных формула принимает значение «истина» (Аи), то такая формула называется тождественно истинной, тавтологией или законом логики. Если при всех наборах переменных формула принимает значение «ложь» (Ал), то такая формула называется тождественно ложной или противоречием. Все остальные формулы называются нейтральными.   Формулы А и В называются равносильными (АВ), если для любого набора переменных совпадают их истинностные значения.     Утверждение: АВ в том и только в том случае, если АВ – тавтология. Законы логики 1) Идемпотентность дизъюнкции и конъюнкции:       , . 2) Коммутативность дизъюнкции и конъюнкции:       . 3) Ассоциативность дизъюнкции и конъюнкции:        4) Дистрибутивность операций дизъюнкции и конъюнкции относительно друг друга:        5) Двойное отрицание:        . 6) Закон де Моргана:        7) Склеивание:        8) Поглощение:        9) Действие с логическими константами 0 и 1:        10) Закон исключения третьего:        11) Тождество:        12) Отрицание противоречия:        13) Контрапозиция:        14) Цепное заключение:        15) Противоположность:        16) Модус поненс (modus ponens):        Сформулированные законы легко проверить с помощью таблицы истинности. Возникает вопрос: как доказать, что выражение действительно является тождеством? Есть два пути:     1. Доказательство на основе таблицы соответствия. Для обеих частей предполагаемого тождество строятся таблицы соответствия. Если эти таблицы получаются одинаковыми (т.е. для каждого набора значений аргументов значения левой и правой части выражения совпадают), то тождество верно.     2. Доказательство путем последовательных тождественных преобразований. Последовательно преобразуя левую и правую части, необходимо привести их к одинаковому виду.     Рассмотрим для примера доказательство дистрибутивного закона с помощью таблицы истинности. Для этого построим таблицы истинности для левой и правой частей предполагаемого тождества.
х
у
z






0
0
0
0
0
0
0
0

0
0
1
1
0
0
0
0

0
1
0
1
0
0
0
0

0
1
1
1
0
0
0
0

1
0
0
0
0
0
0
0

1

·0
1
1
1
0
1
1

1
1
0
1
1
1
0
1

1
1
1
1
1
1
1
1

    Как видно из таблицы, значения левой и правой части (выделены жирным шрифтом) совпадают при всех значениях переменных, что и требовалось доказать.     Аналогично, путем построения таблиц соответствия, могут быть доказаны и другие приведенные выше тождества. Предикаты и кванторы     Предложение с переменными, которое обращается в высказывание после подстановки любого допустимого значения из некоторого заданного множества, называется предикатом. Если предикат зависит от n переменных, то такой предикат называется n-местным.     Предикаты будем обозначать большими латинскими буквами Р(x), Q(x,y) и др., в скобках указывая переменные, от которых зависит предикат. Пример:
Предикат «число х четно» можно обозначить Р(х). Это предикат от одной переменной x. Чтобы превратить его в высказывание, нужно придать значение переменной х.  Р(7) является высказыванием «число 7 четно», это ложное высказывание.
Предикат «х2 + у = 25» можно обозначить Q(x, у). Это предикат от двух переменных. Чтобы превратить его в высказывание, необходимо уже дать конкретные значения паре переменных х, у. Если х=1,  у=24, то предикат «х2 + у = 25» принимает значение истина.
    Предикат Р называется тождественно истинным или тождеством, если он принимает истинные значения при всех значениях входящих в него переменных, при которых он становится высказыванием. (тождественно ложным аналогично) Пример: тождествами являются известные вам из школьной программы предикаты              (х + у)2 = х2 + 2ху + у2, а также sin2x + cos2x = 1.          По аналогии с высказываниями для всяких двух предикатов Р и Q мы можем определить новые предикаты, полученное из P и Q при помощи логических связок отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции. В дальнейших определениях будем считать, что предикаты Р и Q зависят от одних и тех же переменных. Квантор общности     Пусть задан предикат P(x) . Выражение "x P(x) является истинным высказыванием, если предикат P(x) тождественно истинный предикат, в противном случае x P(x) – ложно. Выражение x P(x) можно прочитать «Для любых х P(x)» или «Для всех х P(x)». Пример:
(x R)(x+1=0) – ложное высказывание, т.к. при x=2 предикат P(x) принимает значение ложь.
(xR) (x2
· 0)  – истинное высказывание, т.к. при подстановке любого действительного числа в  предикат P(x) получим истинное высказывание.
Квантор существования     Пусть задан предикат P(x) . Выражение x P(x) является истинным высказыванием, если существует такое значение переменной x, при котором предикат P(x) принимает значение истина. Выражение x P(x) можно прочитать «Существует х, такой что P(x)» или «Найдется такой х, что P(x)». Пример:
(x R)(x+1=0) – истинное высказывание, т.к. существует действительное число -1,  при подстановке которого в  предикат P(x) получим истинное высказывание «-1+1=0».
(xR) (x2 < 0) ложное высказывание, т.к. при подстановке любого действительного числа в  предикат P(x) получим ложное высказывание.
    
Замечание: Если на все переменные, которые входят в предикат «навесить» кванторы общности или существования, то предикат превратиться в высказывание.Рассмотрим предикат P(x,y)- «x+y=1» - это предикат от двух переменных. Установим истинность следующих высказываний:        (x,yR) P(x,y) – это предложение можно прочитать следующим образом «Существуют такие действительные х и у, что x+y=1». Такую пару значений можно подобрать, например х=1, у=0. Данное высказывание  истинно.          (xR) (уR) P(x,y) – «Существует такой действительный х, что для любого действительного у x+y=1». Для того чтобы данный предикат обратился в истинный необходимо подобрать такой х (единый для всех у), что какой бы у мы не подставили, предикат принял бы истинное значение. Такой х подобрать невозможно, потому что для каждого значения х будет находиться новое значение у. Таким образом, данное высказывание ложно.   (xR) (yR) P(x,y) – «Для всех действительных х, найдется такой действительный у, что x+y=1». На самом делен выбирая произвольное действительное значение х, мы всегда сможем найти такое действительное значение у, что равенство x+y=1 обратится в верное тождество.    (x,yR) P(x,y) – «Два любых действительных числа х и у в сумме дают единицу». Это высказывание ложное, т.к. можно подобрать такие числа х и у, которые в сумме единицу не дадут, например х=5, у=7. Отношения равносильности и следования предикатов.     Два предиката P(x) и Q(x) называются равносильными (P(x) Q(x)), если P(x) « Q(x) – тождественно истинное высказывание. Областью истинности предиката P(x) (T(P)) называется множество значений x такое, что P(x)=и.
Замечание: Два предиката P(x) и Q(x) называются равносильными (P(x) Q(x)), если совпадают области истинности этих предикатов.
Пример: Равносильны ли следующие предикаты на множестве действительных чисел? P(x) =              «x>1 x<-3» и Q(x )= «x2+2x-3>0». Найдем области истинности предикатов P(x) и Q(x ), для этого решим соответствующие неравенства.
P(x) = «x>1 x<-3» T(P)=(-
·; -3)U(1;+
·)
Q(x )= «x2+2x-3>0» Q(P)=(-
·; -3)U(1;+
·)

       Множества T(P) и Q(P) равны, это означает, что предикаты P(x) и Q(x ) равносильны. Говорят, что предикат P(x) является логическим следствием предиката Q(x) (Q(x)ЮP(x)), если предикат P(x) принимает значение истина каждый раз, когда предикат Q(x) принимает значение истина.     Следствие: Пусть Т(Q) Т(P), тогда Q(x)=> P (x) Пример: Можно ли установить логическое следование предикатов P(x)= «x>1» и                Q(x)=«x2>1».
P(x) = «x>1» T(P)=(1;+
·)
Q(x )= «x2>1» Q(P)=(-
·; -1)U(1;+
·)

Множество T(P) является подмножеством Q(P), что означает P (x)=>Q(x). Отрицание высказываний, содержащих кванторы.           Отрицание высказываний, содержащих кванторы, строится по следующему правилу: все кванторы меняются на противоположные (квантор общности на квантор существования и наоборот) и строится отрицание к предикату. Пример: построить отрицание для высказываний
Высказывание
Отрицание

(x,yR) P(x,y)
(x,yR)P(x,y)

(xR) (уR) P(x,y)
(xR) (уR)P(x,y)

(xR) (yR) P(x,y)
(xR) (yR)P(x,y)

(x,yR) P(x,y)
(x,yR)P(x,y)

          Рассмотренный пример демонстрирует общее правило построения отрицания. Для построения отрицания предиката вспомним общие правила построения отрицания логических операций: (p/\q)= p\/q (p\/q)= p/\q (pq)=p/\q Пример: построить отрицание для высказываний, перевести высказывание и его отрицание              на обычный язык, оценить истинность полученных высказываний, если              A(x) = «х – четное число»,              B(x) = «х –число кратное 3»,              C(x) = «х – простое число».              Все высказывания определены на множестве целых чисел (Z). а) (x Z) (A(x) /\ С(x)) «Существует простое четное число». Данное высказывание истинно, т.к. такое число существует – 2. Построим отрицание. (x Z) (A(x) \/ С(x)) «Все целые числа таковы, что не делятся на 2 или не являются простыми». Можно подобрать контрпример х=2. Данное высказывание ложно. б) (x Z) (A(x) /\ B(x)) «Существует целое число х, которое и четное и делится на 3». Можно подобрать такое целое число, например х=12. Данное высказывание истинно. Построим отрицание. (x Z) (A(x) \/ B(x)) «Все целые числа таковы, что не делятся на 2 или не делятся на3». Можно подобрать контрпример х=2. Данное высказывание ложно. в) (x, у Z) (A(x) /\ А(у) А(х+у)) «Любые два целых четных числа в сумме дадут четное число». Данное высказывание истинно. Построим отрицание. (x, у Z) (A(x) /\ А(у) /\ А(х+у) «Существуют такие целые четные числа, что их сумма не делится на 2». Такие числа найти невозможно. Данное высказывание ложно. г) (x Z) (A(x) В(х)) «Любое четное число делится на 3». Данное высказывание ложно, т.к. можно найти контрпример – х=4. Построим отрицание. (x Z) (A(x) /\ В(х)) «Существует четное число, которое делится на 3». Данное высказывание истинно, т.к. можно подобрать – х=4. Структура теоремы. Необходимые и достаточные условия. Многие теоремы имеют следующий вид: xM(A(x)B(x))     В этом случае А(х) называется достаточным условием В(х), а В(х) называется необходимым условием для А(х). Пример: Выделить структуру следующей теоремы: «Если многоугольник правильный, то в него можно вписать окружность» М – множество многоугольников, А(х) – «многоугольник правильный», В(х) – «В многоугольник можно вписать окружность». Виды теорем Пусть задана прямая теорема в виде: xM(A(x)B(x)) – прямая теорема xM(B(x) A(x)) – обратная теорема xM(A(x)B(x)) – противоположная теорема xM(B(x) A(x)) – обратная к противоположной теорема Пример: Сформулировать обратную, противоположную и обратную к противоположной теоремы, оценить их истинность. Прямая «Если многоугольник правильный, то в него можно вписать окружность» Обратная «Если в многоугольник можно вписать окружность, то многоугольник правильный» (ложь) Противоположная «Если многоугольник неправильный, то в него нельзя вписать окружность» (ложь) Обратная к противоположной «Если в многоугольник нельзя вписать окружность, то многоугольник неправильный»
Рисунок 1Рисунок 2Рисунок 3Рисунок 4Рисунок 9Рисунок 18Рисунок 19Рисунок 20Рисунок 21Рисунок 22Рисунок 23Рисунок 24Рисунок 25Рисунок 31Рисунок 34Рисунок 40Рисунок 41Рисунок 43Рисунок 46Рисунок 48Рисунок 49Рисунок 50Рисунок 51Рисунок 52Рисунок 55Рисунок 57Рисунок 59Рисунок 61Рисунок 63Рисунок 65Рисунок 68Рисунок 69Рисунок 71Рисунок 74Рисунок 75Рисунок 76Рисунок 77Рисунок 78Рисунок 81Рисунок 82Рисунок 84Рисунок 85Рисунок 88Рисунок 91Рисунок 92Рисунок 94Рисунок 98Рисунок 100Рисунок 102Рисунок 103Рисунок 107Рисунок 109Рисунок 110Рисунок 111Рисунок 112Рисунок 113Рисунок 114Рисунок 115Рисунок 116Рисунок 117Рисунок 120Рисунок 123Рисунок 124Рисунок 125Рисунок 127Рисунок 128Рисунок 133Рисунок 134Рисунок 136Рисунок 137Рисунок 138Рисунок 141Рисунок 145Рисунок 148Рисунок 151Рисунок 154Рисунок 155Рисунок 159Рисунок 160ђ Заголовок 115

Приложенные файлы

  • doc 8958640
    Размер файла: 238 kB Загрузок: 1

Добавить комментарий