7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

1

Wykład 6

Wykład 6

Rachunek Zdań

Rachunek Zdań

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

2

Zdania

Zdania

Przedmiotem badań rachunku zdań
są "zdania”. Niezbyt precyzyjnie
można powiedzieć, że są to zdania w
języku naturalnym, którym można
przypisać wartość prawdy lub fałszu.

Przykłady

(1) Dziś jest środa.
(2) W naszej strefie klimatycznej
są cztery pory roku.
(3) Każdy miesiąc ma tyle samo
dni.

Jaka dziś pogoda?

Mam ochotę
wyjechać do
ciepłych krajów.

Sądzę, że będzie
ładna pogoda.

Oznaczenie

w(a)=1, tzn a jest zdaniem

prawdziwym

w(a)=0, tzn. a jest zdaniem fałszywym

To nie są

zdania

rachunku

zdań

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

3

Zdania złożone

Zdania złożone

Definicja
Niech V będzie zbiorem zdań elementarnych (nazywać
je

będziemy

zmiennymi

zdaniowymi).

Zbiór

poprawnych wyrażeń (formuł) Rachunku Zdań jest to
najmniejszy (w sensie inkluzji) zbiór wyrażeń
zawierający V i taki, że jeśli p i q są zdaniami, to
wyrażenia  p, (p  q), (p  q), (p  q), (p  q) są

zdaniami.

Przykłady

( p  (p  q)) ( (p  q)  (p  q))   p
(2+2=5  Warszawa jest stolicą Polski)

Symbole ,  ,  ,  ,  nazywamy funktorami

zdaniotwórczymi lub spójnikami logicznymi.

( (p  q)   q ) -

nie jest formułą
poprawną

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

4

Tablice logiczne

Tablice logiczne



0 1

0 0 0

1 0 1



0 1

0 0 1

1 1 1



0 1

0 1 1

1 0 1



0 1

0 1 0

1 0 1

p



p

0 1

1 0

 ,  ,  ,  funktory 2

argumentowe

 funktor 1 argumentowy

Zbiór {0,1} z operacjami  , 

,  ,  nazywamy

dwuelementową algebrą
Boole’a .

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

5

Semantyka zdań

Semantyka zdań

złożonych

złożonych

Mając wartości zdań prostych i znając tablice logiczne
dla funktorów można określić wartość logiczną zdań
złożonych.

w(a o b)= w(a) o w(b), w( a)=  w(a),
gdzie o oznacza dowolny dwuargumentowy funktor
oraz a,b są dowolnymi zdaniami

Funktory  ,  ,  ,  , mają wspólną własność : wartość

logiczna zdań utworzonych przy ich pomocy zależy
jedynie od wartości logicznej zdań, z których powstało
wyrażenie a nie od sensu tych zdań. Taką własność
funktorów nazywamy ekstensjonalnością.

Policzmy wartość formuły  wiedząc, że

w()=1 w()=0. w( )=w()w = 0

w 0 ww0 1 00 0 = 1

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

6

Przykład

Przykład

Wartość zdania : ’wszyscy na tej sali żywo interesują
się logiką lub na tej sali wszyscy śpią’ zależy tylko od
tego jaka jest wartość zdań: ‘wszyscy na tej sali żywo
interesują się logiką ‘ i ’na tej sali wszyscy śpią’.
Wartość logiczna zdania ‘Myślę, że wszyscy na sali
żywo interesują się logiką lub na tej sali wszyscy
śpią’ zależy nie od zdań składowych ale od tego co ja o
tym myślę.
"Myślę, że”, "Sądze, że " można uznać za operatory
zdaniotwórczye ale nie mają one własności
ekstensjonalności. Rachunek zdań
nie zajmuje się takimi funktorami.

Ile istnieje funktorów 1-
argumentowych ekstensjonalnych? A
ile 2 argumentowych?

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

7

Tautologie

Tautologie

Definicja Formułę rachunku zdań, której wartością jest
prawda, niezależnie od wartości zmiennych zdaniowych
w niej występujących, nazywamy tautologią lub prawem
rachunku zdań.
Matryca logiczna (tablica wartości logicznych) tautologii
ma kolumnę wartości wypełnioną tylko jedynkami.

Definicja Formuła, której
wartością jest fałsz, niezależnie
od wartości zmiennych
zdaniowych w niej
występujących, nazywamy
sprzeczną.

Matryca logiczna formuły
sprzecznej ma kolumnę
wartości wypełnioną tylko
zerami.

Formuła  rachunku

zdań jest tautologią
wtedy i tylko wtedy,
gdy  jest zdaniem

sprzecznym.

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

8

Przykłady

Przykłady

 

1

prawo symplifikacji

 

2

prawo

wyłączonego

środka
 

3

prawo

wyłączonej

sprzeczności
(4)

prawo

podwójnego

przeczenia
(5)prawo Dunsa Scotusa

(6) prawo Claviusa

(7)  prawo

Fregego

Ad (3) Jeśli w() = 0, to

w(www0

w01 

0

1

Jeśli w() = 1, to

w(www1

w1 0

Tablice

logiczne

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

9

Przykłady

Przykłady

Sprawdźmy, czy formuła ()  ( )

jest prawem (prawo de Morgana)Rachunku Zdań.

()     formuła

0 0 0 1 1 1 1 1
0 1 1 0 1 0 0 1

1 0 1 0 0 1 0 1

1 1 1 0 0 0 0 1

Tak, to jest

prawo RZ

Metoda tu zaprezentowana nosi nazwę metody zero-
jedynkowej. Polega ona na rozważeniu wszystkich
możliwych przypadków wartości zdań składowych i
policzeniu w każdym przypadku wartości formuły.

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

10

Obserwacja

Obserwacja

Jeżeli formuła zależna od zmiennych zdaniowych
p

1

,..., p

n

jest tautologią, to wstawiając na miejsce

zmiennych dowolne zdania otrzymamy zdanie
prawdziwe. Co więcej, jeśli na miejsce zmiennych
wstawimy dowolne schematy zdań (dowolne
formuły), to otrzymany schemat będzie również
tautologią.
Przykład
Formuła ()  (   ) jest tautologią.

Zatem następujące zdania są prawdziwe:
(1) ’x jest elementem A’ implikuje, że ‘x jest
elementem B’ wtedy i tylko wtedy, gdy ‘x nie jest
elementem B’ implikuje, że ‘x nie jest elementem A’.
(2) (())  (    () )

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

11

Reguły wnioskowania

Reguły wnioskowania

Reguły dowodzenia (reguły wnioskowania) są to
przekształcenia postaci



1



2



n



które pewnemu skończonemu zbiorowi schematów
(formuł) 

1

,..., 

n

, przyporządkowują schemat , w taki

sposób, że przy dowolnie wybranych wartościach
zmiennych występujących w schematach 

1

,..., 

n

,  , jeśli

przesłanki są zdaniami prawdziwymi, to wniosek też jest
zdaniem prawdziwym.

przesłanki

wniosek

Czyli musi być spełniony warunek:
Jeśli tylko w(

1

1, w(

2

)=1w(

n

)=1,

to w()=1.

 jest

logiczną konsekwencją



1



2



n

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

12

Przykłady reguł

Przykłady reguł

, 

 



































Czy te reguły są
poprawne?

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

13

Zastosowanie reguł

Zastosowanie reguł

Przykład
Chcemy udowodnić, że formuła (())(()) (tzw.

Prawo eksportacji) jest prawem rachunku zdań. Przypuśćmy,
że tak nie jest, tzn. przypuśćmy, że są takie wartości zdań
składowych, że
w((() )(( ))) = 0. Zatem musiałoby być

(1) w((() ))=1 oraz (2) w(( ))=0.

Znów korzystamy z własności implikacji i z (2) mamy

(3) w()=1 oraz (4) w( )= 0.

Z (4) wynika że w()=1 oraz w()= 0.

Stąd na mocy (3) mamy w()=1 , a zatem w(())=0

(wbrew (1)!).
Korzystając z powyższej reguły wnioskujemy, że
w((())(()))=1.









To jest poprawna reguła
dowodzenia

Dowody tego typu

nazywamy

dowodami

apagogicznymi

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

14

Dowody nie wprost

Dowody nie wprost

Przykład Jeżeli funkcja g : Y X jest funkcją

odwrotną do funkcji f: X Y, to g jest

różnowartościowa.

Gdyby g nie była funkcją różnowartościową zatem musiałyby
istnieć w Y elementy y1y2 takie, że g(y1)=g(y2). Wówczas

mamy

(*) f (g(y1))=f(g(y2)).

Ponieważ g jest funkcją odwrotną do f, zatem Y=f(X) czyli
y1, y2 f(X) Stąd istnieją takie elementy x1,x2X, że

f(x1)=y1

oraz

f(x2)=y2.

Wstawiając do równości (*) otrzymujemy

f(g(f(x1)) ) = f(g(f(x2)) ).

Stąd i z definicji funkcji odwrotnej mamy f(x1)=f(x2), a
zatem y1=y2 . Sprzeczność.
Zatem, jeśli tylko y1y2, to g(y1)g(y2). Czyli funkcja g też

jest funkcją różnowatościową c.b.d.o.

Przypominam, że funkcję g: Y
X nazywamy odwrotną do f :

X Y jeśli Y=f(X) i X=g(Y) oraz

g(f(x))=x dla wszystkich x X

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

15

Sprowadzanie do

Sprowadzanie do

sprzeczności

sprzeczności

Przykład Udowodnimy, że 2 jest liczbą

niewymierną. Chcemy pokazać, że jeśli x jest liczbą
rzeczywistą taką, że x

2

=2, to x jest liczbą

niewymierną. Przypuśćmy przeciwnie, że

(1) x

2

=2 oraz

(2) x jest liczbą wymierną.

Na mocy (2) x= n/m dla pewnych liczb całkowitych
n,m i m 0. Możemy założyć, że n i m nie mają

wspólnych dzielników.
Mamy n

2

/m

2

= 2, czyli n

2

= 2m

2

. Wynika stąd, że n

2

jest liczbą parzystą. W konsekwencji n też musi być
liczbą parzystą (bo gdyby n było nieparzyste, np.
n=2k+1, n

2

= 4k

2

+ 4k+1 byłoby też liczbą

nieparzystą). Niech n = 2k . Wtedy mamy n

2

= 4k

2

=

2m

2

. Stąd 2k

2

=m

2

, tzn. m też jest liczbą parzystą.

Sprzeczność z założeniem, że n i m nie mają
wspólnych dzielników. Zatem 2 jest liczbą

niewymierną. c.b.d.o.

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

16

Własności

Własności

Twierdzenie 1
Jeśli wszystkie przesłanki reguły wnioskowania są
tautologiami, to wniosek w tej regule też jest
tautologią.
Twierdzenie 2
Niech 

1

,..., 

n

,  będą formułami rachunku zdań.

Formuła (

1

... 

n

)  jest tautologią, wtedy i tylko

wtedy, gdy



1

, 

2

, ..., 

n



jest poprawną regułą wnioskowania.

Reguły wnioskowania

pozwalają na

wydedukowanie z już istniejących

nowych tautologii

Tautologie są źródłem

nowych

reguł wnioskowania

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

17

Logika a informatyka

Logika a informatyka

while (p  (p  q)) do x := x+1 od
Jaka jest wartość x po wykonaniu tej
pętli?

If a then I1 else

if b then I2 else I3 fi

fi

Załóżmy, że (a  b) jest prawdą ilekroć

wykonujemy powyższą instrukcję
warunkową.

Czy instrukcja I3 będzie kiedykolwiek
wykonana?

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

18

Pojęcie dowodu

Pojęcie dowodu

Ciąg formuł 

1

,..., 

n

nazywamy

formalnym dowodem formuły  wtedy i

tylko wtedy, gdy każda z formuł 

i

jest

albo

aksjomatem

albo

została

już

wcześniej udowodniona albo jest
wnioskiem w pewnej regule dowodzenia,
w której przesłankami są formuły
występujące wcześniej niż 

i

w tym

ciągu.

Np. tautologie

(1,5,6,7)

Np.: reguła

modus ponens

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

19

Przykład dowodu

Przykład dowodu

formalnego

formalnego

Następujący ciąg formuł jest dowodem formalnym
formuły (AA).

(1) (A ((A  A) A))

(2) (A (A A))

(3) ((A ((A  A) A))  ((A (A  A)) (AA)))

(4) ((A (A  A)) (AA))

(5) (AA)

tautologia postaci (a
(ba))

(prawo

symplifikacji)

Prawo
symplifikacji

prawo Fregego ((a(bc)) ((ab) (ac)))

z (1) i (3) i reguły
m.p.

z (4) i (2) i reguły
m.p.

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

20

Implikacja logiczna

Implikacja logiczna

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

21

Równoważność logiczna

Równoważność logiczna