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ń)
VS

Syntaktyka
S - najmniejszy w sensie inkluzji zbiór spełniający
następujące warunki:
i) pV pS

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 pV 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” {, }

pq  p  q pq  (pq)(qp)

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(pq)

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(10)=0(10)=00=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ą
(pq)  (pq)

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 (pprq)  (pwr)  (pq)

DNF (pprq)  (pwr)  (pq)

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) (pq)  (pq) (pq)  (pq) prawa De Morgana

v) dla iloczynu analogicznie
vi) pq  (q p) prawo kontrapozycji

vii) pq  [(p  q) c] reductio ad absurdum (c zdanie sprzeczne)

viii) pp  p pp  p prawa idempotentności

ix) [(pq)r ]  [p(qr)] 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 rR jest regułą wnioskowania to r2

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

*

} , AksX)

|-   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

, AksX)

=> 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.