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

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

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

Подобно тому как в школьной алгебре понятие тождества (тождественного равенства) приводит к понятию тождественного преобразования алгебраических выражений, так в алгебре логики понятие равносильности формул естественным образом приводит к понятию равносильного преобразования формул логики высказываний. Здесь важно уяснить, что равносильные преобразования формул основываются на лемме 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 (пункт б) можно построить предваренную нормальную форму для формулы, исходя из предваренных нормальных форм и формул и соответственно.

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

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

Похожие статьи




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

Предыдущая | Следующая