Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Формулы логики предикатов

Формулы логики предикатов


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


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


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


– предметные переменные: [math]x,y,z, x_i,y_i,z_i~ (i\in\mathbb{N})[/math];
– нульместные предикатные переменные: [math]P,Q,R,P_i,Q_i,R,~ (i\in\mathbb{N})[/math];
– n-местные [math](n\geqslant1)[/math] предикатные переменные с указанием числа свободных мест в них:

[math]R(~,\ldots,~),~~ P_i(~,\ldots,~),~~ Q_i(~,\ldots,~),~~ R_i(~,\ldots,~)~~ (i\in\mathbb{N})[/math]

– символы логических операций: [math]\lnot,~ \land,~ \lor,~ \to,~ \leftrightarrow[/math];
– кванторы: [math]\forall,~ \exists[/math];
– вспомогательные символы: [math](~,~)[/math] — скобки; [math]{},[/math] — запятая.

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


Определение 21.1 (формулы логики предикатов).


1) Каждая нульместная предикатная переменная есть формула;


2) если [math]P(~,\ldots,~)[/math] — n-местная предикатная переменная, то [math]P(x_1,\ldots,x_n)[/math] есть формула, в которой все предметные переменные [math]x_1,\ldots,x_n[/math] свободны;


3) если [math]F[/math] — формула, то [math]\lnot F[/math] — также формула. Свободные (связанные) предметные переменные в формуле [math]\lnot F[/math] те и только те, которые являются свободными (связанными) в [math]F[/math];


4) если [math]F_1,\,F_2[/math] — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения


[math](F_1\land F_2),\quad (F_1\lor F_2),\quad (F_1\to F_2),\quad (F_1\leftrightarrow F_2)[/math]

также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул [math]F_1,\,F_2[/math], называются свободными (связанными) и в новых формулах;


5) если [math]F[/math] — формула и [math]x[/math] — предметная переменная, входящая в [math]F[/math] свободно, то выражения [math](\forall x)(F)[/math] и [math](\exists x)(F)[/math] также являются формулами, в которых переменная [math]x[/math] связанная, а все остальные предметные переменные, входящие в формулу [math]F[/math] свободно или связанно, остаются и в новых формулах соответственно такими же;


6) никаких других формул логики предикатов, кроме получающихся согласно пп. 1–5, нет.


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


Например, [math]P,\, Q(x,y,z),\, R(x,y,z)[/math] — элементарные формулы, а


