Ws ze chnica Popołudniowa

Jak wnioskują ma szyny

prof. dr hab. Andrzej Szałas

prof. dr hab. Maciej M Sysło

Ze szyt dydaktyczny opracowany w ramach projektu edukacyjne go

— ponadre gionalny program rozwijania kompe tencji

uczniów szkół ponadgimna zjalnych w zakresie technologii
informacyjno-komunikacyjnych (ICT).

Warszawska Wyżs za Szkoła Informa tyki

ul. Lewartowskie go 17, 00 -169 Wars zawa

Projekt graficzny: FRYCZ I WICHA

Wars zawa 2009
Copyright © Wars za wska Wyżs za Szkoła Informatyki 2009
Publikacja nie jes t prze znaczona do sprze da ży.

Instytut Informatyki Uniwersytetu Warszawskiego

[e-mail]

< 4 >

Informa tyka +

Wykład je st poś więcony wprowadzeniu do logiki z perspektywy jej za s tos owa ń w informa tyce i s ztucznej in-
teligencji. Porus za ne treś ci obejmują na s tępujące zagadnienia:

■

wprowadzenie do logiki jako nauki o modelowaniu ś wia ta rzeczywis tego i wnioskowaniu o nim;

■

klas yczny rachunek zdań (składnia , semantyka s pójników logicznych); odnie sienie do zbiorów i użycie
diagramów Venna , jako metody wnioskowania;

■

wyszukiwanie a wnioskowanie na przykładzie wys zukiwarki internetowej Google;

■

automatyczne wnioskowanie (informacja o me todzie rezolucji dla rachunku zdań).

Ws zystkie zagadnienia s ą ilus trowane przykładami, w tym związanymi z robotyką i s ztuczna inteligencją.

Od słuchaczy nie wymaga się żadnej ws tępnej wiedzy z zakre su logiki i matematyki.

1. Wprowadzenie ............................................................................................................................................. 5

2 . Wys zukiwanie i wnioskowanie ..................................................................................................................... 6

3. Kla s yczny rachunek zadań ........................................................................................................................... 7

4 . Diagramy Venna ........................................................................................................................................... 9

5. Automatyczne wnioskowanie ......................................................................................................................11

6. I co dalej? ............................................................................................................................................... 15

Literatura

............................................................................................................................................... 15

Załącznik

............................................................................................................................................... 16

> Jak wnioskują mas zyny

< 5 >

Działalność człowieka – począwszy od tej codziennej po najbardziej zaawansowane badania i konstrukcje – zaczy-
na się od rozpoznawania odpowiedniego zestawu zjawisk, a następnie ich modelowania po to by uzyskany i spraw-
dzony model później wykorzys tywać. Gdy porus zamy się po własnym mieszkaniu, posługujemy się jego modelem
stworzonym w czasie rozpoznawania tegoż mieszkania. Model ten mamy zwykle w głowie, niemniej jednak w po-
równaniu z rzeczywis toś cią jest on bardzo upros zczony. Nie bierze pod uwagę przepływu czą stek powietrza , za-
chowania elektronów w poszczególnych cząs tkach wys tępujących w s tropie i ścianach, nie dbamy o skomplikowa-
ne proces y przepływu wody w rurach wodociągowych itd. Prostota modelu pozwala jednak na skuteczne wniosko-
wanie, poruszanie się po pomies zczeniach i działanie. W informatyce też dba się o to, by dla danego zjawiska czy
problemu obliczeniowego wybrać możliwie jak najprostszy, ale zarazem skuteczny model.
Wyobraźmy sobie zadanie polegające na opracowaniu bardzo prostego robota przemysłowego, który „obserwuje”
ta śmę produkcyjną i którego zadaniem jest przestawianie z niej przedmiotów zielonych na taśmę znajdującą się po
lewej stronie, a czerwonych – na taśmę znajdującą się po prawej s tronie. Tworzymy więc model – trzy taśmy pro-
dukcyjne. Nad środkową ta śmą czuwa robot wypos ażony w:

■

czujniki rozpoznające kolor zielony i czerwony,

■

chwytaki służące do chwytania przedmiotów i przes tawia nia ich na le wą lub pra wą ta śmę.

Mając ten model możemy tera z opisać działanie robota dwoma prostymi regułami:

■

jeśli obserwowany obiekt jes t zielony, to przenieś go na taś mę z lewej strony,

■

jeśli obserwowany obiekt jes t czerwony, to przenieś go na ta śmę z prawej s trony.

Powyżs ze reguły nie gwara ntują przenie sienia ws zys tkich przedmiotów zielonych na le wą s tronę, a czerwo-
nych na prawą, bo zależy to od prędkości ta śm, akcji rozpoznawania koloru i akcji przenoszenia przedmio-
tów. Zaczynamy jednak już mie ć do czynienia z logiką . Przytoczone dwie reguły odzwierciedlają bardzo pro-
ste wnios kowanie. W opis anym przypadku niekoniecznie skuteczne, ale za to skute czne i wys tarczające w in-
nym modelu. Mianowicie, je śli założymy, że robot nie myli się w rozpoznawaniu kolorów i nie zawodnie prze-
nosi obiekty ora z że środkowa taś ma za trzymuje się na cza s rozpoznawania koloru i przenos zenia przedmio-
tu przez robota , a na doda tek zatrzymuje ka żdy przedmiot w za się gu czujników i chwytaków robota – to takie
pros te wnios kowane będzie s kuteczne i można je forma lnie wyka zać. Daje to wiedzę o warunkach, ja kie po-
winno spełniać środowisko robota, by ten mógł działa ć skute cznie wykorzys tując s woje możliwoś ci.

Możemy więc zauwa żyć, że skutecznoś ć wnioskowań zależy od przyjętego modelu rzeczywis toś ci.

I znów zauwa żmy, że omawiane modele biorą pod uwagę jedynie to, co niezbędne dla skutecznego rozwią za-
nia problemu, zaniedbując to, co z punktu widzenia tej skutecznoś ci nie jes t wymagane.

Aby modelować rzeczywis toś ć zwykle zaczynamy od identyfikacji przedmiotów (obiektów), rodzajów

obiektów (pojęć), ich cech (atrybutów) i zwią zków między nimi. Tak pos tępuje się np. w projektowaniu rela-
cyjnych ba z danych (jak Access , Oracle, MySQL,...). Ka żda ba za danych je st modelem pewnej rzeczywistoś ci,
a wyniki zapytań kierowanych do ba z danych – uzyskanymi informacjami, pra wdziwymi w tej rzeczywis toś ci.
Podobnie postępuje s ię w wielu innych obs za rach informatyki, w tym choćby w projektowaniu obiektowym
niesłychanie wa żnym we współczesnych s ys temach.

Załóżmy tera z, że zidentyfikowaliś my dwa rodzaje owoców: cytryny i figi. W zale żnoś ci od potrzeb wy-

nikających z rozwiązywa nego zadania możemy określać ich atrybuty, jak rodzaj, kolor, smak itp. Pows taje
w ten spos ób pe wna ba za danych, zilustrowana w tabeli 1 (oczywiś cie różne rodzaje obiektów mogą mieć
różne atrybuty, co prowadzi do wielu tabel – na przykład, gdyby wś ród obiektów wys tępowali ludzie , atrybut
smak mógłby mieć w ich przypadku mało sensu).

Tabela 1.
Przykładowe obiekty i ich atrybuty

a trybut y

obie kt

rodzaj

sma k

kolor

o1

cytryna

kwaśny

żółty

o2

figa

słodki

brą zowy

o3

cytryna

kwaśny

zielony

< 6 >

Informa tyka +

Tabelę 1 możemy przeks zta łcić do tabeli 2, w której atrybutami s tają się wartości rodzaju, smaku, koloru, za ś
wartościami 0 i 1, gdzie 0 oznacza fałsz, za ś 1 – prawdę:

Tabela 2.
Obiekty i ich a trybuty jako wartości

a trybut y

obiekt

cytryna

figa

kwaśny

słodki

żółty

brą zowy

zielony

o1

1

0

1

0

1

0

0

02

0

1

0

1

0

1

0

03

1

0

1

0

0

0

1

Zapyta nie cytryna AND żółty wybie rze w wyniku obiekt o1, gdyż tylko on jes t je dnocze śnie cytryną i je s t żół-
ty. Zapytanie cytryna OR żółty wybie rze obiekty o1, o3, b owiem wybieramy bę dące cytryną lub mające ko-
lor żółty. Natomia s t zapytanie ←cytryna wybierze obiekt o2, bowiem s ymbol ‘←‘ oznacza negację (za prze -
cze nie).

Możemy te ż określić zwią zki między zidentyfikowanymi pojęciami, np:

jeśli dany obiekt jes t cytryną, to jes t kwa śny i nie jes t figą
jeśli dany obiekt jes t żółty, to jes t cytryną
jeśli dany obiekt jes t figą, to nie jes t cytryną

Znów mamy do czynienia z pe wnymi wyra żeniami typu „jeś li ..., to ...”, s tos owa nymi we wnios kowaniu o rze -
czywis toś ci złożonej z cytryn i fig. Dodatkowo ta kie zwią zki czę s to mogą s łużyć do upros zczenia ta beli. Na
przykład, mając powyżs ze zależnoś ci można opuś cić kolumnę figa , gdyż jes t ona zdefiniowa na jako ←cytry-
na (dlaczego?), a wię c wys tępujące w niej wartoś ci można obliczyć na pods ta wie wartoś ci z kolumny cytryna .

Badaniem metod wnioskowania zajmuje się logika (od greckiego słowa logos, oznaczającego rozum,

słowo, myśl). Z je dnej s trony analizuje się w niej poprawnoś ć wnios kowań, a z drugiej s trony – dos tarcza me -
tod i algorytmów wnioskowania. Korzenie logiki się ga ją s tarożytnej Grecji, ale też Chin, czy Indii. Odgrywała
is totną rolę w śre dniowieczu, burzliwy jej rozwój datuje się od końca XIX wieku. G. Boole, C.S. Peirce , J. Venn,
potem B. Rus sell czy F. Frege s ą wybitnymi logikami z tego okres u. Pojęcie obliczalnoś ci jes t te ż ś ciśle zwią -
zane z badaniami logicznymi dotyczącymi rozs trzygalnoś ci teorii ma tematycznych, czyli s zukania metod al-
gorytmicznych dla automatycznego znajdowania dowodów twierdzeń tych teorii. Wybitnymi prze ds tawicie -
lami tego kierunku s ą J. Dedekind, G. Peano, D. Hilbert, A. Heyting, E. Zermelo, J. von Neumann, K. Gödel czy
A. Tarski. Pierws ze ma tematyczne modele ma s zyn ma tema tycznych zawdzię czamy kontynuacji prac tych lo-
gików, prowadzonych przez E. Pos ta, A. Churcha (prekursorzy języków funkcyjnych), jak równie ż S.C. Kle ene -
go, A.M. Turinga czy C.E. Shannona (prekurs orzy ję zyków impera tywnych).

Można napisać, że logika jes t we wnioskowaniu ws zechobecna , gdyż fałsz, prawda , wnios kowanie, model,
pojęcie, zwią zek (relacja), reguła , czy spójniki (AND, OR, ←) s ą pods tawowymi konceptami rozwa żanymi w lo-
gice. Zaczęliśmy od ba z da nych i wys zukiwania obiektów ma jących intere sujące nas właś ciwoś ci. Przejdźmy
tera z do od wys zukiwarek internetowych. Internet jes t ogromną ba zą danych. Za s adniczą różnicą w porów-
naniu z tradycyjnymi bazami danych, zorganizowanymi w bardzo uporządkowany sposób, jes t w Interne cie
ogromna różnorodnoś ć za sobów i brak ich jednolitej s truktury.

Dla us talenia uwagi za łóżmy, że interesującymi na s obiektami z Internetu są s trony WWW. Wpisując

w okienko wys zukiwarki Google zes taw słów pytamy o te s trony, na których wys tępują wszys tkie wypisane
słowa kluczowe. Jes t to tzw. wyszukiwanie AND. W ję zyku polskim „and” znaczy „i”. W logice taki spójnik na -
zywamy koniunkcją i częs to w literaturze oznaczamy s ymbolem ∧.

> Jak wnioskują mas zyny

< 7 >

Aby koniunkcja p AND q była prawdziwa, prawdziwe mus zą być oba zdania s kładowe: zdanie p i zdanie

q. Jeśli np. wpiszemy dwa słowa: logika informa tyka , to z punktu widzenia wys zukiwarki Google oznacza to
wpis anie wyra żenia logika AND informatyka, czyli wyszukanie s tron (nas zych obiektów), na których wys tępu-
je słowo logika i słowo informatyka. Tak naprawdę nie zaws ze pojawią s ię oba s łowa , co odbie ga od logiczne-
go rozumienia koniunkcji. Aby mieć „prawdziwą” koniunkcję powinniśmy wpis ać wyra żenie + logika + infor-
matyka (operator + umies zczony przed danym s łowem oznacza , że musi ono wys tą pić na wys zukanej s tronie).

Co jeszcze pojawia się w Google? Twórcy tej wys zukiwarki oferują te ż wys zukiwanie OR. W języku pol-

skim „or” to „lub”, czyli logiczny s pójnik alternatywy, w literaturze częs to oznaczany s ymbolem ∨. Aby alter-
natywa p OR q była prawdziwa , prawdziwe musi być co najmniej jedno ze zdań składowych: zdanie p lub zda-
nie q (lub oba te zdania). Na przykład wpis anie w Google wyra żenia logika OR informatyka spowoduje wyszu-
kanie s tron na których wys tępuje słowo logika lub słowo informatyka lub oba te s łowa. Spójnik OR wiąże sil-
niej niż spójnik AND.

1

Oznacza to, że wyra żenie

lekcja informa tyka OR logika

Google rozumie jako

lekcja AND (informatyka OR logika)

a nie jako (lekcja AND informa tyka) OR logika. Wys zukane zos tanę więc s trony, na których poja wia się słowo
lekcja ora z co najmniej jedno ze słów informa tyka lub logika.

I mamy je szcze operator negacji ←, który umieszczony przed słowem oznacza , że nie może ono wy-

s tą pić na wys zukanej stronie. W logice s pójnik „nie ” na zywamy negacją i oznaczamy częs to s ymbolem ←
(a w Google s ymbolem –). Negacja ←p jes t prawdziwa , gdy zdanie p nie jes t prawdziwe. Na przykład wpisa nie
do wys zukiwarki wyra żenia – logika spowoduje wys zukanie tych s tron WWW, na których nie wys tępuje sło-
wo logika . Czyli Google posługuje się logiką, interpretując wyra żenia logiczne i wyszukując zgodnie z nimi in-
tere sujące na s zas oby.

Ta logika to uproszczona wersja kla s ycznego rachunku zdań, zajmującego s ię w s woim pods tawowym

wariancie s pójnikami logicznymi ne ga cji, alternatywy, koniunkcji ora z implikacji i równowa żnoś ci. Implika-
cja to wyrażenie pos taci „jeśli p to q”, za ś równowa żność to wyra żenie postaci „p wtedy i tylko wtedy, gdy q”.
O tym dokładniej poniżej.

Zadania

1. Prze tłumacz na język logiki zdanie określające zbiór obiektów czerwonych i zielonych, ale takich, które nie

s ą słodkie.

Przykładowe rozwią za nie: czerwony AND zielony AND ←słodki.

Wpis z powyżs ze wyra żenie do przeglądarki Google i porównaj je z wynikami wys zukiwania dla wyra żenia
+czerwony AND +zielony AND ←słodki. Zauwa ż dużą różnicę w liczbie wys zukanych s tron. Zinterpretuj tę róż-
nicę.

2. Napis z wyra żenie wyszukujące w Google s trony WWW o restauracjach lub b arach na Mazurach, ale nie za-

wierających słowa Rzym.

Przykładowe rozwią zanie: +Ma zury -Rzym resta uracja OR bar.
Jakie mogą być inne rozwią zania?

I do s amodzielnego rozwią zania:

3. Przetłumacz na język logiki zdanie określające jeden z dni roboczych w tygodniu. Jakie wyra żenie określi

wszys tkie dni robocze?

4. Napis z wyra żenie wys zukujące w Google strony o prowadzonych kierunka ch s tudiów z informatyki lub bio-

logii, ale nie z matema tyki i nie z filologii kla s ycznej.

Kla s yczny ra chunek zdań zajmuje s ię ba daniem prawdziwości zdań złożonych na podstawie zdań składo-
wych i w konsekwencji – badaniem poprawności wnioskowania.

1

Ta konwencja jes t charakterys tyczna dla Google. Tradycyjnie koniunkcja wią że silniej niż alternat ywa .

< 8 >

Informa tyka +

Aby wprowadzić rachunek zdań wprowadza się zmienne zdaniowe repre zentujące wartości logiczne

prawda, fałsz, a zara zem zbiory obiektów mają cych cechy opis ywane tymi zmiennymi (w tym ujęciu zmien-
ne zdaniowe odpowiadają cechom, czyli atrybutom obiektów). Bardziej złożone wyra żenia (zwane formu-
łami) uzyskujemy s tosując spójniki logiczne negacji, koniunkcji, alternatywy, implikacji i równowa żności.
Cza sem wprowadza się te ż inne spójniki. Tak naprawdę ws zys tkie możliwe spójniki można zdefiniować przy
pomocy np. negacji i koniunkcji, jednak przyjęty przez na s zes taw s pójników, choć z tego punktu widzenia
nadmiarowy, jes t z jednej s trony pros ty i na turalny, a z drugiej wystarczają cy w wielu typowych za s tos owa -
niach.

Znaczenie (s emantykę ) spójników logicznych poda je się częs to przy pomocy tablic logicznych, w któ-

rych w kolumnach podaje się wartości pos zczególnych wyra żeń. Przyjmujemy, że wartościami tymi mogą być
jedynie 0, 1; 0 – to fałs z, a 1 – to prawda , pa trz tabele 3 i 4.

