Elementy_mat_logiki_Teoria


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.
Теория Высказывания (основные понятия) Введем специфическую ©логическуюª терминологию и укажем её связь с положениями раздела ©Элементы математической логики. Алгебра булевых функцийª. Определение. Высказывание ‬ это утверждение или повествовательное пр едложение, о котором можно сказать, истинно оно или ложно, но ни то и другое одновременно. В логике высказываний рассматривают не содержание и даже не структуру высказывания, а ограничиваются только тем его свойством, что оно представляет собой истину или ложь. Пример . Предложения, являющиеся высказываниями : а ) Два умножить на два равно четыре ( ) . б) Рим − столица Франции. Предложения, не являющиеся высказываниями: а) Кто Вы? (вопрос). б) Прочтите эту книгу до следующего занятия (п риказ или восклицание). в) Это утверждение ложно (внутренне противоречивое утверждение). Определение. Высказывания, которые соответствуют простым повествовательным предложениям, т.е. не имеют составных частей, называются атомами ( элементарными высказывани ями, атомарными формулами ) . В ысказывание можно рассматривать как величину, ( пропозициональную переменную , высказывательную переменную ) , которая может принимать два значения: ©истинаª и ©ложьª, т.е. принимать истинностное значение . Определение. Под истин ностным значением понимается абстрактный объект (©истинаª или ©ложьª), сопоставляемый высказыванию в зависимости от того, является это высказывание истинным или ложным. О бозначается: ©и стинаª − И, Т (True) или 1, „л ожь  ‬ Л, F (False) или 0. Определение. Множество { И, Л } называется множеством истинностных значений . Пример. Высказывание © ª имеет истинностное значение 1 (И). Высказывание ©Рим − столица Францииª имеет истинностное значение 0 (Л). Можно рассматривать две группы высказыв аний:  высказывания, истинностное значение которых независимо от ситуации можно считать однозначно определенным;  высказывания, завися щие от обстоятельств, которыми руководствуются при его истолковании , и, следовательно, могут принимать различные значения. О бычно эти обстоятельства не фигурируют явно в простом высказывании. Пример. а) Высказывание © ª определено однозначно. б) Истинность таких высказываний, как ©Хорошая погодаª, ©Сегодня 31 декабряª, ©Результат измерений диаметра цилинд ра равен 52 ммª зависит , соответственно , от вкусов или критерия оценки погоды, сегодняшней даты, требуемой точности измерения. Высказывание ©Завтра будет дождьª может получ ить значение ©истинаª или ©л ожьª в зависимости от конкретной ситуации. В качестве с имволов для обозначения атомов используются заглавные буквы латинского алфавита или заглавные буквы с индексами. Каждая буква в рассуждении должна обозначать одно и только одно элементарное высказывание. Пример. а)  ©Снег белыйª. б)  ©Аня является студентк ой университетаª. в) − ©Группа КН - 11 - 1 насчитывает 19 студент ов ª. Логические связки и формулы логики высказываний Рассматривая конструкции естественного я зыка, видим, что простые предложения объединяются в сложные при помощи соответствующих сентенциональных связок (союзов), т.е. сложные предложения состоят из простых предложений и служебных слов (©еслиª, ©тоª, ©иª, ©илиª и т.п.). Пример. Составные (сложны е) высказывания: а) © Снег белый, и температура ниже нуля ª . б) © Если Петр на занятиях, то Аня дома ª . в) © Петр − студент института или шахтер ª . П ростые предложения и союзы можно использовать как элементы словаря, необходимого для формализации естественного языка с помощью логики высказываний. Операции логики высказываний ‬ логические связки ‬ рассматриваются как формальные обозначения соответствующих им связок естественного языка. Сентенциональные связки в разговорном языке допускают различные варианты. Поэт ому при записи сложного предложения в виде формулы алгебры высказываний важно выяснить характер логической связи между предложениями, не вдаваясь в смысл этих предложений. Из одних высказываний различными способами можно строить новые, более сложные высказ ыв ания, называемые формулами или молекулами , используя те же операции (и их символы), что и в булевой алгебре. Примеры связок и их символов приведены в таблице 4.1 . Таблица 4.1 − Логические связки в логике высказываний Название Обозначение Аналоги естестве нного языка Отрицание н е , ©неверно, чтоª Конъюнкция и Дизъюнкция и ли, ©или одно из двух …, или обаª, либо Импликация влечет, ©если, …тоª, ©только еслиª , ©т олько тогда, когдаª, ©есть достаточное условиеª, ©при условии, чтоª, ©есть необходимое условиеª Эквивалентность э квивалентно, равносильно, ©тогда и только тогда , когда ª, ©если и только еслиª , ©есть необходимое и достаточное условие ª Рассмотрим примеры и выражения естественного языка, которые соответствуют логическим связкам . Определение. Отрицание м высказывания называется высказывание (обозначение ) , которое истинно тогда и только то гда, когда ложно. Данная унарная операция соответствует отрицанию в естественном языке, которое может иметь различные синтаксические выражения (см. таблицу 4.1) . Пример. Пусть имеем высказывание − ©Владимир получил электронное письмо от Александраª. Отрицанием высказывания является : − ©Владимир не получил электронное письмо от Александраª. Данное высказывание можно представить следующим образом: − ©Неверно, что Владимир получил электронное письмо от Александраª. Определение. Высказывание , называемое конъюнкцией и , истинно тогда и только тогда, когда истинны оба высказ ывания и . Эта логическая операция соответствует в естественном языке связке ©иª, соединяющей два предложения. Пример. Пусть имеем простые высказывания: − ©Харьков является первой стол ицей Украиныª; − ©Харьков − красивый городª. Составное высказывание, определяющее конъюнкцию , будет иметь вид : − ©Харьков является первой столицей Украины и Харьков − красивый городª. Определение. Высказыв ание , называемое диз ъюнкцией и , ложно тогда и только тогда, когда ложны оба высказывания и . Эта логическая операция соответствует соеди нению высказываний естественного языка с помощью связки ©илиª, употребляемой в смысле ©не исключающее илиª: ©верноª , или верно , или оба высказывания равны. Пример. Пусть имеем два атома: − © ª и − © ª. Тогда высказывание © или ª будет соответствовать формуле . Определение. Высказывание , называемое импликацией (условным предложением), ложно тогда и только тогда, когда истинно, а ложно. В импликации высказывание называется посылкой (у словием, антецедентом) , а  следствием (заключением, консеквентом) . Выражаемая импликацией причинно - следственная связь между и на естественном языке описывается следующими оборотами: © влечет ª, ©если , то ª, © является достаточным основанием для ª, © , потому что ª, © при условии выполнения ª. Используемые в точных науках понятия достаточного и необходимого условий можно формально выразить с помощью импликации. Пример. Пусть имеем два атома: − © − простое ª и − © − нечетное ª. Тогда высказывание © Для того, чтобы было нечетным, достаточно, чтобы было простымª будет соответство вать формуле . Определение. Если и  высказывания, то высказывание , называемое эквиваленцией , истинно тогда и только тогда, когда и либо оба истинны, либо оба ложны. Эта операция в естественном языке соответствует оборотам: ©… тогда и только тогда, когда …ª, ©для того чтобы …, необходимо и достаточно …ª, Пример. Пусть имеем два атома: − ©ид ет дождьª и − ©на небе тучиª. Тогда высказывание ©Дождь идет тогда и только тогда, когда на небе тучиª будет соответствовать формуле . Алфавит логики высказываний содержит следующие символы: 1) высказывательные п еременные или заглавные буквы с индексами; 2) логические символы (связки) ; 3) символы скобок ( ) и запятую. Связки могут быть бинарными и унарными. Операции являются бинарными логическими св язками, операция − унарной логической связкой. При записи формул можно обойтись бе з некоторых скобок, если приписать ранги логическим связкам. Ранги логически х связ ок чаще всего задаются в таком порядке (от высшего к низшему): . Пример. − © Влажность большая ª . − © Температура высокая ª . − 2 Мы чувствуем себя хорошо ª . Высказывание ©Если влажность большая и температура высокая, то мы не чувствуем себя хорошоª можно записать в виде формулы или с учетом рангов операций . Определение. В логике высказываний правильно построенная формула определяется рекурсивно следующим образом: 1. Атом есть формула. 2. Если и  формулы, то  также формулы. 3. Никаких формул, кроме порожденных указанными выше правилами, не существует. Алгебра логики и логика высказываний Определение. Логика высказыв аний ‬ это алгебраическая структура ) с носителем ‬ двоичным множеством { : ©Ложьª, : ©Истинаª } , операциями ( логическими связками ): © ª ‬ конъюнкция, © ª ‬ дизъюнкция, © ª ‬ отрицание, © ª ‬ импликация, © ~ ª ‬ эквивалентность. Если рассмотреть две алгебры: алгебру логики и алгебру логики высказываний , то он и будут изоморфны друг другу , так как можно поставить взаимно однозначное соответствие между множествами , , а операции просто одинаковы. Е сли алгебры изоморфны, то элементы и операции м ожно переименовать так, что совпадает с . Из условия изоморфности следует, что любое эквивалентное соответствие в алгебре сохраняется в . То есть соотношения , пол ученные в алгебре , автоматически распространяются на алгебру . С логической точки зрения двоичные объекты, которые рассматривались в разделе ©Элементы математической логики. Алгебра булевых функцийª,  это выс казывания, которые могут быть истинными или ложными. Формулы  это составные высказывания, истинность которых определяется истинностью входящих в них элементарных высказываний (обозначаемых буквами ) и логическими операциями над высказываниями. Поэтому все утверждения относительно алгебры логики справедливы и для алгебры логики высказываний. Если рассматривать формулы, содержащие только логические операции , то в логике высказываний выполняется закон двойственности. Кроме того, формулы логики высказываний можно представить в виде ДНФ и КНФ, СДНФ и СКНФ (учитывая изоморфизм алгебр). Интерпретация формул логики высказываний . Правильные рассуждения Определение. Приписывание истинностных значений атомам, из которых построено высказывание, называется интерпретацией высказывания . Для высказывания, содержащего атомов, можно составить интерпретаций, так же, как и для - местной булевой функции. Формулы логики высказываний мож но задавать таблицами истинности, подобно булевым функциям. Пример. Рассмотрим таблицу истинности для логических связок логики высказываний ( таблица 4.2 ) Таблица 4.2  Таблица истинности логических связок Л Л И Л Л И И Л И И Л И И Л И Л Л Л И Л Л И И Л И И И И Исходя из принимаемых формулами логики высказываний истинностных значений, фо рмулы разделяются на тождественно истинные, тождественно ложные и необщезначимые. Определение. Формула называется тождественно истинной (тавтологией или общезначимой) , если она принимает значение © и стинаª на всех интерпретациях (наборах значений переменных ) . Определение. Формула называется тождественно ложной (противоречивой или невыполнимой) , если он а принимает значение ©л ожьª на всех интерпретациях. Определение. Формула называется необщезначимой или непротиворечивой , если она на одних интерпретациях прин имает зна чение ©и стинаª, а на других ‬ ©л ожьª. Определение. Все формулы, не относящиеся к противоречивым, образуют множество выполнимых формул. Пример. Формула − тавтология; формула является противоречивой ; формула является выполнимой. Перечислим наиболее важные тавтологии, предполагая, что − произвольные формулы: 1. ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ; 8. ; 9. ; 10. (закон Пирса). При доказательстве утверждений различных математических т еорий обычно используют рассуждения, которые на языке логики можно выразить формулами. Определение. Рассуждение называется правильным , если оно выражается тождественно истинной формулой. Таким образом, проверить правильность рассуждения можно, построив соответствующую ему формулу и определив, является ли она тождественно истинной. Доказать, что формула является тавтологией, можно следующими способами: 1. Построить таблицу истинности этой формулы. Если в таблице истинности на всех интерпретациях функция при нимает значение ©истинаª, то соответствующее формуле рассуждение является тавтологией. 2. Применив тождественные преобразования, привести её к виду одного из логических законов. Если в результате преобразований получим значение ©истинаª, то формула является т автологией. Логическая эквивалентность и логическое следствие Определение. Две формулы называются равносильными , если на всех наборах значений входящих в них переменных эти формулы принимают одинаковые значения. Равносильность формул логики высказывани й вытекает из тождественности соответствующих формул алгебры логики. Равносильности формул и будем обозначать через . Легко видеть, что равносильность − это отношение эквивалентности (о но рефлексивно, симметрично и транзитивно), поэтому равносильность называют также логической эквивалентностью . Теорема. Если − любые формулы, т о и меют место следующие логические эквивалентности: 1. , (коммутативность). 2. , (ассоциативность). 3 . , (дистирибутивность). 4 . , (идемпотентность). 5 . , (закон ы поглощения). 6 . (закон двойного отрицания.) 7 . , (закон ы де Моргана). 8. , . 9. , . 10. , . Кроме того, с помощью отношения равносильности выражаются различные связки между формулами: , , , , , , . Любая из равносильностей может быть доказана с помощью таблиц истинности (а также следует из изоморфизма алгебр и ). Рассмотренные и подобные им равносильные соотношения можно использовать для преобразования и упрощения структуры сложного высказывания. Определение. Высказывание является логическим следствием высказывания , если формула является тождественно истинной. Данное определение может быть обобщено на случай произвольного числа посылок. Определение. Высказывание является логическим следствием выска зываний , если − тождественно истинная формула. Пример. Показать, что высказывание является логическим следованием высказывания . Покажем, что формула является общезначимой. Для этого используем тождества логики высказываний для эквивалентных преобразований, учитывая, что : . Общезначим ость формулы доказана. Исчисление в ысказываний Рассмотренное содержательное описание логики высказываний позволяет ответить на многие вопросы данной логики ( например, является ли формула тавтологией, равносильны ли две заданные формулы и т.д. ) , используя таблицы истинности либо эквивалентн ые преобразования формул. Однако для ответа на более сложные вопросы используется другой метод − метод формальных аксиоматических теорий. Исчисление высказываний , являясь формальной системой , представляет собой пример аксиоматической теории и од ин из возм ожных способов ф ормализации логики высказываний. В исчислении высказываний особое внимание уделяется тождественно истинным высказываниям, поскольку они должны входить в любую теорию в качестве общелогических законов. Их порождение и является основной задач ей исчисления высказываний. Данная формальная система позволяет проверить, является ли заданная формула тавтологией, а также получить общезначимые формулы логики высказываний. Исчисление высказываний содержит язык, систему аксиом и правила вывода . Рассмотр им каждое из этих составляющих. Определение. Язык исчисления высказываний , являясь формальным языком для математических рассуждений, состоит из формул логики высказываний , правильно построенных с использованием алфавита данной логики. Пример. Правильно построенные формулы с использованием алфавита логики высказываний: , . Выражения, не являющиеся формулами: , , . Аксиомы и полнота исчисления логики высказываний В математике и ©чистойª логике доказывают теоремы, т.е. выводят следствия из определенных допущений, которые называются аксиомами или гипотезами . При этом предполагается, что они ( аксиом ы или гипотез ы) тождественно истинны во всей ра ссматриваемой теории. Определение. Аксиомами логики высказываний является некоторое множество общезначимых формул логики высказываний. Аксиомы (гипотезы) представляют собой перечень одного или более высказываний ( посылок ), которые часто называются схем ам и аксиом . Сис т емы аксиом исчисления высказываний подбираются таким образом, чтобы исчисление обладало свойством полноты. Полнота исчисления высказываний заключается в том, что в данной системе имеется достаточное количество аксиом для того, чтобы вывести любую формулу логики высказываний, которая является тождественно истинной. Выводимость в исчислении высказываний Определение. Выводом в исчислении высказывания называется всякая последовательность формул такая, что для любого формула есть либо аксиома, исчисления высказываний, либо непосредственное следствие каких - либо предыдущих формул, полученных по правилу вывода. Определение. Формула называется теоремой ис числения высказывания (как аксиоматической теории), если в ней существует вывод, в котором последней формулой является . Этот вывод называется выводом формулы . Определение. Формула наз ывается следствием множества формул тогда и только тогда, когда существует такая последовательность формул , что есть , и для любого форму ла есть либо аксиома, либо формула из , либо непосредственное следование некоторых предыдущих формул. Эта последовательность называется выводом из . Элементы называются посылками вывода или гипотезами . Сокращенно можно записать так: ( есть следствие ) . Если множество состоит из формул , то пишут . Правила вывода позволяют получать новые формулы, которые являются истинными при условии истинности всех посылок, входящих в правило. В логике правила вывода используются, чтобы выводить одни истинные предложени я из других истинных предложений. Доказательство в исчислении высказываний представляет собой логический вывод списка высказываний. Определение. Дедуктивным выводом называется вывод формулы из формулы , основ анный на том, что является логическим следствием . Правила для дедуктивного вывода строятся на основе общезначимых формул логики высказываний вида . Эти правила часто записывают как пра вила формального вывода в следующем виде , где  посылки вывода, а следствие (заключение) . Тавтология, соответствующая такому правилу,  это . Пример. Рассуждени е по схеме не правильное рассуждение, так как формула не является тавтологией. Например, пусть : ©5 − простое числоª и : ©5 − нечетное числоª, : ©Если 5 − простое число, то 5 − нечетное числоª и : ©5 − нечетное числоª , то : ©5 − простое числоª, не правильное рассуждение. Наиболее часто в практических задачах используются: а) правило отделения ; б) правило подстановки. Правило отделения имеет следующий логический смысл: если посылка верна, то верно и следствие из неё. Пример. Рассуждения с помощью правила отделения: ©Если студент не выучил теорию, то он не выполнит задание. Студент не выучил теор ию. Следовательно, студент не выполнит заданиеª. ©Если студент получил пять, значит, он решил задачу. Студент получил пять. Следовательно студент решил задачуª. Правило подстановки выражает тот факт, что если в тождественно истинной формуле все вхождения какого - либо атома заменить на некоторую формулу, то полученное выражение останется тождественно истинным. Рассмотрим правило подстановки. Пусть и − формулы логики высказываний, − ато марная формула. Если − формула, выводимая в исчислении высказываний, содержащая атом , то − выводимая формула, полученная заменой всех вхождений в формуле на формулу . Правило подстановки записывается следующим образом: . Пример. Используя правило подстановки и коммутативный закон для дизъюнкции, доказать общезначимость следующей формулы: . Запишем тождество, соответствующее коммутативному закону длдя дизъюнкции: . Определим подстановку − атомарную формулу заменим на : . Если опусти ть скобки в соответствии с приоритетом операций, то можно убедиться в истинности исходной формулы. Кроме рассмотренных правил вывода в исчислении высказываний часто использу ются правила дедуктивного вывода , представлен н ы е в таблице 4.3. Таблица 4.3 − П рав ила дедуктивных выводов логики высказываний Правило дедуктивного вывода Тавтология Название правила Правило введения дизъюнкции , Прави ло введения конъюнкции , Правило удаления дизъюнкции (дизъюнктивный силлогизм) Правило удаления конъюнкции Правило контрапозиции импликации , Правило отделения (Modus Ponens) , Отрицательная форма п равила отделения ( ModusTollens ) , Гипотетический силлогизм Непротиворечивость , независимость Проблема непротиворечивости возникает при рассмотрении любого исчисления (это одна из к ардинальных проблем математической логики). Определение. Логическое исчисление непротиворечиво , если в нем не выводимы никакие две формулы, из которых одна является отрицанием другой. Непротиворечивое исчисление − это такое исчисление, что, какова бы ни была формула , никогда формулы и не могут быть одновременно выведены из аксиом этого исчисления с помощью указанных в нем правил. Если в системе обнаруживаются выводимые формулы вида и то такое исчисление называется непротиворечивым. Такие исчисления н икакой ценности не представляют, т.к. они не могут отражать в себе различие между истиной и ложью. Теорема. Исчисление высказываний непроти воречиво. Рассмотрим свойство независимости системы аксиом исчисления высказываний. Определение. Если ни одну из аксиом системы исчисления высказываний нельзя вывести из остальных, применяя правила вывода данной системы, то говорят, что система аксиом н езависима . Аксиомы исчисления высказываний подбираются таким образом, чтобы они были независимы. Различные аксиоматизации исчисления высказываний Существуют различные аксиома тизации исчисления высказываний, т.е. исчисление высказываний можно описать раз личными системами аксиом, используя различные наборы символов алфавита, лишь бы с их помо щью можно было выразить все оста льные логические операции. Пример. 1. Акси о матизация исчисления высказывания Гилберта и Аккермана (1938): а) связки ; б) аксиом ы: , , , ; в) правило : Modus Ponens (правило отделения) . 2. Акси о матизация исчисления высказывания Россера (1953) : а) связки ; б) аксиомы: , , ; в) правило: Modus Ponens (правило отделения). 3. Акси о матизация исчисления высказывания Клини (1952) а) связки ; б) аксиомы: , , , , , , , , , . в) правило: Modus Ponen s (правило отделения). Приведем в качестве примера следующую формальную систему исчисления высказывания: 1. Язык системы состоит из правильно построенных формул логики высказываний, содержащих операции . Алфа вит языка совпадает с алфавитом логики высказываний и содержит, кроме символов перечисленных логических операций, символы скобок и символы для обозначения высказываний. 2. Аксиомы системы : а) ; б) ; в) . 3. Правила вывода: а) правило отделения ( Modus Ponens ) ; б) правило подстановки. Достоинством данной формальной системы является л аконичность при сохранении определ енной наглядности. Некоторые приемы доказательств в исчислении высказываний Для доказательства истинности утверждений в исчислении высказываний существуют определенные приемы. Один из них использует теорем у о дедукции . Теорема о дедукции. Пусть − множество формул, − формулы и . Тогда . Эта теорема обосновывает следующий прием: в математических рассуждениях часто какое - то утверждение доказывают в предположении некоторого другого утвержден ия , после чего зак лючают, что верно утверждение © если то ª . Вместо прямого логического вывода формулы из формулы часто оказывается удобны м доказать противоречивость формулы тем самым доказав истинность формулы . Такой метод (прием) доказательства н азывается методом от противного и может быт ь реализован следующими схемами: 1) − если из предположения, что − верно, а − неверно, следует два противоречащих друг другу высказываний, то это означает, что из следует ; 2) − если из предположения, что − неверно, следует, что неверно, то это означает, что из следует . Основные понятия логики предикатов Логика высказываний, рассмотренная выше, является достаточно узкой логической системой, в ней не все логические рассуждения могут быть осуществлены. Например, в рамках этой системы нельзя записать такое рассуждение ©Простое число 2 − четное. Следовательно, существуют простые четные числаª. Многие утверждения, имеющие форму высказываний, на самом деле таковыми не являются, так как содержат переменные, конкретные значения которых не указаны. Поскольку такое утверждение при одних значениях переменных может быть истинным, а при др угих ‬ ложным, ему не может быть предписано истинностное значение. Такие утверждения называются предикатами . В логику предикатов также введены дополнительные, новые по сравнению с логикой высказываний, логические понятия, а именно, предикат, терм, квантор. Определение. Предикатом называется функция , переменные которой принимают значения из некоторого множества , а сама она принимает два значения (истинное) и (лож ное), т.е. (где ). Понятие предиката является частным случаем понятия функции, для которой четко фиксирована область значений. Предикаты становятся высказываниями, когда их переменным присваиваются значения. Пример. Предикатами являются следующие утверждения: Пусть , тогда утверждение является высказыванием, и это выск азывание истинно. При утверждение тоже является высказыванием, и это высказывание ложно. Определение. Множество значений , которое может принимать , называется у ниверсом или предмет н ой областью . Пример. В частности, предметной областью может являться множество действительных чисел, множество целых чисел или другие подобные множества. Множество значений перменных определяется обычно матема тическим контекстом. Определение. В общем случае определен некоторый предикат , если: 1) задано некоторое (произвольное) множество, называемое областью определения предиката (предметная область); 2) фиксировано множество { И, Л } , называемое областью значени й ; 3) указано правило, с помощью которого каждому элементу, взятому из предметной области, ставится в соответствие один из двух элементов из области значений. Определение. Предикат с одной переменной называется одноместным предикатом и может обозначаться, например, , где − переменная. Предикат, имеющий две переменные, называется дву х местным предикатом и может обозначаться, например, , где − переменные , а предикат, содержащий переменных ( аргументов), называется - местным предикатом и обозначается . Высказывания считаются нульместны м предикат ом. Количество аргументов предикат а называется его порядком . Пример. В ысказывание © − действительное числоª можно представить одноместным предикатом, © меньше ª − двуместным предикатом. Если и замещены конкретными значениями (объектами), то предикат переходит в высказывание, которое рассматривается как нульместный предикат . Определение. Аргументы предиката называются термами . Термы - константы и термы - переменные называются предметными константами и предметными переменными . Предикаты обычно обозначаются большими латинскими буквами . И ногда бывает удобно указыва ть число переменных у предиката путем введения верхнего индекса, например является - местным предикатом. Предикатом чаще всего обозначают свойство или действие, выраженное в высказывании сказуемым, а объекты и субъекты этого действия, а также другие члены предложения являются аргументами данного предикат а. В качестве обозначения предиката также можно выб рат ь слово, отраж ающее его смысловое значение. Пример. Представим в виде предиката высказывания: © делится на 7 ª , © делится на ª , © − простое число ª. Выберем в качестве названий предикатов действия или свойства данных предложений: ДЕЛИТСЯ, ПРОСТОЕ. Тогда заданные высказывания можно записать в виде предикатов следующим образом: ДЕЛИТСЯ( , 7 ), ДЕЛ ИТСЯ( , ), ПРОСТОЕ( ). Здесь первый и третий предикат являются одноместными и каждый выражает некоторое свойство числа ; второй предикат ‬ двуместный и выражает бинарн ое отношение делимости на множестве чисел. Для построения атомов логики предикатов разрешается использовать следующие типы символов :  индивидуальные символы или константы , которые обычно являются именами объектов, например: Сократ, 13;  символы предметных п еременных , в качестве которых обычно выступают буквы латинского алфавита, возможно, с индексами, например: ;  функциональные символы ‬ строчные буквы латинского алфавита или осмысленные слова из строчных букв, например: минус( ) ‬ функциональный символ © ª, отец ( ) ‬ функциональный символ ©отец человека ª;  предикаты ‬ прописные буквы или осмысленные слова из прописных букв, например: , , ДЕЛИТСЯ, БОЛЬШЕ, ПРОСТОЕ. Пример . Переведем на естественный язык следующие высказывания логики предикатов: 1) РАВНЯТЬСЯ ; 2) ЗНАТЬ(папа(Вася), математика). Предикат РАВНЯТЬСЯ соответствует утверждению © равняется 5 ª естественного языка. Здесь 5 ‬ константа, − предметная переменная. В высказывании ЗНАТЬ(папа(Вася), математика) функциональный символ ©папа( )ª принимает значение из множества людей, соответствующее отношению ©быть отцом ª. Поэтому выражение папа(Вася) следует интерпретировать как ©Васин папаª. Таким образом, предикат ЗНАТЬ (папа(Вася), математика) соответствует предложению ©папа у Васи знает математикуª естественного языка. Здесь ©Васяª и ©математикаª являются константами, а − предикатная переменная . Операции логики предикатов. Кванторные операции Над предикатами можно производи ть обычные логические операции, которые обозначаются символами и называются логическими связками (как и в логике высказываний). Пример. Пусть − предикат © делится на 3ª, − предикат © делится на 5ª, тогда выражение означает © делится на 3 и делится на 5ª, т.е . определяет предикат делимости на 15. Кроме операций логики высказываний к предикатам применяются операции с вязывания квантором. Кванторы управляют областью значения переменной, следующей за символом квантора. Определение. Пусть − предикат, определенный на множестве . Высказывание ©для всех истинноª обозначается . Определение. Символ называется квантором всеобщности ( квантором общности ) . Если применяется квантор всеобщности, то говорится, что высказывание истинно для всех из некоторого множества. Определение. Высказывание ©существует такой , что истинноª обозначается , где символ называется квантором существования . Квантор суще ствования применяется, когда нужно указать, что существует хотя бы одно значение переменной, для которой истинно данное высказывание. Пример. Запи шем в виде предикатов с кванторами следующие высказывания: ©Все студенты сдают экзаменыª, ©Некоторые студенты сдают экзамены на отличноª. Введем предикаты: − ©сдавать экзаменыª и − ©сдавать экзамены на отличноª . П редметная область данных предикатов представляет собой множество студентов. Тогда исходные выражения прим ут вид: и . Заметим, что имеют место ранги логических связок, учитывая которые кванторы и размещаются между связками и . Применение кванторов к многоместным предикатам уменьшает количество переменных, от которых зависит данный предикат. Например, применение квантора по одной из переменных двухместного предиката превращает его в одноместный. Квантор общности можно исто лковывать как обобщение конъюнкции, а квантор существования ‬ как обобщение дизъюнкции, т.е. если область определения предиката конечна, например, , то высказывание эквивалентно , а высказывание − дизъюнкции . Пример . Пусть задан предикат , который означает © − нечетное числоª и определен на области . Высказывание означает: © − нечетное числоª, и − нечетное число и − нечетное числоª, а высказывание означает то ж е, что и дизъюнкция © − нечетное число, или − нечетное число, или нечетное число ª Ф ормулы и их интерпретация в логике предикатов На языке предикатов можно составить гораздо более слож ные предложения, чем на языке высказываний. О предели м понятие формулы в логике предикатов. Алфавит логики предикатов в общем случае содержит следующие символы: 1) символы предметных переменных: ; 2) символы предикатов : , где ; 3) логические символы: ; 4) символы кванторов: ; 5) скобки и запятую: ),( . Определение. Если  - местный предикат и  термы, то называется атомом или элементарной формулой логики предикатов . Пример. Атомами являются: ДЕЛИТСЯ( ,13), ДЕЛИТСЯ( , ), БОЛЬШЕ (плюс( ,1), ), РАВНЯТЬСЯ( ,1), СДАВАТЬ(студенты, сессия). Определение. Правильно построенными формулами логики предикатов называются формулы, которые можно рекурсивно определить следующим образом: 1. Атом является фор мулой. 2. Если и − формулы, то также являются формулами. 3. Если − формула, а − свободная переменная, то и тоже формулы. 4. Никаких формул, кроме порожденных указанными выше правилами, не существует. Введем понятие свободного и связанного вхождения переменной в формулу . Определение. В выражениях и форм ула , на которую распространяется действие квантора, называется областью действия квантора . Следует заметить, что формула может и не иметь в хождений переменной . В таком случае считаетс я, что формулы и одинаковые. Определение. Вхождение переменной в формулу называется связанным , если − переменная квантора или , входящего в данную формулу, либо находится в области действия квантора или , входящего в данную формулу. В противоположном случае вхождение переменной в данную формулу называется свободным . Пример. Определим вхождение переменных в следующие формулы: а) ; б) , в) . Единственное вхождение переменной в формул у а) является свободным. Первое вхождение переменной в формулу б) свободное, а второе и третье − связанные. Все вхождения переменной в формулу в) связанные. Определение. Переход от к или называется связыванием переменной , а сама переменная в этом случае ‬ связанной . Переменная, не связанная никаким квантором, называется свободной . Смысл св язанных и свободных переменных в предикатных выражениях различен. Свободная переменная − это обычная переменная, которая может принимать различные значения из ; выражение ‬ переменное высказывание, зависящее о т значения . Выражение не зависит от переменной и при фиксированных и имеет вполне определенное значение. Это в частности означает, что п ереименование связанной переменной, т.е. переход от к , не меняет истинности выражения. Определение. Формула называется замкнутой , если она не имеет свободных переменных. Поскольку действие квантора может рас пространяться не на всю формулу, а только на её часть, то переменная может быть связанной в одной части формулы и свободной в другой. В этом случае полагают, что переменная является и связанной, и свободной одновременно. Чтобы предикат был высказыванием, в се его переменные должны иметь конкретные значения или быть связаны соответствующим квантором. Пример. не является высказывание м , так как переменная не связана никаким квантором. Формулы имеют смысл только т огда, когда существует какая - либо интерпретация символов, входящих в эти формулы. Определение. Интерпретация формулы логики предикатов состоит из элементов непустой предметной области , значений всех констант , функциональных символов и предикатов, встречающихся в . Указанные значения задаются следующим образом: 1. Каждой константе ставится в соответствие некоторый элемент из . 2. Каждому - местному функциональному символу ставится в соответствие отображение из в . Здесь , где . 3. Каждому - местному предикату ставится в соответствие отобра жение из в {И, Л}. Для каждой интерпретации на области формула может получать истинностное значение И или Л согласно следующим правилам: 1. Если заданы значения формул и , то истинностные значения формул ( ), ( ), ( ),( ),( ) получаются с помощью таблиц истинности соответствующих логических операций. 2. Формула получает значение И, если получает значение И для каждого из , в противном случае она получает значение Л. 3. Формула получает значение И, ес ли получает значение И хотя бы для одного из , в противном случае она получает значение Л. 4. Формула, содержащая свободные переменные, не может получать истинностные значения. Пример. Пус ть задан предикат . Формула не истинна , если универс ом (предметной областью) является множество целых чисел , однако она была бы истинн ой , если в качестве предметной области взять множество целых чисел, больших чем 2. Квантифицированный предикат , где , не является истинным, если предметная область − множество целых чисел, потому что имеются значения из этой области (например, ) такие, что ложно. Для истинности должно быть истинным для каждого значения из предметной области. Пример. Предикат , где , является истинным, если предметной областью есть множество действительных чисел, т.к. истинно для Предикат , где , также истинен, если предметно й областью есть множество действительных чисел, однако, он не является истинным, если предметная область есть множество целых чисел, т.к. не существует целого числа, квадрат которого равен 5. При логической (истинностной) интерпретации формул логики преди катов так же, как и в логике высказываний определяются общезначимые , противоречивые, выполнимые , необщезначимые формулы , а также логическое следствие . Законы и тождества логики предикатов Все законы и тождества, которые справедливы в логике высказываний, остаются справедливыми и в логике предикатов. Для эквивалентных преобразований предикатных высказываний с кванторами дополнительно необходимо использовать приведенные ниже законы. 1. Замена связанной переменной : ; , − одноместный предикат. Введение нового обозначения связанной переменной (т.е. переименование связанной переменной) не изменяет смысл формулы логики предикатов, если выполняется следующее условие: никакая свободная переменна я в любой части формулы не должна после переименования оказаться связанной. Пример. Для нового обозначения связанной переменной следует выбирать букву , которая отсутствует в формуле, например, . Здесь осуществлена операция переименов ания связанной переменной . 2. Коммутативные свойства кванторов: ; . Менять местами можно только одноименные кванторы. . 3. Дистрибутивные свойства кванторов ; ; ; , где − формула логики предикатов, которая не содержит ; ; . Сформулиро ванный дистрибутивный закон справедлив только для квантора всеобщности при конъюнкции и квантора существования при дизъюнкции , т.к. другие комбинации приводят к неравенствам: ; . Для преодоления данного ограничения дистрибутивного закона, следует использов ать замену связанной переменной: ; . Таким образом, в общем случае д истрибутивные свойства кванторов можно записать следующей схемой: ; , где − любой из кванторов или . 4 . Закон де Моргана для кванторов : ; . Предваренные нормальные формы Определение. Формула в логике первого порядка находится в предваренной нормальной форме (ПНФ) тогда и только тогда, когда она может быть представлена в виде , где каждое , , есть или , или , а − формула, не содержащая кванторов. Причем называетс я префиксом , а − матрицей формулы . Для преобразования выражений произвольной формы в ПНФ необходимо поочередно выполнить следующие этапы преобразования: 1. Исключить логические связки эквиваленции и импликац ии, выразив их через операции дизъюнкции, конъюнкции и отрицания с помощью следующих законов: ; . 2. Опустить знаки операций отрицания непосредственно на предикаты, используя закон двойного отрицания и законы де Моргана , , в том числе для кванторов: ; . 3. Если необходимо, переименовать связанные переменные. 4. Вынести кванторы в начало формулы, и спользуя соответствующие законы, для получения предваренной нормальной формы Пример. Приведем формулу к предваренной нормальной форме . Сначала исключим импликацию, затем опустим знак операции отрицания непосредственно на предикат и вынесем квантор в начало: . Выводимость в логике предикатов Для дедуктивного вывода в логике предикатов можно использовать правила, которые применяются для подобных выводов в логике высказываний. Однако в л огике предикатов для проведения дедуктивных умозаключений используются также и специфические правила, учитывающие наличие кванторных операций. К таким правилом относятся следующие правила : а) Правило удаления квантора всеобщности ис пользуется для доказательства истинности , где − произвольно выбранный элемент предметной области , в которой справедливо . Пример. Из посылки ©Все студенты любя т получать хорошие оценкиª делаем вывод: ©Студент Петров любит получать хорошие оценкиª. б) Правило введения квантора всеобщности утверждает истинность , если доказана истинность для л юбого , то есть для всех элементов из рассматриваемой предметной области . в) Правило удаления квантора существования в истинной формуле з аключается в указании имени элемента (конкретного или гипотетического), для которого истинно. г) Правило введения квантора существования позволяет заключить, что является истинным, когда известен некоторый элемент , для которого истинно . Исчисление предикатов В логике предикатов, в отличие от логики высказываний, нет эффективного способа для распознавания общезначи м ости формул. Поэтому аксиоматический метод становится существенным при изучении формул, содержащих кванторы. В логике предикатов существует формальная система, которая носит название исчисление предикатов . Выделение общезначимых формул в ней так же, как и в исчислении высказываний, осуществляется путем указания некоторой совокупности формул, которые называются аксиомами, и указания правил вывода, позволяющих из общезначимых формул получить общезначимые. Определение. Исчисление предикатов − это аксиоматиче ская теория, символами которой являются: 1) символы предметных переменных: ; 2) символы предикатов: , где ; 3) логические символы: ; 4) символы кванторов: ; 5) скобки и запятую: ),( . Аксиомами исчисления предикатов являются следующие аксиомы: а) ; б) ; в) ; г) ; д) . В исчислении предикатов исп ользую тся следующие правила вывода: 1. Правило отделения , которое формулируется так же, как и в исчислении высказываний: ; 2. Правило связывания квантором общности ( правило обобщения , правило - введения ) , где содержит свободные вхождения , а их не содержит. 3. Правило связывания квантором существования ( правило - введения ) , где содержит свободные вхождения , а их не содержит. 4. Правило переименования связанной переменной . Связанную переменную формулы можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в . Пример. Докажем правило переименования связанных переменных для квантора общности: 1. (по условию). 2. (аксиома а) ) . 3. (правило обобщения). 4. . Понятия вывода, теоремы, вывода из системы гипотез определяется в исчислении предикатов, как и в любой аксиоматической теории. Теорема (ослабленная тео рема о дедукции) Пусть − множество формул, − формулы и , и существует вывод в исчислении предикатов, построенный с применением только правила отделения , то . Утве рждение 1 . Аксиомы исчисления предикатов − общезначимые формулы. Утверждение 2 . формула, полу чающаяся из общезначимой формулы по любому из правил 1 − 4, является общезначимой.

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

  • pdf 1132931
    Размер файла: 637 kB Загрузок: 0

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