Zdania, język KRZ
Przedmiotem rachunku zdań są tzw. „zdania
kategoryczne”, można powiedzieć, że są to „zdania” w
języku naturalnym, którym można (obiektywnie)
przypisać wartość prawdy lub fałszu.
UWAGA: Zdaniami (w sensie rachunku zdań) nie będą zatem
wyrażane w języku naturalnym sądy, przypuszczenia
lub przekonania.
Przykłady zdań: Dzisiaj jest środa; Tydzień ma siedem dni;
Pada deszcz;
Każda wielokrotność liczby trzy dzieli się
przez cztery
To nie są zdania: Która godzina ? Sądzę, że ten wykład jest
interesujący
Albo Pan wyjdzie albo ja !
Język KRZ - syntaktyka
J=(S,,,, F, T) S- zbiór formuł,
V – zbiór zmiennych
zdaniowych (zdań)
VS
Syntaktyka
S - najmniejszy w sensie inkluzji zbiór spełniający
następujące warunki:
i) pV pS
ii) S S
iii) , S , , S
UWAGA: {,,} to są tzw. funktory zdaniotwórcze
{sądzę, myślę, uważam,..} to też funktory zdaniotwórcze, ale….
Język KRZ - semantyka
Semantyka
Semantyką KRZ jest dwuwartościowa algebra Boole`a
BA={ {0,1},, , , 0, 1}
v ( v:V{0,1} h
v
:S{0,1})
jeśli pV to h
v
(p)=v(p)
h
v
(F)=0
h
v
(T)=1
Jeśli p jest zmienną zdaniową (formułą atomową), to v(p) jest
interpretacją formuły p
(wartością logiczną formuły p w interpretacji v).
Ogólnie h
v
() jest wartością logiczną formuły w interpretacji v.
Język KRZ – semantyka
cd.
Dla formuł wartość logiczną można wyznaczyć na podstawie
poniższych własności:
h
v
()=h
v
()h
v
()
h
v
()=h
v
()h
v
()
h
v
()=h
v
()
UWAGA: Funktory zdaniotwórcze „wtórne” {, }
pq p q pq (pq)(qp)
Tablice logiczne
funktorów
p
p
0 1
1 0
Negacja
0 1
0 0 0
1 0 1
Koniunkcj
a
0 1
0 0 1
1 1 1
Alternaty
wa
0 1
0 1 1
1 0 1
Implikacja
0 1
0 1 0
1 0 1
Równoważnoś
ć
Ekstensjonalność
funktorów
Funktory ,, mają tę własność, że wartość logiczna
formuł utworzonych za ich pomocą zależy jedynie od
wartości logicznej zdań, z których formuły te są
zbudowane (wartość logiczna nie zależy od sensu
zdań)
Przykłady
Warszawa jest stolicą Polski lub 2+2=4; Jeśli Ola jest kobietą to Marek jest łysy
p(pq)
Przykłady
Policzmy wartość formuły () jeśli wiemy już, że h
v
()=1, h
v
()=0
h
v
(())=h
v
()h
v
()=h
v
()(h
v
()h
v
()) =
=1(10)=0(10)=00=1
Własności h
v
Z tablic funktorów
Implikacja i
równoważność
semantyczna
Jaka jest różnica pomiędzy wyrażeniami
() a
a
Wyrażenie
jest formułą KRZ, która może być ale nie musi być tautologią
Wyrażenie jest stwierdzeniem o formułach
,
mówiącym, że są one logicznie
równoważne, tzn, że formuła jest tautologią
Wyrażenie oznacza, że implikuje logicznie , tzn. wtedy i tylko
wtedy, gdy jest tautologią.
UWAGA:
oznacza, że nie może zaistnieć sytuacja h
v
()=1 i h
v
()=0
Tautologia
Definicja
Formułę nazywamy tautologią (twierdzeniem) wttw
v h
v
()=1 (dla każdego wartościowania wartość
logiczna formuły
równa jest 1)
Definicje
Formuła jest spełniona przy interpretacji v wttw
h
v
()=1
(v spełnia ; v jest modelem dla )
X |= ( wynika logicznie ze zbioru formuł X) wttw
v ( h
v
(X){1} h
v
()=1 )
|= X (zbiór formuł X jest spełniony) wttw
h
v
(X){1} dla pewnego v
Aksjomaty i teoria
Definicja
Niech X, będzie zbiorem formuł, zbiór
T(X)={: X |= } nazywamy teorią zbioru formuł X, a
formuły należące do zbioru X nazywamy aksjomatami
Metoda zero-jedynkowa
Przykład: Czy prawo de Morgana jest tautologią
(pq) (pq)
p q p q (p q) p q p q formuła
0 0 0 1 1 1 1
1
0 1 0 1 1 0 1 1
1 0 0 1 0 1 1
1
1 1 1 0 0 0 0
1
Metoda zero-jedynkowa polega na rozważeniu wszystkich
możliwych przypadków wartości zdań składowych formuły i
policzeniu w każdym przypadku wartości formuły.
UWAGA: Metoda kosztowna obliczeniowo ze względu na liczbę
formuł składowych (w szczególności zdań)
Postacie normalne
formuł
Atomem (formułą atomową) nazywać będziemy zmienną
zdaniową (zdanie)
Atom nazywamy również literałem pozytywnym
Negację atomu nazywamy literałem negatywnym
Literały i nazywamy komplementarnymi
Definicja
Formuła jest w koniunkcyjnej postaci normalnej – CNF wtw
jest ona postaci:
=
1
2
..
n
gdzie każde
i
jest alternatywą literałów
Koniunkcją alternatyw (składniami każdej alternatywy muszą być
literały)
Definicja
Formuła jest w alternatywnej postaci normalnej – DNF wtw
jest ona postaci:
==
1
2
..
n
gdzie każde
i
jest koniunkcją literałów
Alternatywą koniunkcji (składniami każdej koniunkcji muszą być
literały)
Postacie normalne cd.
Przykłady
CNF (pprq) (pwr) (pq)
DNF (pprq) (pwr) (pq)
W celu sprowadzenia dowolnej formuły do postaci CNF lub DNF należy:
1. Wyeliminować spójniki ,
()()
2. Wprowadzić znak negacji bezpośrednio przed symbole atomowe:
()
()
()
3. Wprowadzić znak koniunkcji (CNF) lub alternatywy (DNF) na zewnątrz
nawiasów (na najwyższy poziom formuły złożonej)
prawo rozdzielności koniunkcji względem alternatywy
prawo rozdzielności alternatywy względem koniunkcji
Formuły
równoważne
ADT – dla KRZ
Jeśli formuła jest w postaci CNF, to jest tautologią wttw każda z alternatyw zawiera
parę literałów komplementarnych
Jeśli formuła jest w postaci DNF, to jest kontrtautologią wttw każda z koniunkcji
zawiera parę literałów komplementarnych
Twierdzenie
Dla dowolnej formuły istnieją formuły ` i ” równoważne , będące
(odpowiednio) w postaciach CNF i DNF
UWAGA: Powyższe twierdzenie dostarcza procedury rozstrzygania dla KRZ
Spełnialność,
prawdziwość,
niespełnialność,
nieprawdziwość
Przykłady tautologii
(praw) KRZ
Przykłady tautologii
i) prawa przemienności (, )
ii) prawa łączności
iii) prawa rozdzielności
iv) (pq) (pq) (pq) (pq) prawa De Morgana
v) dla iloczynu analogicznie
vi) pq (q p) prawo kontrapozycji
vii) pq [(p q) c] reductio ad absurdum (c zdanie sprzeczne)
viii) pp p pp p prawa idempotentności
ix) [(pq)r ] [p(qr)] prawo eksportacji
x) (p p) prawo wyłączonego środka
System formalny
Definicja
Dwójkę <R, X> w której R jest zbiorem formuł wnioskowania,
X zbiorem formuł (aksjomatów) nazywamy
systemem formalnym.
UWAGA: Jeśli rR jest regułą wnioskowania to r2
S
S.
Wnioskowanie:
Proces polegający na uznaniu pewnych zdań zwanych
wnioskami na podstawie innych zdań zwanych
przesłankami.
UWAGA: Zamiast system formalny można powiedzieć też
system dowodzenia
Reguły wnioskowania
Reguła wnioskowania – zapis
Znaczenie – jeśli przesłanki są prawdziwe, to
konkluzja też jest prawdziwa
n
Reguła jest poprawną regułą wnioskowania, jeśli
X={
1
,
2
,..,
n
} v ( h
v
(X){1} h
v
()=1 )
UWAGA: Mówimy wtedy, że jest konsekwencją logiczną
1
,..,
n
1
,..,
n
|-
Reguły wnioskowania
UWAGA: KRZ podaje się dwa systemy dowodzenia Hilbertowski i
Gentzenowski. Systemy te mają różną liczbę aksjomatów
i różne reguły wnioskowania
Jeżeli formuła zbudowana ze zmiennych zdaniowych p
1
,..., p
n
jest tautologią,
to wstawiając na miejsce zmiennych dowolne zdania otrzymamy zdanie prawdziwe.
Reguła podstawiania
Jeśli na miejsce zmiennych wstawimy dowolne formuły (schematy), to
otrzymana formuła dalej będzie tautologią.
,
Modus ponens
Sylogizm warunkowy
(p
1
, .. , p
n
)
(p
1
/
1
, .., p
n
/
n
)
Przykłady systemów
formalnych
system hilbertowski H
System składa się z trzech aksjomatów i jednej reguły dowodzenia (modus ponens)
W celu ułatwienia wnioskowania wprowadza się wiele reguł pochodnych
(które oczywiście najpierw się udowadnia) jedną z nich jest reguła dedukcji
System hilbertowski H
cd.
Inne reguły to reguła kontrapozycji, przechodniości, podwójnego zaprzeczenia itd.
(ćwiczenia)
Dzięki nowym regułom wnioskowania dowody stają się prostsze
Dla wyrażenia U |- A elementy zbioru U
nazywamy założeniami w dowodzie formuły A
(dotyczy to wszystkich formuł systemu H)
Dowody formalne
Definicja (dotyczy KRZ)
Wnioskowaniem (dowodem) formuły ze zbioru formuł X nazywamy skończony
ciąg formuł
1
,
2
,..,
n
= taki, że formuły
1
,
2
,..,
n-1
są aksjomatami lub
elementami zbioru X lub są wnioskami wyprowadzonymi z „wcześniejszych”
formuł za pomocą dopuszczalnych reguł wnioskowania
Definicja (Konsekwencja logiczna)
Cn(R, X) – zbiór wszystkich formuł posiadających dowód na gruncie
systemu <R, X>
X |- Cn({r
o
,r
*
} , AksX)
|- Cn({r
o
}, Aks) tautologia (system Hilbertowski)
UWAGA: Dowody przeprowadzane zgodnie z przedstawionymi
zasadami nazywa się dowodami dedukcyjnymi (a samo
wnioskowanie – wnioskowaniem dedukcyjnym)
Zbiór formuł X jest niesprzeczny, gdy nie istnieje taka formuła ,
że X |- i X |-
Twierdzenia
Twierdzenie
KRZ jest rozstrzygalny tzn. można obliczyć wartość logiczną
każdej formuły
Twierdzenie (Posta)
Niech X S jest dowolnym zbiorem formuł oraz S, wówczas
X |= X |- tzn. Cn(r
o
, AksX)
=> tw. o pełności
<= tw. o poprawności wnioskowania
Twierdzenie (Twierdzenia)
Systemy G i H są systemami poprawnymi i pełnymi
Metody badania
poprawności formuł
Metoda jest
-
pełna (jeśli dla każdej badanej formuły, która jest tautologią metoda
daje odpowiedź TAK)
-
implementowalna (jeśli dla każdej badanej formuły, która jest
tautologią, metoda da odpowiedź TAK, a dla
formuły nie będącej tautologią metoda da
odpowiedź NIE lub algorytm się zapętli)
Metody dowodzenia
Dowody matematyczne opierają się na podstawach logicznych
Najbardziej naturalna metoda dowodzenia – metoda wprost
(z założeń wyprowadzamy wniosek)
Użyteczne (nawet bardzo) okazują się jednak także metody dowodzenia
nie wprost.
Dowody przeprowadzane według następującej reguły wnioskowania
nazywane są dowodami apagogicznymi (d. przez sprowadzenie
do niedorzeczności)
( )
UWAGA: Za dowody apagogiczne uznawane są m.in. dowody
przeprowadzane wg następujących reguł wnioskowania
i) reductio ad absurdum
ii) reguła Claviusa
Przykład dowodu
apagogicznego
Chcemy udowodnić, że
formuła
[()][()]
jest prawem rachunku zdań
(hip.) Przypuśćmy, że tak nie jest. Co to
znaczy ?
To znaczy, że istnieje takie
h
v
, że
h
v
([()][()])=0
0
[()][()]
1 0
[()][()]
1 0
()
1 0
- 1 - 1 -
0
ale przy takich wartościach , ,
0
()
tymczasem założenie
mówi, że
1
()
Sprzeczność
Dowody nie wprost
Inny rodzaj dowodu nie wprost to dowód przez kontrapozycję.
Udowodnienie twierdzenia
(
1
2
…
n
)
jest równoważne udowodnieniu twierdzenia
(1 2 … n)
UWAGA: Dowody nie wprost są tzw. dowodami niekonstruktywnymi,
które stwierdzają istnienie pewnych obiektów ale ich nie wskazują, ani
nie podają procedury ich znalezienia.