07logika.pdf

(315 KB) Pobierz
Podstawy matematyki dla informatyków
Cz¦±¢ VII. Logika
Logika formalna
(Klasyczny rachunek zda«)
Zima 2013-14
www.mimuw.edu.pl/~urzy/Pmat/07logika.pdf
◦
Skªadnia rachunku zda«
Symbole (zmienne) zdaniowe
(
p
,
q
,
r
, . . .
),
oraz znaki
⊥
i
s¡ formuªami zdaniowymi.
Je±li napis
Skróty i priorytety
Napis
α
↔
β
jest skrótem napisu
(α
→
β)
∧
(β
→
α)
.
Zewn¦trzne nawiasy opuszczamy.
Koniunkcja i alternatywa wi¡»¡ mocniej ni» implikacja
(maj¡ wy»szy priorytet).
Np. zamiast
α
jest formuª¡ zdaniow¡,
to tak»e napis
Je±li
¬α
jest formuª¡ zdaniow¡.
(
p
∧
q
)
→
r
mo»na pisa¢
p
∧
q
→
r
.
oznacza implikacj¦.
α
i
β
s¡ formuªami zdaniowymi to napisy
Negacja ma najwy»szy priorytet:
napis
(α
→
β),
(α
∨
β),
(α
∧
β)
te» s¡ formuªami zdaniowymi.
¬
p
→
q
Koniunkcja i alternatywa wi¡»¡ tak samo:
napis
p
∨
q
∧
r
jest niepoprawny.
◦
◦
Semantyka rachunku zda«
Interpretacja zdaniowa
to funkcja
, która
Przykªad
warto±ciowanie zdaniowe
)
ka»dej zmiennej zdaniowej
p
przypisuje warto±¢ logiczn¡
(
p
)
∈ {
0
,
1
}
.
(inaczej:
:
Warto±¢ formuªy
Formuªa
((
p
∧
q
)
→
r
)
→
(
p
→
r
)
, gdzie
i
ma warto±¢ jeden przy
przy interpretacji
interpretacji
[[⊥]] =
0 oraz
[[ ]] =
1;
[[
p
]] = (
p
)
, gdy
p
jest symbolem zdaniowym;
[[¬α]] =
1
−
[[α]]
;
[[α
∨
β]]
=
max
{[[α]]
,
[[β]]
}
;
[[α
∧
β]]
=
min
{[[α]]
,
[[β]]
}
;
[[α
→
β]]
=
0, gdy
[[α]] =
1 i
[[β]] =
0;
[[α
→
β]]
=
1, w przeciwnym przypadku.
◦
(
p
) = (
r
) =
1
(
q
) =
0.
Ta sama formuªa ma warto±¢ zero przy interpretacji
µ
,
gdzie
µ(
q
) =
µ(
r
) =
0
i
µ(
p
) =
1.
◦
Speªnialno±¢ i prawdziwo±¢
Je±li
Dlaczego tautologie s¡ wa»ne
Fakt:
i mówimy, »e
przez interpretacj¦
.
Przykªad:
Wiadomo, »e formuªa
tautologi¡. Zatem
jest tautologi¡.
Je±li w tautologii
ϕ
podstawimy dowolne formuªy
w miejsce zmiennych zdaniowych,
1
to otrzymamy tautologi¦.
[[ϕ]] =
1
to piszemy te»
formuªa
|=
ϕ
ϕ
jest
speªniona
(
p
→
q
)
↔ ¬
p
∨
q
jest
((
p
→
r
)
→
r
)
↔ ¬(
p
→
r
)
∨
r
te»
Formuªa
ϕ
jest
speªnialna
,
gdy
|=
ϕ
zachodzi
dla pewnej
interpretacji
.
To samo dotyczy dowolnych stwierdze«, którym mo»na
sensownie nadawa¢ warto±¢ logiczn¡. Zatem tautologia
to ogólnie poprawny schemat zdania prawdziwego.
Formuªa speªniona przy
ka»dej
interpretacji
jest
prawdziwa
(jest
tautologi¡
).
Piszemy
|=
ϕ
.
Na przykªad, ta równowa»no±¢ jest na pewno prawdziwa:
[
x
∈
A
→ ∃
y
(
x
∼
y
•
)]
↔
[
x
∈
A
∨ ∃
y
(
x
∼
y
•
)]
,
◦
niezale»nie od tego, co oznaczaj¡ znaki
1
W
∈
,
∼
oraz
•
.
◦
miejsce tej samej zmiennej
p
podstawiamy t¦ sam¡ formuª¦.
Przykªady tautologii
Przykªady tautologii
p
→
(
p
∨
q
)
,
q
→
(
p
∨
q
)
,
p
→
(
q
→
p
)
;
(
p
→
r
)
→
((
q
→
r
)
→
(
p
∨
q
→
r
))
;
(
p
∧
q
)
→
p
,
(
p
∧
q
)
→
q
,
(
p
→
(
q
→
r
))
→
((
p
→
q
)
→
(
p
→
r
))
;
((
p
→
q
)
→
p
)
→
p
;
⊥ →
p
,
p
→
,
.
(
r
→
p
)
→
((
r
→
q
)
→
(
r
→
p
∧
q
))
;
p
∨ ⊥ ↔
p
,
p
∧ ⊥ ↔ ⊥
,
◦
◦
p
∨
p
∧
↔
↔
p
.
;
Przykªady tautologii
p
→ ¬¬
p
,
Wnioskowanie z przesªanek
ϕ
konsekwencj¡
¬¬
p
→
p
;
(¬
q
→ ¬
p
)
→
(
p
→
q
)
;
¬(
p
∧
q
)
↔
(¬
p
∨ ¬
q
)
;
Mówimy, »e formuªa
i piszemy
je»eli
jest
zbioru zaªo»e«
Γ
,
Γ
|=
ϕ
,
gdy dla dowolnej interpretacji zdaniowej
dla ka»dego
(
p
→
q
)
→
(¬
q
→ ¬
p
)
,
¬(
p
∨
q
)
↔
(¬
p
∧ ¬
q
)
,
(
p
→
q
)
↔
(¬
p
∨
q
)
;
[[γ]] =
1
γ
∈
Γ
,
to tak»e
[[ϕ]] =
1.
Przykªad:
{ϕ →
ψ, ψ
→
ϑ}
|= {ϕ →
ϑ}
.
Zwi¡zek
((
p
↔
q
)
↔
r
)
↔
(
p
↔
(
q
↔
r
))
;
Γ
|=
ϕ
to ogólnie poprawny schemat wnioskowania.
◦
◦
Normalizacja formuª
Literaª
gdy
to symbol zdaniowy lub negacja symbolu zdaniowego.
Normalizacja formuª
Twierdzenie:
Szkic dowodu:
Najpierw eliminujemy implikacje, stosuj¡c zasad¦:
Dla ka»dej formuªy zdaniowej istnieje
Formuªa zdaniowa
ϕ
jest w
koniunkcyjnej postaci normalnej
,
r
równowa»na jej formuªa w koniunkcyjnej postaci normalnej.
ϕ
jest koniunkcj¡ alternatyw literaªów, tj. wygl¡da tak:
k
1
1
k
(
p
1
∨ · · · ∨
p
1
1
)
∧ · · · ∧
(
p
r
∨ · · · ∨
p
r
)
,
gdzie wszystkie
p
ji
s¡ literaªami.
(α
→
β)
↔
(¬α
∨
β)
.
Uwaga:
(1) Pusta koniunkcja (
r
(2) Pusta alternatywa
=
0) to staªa .
(
k
i
=
0) to staªa
⊥
.
◦
Otrzymujemy formuª¦, w której wyst¦puj¡ tylko
∨
,
∧
i
¬
.
◦
Normalizacja formuª
∨
,
∧
i
¬
.
r
Reguªy przepisywania
Eliminujemy podwójne negacje:
Dana jest formuªa, w której wyst¦puj¡ tylko
formuªa nie jest w postaci normalnej
Je±li ta
¬¬α
⇒
α
.
Przesuwamy w dóª negacje z pomoc¡ praw De Morgana:
k
1
1
k
(
p
1
∨ · · · ∨
p
1
1
)
∧ · · · ∧
(
p
r
∨ · · · ∨
p
r
)
,
to zawiera podformuª¦ jednej z nast¦puj¡cych postaci:
¬(α ∨
β)
⇒
(¬α
∧ ¬β)
¬¬α
,
¬(α ∧
β)
⇒
(¬α
∨ ¬β)
¬(α ∨
β)
,
∨
α
,
¬(α ∧
β)
,
∧
α
,
¬
,
¬⊥
,
⊥∨
α
Eliminujemy nadmiar staªych logicznych:
⊥ ∧
α
,
∨
α
⇒
,
∧
α
⇒
α
,
⊥ ∨
α
⇒
α
.
α
∨
(β
∧
γ)
⊥ ∧
α
⇒
⊥
,
Przesuwamy w dóª alternatywy:
◦
α
∨
(β
∧
γ)
⇒
(α
∨
β)
∧
(α
∨
γ)
.
◦
Przykªad
Dlaczego ta procedura musi si¦ zako«czy¢?
¬(
p
∨ ¬
q
)
∨
(
r
∧
)
¬(
p
∨ ¬
q
)
∨
r
(¬
p
∧ ¬¬
q
)
∨
r
(¬
p
∧
q
)
∨
r
(¬
p
∨
r
)
∧
(
q
∨
r
)
.
przepisujemy do postaci:
Ka»dej formule (bez
Formuª¦
→
i
↔
)
przypiszemy liczbow¡
wag¦
:
waga
(
p
) =
2, gdy
p
jest atomem.
waga
(ϕ
∧
ψ)
=
waga
(ϕ) +
waga
(ψ) +
2;
waga
(ϕ
∨
ψ)
=
2
·
waga
(ϕ)
·
waga
(ψ)
;
waga
(¬ϕ) =
2
waga
(ϕ)
.
Fakt:
Ka»da operacja zmniejsza wag¦.
Wtedy:
Na przykªad niech
Wszystkie te formuªy s¡ równowa»ne.
Ostatnia formuªa jest w koniunkcyjnej postaci normalnej.
waga
(α) =
a
i
waga
(β) =
b
.
waga
(¬(α
∨
β))
=
2
waga
(α∨β)
=
2
2
ab
;
waga
(¬α
∧ ¬β)
=
2
a
+
2
b
+
2
<
2
2
ab
.
◦
◦
J¦zyk logiki pierwszego rz¦du (uproszczony)
Rachunek predykatów
Zmienne indywiduowe, np.
Symbole relacyjne, np.
x
,
y
, . . .
itp.
r
,
≤
,
(pierwszego rz¦du)
Mog¡ by¢ symbole funkcyjne, staªe, i wyra»enia
algebraiczne z nich utworzone (
termy
).
◦
◦

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin