Modul 2 Wynikanie logiczne i elementy rachunku kwantyfikatorow, Logika i teoria mnogości. Mirosław Kurkowski ...
[ Pobierz całość w formacie PDF ]
Wynikanie logiczne
i elementy rachunku kwantyfikatorów
Wstęp
2
1. Wynikanie semantyczne
3
2. Reguły inferencyjne i pojęcie dowodu formalnego
5
3. System dedukcji naturalnej
9
4. Dowody przez dodatkowe założenie
16
5. Formy zdaniowe
17
6. Kwantyfikatory
19
Bibliografia
21
Wstęp
W niniejszej części materiałów przedstawimy ciąg dalszy rozważań dotyczących
rachunku zdań. Zdefiniowane zostanie — a także scharakteryzowane
odpowiednimi twierdzeniami — pojęcie wynikania semantycznego. Na tej bazie
wprowadzimy analogiczne pojęcie, jakim jest wynikanie syntaktyczne. Zdefiniujemy
zatem pojęcie dowodu formalnego wprost i nie wprost. Wprowadzimy pewien
układ reguł dedukcji naturalnej zupełny wobec prezentowanego w poprzednim
module semantycznego ujęcia rachunku zdań. Zdefiniowane zostanie też pojęcie
formy zdaniowej i wprowadzone kwantyfikatory. Omówimy pojęcia zmiennej
wolnej i zmiennej związanej. Zaprezentujemy przykładowe prawa rachunku
kwantyfikatorów.
2
1. Wynikanie semantyczne
Powiemy, że
formuła
α
wynika
semantycznie ze zbioru formuł
X
, co będziemy oznaczać
X
׀
= α, jeżeli formuła α jest prawdziwa dla wszystkich wartościowań dających
wartość 1 dla wszystkich formuł ze zbioru
X
.
Przykład 1
Rozważmy formułę
p
⇒
q
oraz zbiór formuł
X
= {
p
,
q
}. Rozważmy wszystkie
wartościowania
v
, w których są prawdziwe wszystkie formuły (zmienne) ze zbioru
X
. Mamy wartościowanie
v
(
p
) = 1 oraz
v
(
q
) = 1. Ale wtedy mamy również
w
(
p
⇒
q
) = 1. Zatem zdanie
p
⇒
q
wynika ze zbioru
X
= {
p
,
q
} ({
p
,
q
}
׀
=
p
⇒
q
).
Przykład 2
Rozważmy formułę ¬(¬
p
∧
q
) oraz zbiór formuł
X
= {
p
, ¬
q
}. Rozważmy
wszystkie wartościowania
v
, w których są prawdziwe wszystkie zdania ze zbioru
X
. Mamy wartościowanie
v
(
p
) = 1 oraz
v
(
q
) = 0. Dla tego wartościowania
jest:
w
(¬(¬
p
∧
q
)) = 1. Zatem formuła ¬(¬
p
∧
q
) wynika ze zbioru
X
= {
p
, ¬
q
} ({
p
, ¬
q
}
׀
= ¬(¬
p
∧
q
)).
Z definicji wynikania można wyprowadzić warunek na fakt, że dane zdanie nie
wynika z odpowiedniego zbioru zdań.
Powiemy, że
formuła
α
nie wynika
semantycznie ze zbioru formuł
X
(
X
׀
≠ α), jeżeli dla
pewnego wartościowania
v
wszystkie zdania ze zbioru
X
są prawdziwe, zaś zdanie
α jest fałszywe (
w
(α) = 0).
Przykład 3
Rozważmy formułę ¬
p
∧
q
oraz zbiór formuł
X
= {
p
,
q
}. Rozważmy wszystkie
wartościowania
v
, w których są prawdziwe wszystkie zdania ze zbioru
X
.
Mamy wartościowanie
v
(
p
) = 1 oraz
v
(
q
) = 1. Dla tego wartościowania jest:
w
(¬
p
∧
q
) = 0. Zatem formuła ¬
p
∧
q
nie wynika ze zbioru
X
= {
p
,
q
} ({
p
,
q
}
׀
≠ ¬
p
∧
q
).
Zachodzą następujące twierdzenia:
Twierdzenie 1
Formuła α jest tautologią wtedy i tylko wtedy, gdy wynika semantycznie ze zbioru
pustego. Symbolicznie ∅
׀
= α lub krócej
׀
= α (bez wypisywania zbioru przed
symbolem wynikania).
Twierdzenie 2
Formuła α wynika semantycznie ze skończonego zbioru formuł
X
= {α
1
, α
2
, ..., α
n
} (
X
׀
= α) wtedy i tylko wtedy, gdy implikacja (α
1
∧ α
2
∧ ... ∧ α
n
) ⇒ α
jest tautologią.
3
Dowód
Załóżmy, że formuła α wynika semantycznie ze skończonego zbioru formuł
X
= {α
1
, α
2
, ..., α
n
}. Wtedy dla dowolnego wartościowania, dla którego formuły
α
1
, α
2
, ..., α
n
przyjmują wartość 1, również formuła α przyjmuje wartość 1.
Rozważmy implikację (α
1
∧ α
2
∧ ... ∧ α
n
) ⇒ α. Wszystkie wartościowania możemy
podzielić na dwie grupy: takie, dla których wartość koniunkcji α
1
∧ α
2
∧ ... ∧ α
n
wynosi 0 oraz takie, dla których wartość tej koniunkcji jest równa 1. W pierwszym
przypadku mamy fałszywy poprzednik rozpatrywanej implikacji, jest ona
zatem prawdziwa. W drugim przypadku zauważmy, że jeżeli wartość koniunkcji
α
1
∧ α
2
∧ ... ∧ α
n
jest równa 1, to każda z formuł α
1
, α
2
, ..., α
n
musi również
przyjmować wartość 1. Możemy wtedy skorzystać z założenia, że również formuła
α (następnik rozpatrywanej implikacji) ma wartość 1, zatem implikacja jest
także prawdziwa. Widzimy, że dla dowolnych wartościowań wartość implikacji
(α
1
∧ α
2
∧ ... ∧ α
n
)
⇒ α jest równa 1. Zatem jest ona tautologią.
Załóżmy teraz, że implikacja (α
1
∧ α
2
∧ ... ∧ α
n
) ⇒ α jest tautologią. Rozważmy
wszystkie wartościowania, dla których formuły ze zbioru
X
= {α
1
, α
2
, ..., α
n
} mają
wartość 1. Oczywiście, dla tych wartościowań formuła α
nie może mieć wartości
0, gdyż byłoby to sprzeczne z tautologicznością implikacji (α
1
∧ α
2
∧ ... ∧ α
n
) ⇒ α.
Zatem formuła α musi mieć wartość 1. Oznacza to oczywiście, że formuła α wynika
semantycznie ze skończonego zbioru formuł
X
= {α
1
, α
2
, ..., α
n
} (
X
׀
= α).
4
2. Reguły inferencyjne
i pojęcie dowodu formalnego
W dotychczasowych rozważaniach przedstawiliśmy tzw. semantyczne ujęcie
rachunku zdań. Oznacza to, że odwoływaliśmy się do pojęcia wartości logicznych,
wartościowania zmiennych i wartości formuł dla danych wartościowań zmiennych.
Przedstawimy teraz tak zwane syntaktyczne ujęcie omawianego rachunku
logicznego. W ujęciu tym nie odwołujemy się do pojęć semantycznych (wartości
logicznych itp.), ale wykonujemy wnioskowanie, wyprowadzając (dedukując) jedne
formuły z innych.
Odpowiednikiem omawianego wyżej pojęcia wynikania semantycznego jest tutaj
pojęcie wynikania syntaktycznego związane ściśle z pojęciami reguł inferencyjnych
oraz dowodu formalnego.
Reguły inferencyjne
to schematy pozwalające wyprowadzać (dedukować) formuły
z innych formuł. Schematy te przedstawiać będziemy w następującej postaci:
, gdzie formuły α
1
, α
2
, ..., α
n
będziemy nazywać
przesłankami
, zaś
formułę β
—
wnioskiem
. Ogólnie reguła o schemacie:
pozwala z for-
muł (przesłanek) α
1
, α
2
, ..., α
n
wyprowadzić (wydedukować) formułę β (wniosek).
Dla uproszczenia zapisu będziemy czasem stosować następującą notację
dla symetrycznych par reguł postaci: oraz .
Przykład 4
Jako przykład przedstawimy reguły
E
liminacji
K
oniunkcji (
EK
) o schematach:
oraz . Reguły te pozwalają z dowolnej koniunkcji α ∧ β (zauważmy, że α
oraz β mogą być dowolnymi formułami) wyprowadzać czynniki tej koniunkcji.
I tak — jeżeli rozważymy formułę (¬
r
∨
p
) ∧ ¬(¬
p
∨
q
⇒
s
) — to na mocy reguł
EK
możemy z tej formuły wyprowadzić oba jej czynniki: ¬
r
∨
p
oraz ¬(¬
p
∨
q
⇒
s
).
Oczywiście, dane reguły nie zawsze możemy stosować do dowolnych formuł.
Powyższych reguł
EK
nie możemy zastosować na przykład do formuły
¬(¬
p
∨
q
⇒
s
), gdyż ta nie jest koniunkcją.
Przykład 5
Reguły
E
liminacji
A
lternatywy (
EA
) mają następujące schematy:
,
.
5
[ Pobierz całość w formacie PDF ]