Равносильные преобразования формул и логическое следование формул логики предикатов

Размещено на http://www.allbest.ru/

Курсовая работа на тему:

«Равносильные преобразования формул и логическое следование формул логики предикатов»

Логика предикатов - раздел классической символической логики, изучающий субъектно-предикатну структуру высказываний, на основании чего определяют значения истинности высказываний; по-другому - это дедуктивная теория, которая моделирует процесс вывода одних высказываний из других, учитывая их структуру. Логику предикатов трактуют как расширение логики высказываний через выявление внутренней структуры высказываний и введение новых терминов и системы аксиом.

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

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

Высказыванию, в котором эмпирическом или абстрактному объекту приписывают свойство Р или определяются отношения между объектами, придают два значения истинности: "истина"; "ложь". Соответственно, логика предикатов - двузначная по количеству значений истинности высказываний.

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

Структура логики предикатов (ЛП) - алфавит, правила построения формул из символов алфавита, правила дедуктивного вывода из аксиом новых формул (доказательства теорем), правила интерпретации.

Язык логики предикатов - это система символов, образующих алфавит. К нему относятся символы, введенные в логике высказываний, и новые символы, которые обозначают термины, введенные в логике предикатов.

Алфавит:

- символы, обозначающие элементарные (простые) высказывания (формулы, формальные выражения) Р, Q;

- символы, которые обозначают истинностные значения высказываний - И, Л;

- символы, обозначающие предметные (индивидные) переменные х, у, z,... (множество предметных переменных может быть бесконечным, можно использовать для образования новых символов индексы);

- символы, которые обозначают предметные константы (постоянные) - а, в, с, d,...;

- символы, обозначающие n-местные предикаты - Р_n, Q_n, …

- символы, обозначающие предметные функции - f_nⁱ (верхний индекс обозначает местность предметных функций, а нижний определяет их номер по порядку);

- символ, что обозначает терм t;

- символ, который обозначает предикатную переменную X;

- символ, обозначающий отношение предикации ???,

- символ, который обозначает квантор всеобщности ;

- символ, что обозначает квантор существования ;

- символы, которые обозначают пропозициональные связи (логические союзы, логические постоянные): конъюнкция , дизъюнкция , импликация , эквивалентность , отрицание ;

- технические символы: ( - левая скобка; ) - правая скобка.

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

Терм - любая предметная константа или предметная переменная.

Предикат (предикатор) (лат. - срок, в традиционной логике означает свойство, присущее субъекту, если вместо переменной, от которой зависит предикат подставить конкретное значение, предикат становится высказыванием) В логике предикатов понятие "предикат" двоякий по смыслу: 1. Свойство. 2. Отношение.

1. Свойство (качество, признак, характерная черта, атрибут) - все, что присуще предметам, явлениям, процессам объективного мира, событиям и происходит в мире как их сущностная и специфическая особенность. Обозначают термином "одноместный предикат".

Одноместный предикат - логическая функция высказывания, выражающая свойство. Отношение между объектом и его свойствами называют отношением предикации. На языке логики предикатов это означает установление отношения между термином, обозначающим эмпирический объект, и термином, обозначающим абстрактный объект, который выражает свойство Р, присущее эмпирическому объекту. Термин "эмпирический объект" определяют как предметный (индивидный) концепт, термин "абстрактный объект" - как предикатное концепт, а отношения между ними - как двухместное отношение в структуре определенного высказывания. Формальный выражение такого отношения "х <= X", где "я" - предметная переменная для терминов, обозначающих эмпирический объект; "X" - предикатна переменная для терминов, обозначающих абстрактный объект; <= - знак предикации. Пример такого двухместного отношения - высказывания "Украина является республикой", где "Украина" - термин, обозначающий эмпирический объект, то есть Украинское государство, а "республика" - - термин, обозначающий абстрактный объект, то есть свойство, присущее Украинскому государству - "быть республикой" (по форме государственного правления). Последовательная формализация этого высказывания на языке логики предикатов такая: - Р,(х) - одноместная пропозиційна функция; х <=. Р(Х), где "ох" - символ для обозначения предметного (индивидного) концепта "Украина" (Украинская держава); <= - знак предикации; Р{Х) - символ для обозначения основного концепта (свойства) "республика".

Логическая равносильность формул

Понятие равносильности формул

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

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

Проверьте самостоятельно справедливость равносильностей

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

Для лучшего усвоения понятия равносильности формул алгоритм проверки на равносильность двух формул и можно представить в виде условной схемы (приведена в тексте). Формулы и заданы своими таблицами значений:

Алгоритм проверки формул на равносильность

Проанализируйте работу данного алгоритма и сопоставьте ее с определением понятия равносильности формул.

Признак равносильности формул

Сущность признака состоит в выявлении тесной связи между понятием равносильности формул и понятием тавтологии.

Теорема 4.2 (признак равносильности формул). Две формулы и алгебры высказываний равносильны тогда и только тогда, когда формула является тавтологией:

Доказательство. Если , то по определению 4.1 для любых высказываний . Тогда (по определению 1.9 операции эквивалентности) , откуда на основании соотношения (1.5) заключаем, что для любых . Последнее означает по определению тавтологии, что . Обратными рассуждениями доказывается утверждение: если , то . Итак, теорема доказана.

Отметим, что равносильность формул -- это не (логическая) операция над формулами, а отношение между формулами логики высказываний. Это означает, что если и -- формулы, то выражение уже не является формулой алгебры высказываний; оно -- утверждение о некотором взаимоотношении между формулами и , лишь сокращенная (символическая) запись утверждения (высказывания) " равносильна " об этих формулах. Это утверждение либо истинно, либо ложно, т.е. и либо находятся в отношении равносильности, либо нет. В приведенном далее следствии из теоремы 4.2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний.

Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: ;

б) симметрично: если , то ;

в) транзитивно: если и , то , т.е. отношение равносильности является отношением эквивалентности.

Доказательство. Рефлексивность следует непосредственно из тавтологии теоремы 3.3, о и теоремы 4.2.

Для доказательства симметричности отношения предположим, что , т.е. на основании признака равносильности (теорема 4.2) . Тогда по тавтологии теоремы 3.3, пункт п) заключаем: формула принимает всегда те же самые значения, что и формула , т.е. только истинные значения. Следовательно, или (по признаку равносильности) . Симметричность доказана.

Наконец, если и , т.е. и , то на основании определения конъюнкции заключаем, что: . Привлекая теперь тавтологию из теоремы 3.3, пункт р) и правило заключения для получения тавтологий (теорема 3.5), получаем , или (по теореме 4.2) . Следовательно, отношение транзитивно.

Таким образом, отношение есть отношение эквивалентности, что и требовалось доказать.

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

Примеры равносильных формул

В теореме 4.4 перечисляются некоторые основные равносильности. Они получаются из тавтологий, приведенных в теоремах 3.1-3.4, на основании признака равносильности формул.

Теорема 4.4. Справедливы следующие равносильности:

Сформулируем и докажем лемму о замене, которая служит основанием для равносильных преобразований и упрощения формул.

Лемма 4.5 (о замене). Если , то для любой формулы алгебры высказываний имеет место равносильность

Другими словами, если в формуле некоторую ее подформулу заменить на равносильную ей формулу, то полученная формула будет равносильна исходной.

Доказательство. Поскольку формулы и принимают всегда одинаковые значения при одинаковых значениях пропозициональных переменных , то формулы

и

принимают одинаковые значения при любых одинаковых наборах значений переменных и Следовательно,

то есть, что и требовалось доказать.

Например, на основании этой леммы и равносильности из теоремы 4.4 (пункт п), формула

равносильна формуле .

Общая формулировка леммы о замене может быть конкретизирована в соответствии с индуктивным определением формулы следующим образом. Пусть имеется формула . Если , то . Далее, пусть исходная формула имеет следующее строение: . Если , то . Если, кроме того, , то

, то есть .

Об этом свойстве говорят, что отношение равносильности формул стабильно относительно операции конъюнкции. (Предыдущее свойство означает стабильность относительно отрицания.) Аналогично, отношение равносильности стабильно и относительно остальных логических операций -- дизъюнкции, импликации и эквивалентности. Это означает, что если и , то

Равносильные преобразования формул

формула логика предикат язык

Используя лемму о замене и приведенные в теореме 4.4 равносильности, можем от одной формулы переходить к равносильной ей формуле. Такой переход называется равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул.

Пример 4.6. Упростим формулу , используя равносильности из теоремы 4.4:

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

Замечание 4.7. Отметим, что если некоторая формула является тавтологией, то и всякая равносильная ей формула также является тавтологией:

и .

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

Равносильности в логике и тождества в алгебре

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

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

Подобно тому как в школьной алгебре понятие тождества (тождественного равенства) приводит к понятию тождественного преобразования алгебраических выражений, так в алгебре логики понятие равносильности формул естественным образом приводит к понятию равносильного преобразования формул логики высказываний. Здесь важно уяснить, что равносильные преобразования формул основываются на лемме 4.5 о замене. Равносильные преобразования используют основные равносильности, приведенные в теореме 4.4.

Полезно сравнить свойства логических операций, выраженные в основных равносильностях, со свойствами арифметических операций, помня, что некоторые логические операции имеют претензии на аналогию с некоторыми арифметическими операциями. Так, конъюнкция нередко называется логическим умножением, а дизъюнкция -- логическим сложением. Наиболее разительны отличия в следующих свойствах: идемпотентность конъюнкции и дизъюнкции (это означает, что невозможны степени и "умножения" на натуральные числа), дистрибутивность дизъюнкции относительно конъюнкции, законы поглощения. Таким образом, мы приходим к некой новой алгебре, необычной по сравнению со школьной алгеброй, основанной на вещественных числах. Это и есть алгебра логики или алгебра высказываний. Равносильные преобразования в ней, как и в школьной алгебре, предназначены для приведения логических выражений (формул) к определенному виду.

Понятие равносильности формул

Определение 1. Две формулы, и логики предикатов называются равносильными на множестве , если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на , формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными. Равносильность формул будем обозначать так: .

Приведем пример двух неравносильных формул логики предикатов. Покажем, что

В самом деле, подставим вместо предикатных переменных и конкретные предикаты и , определенные на множестве соответственно, где есть " -- четно", а есть " -- нечетно". Тогда левая формула превратится в высказывание (нульместный предикат) "каждое натуральное число либо нечетно, либо четно", которое истинно. Правая формула превращается в высказывание (нульместный предикат) "либо каждое натуральное число четно, либо каждое натуральное число нечетно", которое ложно.

Нетрудно понять на основании определений 22.1 и ??? что формулы и равносильны тогда и только тогда, когда формула является тавтологией:

Это замечание вместе с теоремами 21.9-21.14 позволяет указать наиболее важные примеры равносильных формул.

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

Приведенная форма для формул логики предикатов

Равносильные преобразования позволяют приводить формулы к тому или иному более удобному виду. Один из таких видов носит название приведенной формы.

Определение 2. Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции , причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Теорема 3. Для каждой формулы логики предикатов существует приведенная форма.

Доказательство. Проведем доказательство методом математической индукции по числу логических связок в формуле (включая кванторы общности и существования).

Если формула не имеет логических связок, т. е. является атомарной, то она сама имеет приведенную форму. Предположим, что всякая формула, содержащая не больше логических связок, обладает приведенной формой. Покажем теперь, что приведенной формой обладает также и всякая формула, содержащая k логических связок. Пусть -- такая формула. Тогда, на основании определения 21.1, она имеет один из следующих видов:

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

Остается рассмотреть случаи, когда имеет один из следующих видов: или .

Пусть есть . Тогда формула может не быть приведенной формой для формулы . Строго говоря, для этого случая следует провести доказательство также методом математической индукции по числу логических связок формулы . Если атомарна, т.е. -- предикатная переменная , то есть -- приведенная форма. Если же -- составная формула, то задача сводится к пронесению знака через кванторы и операции и (другие логические операции не входят в приведенную форму ). Это пронесение осуществляется на основании равносильностей из логики предикатов и алгебры высказываний, называемых законами де Моргана (см. теоремы 21.9 и 4.4, пункты р, с). Итак, если есть и обладает приведенной формой , то мы сможем найти приведенную форму и для .

Далее, пусть есть . Тогда на основании теоремы 4.4 (пункт у) формула равносильна формуле . Заменив формулы и на равносильные им приведенные формы и соответственно, получим равносильную формулу , которая, вообще говоря, не является приведенной. Но, на основании предыдущего абзаца, можно найти для формулы приведенную форму . Тогда ясно, что формула имеет приведенный вид и равносильна исходной формуле .

Наконец, если есть , то на основании равносильности теоремы 4.4, (пункт ч) равносильна формуле . В предыдущем абзаце было показано, как найти приведенные формы и для формул и соответственно. Тогда ясно, что формула и имеет приведенный вид и равносильна исходной формуле .

Итак, в любом случае формула обладает приведенной формой. Теорема доказана.

Предваренная нормальная форма для формул логики предикатов

Еще одним удобным видом формулы, к которому ее можно привести равносильными преобразованиями, является предваренная нормальная форма.

Определение 22.4. Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т. е. это формула вида , где есть один из кванторов или , причем формула не содержит кванторов и является приведенной формулой. (Заметим, что кванторы в формуле могут отсутствовать вовсе.)

Теорема 22.5. Для каждой формулы логики предикатов существует предваренная нормальная форма.

Доказательство. Проведем доказательство по индукции, следуя правилу построения формул логики предикатов (определение 21.1).

Если формула атомарна, то она сама представляет собой предваренную нормальную форму. Поскольку каждая формула равносильна формуле, полученной из более простых формул и с помощью операций (операции и выражаются через и ), то теперь остается научиться находить предваренные нормальные формы для формул

если известны предваренные нормальные формы и формул и соответственно. Пусть, например, имеет вид

a имеет вид .

Рассмотрим формулу . Поскольку , то . Но формула , в свою очередь, равносильна, на основании законов де Моргана для кванторов (теорема 21.9), формуле

Остается по законам де Моргана для конъюнкции и дизъюнкции (теорема 4.4, пункты р, с) пронести знак отрицания до предикатных переменных: . Тогда будет иметь предваренную нормальную форму.

Далее, покажем, как отыскивается предваренная нормальная форма для , если есть . Поскольку при переименовании связанной переменной формула, очевидно, переходит в равносильную, то можно считать, что переменные не входят в формулу , а переменные не входят в . Ясно, что , но последняя формула еще не представляет собой предваренной нормальной формы. Покажем, как ее можно преобразовать к такой форме. На основании равносильности (получаемой из тавтологии) теоремы 21.11, а формула равносильна формуле.

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

И так далее. Наконец, на основании равносильности (получаемой из тавтологии) теоремы 21.11 (пункт г) последняя формула равносильна формуле.

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

Аналогичным образом при помощи равносильностей (получаемых из тавтологий) теоремы 21.11 (пункт б) можно построить предваренную нормальную форму для формулы , исходя из предваренных нормальных форм и формул и соответственно.

Наконец, нетрудно понять, что формула равносильна формуле и является ее предваренной нормальной формой. Аналогично, -- предваренная нормальная форма для формулы .

Итак, в каждом случае обладает предваренной нормальной формой. Теорема доказана.

Логическое следование формул логики предикатов

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

причем обратное следование не выполняется.

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

Наконец обратим внимание на тавтологии теоремы 21.13, выражающие законы удаления квантора общности и введения квантора существования

при условии, что предметная переменная у не входит свободно в формулу . Из этих тавтологий получаются следующие логические следования:

1) -- правило удаления квантора общности или правило универсальной конкретизации);

2) -- правило введения квантора существования (или правило экзистенциального обобщения).

Эти правила можно представить также в следующих видах:

при условии, что ни в одну формулу из совокупности и в формулу предметная переменная не входит свободно.

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

Размещено на Allbest.ru