Matematicheskaya_logika
.pdf2. ( хС(х)→D)↔ у(С(у)→D), где С(х) и D не содержат у в качестве свободной переменной
3. (D→ хС(х))↔ у(D→С(у)), где С(х) и D не содержат у в качестве свободной переменной
4. (D→ хС(х))↔ у(D→С(у)), где С(х) и D не содержат у в качестве свободной переменной
5. ¬ хА(х)↔ х¬А(х)
6. ¬ хА(х)↔ х¬А(х).
Доказательство:
1. 1) х С(х)→D - гипотеза
2)¬ у (С(у)→D) - гипотеза
3)¬¬ у¬(С(у)→D) (2, определение существования)
4)у¬(С(у)→D) (3, ¬¬В→В, МР)
5)¬(С(х)→D) (4, А4, МР)
6)С(х)&¬D (5, ¬(А→В)→А&¬В. МР)
7)С(х) (А&В→А, МР)
8)¬D (А&В→В, 6, МР)
9)х С(х) (7, ПО)
10)D (1, 9, МР)
11)D&¬D (8, 10, А→(В→(А&В)), МР дважды)
1–11) х С(х)→D, ¬ у (С(у)→D) D&¬D по теореме дедукции:
х(С(х)→D)→(¬ у(С(у)→D)→D&¬D) /вследствие (¬А→В)→(¬В→А),
(А→В)→((В→С)→(А→С))/ ( хС(х)→D)→(¬(D&¬D)→ у(С(у)→D)) ( хС(х)→D)→ у(С(у)→D)
|
|
|
у(С(у)→D)→( хС(х)→D) |
|||||||
|
|
|
||||||||
1) |
у(С(у)→D) - гипотеза |
|
|
|
|
|
||||
2) |
хС(х) - гипотеза |
|
|
|
|
|
||||
3) С(b)→D b – элемент, при котором формула выполняется |
||||||||||
4) |
С(b) (А4, 2, МР) |
|
|
|
|
|
||||
5) |
(3, 4, МР) |
|
|
|
|
|
||||
|
|
|
|
|
|
|
||||
1 – 5 у(С(у)→D), хС(х) |
|
|
D у(С(у)→D), хС(х) |
|
D, по теореме дедукции, |
|||||
|
|
|
||||||||
применённой дважды , имеем |
|
|
у(С(у)→D)→( хС(х)→D). |
|||||||
|
|
|||||||||
|
|
|||||||||
Аналогично 2 – 6. |
|
|
|
|
|
Пример. х(А11(х)→ у(А12(х, у)→¬ zА22(у, z))). Привести к ПНФ.
х(А11(х)→ у(А12(х, у)→ z¬А22(у, z)))х(А11(х)→ у U(А12(х, у)→¬А22(у, U)))х v(А11(х)→ U(А12(х, v)→¬А22(v, U)))х v T(А11(х)→(А12(х, v)→¬А22(v, T)))
2. Следуя Дедекинду, (1901) рассмотрим формальную арифметику (ФА) при помощи теории I порядка S, содержащей предметную константу а1, функциональный символ f11, f12, f22 и предикатный символ A12. При этом будем использовать обозначения:
а1 - 0
f11(x)-х f12(t, s)-t+s
f22(t, s)-t is A12 - t=s.
Тогда собственные аксиомы имеют вид:
(S1): (х1=х2)→(х1=х3→х2=х3) (S2): х1=х2→х1 =х2
(S3): 0≠х1
(S4): х1 =х2 →х1=х2
(S5): х1+0=х1
(S6): х1+х2 =( х1+х2 ) (S7): х1 i0=0
(S8): х1 iх2 = х1 iх2 + х1
(S9): А(0)→( х(А(х)→А(х ))→ хА(х))
Для произвольной формулы А(х) в теории S.
Из схемы аксиомы S9 следует правило индукции:
А(0), хА(х)→А(х )) хА(х)
Лемма. Для произвольных термов t, r, s следствие формулы является теоремами для теории S.
[S1] t=r → (t=s→r=s)
[S2] t=r→t =r [S3] 0≠ t
[S4] t =r → t=r [S5] t+0=t
[S6] t+r = (t+r) [S7] t i0=0
[S8] t ir =t ir+t
Доказательство: т.к., применяя ПО к аксиомам S1-S8 и А4, подставляя вместо переменных соответствующие термы, при помощи МР, получим данное утверждение. Например, рассмотрим аксиому (S1):
1. (S1) (х1, х2, х3) (S1)
2. х3 S1(х1, х2, х3) (1, ПО)
3. х3 S1(х1, х2, х3)→S1(х1, х2, s) (А4) 4. S1(х1, х2, s) (2, 3, МР)
5. х2 S1(х1, х2, s) (4, ПО) и аналогично получаем
S1(t,r,s)
Теорема. Для произвольных термов t, r, s следствие формулы является теоремами теории S.
1. t=t
2.t=r→r=t
3.t=r→(r=s→t=s)
4.r=t→(s=t→r=s)
5.t=r→(t+s=r+s)
6.t=0+t
7.t +r= (t+r)
8.t+r=r+t
9.t=r→(s+t=s+r)
10.(t+r)+s=t+(r+s)
11.t=r→(t is=r is)
12.0=0 it
13.t ir=t ir+r
14.t ir=r it
15.t=r→(s it=s ir)
Доказательство:
1.1) t+0=t→(t+0=t→t=t) ([S1])
2)t+0=t ([S5])
3)t=t (1, 2, MP2)
2.1) t=r→(t=t→r=t) ([S1])
2)t=t (1.)
3)t=r→r=t (вследствие 1, 2, тавтолгии В→((А→(В→С))→(А→С)), МР2)
1)-3) 2.
3.1) r=t→(r=s→t=s) ([S1])
2)t=r→r=t (1.)
3)t=r→(r=s→t=s) (2, 1, тавтология А→В→((В→С)→(А→С))
1)-3) |
|
|
3. |
|
|
|
|
|
|||
4. 1) r=t→(t=s→r=s) |
(3) |
|
|||
2) |
|
|
t=s→(r=t→r=s) |
(1, правило замены посылок (ПЗП), т.е. |
|
(А→(В→С))→(В→(А→С)), МР) |
|||||
3) s=t→t=s (2) |
|
|
|||
4) s=t→(r=t→r=s) |
(3, 2, тавтология) |
||||
5) r=t→(s=t→r=s) |
(4, ПЗП) |
|
|||
1-5 |
|
4. |
|
|
|
|
|
|
|||
|
|
|
5. Рассмотрим формулу А(z): x=y→(x+z=y+z) I. A(0) - ?
1)x=y (гипотеза)
2)x+0=x ([S5])
3)x+0=y (2, 1, правило силлогизма (ПС))
4)y+0=y ([S5])
5) x+0=y+0 |
(3, 4, 4) |
1 - 5, x=y |
x+0=y+0, по теореме дедукции х=у→(х+0=у+0) |
А(0) ! |
|
II. 1) х=у→(х+z=у+z) (гипотеза)
2)х=у (гипотеза)
3)х+z=у+z (1, 2, МР)
4) |
(х+z) =(у+z) (3, [S2], МР) |
|
||
5) |
х+z =(х+z) |
([S6]) |
|
|
6) |
х+z =(у+z) |
(5, 4, ПС) |
|
|
7) |
у+z =(у+z) |
([S6]) |
|
|
8) |
х+z =у+z |
(6, 7, 4) |
|
|
1 - 8, |
1), 2) |
х+ z =у+z по теореме дедукции 1) |
х=у→(х+z =у+z ) |
А(z)→А(z ) (ПО) z (А(z)→ А(z ))
по правилу индукции z (А(z). Тогда, применяя А4, заменяя z на s и МР, и у на r и х на t получим утверждение 5.
A(t, r, s)
6. t=0+t А(х): х=х+0
|
|
|
х (А(х). |
|
||||||
|
|
|
|
|||||||
I. A(0) - ? |
|
|||||||||
1) |
0+0=0 |
([S5]) |
||||||||
2) |
0+0=0→0=0+0 (теорема2) |
|||||||||
3) |
0=0+0 |
(1, 2, MP) |
||||||||
1) |
- 3) |
|
|
А(0) |
|
|||||
|
|
|
||||||||
|
|
|
||||||||
II. |
|
|
А(x)→A(x ) |
|||||||
|
||||||||||
|
|
|||||||||
1) |
A(x): x=0+x |
(гипотеза) |
||||||||
2) |
х =(0+х) |
([S2], 1, МР) |
3)0+х =(0+х) ([S6])
4)х =0+х (4, 2, 3)
|
|
|
|
|
|
|
A(x ), |
|
|
|
|
А(x)→A(x ) по теореме |
|
|
|
||
1)-4), х=0+х |
|
|
|
|
|
дедукции и ПО |
|||||||||||
|
|
|
|
||||||||||||||
|
|
х(А(x)→A(x )) |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|||||||||
I, II, ПИ |
|
|
х А(x) по (А4) |
|
|
|
х А(x)→А(t), по МР |
|
|
А(t). |
|||||||
|
|
|
|
|
|
||||||||||||
|
|
|
При помощи рассмотренной теоремы можно получить вследствие теоремы 2 о теории I порядка с равенством, что S является теорией I порядка с равенством.
Если рассмотрим интерпретацию этой теории при помощи области интерпретации, состоящей из множества неотрицательных целых чисел.
а1-0
f11(t, s)-х
f12(t, s)-t+s f22(t, s)-t is А12(t, s)- t=s
Принимая данную интерпретацию в качестве модели теории S, получаем нормальную модель, которая называется стандартной моделью теории S. Все остальные, неизоморфные этой модели – нестандартными.
В 1931 г. Гёдель доказал, в любой теории, формализующей формальную арифметику, невозможно доказать (в рамках этой теории) непротиворечивость формальной арифметики, т.е. существует утверждение о непротиворечивости формальной арифметики, которое ни доказать, ни опровергнуть нельзя. (Теорема Гёделя о неполноте).
3. Интерпретация.
Все формулы теорий I порядка K имеют смысл только в некоторой интерпретации.
Под интерпретацией понимается непустое множество D, называемое областью интерпретации, и соответствие сопоставляющее предикатному символу Ajn , n-местное отношение (какое-либо подмножество прямого произведения n множеств D ), функциональному символу fjn - n-местные операции, предметная константа ai понимается как элемент множества D, при этом предметная переменная считается пробегающей всю область D.
Например, рассмотрим интерпретацию формул (1), (2), (3) при помощи D – N, А12 - ≤ , тогда 1) Формула А12 (х1, х2) интерпретируется как бинарное отношение ( так как имеет две свободные переменные ) ≤ на множестве N (натуральные числа). 2) Формула х1 А12(х2, х1) интерпретируется как свойство
( так как имеет одну свободную переменную ) натурального числа быть наименьшим. 3) х2 х1 А12(х2, х1) интерпретируется как высказывание ( так как не имеет свободных переменных ), утверждающее существование наименьшего натурального числа.
Рассмотрим понятие выполнимости формулы на некотором наборе в данной интерпретации. Для этого под ϕ(А) будем понимать интерпретацию формулы А посредством подстановки вместо всех свободных переменных соответствующих компонент из набора ϕ и выполнения предписанных интерпретацией действий.
Рассмотрим определение выполнимости формулы индуктивно, следуя пунктам определения формулы:
1.Формула Ajn(t1,...,tn) выполняется на ϕ тогда и только тогда, когда ϕ(Ajn(t1,...,tn))
– истино, то есть (ϕ(t1), ϕ(t2),...,ϕ(tn)) Bjn ., где Bjn есть отношение, интерпретирующее предикатный символ Ajn.
2.Формула ¬А выполняется на ϕ тогда и только тогда, когда А не выполняется на
ϕ.
3.Формула А→В выполняется на ϕ тогда и только тогда, когда А не выполняется на ϕ или В выполняется на ϕ.
4.Формула хiА выполняется на ϕ тогда и только тогда, когда формула А выполняется на любом наборе ψ, который отличается от ϕ не более, чем только
своей i-ой компонентой, то есть ψ(хj)=ϕ(хj) при i≠j.
Таким образом, формула А является выполнимой на последовательности ϕ, если при подстановке в формулу А вместо всех её свободных переменных
соответствующих компонент набора ϕ и интерпретации всех символов получается истинное высказывание.
Формула называется истинной в данной интерпретации, если она выполняется на любом наборе из данной интерпретации, и - ложной, если она не выполняется на любом наборе из данной интерпретации
Формула является логически общезначимой, если она является истинной в
любой интерпретации. |
|
Пример 1.Пусть интерпретация имеет в качестве области интерпретации |
D |
множество неотрицательных целых чисел N, а предикатный символ |
A12 |
интерпретируется при помощи отношения ≤ х2 .Тогда |
|
1)Формула А12(х1, х2) является выполнимой на любом наборе, первая компонента которого совпадает с 1. Поэтому, мы можем назвать эту формулу выполнимой для
1.
2)Формула х1 х2 А12(х1, х2) интерпретируется как высказывание, которое является истинным, так как утверждает существование наименьшего натурального числа.
Рассмотрим свойства выполнимости и истинности формул.
1.¬А - истина в данной интерпретации тогда и только тогда, когда А - ложна в данной интерпретации; ¬А - ложна в данной интерпретации тогда и только тогда, когда А - истина в данной интерпретации.
2.Никакая формула не может быть одновременно истинной и ложной в данной интерпретации.
3.Если А и А→В - истины, то и В - истина.
4.А→В - ложна тогда и только тогда, когда А - истина, В - ложна.
5.А&В выполнена на ϕ в данной интерпретации тогда и только тогда, когда А -
выполнена на ϕ и В – выполнена на ϕ .
А В выполнена на ϕ в данной интерпретации тогда и только тогда, когда А – выполнена на ϕ или В – выполнена на ϕ.
А↔В выполнена на ϕ в данной интерпретации тогда и только тогда, когда либо А – выполнена на ϕ и В – выполнена на ϕ, либо А - не выполнено на ϕ и В - не выполнена на ϕ.
хiА выполняется на ϕ тогда и только тогда, когда существует набор ψ, который отличается от ϕ не более, чем своей i-ой компонентой, на котором выполнена формула А.
6. А - истина тогда и только тогда, когда хi А истина в данной интерпретации. Навешивание кванторов со всеми свободными переменными в порядке их
убывания называется замыканием формулы.
Пример: х2 х1(А12(х1, х2)→ х3 А13(х1, х2, х3)) является замыканием формулы
А12(х1, х2)→ х3 А13(х1, х2, х3)
Формула называется замкнутой, если она не содержит свободных переменных.
7.Всякий частный случай тавтологии, т.е. формула, которая получается из тавтологии посредством замены всех вхождений одних и тех же пропозициональных букв на одну и ту же формулу теории К, является логически общезначимой формулой.
8.Если наборы ψ и ϕ совпадают i1,...,in компонентами и свободные переменные формулы А находятся среди xi1, xi2, ...xin, то формула А выполняется на ϕ тогда
и только тогда, когда она выполняется на ψ.
Отношение, интерпретирующее данную формулу, называется отношением соответствующим данной формуле.
Пример:1. х3А12(х1, х3)&А22(х3, х2) в интерпретации, где в качестве D берется множество всех людей, А12(х, у) - интерпретируется при помощи отношения "быть братом", А22 - "быть отцом", соответствует отношение родства, связывающее дядю и племянника.
2. Формула¬А12(х1, а) |
& х2 ( х3 А12(х1, f12(х2, х3)))→ А12(х2, а) А12(х2, х1) в |
интерпретации с D=Z; |
А12(х, у) - х=у; а - 1; f12(х, у) - х i у |
соответствует свойству числа быть простым..
9.Любая замкнутая формула либо истина, либо ложна в данной интерпретации.
10.Если терм t является свободным для хi в формуле А, то формула А(t), получающаяся подстановкой вместо всех свободных вхождений хi терма t,
выполнена на всяком наборе, на котором выполняется хiА, т.е.хiА→ А(t) является логически общезначимой формулой.
11. Если формула А не имеет свободных вхождений переменной хi, то формулахi (А→В)→(А→ хiВ) является логически общезначимой.
Докажем свойство 11. Предположив противное, будем иметь, что в некоторой интерпретации, на некотором наборе ϕ эта формула не выполняется. Тогда х1 (А→В)– выполнена на ϕ (1), а А→ х1В – не выполнена на ϕ (2). Поэтому из (2) имеем, что А выполнена на ϕ, а
х1В не выполнена на ϕ, то есть на некоторой последовательности ψ, которая отличается от ϕ не более чем только своей i-ой компонентой, формула В не выполнена. А так как в силу свойства 8 формула А выполнена на ψ, то формула А→В является не выполненной на ψ, что противоречит утверждению (1).
Интерпретации, в которых все формулы некоторого множества формул Γ являются истинными, называется моделью данного множества Г.
Если в некоторой интерпретации истинны все аксиомы некоторой теории, то она называется моделью данной теории.
Формула В называется логическим следствием формулы А, если в любой интерпретации В выполняется на любом наборе, где выполняется А. Тогда А→В - является логически общезначимой.
А, В - логически эквивалентны, если В является логическим следствием А и
наоборот. Тогда А↔В - логически общезначимая.
Покажем, что формула х1 х2 А12( х1, х2)→ х2 х1 А12(х1, х2) не является логически общезначимой.
Рассмотрим интерпретацию с областью D=N и А12(х, у) - бинарное отношение <. Тогда посылка будет истиной, а заключение - ложной. Таким образом, формула не является логически общезначимой.
1. Являются ли следующие выражения формулами или термами теории I порядка:
1) x1, A12 (x1, x2 ) →a1;
2) x2 x1, A12 ( f11(x1), f22 (x1, x2 )) → A11(A12 (x1, x2 )); 3) a1, A12 ( f11(x1),a1) → A11(x1);
4) x2, A11( f11(x1)) → f11(x1);
5)(( x1(A12 ( f11(x1), f12 (x1, x2 )) & A21(x1)))→(A22 (x1, x2 ))A11(x1)));
6)(( x1, A12 (x1, f12 (x1, x2 )))→( x2 (A12 (x1, x2 ) & A11( f12 (x1, x3)))));
7)(( x1(A12 (x1, x2 ) →x2 A12 (x1, x3))) ↔(A22 (x1, x2 ) → →x2 A11(x2 ))).
2. Является ли терм
f12 (x1, f11(x2 ))
свободным для переменных в этой формуле?
3. Свободен ли терм
f12 (x1, f11(x2 ))
для переменных в формулах 5), 6), 7) задания №1.
4. Проинтерпретируйте следующие формулы:
1)A12 ( f12 (x1, x2 ),a1);
2)A12 (x1, x2 ) →A12 (x2, x1);
3) x1 x2 x3((A12 (x1, x2 ) →A12 (x2, x3) →A12 (x1, x3))
при помощи интерпретаций:
a)D =N, A12 (x, y) =x ≥ y, f12 (x, y) =x • y a1 =1;
б) D- множество всех людей
A12 (x, y): ХлюбитУ
f12 (x, y): y a1 =некто;
в) D= множество всех множеств целых чисел
A12 (x, y): x y, f12 (x, y): x y;a1 −пустое.
5. Выразите на языке теории I порядка следующие утверждения:
1)Все рыбы, кроме акул, добры к детям.
2)Либо всякий весомый человек весьма общителен, либо некий скептик замкнут.
3)Не все птицы могут летать.
4)Либо каждый любит кого-нибудь, и ни один не любит всех, либо некто любит всех, и кто-то не любит никого.
5)Если кто-нибудь может сделать это, то и Джон может.
6)Всякий, в ком есть упорство, может изучить логику.
7)Некоторые ходят в кино только тогда, когда там показывают кинокомедии.
8)Если всякий разумный философ – циник и только женщины являются разумными философами, то тогда, если существует разумные философы, то некоторые женщины – циники.