Формулы алгебры предикатов. Нормальные формы для формул алгебры предикатов

Понятие формулы логики предикатов. Это понятие вводится аналогично понятию формулы алгебры высказываний. Сначала задается алфавит символов, из которых будут составляться формулы: предметные переменные: х, у, z,…; нульместные предикатные переменные: P, Q, R, …; п -местные ((n ³1)) предикатные переменные: P (,...,), Q (,...,), R (,...,),… с указанием числа свободных мест в них; символы логических операций:, Ù, Ú, ®, «; кванторы: ", $; вспомогательные символы: (,) — скобки;, — запятая. Теперь дадим определение формулы логики предикатов, которое также носит индуктивный характер.

Определение 21.1 (формулы логики предикатов). 1) Каждая нульместная предикатная переменная есть формула; 2) если P (,...,) — п -местная предикатная переменная, то P (x 1,..., xn)есть формула, в которой все предметные переменные x 1,..., xn свободны; 3) если F — формула, то F — также формула. Свободные (связанные) предметные переменные в формуле F те и только те, которые являются свободными (связанными) в F; 4) если F 1, F 2 — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения (F 1Ù F 2), (F 1Ú F 2), (F 1® F 2), (F 1«F 2) также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул F 1, F 2, называются свободными (связанными) и в новых формулах; 5) если F — формула и x — предметная переменная, входящая в F свободно, то выражения (" x)(F) и ($ x)(F) также являются формулами, в которых переменная х связанная, а все остальные предметные переменные, входящие в формулу F свободно или связанно, остаются и в новых формулах соответственно такими же; 6)никаких других формул логики предикатов, кроме получающихся согласно пп. 1—5, нет.

Формулы, определенные в п. 1 и п. 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными.

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

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

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

Теорема 21.9 (законы де Моргана для кванторов). Следующие формулы логики предикатов являются тавтологиями:

а)

б)

Следствие 21.10 (выражение кванторов одного через другой). Следующие формулы логики предикатов являются тавтологиями:

а)

б)

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

Теорема 21.11 (законы пронесения кванторов через конъюнкцию и дизъюнкцию). Следующие формулы логики предикатов являются тавтологиями:

а) ((" x)(P (x)) Ù Q (x)) «(" x)(P (x)) Ù (" x)(Q (x));

б) (($ x)(P (x))Ú Q (x)) «($ x)(P (x))Ú ($ x)(Q (x));

в) ((" x)(P (x))Ú Q) «(" x)(P (x))Ú Q;

г) (($ x)(P (x)) Ù Q) «($ x)(P (x)) Ù Q.

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

|= (($ x)(P (x)) Ù Q (x))® ($ x)(P (x)) Ù ($ x)(Q (x)); (3)

|= ((" x)(P (x))Ú (" x) Q (x))® (" x)(P (x))Ú (Q (x)). (4)

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

Понятие равносильности формул. Определение 22.1. Две формулы, F и H логики предикатов называются равносильными на множестве М, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на М, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными. Равносильность формул будем обозначать так: F @ H. Нетрудно понять на основании определений 22.1 и 21.6, что формулы F и H равносильны тогда и только тогда, когда формула F «H является тавтологией. Как и в алгебре высказываний, можно заменять одну равносильную формулу другой. Переход от одной равносильной формулы к другой называется равносильным преобразованием исходной формулы. В процессе равносильных преобразований формул логики предикатов могут использоваться равносильности, известные из алгебры высказываний.

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

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

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

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

Определение 22.4. Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т. е. это формула вида (K 1 x 1)...(Km xm)(F (x 1,..., xn)), где i K есть один из кванторов " или $(i =1,..., m), m £ n, причем формула F не содержит кванторов и является приведенной формулой. (Заметим, что кванторы в формуле могут отсутствовать вовсе.)

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