[math](\exists y)\bigl(P(x,y,z)\bigr),\quad (\forall x)(\exists y)\bigl(P(x,y,z)\bigr),\quad \bigl(((\forall x)(P(x))\land Q\bigr)\to\lnot (\exists y)[/math]

являются составными формулами. При этом в первой составной формуле предметная переменная [math]y[/math] связана, а переменные [math]x,\,z[/math] — свободные. Во второй составной формуле свободна лишь переменная [math]z[/math], остальные — связаны. В третьей составной формуле первое вхождение переменной [math]x[/math] связано, а второе — свободно. Переменная у связана. Последнюю формулу более целесообразно было бы записать в следующем виде (заменив связанную переменную х какой-нибудь буквой, не входящей в данную формулу):


[math]\bigl(((\forall z)(P(z))\land Q \bigr)\land\to\lnot (\exists y)\bigl(R(x,y)\bigr).[/math]

Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать, если только она не является частью более сложной формулы. Отметим кстати, что на основании пунктов 1, 3 и 4 сформулированного определения всякая формула алгебры высказываний будет также и формулой логики предикатов.


В формулах вида [math](\forall\xi)(F)[/math] и [math](\exists\xi)(F)[/math] формула [math]F[/math] называется областью действия квантора [math]\forall\xi[/math] или [math]\exists\xi[/math], соответственно. Тогда ясно, что вхождение предметной переменной в формулу будет связанным, если эта переменная находится в области действия квантора по этой переменной.


Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, — открытыми. Так, все приведенные выше формулы логики предикатов, кроме формулы [math]P[/math], являются открытыми.


Примеры замкнутых формул:


[math]P,~~ (\forall z)\bigl(R(z)\bigr),~~ (\exists x)(\forall y)\bigl(P(x,y)\bigr),~~ (\forall x)\bigl(Q(x)\bigr)\to\lnot (\forall x)(\exists x)\bigl(R(x,y)\bigr).[/math]



Классификация формул логики предикатов


Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный на некотором выбранном множестве [math]M[/math], то формула превратится в конкретный предикат, заданный над множеством [math]M[/math]. При этом, если исходная формула была замкнутой, то полученный конкретный предикат окажется нульместным, т.е. будет высказыванием. Если же исходная формула была открытой, т. е. содержала свободные вхождения предметных переменных, то в результате подстановки получим предикат, зависящий от некоторых предметных переменных. Если теперь подставить вместо этих предметных переменных конкретные предметы из множества [math]M[/math], то полученный предикат, а следовательно, и исходная формула превратятся в конкретное высказывание.


Превращение формулы логики предикатов в высказывание описанным выше способом (а также само получаемое высказывание) называется интерпретацией этой формулы на множестве [math]M[/math]. Итак, если формула логики предикатов замкнутая, т.е. не содержит свободных предметных переменных, то ее интерпретация состоит из одного этапа и сводится к подстановке вместо всех предикатных переменных конкретных предикатов, в результате чего формула превращается в конкретное высказывание (нульместный предикат). Если же формула логики предикатов открытая, т. е. содержит ряд свободных предметных переменных, то ее интерпретация состоит из двух этапов. Во-первых, вместо всех предикатных переменных необходимо подставить конкретные предикаты, в результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных в исходной формуле. Во-вторых, нужно придать значение каждой предметной переменной, от которой зависит получившийся предикат, в результате чего этот предикат (и, значит, вся исходная формула) превратится в конкретное высказывание (истинное или ложное).




Пример 21.2. Дадим интерпретацию формуле [math](\forall x)(\exists y)\bigl(P(x,y)\bigr)[/math]. В качестве множества [math]M[/math] возьмем множество всех мужчин, а вместо предикатной переменной [math]P(x,y)[/math] подставим конкретный предикат, определенный на [math]M\colon[/math] "[math]x[/math] есть отец [math]y[/math]". Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание [math](\forall x)(\exists y)[/math]([math]x[/math] есть отец [math]y[/math]) — "у каждого мужчины есть сын". Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве [math]M[/math] множество [math]\mathbb{N}[/math] всех натуральных чисел, а вместо предикатной переменной [math]P(x,y)[/math] подставим предикат "[math]x<y[/math]", определенный на [math]\mathbb{N}^2[/math]. Тогда исходная формула превратится в (очевидно, истинное) высказывание [math](\forall x)(\exists y)(x<y)[/math] — "Для каждого натурального числа существует большее по сравнению с ним натуральное число".


Пример 21.3. В предыдущем примере была рассмотрена интерпретация замкнутой формулы. Дадим интерпретацию открытой формуле [math](\exists z)\bigl(P(x,y,z)\to Q(x,y,z)\bigr)\to R[/math]. В качестве множества [math]M[/math] возьмем множество [math]\mathbb{N}[/math] всех натуральных чисел. Вместо предикатных переменных [math]P(x,y,z)[/math] и [math]Q(x,y,z)[/math] подставим трехместные предикаты "[math]x\cdot y=z[/math]" и "[math]x+y=z[/math]" соответственно, а вместо нульместного предиката [math]R[/math] подставим (ложное) высказывание "[math]2=4[/math]". Тогда данная формула превратится в двухместный предикат (от предметных переменных [math]x,y[/math]):


[math](\exists z)(x\cdot y=z\to x+y=z)\to 2=4\,.[/math]

Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных [math]x[/math] и [math]y[/math] конкретных предметов (чисел) из [math]\mathbb{N}[/math]. Нетрудно понять, что двухместный предикат [math](\exists z)(x\cdot y=z\to x+y=z)[/math] превращается в истинное высказывание при любой подстановке вместо его предметных переменных [math]x[/math] и [math]y[/math] натуральных чисел. В самом деле, для натуральных тип получаем высказывание


[math](\exists z)(m\cdot n=z\to m+n=z).[/math]

Одноместный предикат (зависит от [math]z[/math]) [math]m\cdot n=z\to m+n=z[/math], стоящий под знаком квантора [math]\exists z[/math], выполним, потому что всегда можно найти такое натуральное число [math]k[/math], что [math]m\cdot n\ne k[/math] и [math]m+n\ne k[/math], т. е. высказывания [math]m\cdot n=k[/math] и [math]m+n=k[/math] будут ложны, а значит, высказывание [math]m\cdot n=k\to m+n=k[/math] — истинно. А раз так, то высказывание [math](\exists z)(m\cdot n=z\to m+n=z)[/math] истинно. Поэтому высказывание


[math](\exists z)(m\cdot n=z\to m+n=z)\to 2=4\,,[/math]

в которое превращается данный предикат, ложно. Итак, исходная открытая формула логики предикатов превращена в тождественно ложный предикат. Нетрудно понять, что если вместо предикатных переменных [math]P(x,y,z)[/math] и [math]Q(x,y,z)[/math] подставить только что рассмотренные предикаты, а вместо нульместной предикатной переменной [math]R[/math] — любое истинное высказывание, то исходная формула превратится в тождественно истинный предикат.




Сформулируем классификационные определения для формул логики предикатов.


Определение 21.4. Формула логики предикатов называется выполнимой (опровержимой) на множестве [math]M[/math], если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.


Другими словами, формула выполнима (опровержима) на [math]M[/math], если существует истинная (ложная) ее интерпретация на [math]M[/math]. Формула из примера 21.2 является как выполнимой, так и опровержимой.


Определение 21.5. Формула логики предикатов называется тождественно истинной {тождественно ложной) на множестве [math]M[/math], если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.


Определение 21.6. Формула логики предикатов называется общезначимой, или тавтологией (тождественно ложной или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат. (Тот факт, что формула [math]F[/math] является тавтологией, обозначается, как и в алгебре высказываний, [math]\vDash F[/math].) Так, формула из примера 21.3 не является тавтологией, потому что хотя при одной подстановке она и превратилась в тождественно истинный предикат, при другой она оказалась превращенной в предикат тождественно ложный. Поэтому данная формула не является и противоречием.




Пример 21.7. Покажем, что формула [math]\lnot P(x)\land (\forall y)\bigl(P(y)\bigr)[/math] является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве [math]M[/math] имеется конкретный предикат [math]A(x)[/math], такой, что данная формула превращается в выполнимый предикат (от [math]x[/math]) [math]\lnot A(x)\land (\forall y)\bigl(A(y)\bigr)[/math]. Последнее означает: найдется предмет [math]a\in M[/math], такой, что высказывание [math]\lnot A(a)\land (\forall y)\bigl(A(y)\bigr)[/math] истинно. Истинность конъюнкции дает истинность высказываний [math]lnot A(a)[/math] и [math](\forall y)\bigl(A(y)\bigr)[/math]. Из истинности первого следует, что высказывание [math]A(a)[/math] ложно, а из истинности второго — что предикат [math]A(y)[/math] тождественно истинный и, значит, для любого предмета из [math]M[/math], в том числе и для [math]a\in M[/math], высказывание [math]A(a)[/math] истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved