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

Элементы математической логики (лекция) Когда говорят о логике (как науке о правильности суждений), то имеют в виду либо аристотелеву (неформальная логика), либо математическую (формальная логика). В данной лекции изложение материала будет основываться на интуитивном подходе с элементами математического (аксиоматического) построения. Основными неопределяемыми понятиями являются: «высказывание», «предикат»; неопределяемое отношение – принимать высказыванию значения «истина» или «ложь». Под высказыванием будем понимать любое повествовательное предложение, о котором определённо можно сказать, истинно оно или ложно. Высказывание будем обозначать строчными греческими или латинскими буквами: . И – истина; Л – ложно. Для обозначения Истина или Ложь можно применять следующие обозначения: 1 \ 0, t \ f, + \ -, да \ нет. Примеры высказываний: α:=””; α =И; β:=”3”; β =Л; «Москва – столица России». Не является высказыванием (Москва – название нескольких населённых пунктов). Столица России – Москва, это высказывание. = Луна – естественный спутник Земли = И. Операции на множестве высказываний 1. Дизъюнкция: дизъюнкцией высказываний и называют высказывание, обозначаемое , принимающее значение Л в случае, когда и - ложь, и истина в противном случае. Замечание: Дизъюнкция в русском языке – способ получения из двух простых предложений сложное с помощью союза «или». 2. Конъюнкция: конъюнкцией двух высказываний и называют высказывание, обозначаемое (&) и принимающее значение И, когда оба компонента И, и Л в противном случае. Замечание: В русском языке конъюнкция – способ получения сложных предложений из двух простых с помощью союза «и» (и то, и другое). 3. Импликация: импликацией высказываний и называют высказывание, обозначаемое и принимающее значение Л, когда посылка – И, а заключение – Л, и И в противном случае. Замечание: В русском языке импликация: если <предл.1>, то <предл.2> (из предложения 1 следует предложение 2). 4. Эквиваленция: эквиваленцией высказываний и называют высказывание, обозначаемое и принимающее значение И при одинаковой истинности и , и Л в противном случае. 5. Отрицание: отрицанием высказывания называют высказывание, обозначаемое , читаемое «не », и принимающее значение, противоположное значению . Замечание: В конструкции русского языка отрицание – построение сложного предложения, замещающего данные предложения со связкой «не», И И И И И И Л И Л И Л Л Л Л Л И И Л И Л И Л Л Л Л И И И Формулы Определение: Формулой называют всякое выражение, обозначаемое заглавными латинскими буквами, удовлетворяющее следующим условиям: 1. Всякое высказывание является формулой; 2. Если A, B – формулы, то формулами являются: ; 3. Других формул нет. Примеры: 1. ; 2. ; 3. . Замечание: Приоритеты в выполнении операций: 1. выражение в скобках; 2. конъюнкция (при отсутствии скобок); 3. дизъюнкция; 4. импликация; 5. эквиваленция; 6. отрицание. Расставить порядок действий в следующих формулах: 1. ; 2. . Подформулы Подформулой данной формулы называют формулу из следующей последовательности: 1. Всякое высказывание – формула нулевого уровня; 2. Операции над формулами нулевого уровня – формулы первого уровня; 3. Операции над формулой n-го уровня – подформула (n+1) уровня. Пример. Расписать подформулы формулы: 0-й: ; 1-й: ; 2-й: ; 3-й: A 0-й: ; 1-й:; 2-й: ; 3-й: ; 4-й: A. Таблица значений формул Для построения таблицы истинности определяют количество высказываний этой формулы и по установленному ранее образцу определяют количество строк, равное 2n и + одна строка “подлежащее”. 1. Определить количество элементов 0-го уровня (сколько высказываний); 2. Построить формальную таблицу: • количество строк равно +1, где n – число высказываний; • в каждом столбце высказываний (n штук) поставить И и Л по следующему правилу: В крайнем правом столбце чередуют И и Л, в слева стоящем столбце – удваивают И в чередовании с Л от каждого предыдущего. В столбце значений формулы конкретный набор значений высказываний в данной строке отыскивается для данной формулы и записывается в данную строку. Составить таблицу значений для данных формул: ; ; . A B C И И И И И Л И И Л И Л И И Л И Л Л И И Л Л Л Л И Л И И И Л И Л И Л И Л Л Л Л И И И Л Л Л Л И Л Л Замечание: Формул можно записать бесконечное множество, а таблиц с соответствующими столбцами формул – вполне конечное число для данного числа переменных, а именно: равно 2 в степени 2n , где n – число различных высказываний. Равносильность формул Определение: Две формулы A и B называют равносильными (), если при каждом наборе входящих в них высказываний они принимают одинаковые значения. Иначе , если в таблице истинности совпадают их столбцы значений. Теорема: Отношение равносильности есть отношение эквивалентности. Доказательство: 1. (рефлексивность выполнена); 2. следует (симметричность выполнена); 3. Изи следует (равенство столбцов значений A, B, C обеспечивает транзитивность, тем самым отношение эквивалентности доказано). Множество всех формул можно разбить на классы эквивалентности. Группы равносильностей: I. Коммутативность: 1. ; 2. ; 3. . II. Ассоциативность: 1. ; 2. ; III. Нейтральные элементы: 1. ; 2. ; ; . IV. Противоположные элементы: 1. ; 2. V. Свёртки: 1. ; 2. . VI. Снятие отрицания: 1. ; 2. ; 3.. VII. Формулы де Моргана: 1. ; 2. . VIII. Замена операций: 1. ; 2. . IX. Раскрытие на новую переменную. 1. ; 2. . Преобразование формул «Преобразовать формулу А» означает «осуществить поиск формулы B, равносильной A». Имеется два способа поиска: 1. С помощью равносильных преобразований; 2. С помощью таблиц истинности. Доказательство равносильностей И Л И И И И И И Л Л Л И Л Л Л Л ; ; ; ; ; ; ; И И И И Л Л И И И И И Л И И Л Л Л Л И И Л И И И Л Л И И Л Л Л Л Л Л И И И И Л Л И И И И И И И И И Л Л Л И И И Л И Л Л И И И Л Л Л Л Л Л Л И И Л Л Л Л Л И Л Л Л Л Л Л Л И Л Л Л Л Л Л Л Л Л Л Л Замечание: Преобразовать формулу A в формулу B означает получить формулу B, равносильную формуле A. Существует два вида операций преобразования: 1. с помощью равносильностей; 2. с помощью таблиц истинности. СДНФ, СКНФ Как было отмечено ранее, отношение равносильности обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности. Тем самым множество всех формул можно разбить на классы, в каждом из которых размещены формулы, равносильные друг другу. Классификация формул связана с понятиями: 1) нормальные формулы (НФ); 2) дизъюнктивно-нормальные формулы (ДНФ); 3) конъюнктивно-нормальные формулы (КНФ). Определение: Формула A называется нормальной, если она содержит только операции дизъюнкции, конъюнкции и отрицания. Теорема: Всякая формула A может быть представлена равносильной ей НФ. Доказательство: 1. Если формула A не содержит импликации и эквивалентности, то она есть НФ. 2. Если формула A содержит одну или несколько операций импликации, то заменим формулы: . Последняя формула не содержит импликации. Выполнив подобную операцию, получим формулу A в равносильном варианте без импликации. 3.Если формула A содержит эквиваленцию , то последняя формула больше не содержит никаких операций, кроме отрицания, дизъюнкции и конъюнкции. Вывод: Для любой формулы A последовательно заменяем импликацию и эквиваленцию и получаем НФ. Замечание: Последовательным преобразованием снятия отрицания можно получить формулу, содержащую отрицание только над высказываниями. Пример: - не НФ . Определение: Элементарной дизъюнкцией называют: 1. Всякое высказывание, или его отрицание (); 2. Если - элементы дизъюнкции (ЭД), то также ЭД. 3. Других ЭД нет. Пример: - ЭД; - не ЭД; - ЭД. Определение: Формулу B называют элементарной конъюнкцией (ЭК), если: 1. B – высказывание или его отрицание (); 2. - ЭК, то - ЭК; 3. других ЭК нет. Определение: Формулу A называют дизъюнктивно-нормальной формулой (ДНФ), если она является дизъюнкцией элементарных конъюнкций (ДЭК). Определение: Формулу B называют конъюнктивно-нормальной формулой (КНФ), если она является конъюнкцией элементарной дизъюнкции (КЭД). Пример: – ЭД, КНФ, не ЭК, ДНФ; – не ЭК, не ЭД, ДНФ, КНФ. Теорема: Всякую нетождественно истинную и нетождественно ложную формулу можно представить в виде ДНФ и КНФ. Без доказательств. Определение: Формула A называется совершенной или СДНФ (СКНФ), если она: 1. ДНФ (КНФ); 2. Обладает свойством совершенства: • каждая входящая ЭК содержит все переменные или их отрицания; • каждая ЭК не содержит одновременно высказывание и его отрицания; • каждая ЭК не содержит одну и ту же переменную или её отрицание более одного раза. 3. Для ЭД эти условия аналогичны; 4. Никакие две ЭК составляющие ДНФ не совпадают (с точностью до перестановки). Пример: – все компоненты совпадают. Теорема: Всякая выполнимая формула A представима СДНФ. Без доказательств. Замечание. Формула А называется выполнимой, если она нетождественно истинная и нетождественно ложная. И И И И Л И И Л И Л И Л И И Л И Л Л Л И Л И И И Л Л И Л Л И Л Л И И Л Л Л Л Л И И И И Л Л И И Л Л Л И Л И И И И Л Л Л И Л И И Л И Л И Л Л И Л Л И И И Л Л Л Л И Каждую выполнимую формулу A можно привести к СДНФ равносильными преобразованиями: • привести к КНФ; • преобразовать; • привести к ДНФ; • дополнить компоненты, группы. ******************************************* Теорема: Если формула A выполнима, то СКНФ(А) =. Замечание: СКНФ и СДНФ(А) образуют полный набор элементарных объектов: • элементы конъюнкции; • элементы дизъюнкции. • • • • СКНФ(B) =