Область действия кванторов. Свободные и связанные вхождения переменных в формулу. – см. лекцию
Введение в формальную логику
Учебное пособие
| Для упражнений, помеченных знаком +, в конце даны ответы |
Глава 4 [начало]
Классическая логика предикатов
Логика предикатов – логическая теория, в которой вводятся параметры трех типов для выражений естественного языка: для предикатных выражений, функторных и для логических имен. В классической логике предикатов продолжают действовать принцип двузначности классической логики высказываний: каждое высказывание принимает в точности одно из двух значений – истина (истинно) или ложь (ложно). Принцип функциональности работает для связок логики высказываний, но в логике предикатов вводятся две новые логические операции, которые не функциональны – кванторы: $ и ". В естественном языке символу $ – квантору существования – соответствуют выражения некоторый, какой-то, существует, найдется, какой-нибудь и т.п., а символу " – квантору общности – соответствуют выражения любой, всякий, произвольный, все, каждый и т.п.
Тема 1: Язык классической логики предикатов первого порядка
| Основные понятия, которые необходимо усвоить: · логические и нелогические символы в ЯКЛП1 = · язык классической логики предикатов с символом равенства = (ЯКЛП1=) · логические и нелогические символы в ЯКЛП1 · правильно построенные выражения ЯКЛП1: терм и формула ЯКЛП1= · графы, соответствующие процедуре построения термов и формул ЯКЛП1= · область действия квантора · свободные и связанные переменные · предложение ЯКЛП1 = (замкнутая формула) |
Алфавит ЯКЛП1= (перечень исходных символов)
I. Нелогические символы:
1. a, b, c, a1, b1, c1, a2… - индивидные (предметные) константы;
2. fn, gn, hn, f1n, g1n, h1n, f2n,… - функциональные константы;
3. Pn, Qn, Rn, Sn, P1n, Q1n, R1n, S1n, P2n … – предикатные константы;
4. x, y, z, x1, y1, z1, x2… - индивидные (предметные) константы.
II. Логические символы:
Ø, &, Ú, É, º, ^, Т, $, ", =.
III. Технические символы: левая и правая скобки и запятая: ( ) , .
Терм ЯКЛП1:
1. всякая индивидная константа (a, b, c, a1, b1, c1, a2 и т.д.) есть терм;
2. всякая индивидная переменная (x, y, z, x1, y1, z1, x2 и т.д.) есть терм;
3. если Fn есть какой-либо n-местный функциональный символ (fn, gn, hn, f1n, g1n и т.д.) и о последовательностях символов t1, t2,…, tn известно, что каждый из них есть терм, тогда термом также будет такая последовательность символов: Fn(t1, t2,…, tn).
4. терм есть последовательность символов, которая может быть построена по пп.1-4.
Примеры термов
1. b - по п.1
2. b411 – по п.1
3. x1 – по п.2
4. h1(z) – по пп.2,3
5. h2(c,с) – по пп.1,3
6. h1(h1(z)) – по пп.2,3
7. f2(h1(z),a) – по пп.1,2,3
8. f2(h1(z), h2(y,z)) – по пп. 1,2,3
9. g3(h1(h1(а)), a, с) – по пп.1,3
Определение терма носит чисто синтаксический характер: оно задает некоторый класс записей, составленных из символов алфавита нашего языка, но не аппелирует к возможным смыслам этих записей, т.е. сами записи, подпадающие под определение терма, рассматриваются просто как последовательности некоторых объектов. Но эта дефиниция вводилась, разумеется, для того, чтобы впоследствии связать с ней осмысленные выражения некоторого типа, а именно: задающие объекты. Покажем (в предварительном порядке), как записи, имеющие вид терма, определяют структуры имен и именных форм. Так, структуру h1(h1(а)) имеют выражения 622, ÖÖ5, отец отца Сократа. А такую форму как f2(a,h1(z)) имеют, например, выражения 5+z2, 7-z3, p+Öy, 5×у4, 5×sinx.
Формула ЯКЛП1=:
1. ^, Т – формулы;
2. если Рn есть какой-либо n-местный предикатный символ (Pn, Qn, Rn, Sn, P1n и т.д.), а t1, t2,…, tn – термы, тогда последовательность символов
Рn( t1, t2,…, tn) является формулой;
3. если t1, t2 – термы, тогда последовательность t1=t2 есть формула;
4. если А – формула, тогда ØА тоже формула;
5. если А и В – формулы, тогда (А&В), (АÚВ), (АÉВ), (АºВ) – формулы;
6. если К – квантор ($ или "), a - индивидная переменная и А – формула, тогда следующая последовательность также является формулой: КaА;
7. формулой является последовательность символов, которая может быть построена по пп.1-7.
Самые простые (в смысле построения) формулы назовем атомарными. Атомарная (элементарная) формула – формула, построенная по каким-то из пунктов 1-3.
Формулы, процедура построения которых включает хотя бы один из пп.3-6 назовем составными (сложными, молекулярными).
Вместо Ø t1=t2 будем писать t1¹t2.
Примеры атомарных формул
^
P1(a) (читается «Р от а»; подразумевается объект а обладает свойством Р)
P1(x)
P1(f1(а)) (читается «Р от f от а»; подразумевается объект, сопоставленный объекту а функцией f, обладает свойством Р)
R2(x,a) (читается «R от х, а»; подразумевается свойство находится в отношении R с объектом а)
R2(y,y)
R2(y11,y)
R3(f1(c), f1(a), a)
R3(f1(c), f1(a), h2(y,z))
a=b
f1(a)= h1(h1(с))
f1(a)= h1(g2(y,z))
Примеры термов и формул
Примеры составных формул
$xP(x)
$x(P(x)&Q(x)) (главный знак - $)
$xP(x)&Q(x) (главный знак - &)
"y"zQ(z,f1(y)) (главный знак – квантор "y )
Ø"y"zQ(z,y) (главный знак - Ø)
"x$yR(x,y)Ú"y"zQ(z,y) (главный знак - Ú)
"x($yR(x,y)Ú"zQ(z,x)) (главный знак - квантор "x)
ØR(x,y)ÚQ(z,x) (главный знак - Ú)
Ø (a=b Ú c=b) Éa ¹b (главный знак - É)
Примеры неправильно построенных выражений (не термы и не формулы)
1. х&у. Ошибка: х и у – термы, а связка & (так же, как Ú, É, º), могут связывать только формулы.
2. f1(Q1(a)). Ошибка: после одноместного функционального символа (f1) должен стоять один терм, а в нашем случае в скобках стоит формула - Q1(a).
3. Øх & Øу. В этой записи два неправильно построенных выражения – Øх, Øу – соединены конъюнкцией. Øх – неосмысленная запись, поскольку в нашем языке отрицание может относится к структуре предложения (формуле), а не к терму (х - терм). То же с Øу.
4. P2(Q1(a),S1(a)). Ошибка: после символа двухместного предиката (P2) в скобках должны находиться два терма, а в нашей записи стоят две формулы (Q1(a) и S1(a)).
5. x. Кванторы используются только при построении формулы, но в составе формулы в обязательном порядке должны присутствовать а) предикатные символы(Pn, Qn, Rn, Sn, P1n и т.д.), либо б) выделенный предикатный символ равенства, либо в) логические константы (^, Т). В нашей записи их нет.
6. x É y. Слева и справа от импликации должны стоять формулы, а в примере 6 слева и справа от знака É стоят не формулы, а неправильно построенные выражения (см. предыдущий пример).
7. xР1(х) É yР1(х). Плохое место: Р1(х). В скобках после одноместного предиката Р1 должен стоять аналог имени – терм, а х - не терм (в состав термов не входят кванторы). Если убрать из примера 7 символ квантора существования, тогда получим формулу xР1(х)ÉyР1(х).
8. Р(а)=Р(с). Ошибка: символ равенства связывает термы, а в этом примере слева и справа от равенства стоят формулы.
9. $x"yR(x,y)ÉØ$y"аØR(x,а). Ошибка: запись "а невозможна, после квантора сразу должна идти переменная (x, y, z, x1, y1, z1, x2 и т.д.), а не константа (а – индивидная константа)[2].
10. Ø$y"ØR(x,у). Ошибка: после квантора общности (") нет переменной.
Упражнения
1. Что соответствует в естественном языке терму ЯЛП? Что формуле?
2.Определите, являются ли следующие последовательности символов осмысленными (правильно построенными) выражениями ЯЛП1 (то есть термами или формулами). Там, где не указана местность функтора или предиката, считайте, что она та, которая и требуется записью (Например, в Р(х) Р – одноместный предикат, а в Р(а,у) - двухместный).
1. + xy
2. + (x,y)
3. + P2(x&y)
4. + Øа
5. + h3(g1(f2(a,b)))
6. + x(R(x)y(P(y)&Q(x,y)))
7. a
8. x
9. f2(x,x)
10. x1824
11. f2(h2(a,b))
12. h1(f2(a, h1(z)))
13. f2h1(a)
14. f1(P1(a))
15. f1(a)& f1(c)
16. P(z1)
17. $P(x)
18. P(x,х)
19. "х f1(x)
20. "х f1(x)=h1(h1(x))
21. "aP(a)
22. P(a)
23. y1(x)
24. Q2
25. Q1("х)
26. ØR(x,y)
27. $xP(a)
28. Ø"xØ"y R(x,y)
29. $y(Q1 É Р1)
30. P1(Q1(a))
31. Ø $x"yÉ "хØ$y
32. $x"yR(x,y)ÉØ$y"xØR(x,y)
3. Укажите граф, соответствующий процедуре построения данного терма / формулы.
а) g(a, f(b))
б) Ø$x "y R(x,y) É"х$уØR(x,y)
в) $x(R(x) & "у(ØR(x,y)Ú ØR(x,y))
4. Укажите логические и нелогические константы, входящие в состав данных формул.
(а) P (x,c)
(б) "x P (x,c)
(в) "x P (x,c)É^
(г) Ø (Т º (xy((R(x) & R(y)) É Q(x,y)))
(д) $x("yQ(b,c,y) º R(x,y))Ú("z (Q (z) º R(z,b)))
Область действия кванторов. Свободные и связанные вхождения переменных в формулу. – см. лекцию
5. Укажите область действия каждого квантора в следующих формулах.
(а) "x P (x,c) ÉR(x)
(б) "x (P (x,c) ÉR(x))
(в) $x("yQ(y)ÉR(x,y))Ú("zQ(z)ÚR(z,x))
(г)+"x(P(x,y1)º$yQ(y,x))&"z(R(x,y)ºR1(y, x))
| Зачем различать свободные и связанные вхождения переменных в формулу? Свободные вхождения переменных можно заменять на имена объектов, а для связанных вхождений такая замена – незаконна, бессмысленна. Пример Рассмотрим два выражения (записанные в прикладном языке арифметики) (1) x+y=7 (2) $х$у x+y=7. Выражение (1) ни истинно, ни ложно. Все зависит от того, что мы припишем в качестве значений переменным х и у (какими числами их заменим, точнее – именами каких чисел). Выражение (2) уже есть (истинное) предложение (оно утверждает, что есть такие 2 (допустим, натуральных) числа, сумма которых есть число 7). Замена переменных на имена конкретных объектов в этом случае бессмысленна. |
6. Определить, какие вхождения переменных являются свободными, а какие связанными в следующих формулах:
а. "x P (x,c)
б."x (P(x)ÉQ(y))
в. $x("yQ(y)ÉR(x,y))Ú("z Q (z)ÚR(z,x))
г. "x(P(x,y)É$yQ(y,z,x))
д.+ "x(P(x,y)ºQ(y,x))&"z(R(x,y)ºR1(y, x))
е.+$x(P(x)ºQ(y))
ж.+ "x$y(P(x,y)ºQ(y,x))&"x"y(R(x,y)ºR1(y, x))
Формула ЯКЛП называется замкнутой или предложением, е.т.е. она не содержит свободных переменных.
| Термин предложение употребляется, таким образом, в двух смыслах: предложение естественного языка и предложение (формального) языка логики предикатов (= формула без свободных переменных) |
7. Какие из следующих формул являются предложениями ЯКЛП?
a. P1(x)
b. P1(a)
c. $xP1(x)
d. Q2(c,y)
e. Q3(a2,a2,c)
f. $x(P1(x)& Q2(c,y))
g. $y(P1(y)& Q2(c,y))É ($yR1(y)& Q2(c,y))
h. "x"x4"y((R(x4)& R(x)& R(y))ÉØQ3(x,y,x4))
i. "x"x4"y(R(x4)& R(x)& R(y))ÉØQ3(x,y,x4)
j.+ $z"x(R2(x,z)ºQ2(x,x))ÉØQ3(x,z,z)
| Договоренность Пусть a1, a2,…,an – какие-то предметные переменные (х, х1, у, у2, у1 и т.п.) и А – какая-то формула. Вместо "a1"a2…"an А будем писать "a1, a2,…, an А. Вместо $a1$a2…$an А будем писать $a1, a2,…, an А. Например, вместо "x"x4"y (Р(x,y) Ú S(х4,у) É Q(х,х4)) будем писать "x,x4,y(Р(x,y) Ú S(х4,у) É Q(х,х4)). |
Ответы
Гл.4 Упр.3
1) Неосмысленная запись: ни терм, ни формула. Раз нет предикатных знаков, значит это либо терм, либо неправильная (неосмысленная) запись. Две переменные, записанные подряд не являются осмысленной записью.
2) Неосмысленная запись: ни терм, ни формула. Раз нет предикатных знаков, значит это либо терм, либо неправильная (неосмысленная) запись. Две переменные, записанные через запятую и взятые в скобки, не являются термом.
3) Неосмысленная запись: ни терм, ни формула. Раз в состав записи входит предикатный символ, то она является либо формулой, либо неправильно построена. Ошибка в данной записи: два терма
(x и y) соединены пропозициональной связкой &, которая может связывать, согласно определениям терма и формулы, только формулы.
4) Неосмысленная запись: ни терм, ни формула. Ошибка: нельзя отрицать термы (индивидная константа а – терм).
5) Терм.
6) Формула. Ее нагруженное дерево:
Гл.4 Упр.5(г)
Область действия квантора "x (подчеркнута):
"x (P(x,y1)º$yQ(y,x)) & "z(R(x,y)ºR1(y, x))
Область действия квантора $у (подчеркнута):
"x(P(x,y1)º$yQ(y,x))&"z(R(x,y)ºR1(y, x))
Область действия квантора "z (подчеркнута):
"x(P(x,y1)º$yQ(y,x))&"z(R(x,y)ºR1(y, x))
Гл.4 Упр.6
Свободные вхождения выделены жирным шрифтом и подчеркнуты, остальные вхождения переменных – связанные.
д."x(P(x,y)ºQ(y,x))&"z(R(x,y)ºR1(y,x))
е. $x(P(x)ºQ(y))
ж. свободных вхождений переменных нет
Гл.4 Упр.7(j) Не предложение, формула содержит свободные вхождения переменных (они подчеркнуты):
$z"x(R2(x,z)ºQ2(x,x))ÉØQ3(x,z,z)
[1] Граф набран Т.В.Сальниковой; задание, взятое из книги Р.Столл «Множества. Логика. Аксиоматические теории» М., 1968, помечено [Ст], а из учебника Н.Н.Непейводы «Прикладная логика» - [Н].
[2] Выражения с постоянным значением бессмысленно квантифицировать (ставить перед ними кванторные слова: все, любой, некоторый, существует, есть, какой-нибудь и т.д.). Ср., например, выражения для любой РФ верно, что… или есть такие Соединенные Штаты Америки, в которых… Очевидно, что употребление слов любой и есть в этих фразах бессмысленно.