Tabela 3.
Tablica dla ne gacji:

p

←

p

0

1

1

0

Tabela 4.
Tablica dla koniunkcji, alterna tywy, implikacji i równowa żności:

koniunkcja

alterna tywa

implikacja

równowa żnoś ć

p

q

p AND q

p OR q

p ⇒ q

p ⇔ q

0

0

0

0

1

1

0

1

0

1

1

0

1

0

0

1

0

0

1

1

1

1

1

1

Na tej pods ta wie mamy bardzo skuteczny mechanizm s prawdzania poprawnoś ci wnioskowania dla formuł
z nie wielką liczbą zmiennych zdaniowych. Mianowicie kons truujemy tablice logiczne, w których w pierws zych
kolumnach s ą zmienne zdaniowe, za ś w kolejnych – wyra żenia wys tępujące w badanej formule ułożone w ten
spos ób, by wartość danego wyra żenia można było policzyć na pods ta wie wcześniej wys tępujących wyra żeń.
Wiersze w tabeli wype łnia się najpierw wszys tkimi możliwymi układami wartoś ci logicznych, a na stępnie wy-
licza wartoś ci wyra żeń w kolejnych kolumnach.

Formuła nazywa się tautologią jeśli przyjmuje wartość 1 (prawda) niezależnie od wartości wchodzących w jej

skład zmiennych zdaniowych. Jes t ona spełnialna, gdy przyjmuje wartość 1 co najmniej dla jednej kombinacji war-
toś ci zmiennych zdaniowych. Jest na zywana kontrtautologią, jeśli zawsze przyjmuje wartość 0 (fałs z).

Dla przykładu sprawdźmy jakie wartości przyjmuje formuła ←(p OR q)

⇒

←p, patrz tabela 5.

Tabela 5.
Tablica logiczna dla przykładowej formuły

p

q

p OR q

←

(p OR q)

←

p

←

(p OR q)

⇒

←p

0

0

0

1

1

1

0

1

1

0

1

1

1

0

1

0

0

1

1

1

1

0

0

1

Badana formuła jes t zaws ze pra wdziwa , jes t więc tautologią (ka żda tautologia jes t równie ż spe łnialna). For-
muły wys tępujące we wcze śniejs zych kolumna ch s ą s pełnialne, ale nie s ą tautologia mi.

> Jak wnioskują mas zyny

< 9 >

Spra wdźmy jes zcze zas adę dowodzenia przez doprowadzanie do sprzecznoś ci. Zos ta ła ona odkryta

już przed niemal 2.5 tysiącami lat (przypisuje się ją Zenonowi z Elei). Jednak jes t ona wa żna współcześnie.
Stos uje się ją w matema tyce, ale też odgrywa za sadniczą rolę we wnioskowaniu z ba z danych wie dzy. Będzie -
my z niej korzys tać przy omawianiu metody rezolucji, najpopularniejs zej ws półczesnej metody automatycz-
nego wnios kowania. Za s ada ta mówi, że w celu wykazania implikacji p

⇒

q, zaprzeczamy q i wyka zujemy, że

prowadzi to do fałs zu. Innymi słowy, chcemy wyka zać formułę:

(p

⇒

q)

⇔

((p AND ←q)

⇒

0).

Kons truujemy tablicę logiczną jak w tabeli 6.

Tabela 6.
Tablica logiczna dla formuły uzas adniającej zasadę dowodzenia przez sprzecznoś ć.

p

q

p ⇒ q

←

q

p AND

←

q

(p AND

←

q) ⇒ 0

(p ⇒ q) ⇔

((p AND

←

q) ⇒ 0)

0

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

0

1

1

0

1

1

1

1

0

0

1

1

Badana formuła jes t wię c rzeczywiś cie tautologią.

W Internecie można znale źć wiele appletów kons truują cych tablice logiczne dla zadanych formuł. Przykłado-
wy applet można znaleźć pod adresem:
http:// highe re d.mcgra w-hill.com/ sites/ 00728 80082/ s tudent_view0/ chapter1/ intera ctive _demons tration_
applet__truth_tables _.html

Zadania (do s amodzielnego rozwią zania)

1. Zbuduj tablice logiczne dla poniżs zych formuł i stwierdź, które z nich s ą tautologiami:

a. (p

⇒

q)

⇔

(←p OR q)

b. ←(p OR q)

⇔

(←p AND ←q

2. Zapis z prawe s trony równowa żności tak, by były one tautologiami i sprawdź rozwią zanie używając tablic lo-

gicznych:
a. ←(p AND q)

⇔

..........

b. ←(p

⇒

q)

⇔

..........

W praktycznych za s tosowaniach częs to trzeba s prawdzać spełnialnoś ć formuł za wierających dużą liczbę
zmiennych. Potrafi ona dochodzić do tys ięcy. Załóżmy, że mamy formułę mającą 100 zmiennych. Tabela lo-
giczna bę dzie wię c mia ła 2

100

wiers zy (dlaczego?). Ile czasu spędziłby na obliczeniach bardzo s zybki kompu-

ter, wykonujący, powie dzmy 2

34

operacji na s ekundę (to więcej niż 10

10

operacji na s ekundę )? Aby wygenero-

wać 2

100

wiers zy potrzebujemy więcej niż 2

10 0

/ 2

34

(= 2

6 6

) s ekund, czyli wię cej niż 2

66

/ 60 minut. To więcej niż

2

66

/ 2

6

(= 2

60

) minut i więcej niż 2

6 0

/ 2

6

(= 2

54

) godzin i więcej niż 2

54

/ 2

5

(= 2

49

) dób. To z kolei więcej niż 2

40

la t

(czyli wię cej niż 10

12

lat!). Wiek Wszechś wia ta s zacuje się na 13-14 miliardów lat (czyli nie wię cej niż 14

*

10

9

lat).

Diagramy Venna ilus trują zależnoś ci pomię dzy zbiorami obiektów. Ponieważ na zmienne logiczne możemy
pa trzeć ja ko na cechy obiektów, możemy też im przypis ać zbiory obiektów mających te cechy. Diagramy Ven-
na mogą ilus trować zbiory obiektów i posługując się nimi można znajdować zależnoś ci między rozwa żanymi
pojęciami. Zbiory na tych diagramach re prezentujemy przy pomocy kół: z ka żdą rozwa żaną zmienną zdanio-
wą zwią zujemy koło. Jeśli nie mamy żadnych doda tkowych za łożeń, umies zczamy koła w ten spos ób, by wy-

< 10 >

Informa tyka +

dzieliły ws zystkie możliwe zależnoś ci (obs zary) na danej pła szczyźnie. Obszary te oznaczamy kolejnymi lite -
rami lub liczba mi. Zbiór ws zys tkich obiektów jes t reprezentowa ny przez prostokąt otaczający wszys tkie koła.

Dia gram dla trzech zmiennych zdaniowych p, q, r je st przeds tawiony na rys. 1. Na tym diagramie:

■

zbiór obs zarów przypis anych zmiennej p to {b, c, e , f}

■

zbiór obs zarów przypis anych zmiennej q to {c, d, f, g}

■

zbiór obs zarów przypis anych zmiennej r to {e, f, g, h}.

p

b

d

g

e

h

a

q

r

c

f

Rysunek 1.
Dia gram Venna dla trzech zbiorów

Zauwa żmy, że obs zar oznaczony przez a reprezentuje ws zystkie obiekty le zące poza kołami repre zentujący-
mi p, q ora z r.

Spójniki ne ga cji, alternatywy i koniunkcji na diagramach Venna interpre tujemy nas tępująco:

■

ne gacja formuły jes t reprezentowana przez zbiór wszys tkich obs zarów nie bę dących obszarami
reprezentującymi da ną formułę; na przykład ←p reprezentujemy prze z zbiór tych obszarów, które leżą poza
p, czyli wykluczamy obs zary b, c, e, f, otrzymując {a , d, g, h}

■

alternatywa dwóch formuł jes t reprezentowana prze z zbiór obs za rów reprezentujących pierws zą lub drugą
formułę; na przykład p OR r repre zentujemy przez zbiór obs zarów {b, c, e, f, g, h}

■

koniunkcja dwóch formuł jes t reprezentowana przez zbiór obszarów wspólnych dla pierws zej i drugiej
formuły; na przykład p AND q reprezentujemy prze z zbiór obs zarów {c, f}.

Spójnik implikacji odzwierciedla zawieranie się zbiorów: p

⇒

q oznacza , że zbiór obiektów reprezentujących

p za wiera się w zbiorze obiektów reprezentujących q.

Spójnik równowa żności odzwierciedla równoś ć zbiorów: p

⇔

q oznacza , że zbiór obiektów reprezentu-

jących p jes t taki s am, jak zbiór obiektów reprezentujących q.

Dia gramy Venna mogą być wykorzys tane do znajdowania zale żnoś ci między formułami.

Jako pierws zy przykład rozwa żmy formułę (p AND q)

⇒

p. Użyjmy poprze dniego diagramu (oczywiś cie

koło repre zentujące r moglibyśmy pominąć, gdyż r nie wys tępuje w nas zej formule). Już zauwa żyliśmy, że p
AND q repre zentujemy prze z zbiór obs zarów {c, f} ora z p reprezentujemy przez {b, c, e, f}. Oczywiś cie zbiór {c,
f} zawiera s ię w zbiorze {b, c, e, f}, a więc badana implikacja jes t prawdziwa.

Jako drugi przykład rozważmy formułę ((p AND q) OR r )

⇔

((p OR r) AND (q OR r)):

■

formuła p AND q jes t repre zentowana przez zbiór {c, f}

■

formuła r jes t reprezentowana prze z zbiór {e, f, g, h}

■

formuła ((p AND q) OR r jes t więc repre zentowana przez zbiór {c, e, f, g, h}

■

formuła (p OR r) jes t reprezentowana prze z zbiór {b, c, e, f, g, h}

■

formuła (q OR r) jes t reprezentowa na prze z zbiór {c, d, e , f, g, h}

■

formuła ((p OR r) AND (q OR r)) jest więc reprezentowana przez zbiór {c, e, f, g, h},

> Jak wnioskują mas zyny

< 11 >

zatem zbiory reprezentujące le wą i prawą s tronę równowa żnoś ci s ą identyczne, co oznacza że równowa żność
ta jes t prawdziwa .

Zadania (do s amodzielnego rozwią zania)

1. Zbuduj diagramy Venna dla poniższych formuł i s twierdź, które z nich s ą tautologiami:

a. (p AND q)

⇔

←(←p OR ←q)

b. ←(p AND q)

⇔

(←p OR ←q).

2. Zapis z prawe s trony równowa żności tak, by były one tautologiami i sprawdź rozwią zanie używając tablic lo-

gicznych:
a. ←(p OR ←q)

⇔

..........

b. ←(p AND ←q)

⇔

..........

Rozwa żmy s ytua cję , w której:

■

robot wybiera obiekt duży lub ma ły: p OR q

■

robot nie może wybra ć jednocześ nie obiektu duże go lub ma łego: ←(p AND q)

■

jeśli podłoże jes t śliskie, to nie wybiera dużych obiektów: r

⇒

←p, czyli ←r OR ←p (dlaczego?)

■

jeśli podłoże nie je st śliskie, to wybiera małe obiekty: ←r

⇒

q, czyli r OR q.

Czy koniunkcja powyżs zych formuł implikuje, że zos tanie wybrany mały obiekt? Innymi słowy, pytamy czy
pra wdziwa jes t formuła:

((p OR q) AND ←(p AND q) AND (←r OR ←p) AND (r OR q))

⇒

q.

Znów korzystamy z wcze śniejs zego diagramu:

■

formuła p OR q je st repre zentowana przez {b, c, e, f, g}

■

formuła p AND q jes t reprezentowa na prze z {c, f}, a więc formuła ←(p AND q) jes t reprezentowana przez {a,
b, d, e, g, h}

■

formuła ←r jes t reprezentowa na przez {a , b, c, d}

■

formuła ←p jes t reprezentowana przez {a , d, g, h}, a więc formuła (←r OR ←p) jes t reprezentowana prze z {a, b,
c, d, g, h}

■

formuła (r OR q) jes t reprezentowana prze z {c, d, e , f, g, h}

■

koniunkcja wys tępująca z lewej s trony implikacji jes t więc reprezentowana przez częś ć wspólną zbiorów {b,
c, e, f, g}, {a , b, d, e, g, h}, {a , b, c, d, g, h},
{c, d , e, f, g, h}, czyli prze z {g}

■

formuła q jes t reprezentowana prze z zbiór {c, d, f, g}, w którym {g} się zawiera , a więc odpowiedź na pytanie
o prawdziwoś ć badanej implikacji jest twierdząca .

Metoda diagramów Venna jes t bardzo a trakcyjna ze względu na ła twoś ć wizualnego odkrywania s tosunkowo
złożonych pra w logicznych. Doczekała się wielu ba dań i uogólnień. Więcej na jej temat można znale źć np. na
bardzo interesującej s tronie:

http:// www.combinatorics.org/ Surveys/ ds5/ VennEJC.html

na której przeds tawiono m.in., ja k można kons truowa ć diagramy Venna dla więcej niż trzech zbiorów, czyli
w taki spos ób, aby diagram jednego zbioru mia ł czę ś ć wspólną z dia gramem ka żde go innego zbioru.

Dotychczas omawialiś my metody wnioskowania skuteczne w niewielkich przykładach. Rze czywis te s ys temy
obsługujące kla s yczny rachunek zdań, na zywane SAT Solvers (SAT pochodzi od a ngielskiego satisfia bility,
czyli s pe łnialnoś ć), potrafią s obie radzić z bardzo dużymi formułami wys tępującymi w niema łym obs zarze za -
stos owań (z formułami mającymi kilka set, czas em nawet tysiące zmiennych). Ich siła polega na stos owaniu
dużej liczby algorytmów skute cznych dla wybranych rodzajów formuł. Poniżej przeds ta wimy jeden z takich
algorytmów, bardzo skute czny i powszechnie s tos owany w informa tyce i s ztucznej inteligencji, zwany me to-

< 12 >

Informa tyka +

dą rezolucji. Metoda re zolucji dzia ła na koniunkcjach klauzul, przy czym klauzula jes t alternatywą zmiennych
zdaniowych lub ich negacji. Na przykład kla uzulą jes t:

p OR ←q OR ←r OR s

za ś nie jes t: p OR ←←q (dlaczego?) a ni te ż p AND ←r (dlacze go?).

UWAGA: pus ta klauzula (nie mająca żadnych wyra żeń) jes t równowa żna fałs zowi (czyli 0).

Wiedza w s ys temach sztucznej inteligencji, w tym w bazach wiedzy, s ystemach eksperckich itd., zwykle ma
pos tać klauzulową. Mia nowicie implikacja w pos taci:

(p

1

AND p

2

AND ... AND p

k

)

⇒

(r

1

OR r

2

OR ... OR r

m

)

jes t równowa żna klauzuli (dla cze go?):

←p

1

OR ←p

2

OR ...OR ←p

k

OR r

1

OR r

2

OR ...OR r

m

.

Implikacje ws pomnianej pos taci odzwierciedlają re guły, jakimi pos ługujemy się codziennie, np.:

gorączka AND kas zel

⇒

przeziębienie OR grypa

des zcz AND bezwietrznie ⇒ pa rasol OR kurtka _z_kapturem
des zcz AND wia tr ⇒ samochód

Aby przekszta łcić formuły do pos taci klauzulowej zamieniamy wys tępujące w niej podformuły zgodnie z re -
gułami podanymi poniżej a ż do momentu uzyskania koniunkcji klauzul.

Reguły (jako zadanie przekonaj się, s tosując me todę tablic logicznych, że formuła zas tępowana je st za-

ws ze równowa żna formule za s tępującej):

1. za s tą p (A ⇔ B) przez (←A OR B) AND (A OR ←B)
2. za s tąp (A ⇒ B) przez (←A OR B)
3. za s tąp ←←A przez A
4. za s tą p ←(A AND B) przez (←A OR ←B)
5. za s tąp ←(A OR B) prze z (←A AND ←B)
6. za s tąp A OR (B AND C) przez (A OR B) AND (A OR C)
7. za s tąp (B AND C) OR A przez (A OR B) AND (A OR C).

Zakładamy, że usuwane są te ż zbędne nawia s y, np. ((A)) można zas tąpić prze z (A), za ś (A OR B) OR C – przez
A OR B OR C ora z powtórzenia wyra że ń, np. (A OR A OR B) można zas tąpić przez równowa żną formułę (A OR B).
Na przykład rozwa żmy formułę: (←(p AND ←q) OR (p ⇒ r) ) OR (r ⇔ ←s). Jej sprowa dzenie do pos taci klauzu-
lowej może składać się z kroków:

■

((←p OR ←←q) OR (p ⇒ r) ) OR (r ⇔ ←s)

■

((←p OR ←←q) OR (←p OR r) ) OR (r ⇔ ←s)

■

(←p OR ←←q OR ←p OR r) OR (r ⇔ ←s)

■

(←p OR q OR ←p OR r) OR (r ⇔ ←s)

■

(←p OR q OR ←p OR r) OR ((←r OR ←s) AND (r OR ←←s))

■

(←p OR q OR ←p OR r) OR ((←r OR ←s) AND (r OR s))

■

(←p OR q OR r) OR ((←r OR ←s) AND (r OR s))

■

(←p OR q OR r OR ←r OR ←s) AND (←p OR q OR r OR r OR s)

■

(←p OR q OR r OR ←r OR ←s) AND (←p OR q OR r OR s).
Powyżs zą formułę można z ła twoś cią uproś cić (jak?).

Zadania (do s amodzielnego rozwią zania)

1. Przekszta łć do pos taci klauzulowej formuły:

a . (p AND q) ⇔ ←(←p OR ←q)
b. ←(p AND q) ⇔ (←p OR ←q).

2. Za stąp uzyskane kla uzule równowa żnymi im implikacjami pos taci rozważanej w podrozdziale „Dlaczego

klauzule s ą wa żne”.

> Jak wnioskują mas zyny

< 13 >

Metoda re zolucji wykorzys tuje za sadę dowodzenia przez doprowadzanie do sprzecznoś ci. Jes t ona na w s wo-
jej is tocie oparta na prze chodniości implikacji, czyli na regule mówiącej że z (p ⇒ q) ora z (q ⇒ r) mamy pra-
wo wnios kowa ć (p ⇒ r). Sformułowanie tej reguły w pos taci klauzulowej jes t na stępujące:

(←p OR q) AND (←q OR r) ⇒ (←p OR r).

Uogólniając na dowolne kla uzule uzyskamy re gułę re zolucji mówiącej, że z klauzul:

←p

1

OR ←p

2

OR ...OR ←p

k

OR r

1

OR r

2

OR ...OR r

m

p

1

OR ←q

1

OR ...OR ←q

n

OR s

1

OR s

2

OR ...OR s

m

uzyskujemy klauzulę:

←p

2

OR ...OR ←p

k

OR r

1

OR r

2

OR ...OR r

m

OR ←q

1

OR ...OR ←q

n

OR s

1

OR s

2

OR ...OR s

m

,

czyli us uwamy jedną ze zmiennych wys tępującą w pierws zej klauzuli wraz z jej negacją wys tępującą w dru-
giej klauzuli. Dla wygody zapis aliśmy je jako pierws ze, ale miejsce wys tąpienia w klauzulach nie ma zna cze -
nia – wa żne jes t tylko, by wys tąpiły one w dwóch klauzulach.

Jak wspomnieliśmy, metoda rezolucji to za sada wnioskowania przez doprowadzanie do s przecznoś ci.

Oznacza to, że najpierw negujemy sprawdzaną formułę , a na stępnie s taramy się z tej negacji uzyskać fa łs z,
a wię c klauzulę pus tą. Jeśli się to uda , początkowa formuła jes t tautologią. Jeś li pus tej klauzuli nie da się
w żaden sposób uzyskać, formuła tautologią nie jes t.

Wa żnym przykładem jes t wykazywanie, że pe wna formuła wynika z ba zy danych wiedzy, w której wie -

dza jes t reprezentowana jako zbiór klauzul. Chcemy sprawdzić czy D ⇒ q, gdzie D jes t ba zą wiedzy, a q jest
formułą wykazywaną przy założeniu, że wiedza zawarta w D odzwierciedla interesują cą nas rze czywis toś ć.
W me todzie rezolucji zaprzeczamy implikacji (D ⇒ q). Zaprzeczenie to je st równowa żne formule (D AND ←q).
Czyli ←q dokładamy do ba zy wiedzy D (przekszta łcają c ←q do pos taci klauzulowej) i s taramy się wyprowa-
dzić klauzulę pus tą. Ba za D nie zmienia się ! Z wydajnościowego punktu widzenia je st to bardzo wa żne, bo
zwykle taka ba za danych jes t duża , podcza s gdy badane wnioski zwykle s tosunkowo małe, gdyż reprezen-
tują one typowe zapyta nia użytkowników. Zwykle zapytania mają bardzo nie wielkie rozmiary w porównaniu
z rozmiarem ba zy danych.

Dla przykładu wyka żmy, że z koniunkcji klauzul (p ⇒ q) AND (←p ⇒ q) można wywnioskować q. Jes t to

formalizacja wnioskowania przez przypadki, bo spełniony jes t warunek p albo warunek ←p. Bez względu na
to, który z nich jes t s pełniony, konsekwencją jes t q. W życiu częs to s tosujemy takie wnios kowanie. Na przy-
kład, gdy chcemy zabe zpieczyć się prze d zmoknięciem, bierzemy para sol. W tej s ytuacji s tosujemy wniosko-
wanie:

(←des zcz ⇒ ←zmoknę) AND (des zcz ⇒ ←zmoknę),

a więc wnioskuję, że nie zmoknę bez względu na to czy będzie des zcz, czy nie.
Za s adę wnioskowania przez przypadki można zapisać w p os taci klauzulowej jako:

(←p OR q) – pierwsze za łożenie w pos taci klauzulowej
(p OR q) – drugie założenie w pos ta ci klauzulowej
←q – zaprzeczona konkluzja.
Stosując re gułę rezolucji do dwóch pierws zych klauzul uzys kujemy klauzulę (q OR q), usuwamy zbęd-

ne powtórzenie q, uzyskujemy więc klauzulę za wierającą jedynie q. Tera z z tej klauzuli ora z z ←q uzyskujemy
klauzulę pus tą. Graficznie to wnioskowanie można przedstawić jak na rys . 2.

←p OR q

q

p OR q

0

←q

Rysunek 2.
Graficzna reprezentacja wnioskowania rezolucyjnego

< 14 >

Informa tyka +

Zadania (do s amodzielnego rozwią zania)

1. Korzys tając z metody rezolucji wyka ż, że

a . ((p OR q) AND r) ⇒ ((p AND r) OR (q AND r)).
b. ((p AND q) OR r) ⇒ ((p OR r) AND (q OR r)).

Załóżmy, że mamy na s tępującą ba zę wiedzy:

■

Pude łka s ą ma łe lub ś re dnie (m OR s).

■

Ka żde pude łko jes t czerwone , zielone lub niebieskie (c OR z OR n).

■

Ma łe pude łka s ą czerwone lub niebieskie (m ⇒ (c OR n)).

■

Średnie pude łka s ą zielone lub niebie skie (s ⇒ (z OR n)).

■

Do przewozu robot wybiera czerwone pude łka (p ⇒ c).

■

Do aktywnoś ci innych niż przewóz robot nie wybiera pudełek niebieskich ani zielonych (←p ⇒ (←n AND ←z)).

Jakie pude łko wybierze robot? Mamy ba zę wiedzy zawierającą klauzule (dla cze go?):

(m OR s), (c OR z OR n), (←m OR c OR n), (←s OR z OR n), (←p OR c), (p OR ←n), (p OR ←z).

Przykładowe rozumowanie rezolucyjne wykorzys tują ce te kla uzule jes t przeds ta wione na rys . 3. Z tego

rozumowania widzimy, że uzupe łnienie bazy wiedzy o klauzulę ←c dałoby natychmia stowy wywód klauzuli
pustej, ma my już bowiem wyprowadzoną klauzulę zawierającą jedynie c. Stąd wnios kujemy, że z nas zej ba zy
wie dzy wynika c (w metodzie rezolucji taka konkluzja – po zaprzeczeniu – trafia do ba zy wiedzy).

Zauwa żmy, że dowód rezolucyjny jes t tu na prawdę bardzo krótki. Dla porównania – korzystanie z tablic

logicznych wymagałoby skonstruowania 2

6

= 64 wierszy, mamy bowiem 6 różnych zmiennych.

m OR s

c OR z OR n

←m OR c OR n

←s OR z OR n

c OR z

←p OR c

c

p OR ←n

c OR ←n

p OR ←z

c OR ←z

Rysunek 3.
Przykładowe wnioskowanie rezolucyjne

Załóżmy, że nas za ba za danych zawiera formuły:

■

K twierdzi, że Jan pracuje w s oboty (p).

■

K twierdzi także, że w soboty Jan czyta ksią żki i nie ogląda telewizji (k AND ←t).

■

P twierdzi, że gdy Jan nie pracuje, nie oglą da również telewizji (←p ⇒ ←t).

■

P twierdzi, także, że w s oboty Jan czyta ksią żki ogląda telewizję lub gotuje
(k OR t OR g).

Wiedząc, że K zaws ze kłamie, a P zaws ze mówi prawdę , odgadnijmy, co Jan robi w soboty i wyka żmy to s tosu-
jąc metodę re zolucji. Skoro K kłamie, a P mówi prawdę , mamy bazę danych klauzul (dlaczego?):

←p, (←k OR t), (p OR ←t), (k OR t OR g).

Wnioskowanie metodą rezolucji jes t przeds tawione na rys . 4.

Z powyżs zego wywodu uzyskaliśmy jako wniosek g, czyli fakt, że w s oboty Jan gotuje. Formalne wykazanie
pole ga łoby na dodaniu zaprze czonej konkluzji (czyli ←g) do zbioru klauzul i wyprowadzeniu klauzuli pustej,
co w obecnoś ci klauzuli zawierającej jedynie g jes t natychmia stowe.

I znów wnioskowa nie re zolucyjne jes t krótkie. Oczywiś cie rob ot, s tosując regułę „na ślepo”, może błą -

dzić zanim znajdzie rozwiązanie. Jednak nadal proces dowodzenia jes t tu bardzo wydajny. Warto jednak pod-

> Jak wnioskują mas zyny

< 15 >

kreślić, że w pes ymistycznym przypadku wymaga on 2

n

kroków, gdzie n jes t liczbą zmiennych wys tępujących

w formule. Nie jes t znany żaden algorytm działający efektywnie dla ka żdej formuły wejściowej.

W wykładzie pojawiła się jedna logika – kla s yczny rachunek zdań. Trudno przecenić jego rolę i zakres zas to-
sowań. Wielu na ukowców poś więca ca łą s woją aktywnoś ć badawczą np. na pos zukiwanie efektywnych s ys-
temów wnioskowania dla wybranych rodzajów formuł, pojawiających się w danych zas tos owaniach w wyniku
modelowania lub tłumaczenia ła twiejs zych w użyciu formalizmów. W końcu jeden z kilku problemów milenij-
nych, za rozwią zanie którego czeka nagroda w wys okoś ci miliona USD, dotyczy wyka zania istnienia lub nie -
is tnienia efektywnego algorytmu badania czy dana formuła kla s ycznego rachunku zdań jes t s pełnialna. Nie -
mniej je dnak z punktu widzenia wielu wa żnych za s tos owań jes t to bardzo pros ty formalizm i – jako taki – nie
jes t w s tanie dobrze modelować złożonej rzeczywis toś ci s ystemów informatycznych, ję zyka naturalnego, re -
prezentacji wiedzy czy wnioskowania o ś wiecie rzeczywis tym.

W minionych czterdzie stu latach w informatyce prowadzono bardzo intens ywne badania na d logikami,

np. modelującymi wnioskowanie człowieka lepiej niż klas yczny rachunek zdań (znanymi w s ztucznej inteli-
gencji jako wnioskowanie zdroworozs ądkowe lub niemonotoniczne). Dziedzina ta nadal intens ywnie s ię roz-
wija, bowiem s zuka się coraz leps zych me tod modelujących inteligentne zachowania w s ys temach autono-
micznych, jak be zzałogowe helikoptery, czy złożone s ystemy robotyki.

Ale o tym kiedy indziej, na przykład na s tudiach informa tycznych...

Ben-Ari M., Logika matematyczna w informatyce, WNT, Wars zawa 2004

←p

←k

←k OR t

←t

g

p OR ←t

k OR g

k OR t OR g

Rysunek 4.
Wnioskowanie rezolucyjne dla przykładu o kłamcy i prawdomównym

< 16 >

Informa tyka +

Poniżej przeds tawiamy krótki fra gment pracy magisterskiej C.E. Shannona z 1940 roku. Uchodzi ona za naj-
leps zą pracę magis ters ką XX wieku i „przekłada” język logiki na obwody, z jakich korzys tają inżynierowie
konstruujący także współczes ne komputery.

Nota tki

< 17 >

< 18 > Notatki

Informa tyka +

Nota tki

< 19 >

W projekcie

, poza wykładami i warsztatami,

przewidziano następujące działania:

■

24-godzinne kursy dla uczniów w ramach modułów tematycznych

■

24-godzinne kurs y metodyczne dla nauczycieli, przygotowujące

do pracy z uczniem zdolnym

■

nagrania 60 wykładów informatycznych, prowadzonych

przez wybitnych specjalistów i nauczycieli akademickich

■

konkursy dla uczniów, trzy w ciągu roku

■

udział uczniów w pracach kół naukowych

■

udział uczniów w konferencjach naukowych

■

obozy wypoczynkowo-naukowe.

Szczegółowe informacje znajdują się na stronie projektu