Wykład 4

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

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

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

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



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

Semantyka zdań

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

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

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

Przykłady

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

prawo symplifikacji

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

prawo

wyłączonego

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

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 

Jeśli w() = 1, to

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

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

Tablice

logiczne

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

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

Obserwacja

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

,..., p

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

Reguły wnioskowania

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









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

,..., 

, przyporządkowują schemat , w taki

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

,..., 

,  , 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, w(

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

)=1,

to w()=1.

 jest

logiczną konsekwencją







7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

Przykłady reguł

, 

 



































Czy te reguły są
poprawne?

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

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

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

Sprowadzanie do

sprzeczności

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

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

=2, to x jest liczbą

niewymierną. Przypuśćmy przeciwnie, że

(1) x

=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, czyli n

= 2m

. Wynika stąd, że n

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

= 4k

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

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

= 4k

. Stąd 2k

, 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

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  

,..., 

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

Formuła (

... 

)  jest tautologią, wtedy i tylko

wtedy, gdy



, 

, ..., 



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

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

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

Pojęcie dowodu

Ciąg formuł 

,..., 

nazywamy

formalnym dowodem formuły  wtedy i

tylko wtedy, gdy każda z formuł 

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ż  

w tym

ciągu.

Np. tautologie

(1,5,6,7)

Np.: reguła

modus ponens

7 listopada 2001

Matematyka Dyskretna, G.Mir
kowska, PJWSTK

Przykład dowodu

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.

Document Outline