LOGPOL pol.pdf

(448 KB) Pobierz
LOGIKA
Prof. dr hab. Bogdan WĘGLORZ
§0 . Rachunek zdań, algebry uniwersalne.
§1 . Systemy relacyjne.
§2 . Algebry Boole’a.
§3 . Rachunek predykatów, termy i formuły.
§4 . Wartościowania termów, spełnianie formuł, teorie i modele.
§5 . Dolne Twierdzenie Löwenheima – Skolema.
§6 . Ultraprodukty, zwartość, Górne Twierdzenie Löwenheima –
Skolema.
§7 . Aksjomaty, dowody, Twierdzenie o Dedukcji.
§8 . Równoważność logiczna, algebry Lindenbauma.
§9 . Podstawienia.
§10 . Logika pierwszego rzędu.
§11 . Twierdzenie o zupełności.
§12 . Rozwiązywanie równań – problem unifikacji.
§13 . Preneksowa postać normalna.
§14 . Skolemizacja.
§15 . Klauzule, klauzule hornowskie.
§16 . Rachunek rezolucyjny.
§17 . Przykład "grecki".
§0 . Rachunek zdań, algebry uniwersalne.
Rachunek zdań
tradycyjnie budujemy następująco:
- mamy pewien zbiór symboli V , zwanych zmiennymi zdaniowymi;
- mamy pewien zbiór symboli stałych;
- mamy pewien zbiór spójników : {s
j
}
j
∈
J
. Każdy ze spójników uważamy za symbol logiczny i z
każdym mamy związany jego arność
u
j
będącą liczbą naturalna > 0 .
To pozwala nam zdefiniować zdanie:
DEFINICJA.
Zdaniem
nazywamy ciąg symboli każdy zdefiniowany następująco:
- każda zmienna jest zdaniem i każdy symbol stały jest zdaniem;
- jeśli
s
j
jest symbolem
u
j
– arnym oraz
α
1
, ... ,
α
u
j
są zdaniami, to
s
n
α
1
...
α
u
j
jest też
zdaniem;
- innych zdań nie ma.
2
UWAGA. I tradycyjnie i dla wygody będziemy raczej pisać
s
n
(α
1
, ... ,
α
u
j
) mimo iż symboli ( , )
nie ma w opisanym przez nas rachunku.
Zdania tworzą algebrę uniwersalną. Wyjaśnimy to dokładniej.
A
= <A , {S
j
}
j
∈
J
, {a
k
}
k
∈
K
> jest
algebrą uniwersalną
jeśli A jest niepustym zbiorem (zwanym
u
nośnikiem
lub
uniwersum),
każde S
j
jest
u
j
– arną operacją (działaniem) na A , czyli S
j
: A
j
→
A ,
oraz każde
a
k
jest ustalonym elementem A .
Typem podobieństwa
algebry
A
jest funkcja
u
przypisująca operacji S
j
jej arność
u
j
wraz ze
zbiorem K indeksującym wyróżnione elementy
A
.
Dla ustalonego typu algebr (algebry tego samego typu nazywamy
podobnymi)
możemy
wprowadzić pojęcia znane w przypadku algebry: homomorfizmu i podalgebry.
Dla
homomorfizmu
robimy to następująco:
jeśli
A
= <A , {S
j
}
j
∈
J
, {a
k
}
k
∈
K
> i
B
= <B , {T
j
}
j
∈
J
, {b
k
}
k
∈
K
> są algebrami podobnymi, to
odwzorowanie
h
: A
→
B spełniające dla każdego
j
, warunek:
h(S
j
(x
1
, ... ,
x
u
j
)) = T
j
(h(x
1
) ... ,
h(x
u
j
))
oraz dla każdego
k
, warunek
h(a
k
) =
b
k
,
nazywamy
homomorfizmem
algebry
A
w
B
, symbolicznie
h
:
A
→
B
. Jeśli
h
: A
→
B jest
na, to
h
nazywamy
homomorfizmem
algebry
A
na
B
. Jeśli
h
jest 1 – 1 to
h
nazywamy
izomorfizmem
algebry
A
w
B
. Jeśli
h
jest 1 – 1 i na, to algebry
A
i
B
nazywamy
izomorficznymi.
Jeśli
A
= <A , {S
j
}
j
∈
J
, {a
k
}
k
∈
K
> i
B
= <B , {T
j
}
j
∈
J
, {b
k
}
k
∈
K
> są algebrami podobnymi,
oraz A
⊆
B i dla każdego
j
i
x
1
, ... ,
x
u
j
∈
A mamy
S
j
(x
1
, ... ,
x
u
j
) = T
j
(x
1
, ... ,
x
u
j
) ,
oraz dla każdego
k
, mamy
a
k
=
b
k
,
to mówimy,
że
A
jest
podalgebrą
B
, symbolicznie
A
⊆
B
.
Mając dany typ podobieństwa
τ
możemy zdefiniować rachunek zdań typu
τ
przez
wprowadzenie dla każdego
j
symbolu
s
j
dla spójnika
u
j
– arnego oraz dla każdego
k
symbolu stałej
c
k
.
Następnie dla danego zbioru zmiennych zdaniowych V możemy utworzyć zbiór Z(V)
wszystkich zdań typu
τ
. W końcu, możemy też utworzyć algebrę
Z(V)
zdań następująco:
- uniwersum algebry
Z(V)
jest zbiór Z(V)
- wyróżnionym elementem
Z(V)
odpowiadającym symbolowi stałej
c ,
czyli
c
jest zdanie c;
- dla każdego spójnika
s
j
określamy operację
s
Z
(V)
w algebrze
Z(V)
następująco :
j
jeśli
α
1
, ... ,
α
u
j
są zdaniami oraz
s
j
jest spójnikiem
u
j
– arnym to działanie
s
Z
(V)
j
określamy przez
s
Z
(V)
(α
1
, ... ,
α
u
j
) =
s
j
α
1
...
α
u
j
(czyli zgodnie z naszą umową
j
s
j
(α
1
, ... ,
α
u
j
)).
Tak otrzymana algebra jest oczywiście algebra typu
τ
.
Najważniejszą własnością algebry zdań jest własność przedłużania odwzorowań. Dokładniej,
mamy następujące twierdzenie.
TWIERDZENIE 0.1.
Niech
A
= <A , {S
j
}
j
∈
J
, {a
k
}
k
∈
K
> będzie algebrą typu
τ
i weźmy
algebrę zdań
Z(V)
typu
τ
. Jeśli
h
0
: V
→
A jest dowolnym odwzorowaniem, to istnieje jedyny
homomorfizm
h
:
Z(V)
→
A
taki,
że
h
0
⊆
h
.
3
Dowód.
Homomorfizm
h
budujemy przez indukcję zgodnie z indukcyjną budową zdań. Jeśli
zdanie
α
jest zmienną
v
∈
V , to
h(α)
=
h
0
(α) . Jeśli zdanie
α
jest stałą
c
k
, to
h(c
k
) =
d
k
. W
końcu, jeśli
α
=
s
j
(α
1
, ... ,
α
u
j
) , to
h(α)
= S
j
(h(α
1
) , ... ,
h(α
u
j
)) .
Niech P
⊆
A . Parę <
A
, P > nazywamy
matrycą logiczną
rachunku zdań. Pozwala ona
zdefiniować pojęcie prawdy. Odwzorowanie
h
0
nazywać będziemy
wartościowaniem
zdań. Dla
uproszczenia będziemy (ze względu na jedyność) opuszczali dolny indeks przy wartościowaniu zdań.
DEFINICJA.
Zdanie
α
jest
prawdziwe przy wartościowaniu
h
:
Z(V)
→
A
względem
matrycy logicznej <
A
, P > jeśli
h(α)
∈
P . Nic nie stoi na przeszkodzie, by zdania prawdziwe przy
każdym podstawieniu nazwać
tautologiami.
UWAGI. W klasycznym rachunku zdań mamy spójniki
∧
,
∨
,
¬
,
→
,
↔
. Nie mamy symboli
stałych. Prawdziwość zdań definiuje się przez wartościowania w algebrze
2
= < {0 ,
1}
,
AND
,
OR
,
NOT
,
IMP
,
IFF
> ,
którą opisujemy podając odpowiednie tabelki tych działań, np. dla
→
mamy tabelkę:
x
→
y
X
=
0
x
=
1
Komentarz [a1]:
y
=
0
1
0
y
=
1
1
1
Matrycą logiczną opisującą zdania prawdziwe (przy danym podstawieniu) jest <
2
, {1} > .
§1 . Systemy relacyjne.
Pojęcie algebry uniwersalnej ma swoje naturalne uogólnienie. Wystarczy w tym celu obok
operacji i wyróżnionych elementów rozpatrywać jeszcze relacje.
A
= <A , {R
i
}
i
∈
I
, {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> jest
systemem relacyjnym,
jeśli
–
A
= <A , {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> jest algebrą uniwersalną, oraz
– każde R
i
jest
v
i
– arną relacją na A , czyli R
i
⊆
A
v
i
.
Podobnie jak dla algebr, zbiór A nazywamy
uniwersum
(rzadziej nośnikiem) systemu
A
.
Typem podobieństwa
systemu
A
jest trójka (v ,
u
, K) , gdzie
v
jest funkcją przypisującą
każdej relacji R
i
jej arność
v
i
,
u
jest funkcją przypisująca operacji f
j
jej arność
u
j
oraz zbiór K
indeksuje wyróżnione elementy
A
. Dwa systemy mające ten sam typ podobieństwa nazywamy
systemami
podobnymi.
Oczywiście każdy element takiej trójki może być pusty. Zauważmy na przykład,
że
gdy
v
=
∅
, to typ (∅ ,
u
, K) jest w istocie typem podobieństwa algebr uniwersalnych.
Rozszerzymy teraz nasze konstrukcje homomorfizmu i podalgebry na systemy. Zaczniemy od
homomorfizmu.
Przypuśćmy,
że
mamy dane dwa systemy podobne
A
= <A , {R
i
}
i
∈
I
, {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> i
B
= <B , {P
i
}
i
∈
I
, {g
j
}
j
∈
J
, {b
k
}
k
∈
K
>
oraz,
że
h
: A
→
B .
Odwzorowanie
h
nazywamy
homomorfizmem
systemu
A
w
B
jeśli
h
jest homomorfizmem algebry
A
= <A , {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> w algebrę
B
= <B , {g
j
}
j
∈
J
, {b
k
}
k
∈
K
> oraz
dla każdego
i
i
x
1
, ... ,
x
v
i
∈
A ,
(w)
jeśli (x
1
, ... ,
x
v
i
)
∈
R
i
, to (h(x
1
) ... ,
h(x
v
i
))
∈
P
i
.
Fakt,
że
h
jest homomorfizmem systemu
A
w
B
zapisujemy symbolicznie
h
:
A
→
B
.
Obok powyższej definicji homomorfizmu mamy też pojęcie
silnego homomorfizmu,
w którym
warunek (w) zostaje zamieniony silniejszym warunkiem
(s)
(x
1
, ... ,
x
v
i
)
∈
R
i
iff (h(x
1
) ... ,
h(x
v
i
))
∈
P
i
.
4
Jeśli
h
jest 1 – 1 silnym homomorfizmem systemu
A
na
B
system , to
h
jest
izomorfizmem,
a systemy
A
i
B
nazywamy
izomorficznymi.
UWAGI. (1). Ponieważ zarówno warunek (w) jak też (s) dotyczą relacji, więc w przypadku,
gdy system jest algebrą (a więc nie ma relacji) pojęcia homomorfizmu i silnego homomorfizmu
pokrywają się.
(2). Jeśli
h
jest izomorfizmem to oczywiście
h
–1
jest też izomorfizmem, natomiast jeśli
h
jest
1 – 1 homomorfizmem
A
na
B
, to
h
–1
nie musi być nawet homomorfizmem.
Podsystem
i
rozszerzenie.
Przypuśćmy,
że
mamy dane dwa systemy podobne
A
= <A , {R
i
}
i
∈
I
, {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> i
B
= <B , {P
i
}
i
∈
I
, {g
j
}
j
∈
J
, {b
k
}
k
∈
K
>
oraz,
że
algebra <A , {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> jest podalgebrą <B , {g
j
}
j
∈
J
, {b
k
}
k
∈
K
> , wtedy system
A
jest
podsystemem
systemu
B
, jeśli dla każdego
i
i
x
1
, ... ,
x
v
m
∈
A ,
(x
1
, ... ,
x
v
i
)
∈
R
i
iff (x
1
, ... ,
x
v
i
)
∈
P
j
.
Inaczej mówiąc funkcja identycznościowa
id
:
A
→
B
jest silnym homomorfizmem (jest
izomorfizmem w)
A
w
B
.
Fakt,
że
A
jest podsystemem systemu
B
oznaczamy symbolicznie
A
⊆
B
. Jeśli
A
jest
podsystemem systemu
B
, to system
B
nazywamy
rozszerzeniem
systemu
A
.
Redukt
i
wydłużenie.
Jeśli
A
= <A , {R
i
}
i
∈
I
, {f
j
}
j
∈
J
, {a
k
}
k
∈
K
> jest systemem typu (v ,
u
, K) ,
to możemy opuścić pewną ilość relacji, funkcji i wyróżnionych jego elementów otrzymując w ten sposób
system
A’
= <A , {R
i
}
i
∈
I
’
, {f
j
}
j
∈
J
’
, {a
k
}
k
∈
K
’
> typu (v’ ,
u’
, K’) , gdzie
v’
⊆
v
,
u’
⊆
u
oraz K’
⊆
K .
System
A’
nazywamy
reduktem
systemu
A
, natomiast system
A
nazywamy
wydłużeniem
systemu
A’
.
UWAGA. W odróżnieniu od poprzednio zdefiniowanych operacji, operacja wydłużenia czy też
reduktu może zmienić typ systemu.
KONWENCJA.
Ponieważ w oznaczeniach związanych z systemami występuje zbyt dużo
indeksów utrudniających zrozumienie spraw istotnych, od tej pory – o ile to nie zostanie zanaczone
inaczej – będziemy zakładać,
że
nasze systemy mają tylko jedną relację, która jest
m
– argumentowa,
jedną
n
– arną funkcję, oraz jeden wyróżniony element; czyli
A
= < A , R , f ,
a
> .
Przyjęcie tej konwencji ułatwi nam zrozumienie następnej definicji.
Produkt.
Przypuśćmy,
że
A
i
= < A
i
, R
i
, f
i
,
a
i
> ,
i
∈
I , jest rodziną systemów podobnych, oraz
I
≠ ∅
. Przypomnijmy,
że
produktem
∏
A
i
rodziny zbiorów {A
i
:
i
∈
I} nazywamy zbiór wszystkich
i
∈
I
funkcji
a
: I
→
produkt
A
=
i
∈
I
∏
A
i
= <A , R , f ,
a>
i
∈
I
U
A
i
, takich,
że
dla każdego
i
∈
I mamy
a(i)
∈
A
i
. To pozwala nam zdefiniować
naszej rodziny systemów, przez zdefiniowanie wszystkich
i
∈
I
składników
A
– ”po osiach”. Uniwersum
A
jest zbiór A =
∏
A
i
,
m
– miejscową relację R
definiujemy następująco:
(a
1
, ... ,
a
m
)
∈
R iff dla każdego
i
∈
I mamy (a
1
(i) , ... ,
a
m
(i))
∈
R
i
,
f(a
1
, ... ,
a
n
) =
a
iff dla każdego
i
∈
I mamy f
i
(a
1
(i) , ... ,
a
m
(i)) =
a(i)
, oraz
dla każdego
i
∈
I mamy
a(i)
=
a
i
.
Zauważmy,
że
mając dany produkt zbiorów
∏
A
i
możemy zdefiniować operację
rzutowania
tego produktu na ”i – tą oś”, mianowicie
π
i
:
a
∈
i
∈
I
∏
A
i
i
∈
I
i
∈I
→
A
i
definiujemy przez
π
i
(a) =
a(i)
, dla każdego
π
i
:
∏
A
i
. Zauważmy przy tym,
że
na mocy definicji produktu systemów,
∏
A
i
→
A
i
i
∈
I
jest
homomorfizmem.
Część tę skończymy jeszcze dwoma operacjami związanymi z konstrukcją podsystemów.
Pierwsza z nich, to konstrukcja systemu generowanego przez podzbiór.
5
Zauważmy,
że
jeśli
A
i
= < A
i
, R
i
, f
i
,
a
i
> ,
i
∈
I , jest rodziną podsystemów systemu
B
, to
możemy, o ile
I
A
i
≠ ∅
, zdefiniować ich przekrój
I
A
i
, będący największym podsystemem ich
wszystkich. W ten sposób, jeśli mamy niepusty zbiór X
⊆
A , to możemy zdefiniować najmniejszy
podsystem systemu
A
zawierający zbiór X . Jest to po prostu przekrój wszystkich podsystemów
systemu
A
, których uniwersum zawiera zbiór X . System ten nazywamy
podsystemem generowanym
przez
X .
Druga jest związana w pewnym sensie z homomorfizmem. Wystartujemy z dowolnego systemu
A
= <A , R , f ,
a
> i przypuśćmy,
że
≈
jest relacją równoważności na A . Wtedy mamy kanoniczne
odwzorowanie
x
→
[x] przyporządkowujące każdemu elementowi
x
∈
A , jego
klasę abstrakcji
(warstwę, klasę równoważności – w innych terminologiach). Zbiór wszystkich klas abstrakcji oznaczać
będziemy A/≈ . Zbiór ten nazywa się często zbiorem lub przestrzenią ilorazową.
Relację
≈
nazywać będziemy
kongruencją
dla działania f jeśli
x
1
≈
y
1
, ... ,
x
m
≈
y
m
implikuje f(x
1
, ... ,
x
m
)
≈
f(y
1
, ... ,
y
m
) .
Jeśli
≈
jest kongruencją, to możemy w naturalny sposób zdefiniować działanie na A/≈ przez:
f
≈
([x
1
] , ... , [x
m
]) = [f(x
1
, ... ,
x
m
)] .
Co więcej możemy utworzyć
system ilorazowy
A
/≈ = <A/≈ , R
≈
, f
≈
, [a] > . Ponieważ większość
symboli została już zdefiniowana, pozostaje nam przyjąć następująca definicje relacji R
≈
:
<[x
1
] , ... , [x
n
]>
∈
R
≈
iff istnieją
y
1
≈
x
1
, ... ,
y
n
≈
x
n
takie,
że
<
y
1
, ... ,
y
n
>
∈
R .
Zauważmy,
że
taka definicja powoduje,
że
odwzorowanie
x
→
[x] jest homomorfizmem
systemu
A
na system ilorazowy
A
/≈ . Homomorfizm ten nie jest na ogół silnym homomorfizmem. Aby
tak było równoważność musi spełniać następujący warunek ”zgodności” z relacją:
Jeśli
y
1
≈
x
1
, ... ,
y
n
≈
x
n
i <
y
1
, ... ,
y
n
>
∈
R , to <
x
1
, ... ,
x
n
>
∈
R .
i
∈
I
i
∈
I
§2 . Algebry Boole’a.
Algebry Boole’a są to algebry uniwersalne typu ({2 , 2 , 1} , 2) , czyli systemy postaci
A
=<A,
∧
,
∨
,
′
,
0
,
1
>,
gdzie
∧
i
∨
są operacjami binarnymi,
′
– jest operacją unarna, natomiast
0
i
1
są wyróżnionymi
elementami. Tradycyjnie, operację
∧
nazywamy mnożeniem lub przekrojem (z tego powodu często
oznacza się ją
⋅
) , operację
∨
– dodawaniem (z tego powodu oznacza się ją często + ), natomiast
operację
′
nazywamy często dopełnieniem lub negacją. (ma ona też inne oznaczenia: - ,
c
,
¬)
. W celu
ominięcia niepotrzebnych dyskusji zakładamy zawsze,
że
0
≠
1
. Operacje te spełniają następujące
aksjomaty:
(1)
x
∨
y
=
y
∨
x
(6)
x
∧
y
=
y
∧
x
(2) (x
∨
y)
∨
z
=
x
∨
(y
∨
z)
(3) (x
∨
y)
∧
z
= (x
∧
z)
∨
(y
∧
z)
(4)
x
∨
0
=
x
(5)
x
∨
(x
′)
=
1
(7) (x
∧
y)
∧
z
=
x
∧
(y
∧
z)
(8) (x
∧
y)
∨
z
= (x
∨
z)
∧
(y
∨
z)
(9)
x
∧
1
=
x
(10)
x
∧
(x
′)
=
0
Ten układ aksjomatów nie jest najoszczędniejszy, pozwala jednak na zauważenie jednego bardzo ważnego
twierdzenia z metamatematyki
TWIERDZENIE 2.1.
Jeśli
Γ
jest twierdzeniem teorii algebr Boole’a i
∆
powstaje z
Γ
przez
jednoczesne zastąpienie
wszędzie
symboli
∧
,
∨
, 0
,
1
przez
∨
,
∧
,
1
,
0
– odpowiednio, to
∆
jest też
twierdzeniem teorii algebr Boole’a.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin