Logika dla informatyków - Materiały do zajęć - 2004

Uniwersytet Wrocławski, Instytut Informatyki Studia magisterskie na kierunku Informatyka Przedmiot obowiazkowy ˛ w semestrze zimowym pierwszego roku studiów 30 godzin wykładu + 30 godzin repetytorium + 30 godzin ćwiczeń Logika dla informat...

Uniwersytet Wrocławski, Instytut Informatyki Studia magisterskie na kierunku Informatyka Przedmiot obowiazkowy ˛ w semestrze zimowym pierwszego roku studiów 30 godzin wykładu + 30 godzin repetytorium + 30 godzin ćwiczeń Logika dla informatyków Materiały do zaj˛eć Leszek Pacholski Wrocław, 2004  2004/5 Właściciel tej kopii notatek Rok akad. Uwaga: W niniejszej ksiażeczce ˛ zebrano listy zadań, notatki do wykładów oraz inne materiały przygotowywane do zaj˛eć z Logiki dla informatyków w latach 1997–2004. Mimo iż materiały te posiadaja˛ bardziej dopracowana˛ form˛e, niż przygotowywane do innych zaj˛eć kserograficzne kopie oraz zostały oddane do druku i oprawy, jednak nie były poddane — jak to ma miejsce w przypadku podr˛eczników — solidnej korekcie i zawieraja˛ sporo bł˛edów. Nie zamieszczono w nich także szczegółowych wyjaśnień i komentarzy. Dlatego notatki te nie sa˛ podr˛ecznikiem do wykładu. Maja˛ jedynie słu- żyć jako wykaz zagadnień obowiazuj ˛ acych ˛ do egzaminu i lista zadań przerabianych na ćwiczeniach. Przeglad ˛ zalecanych do zaj˛eć podr˛eczników jest zamieszczony na stronie xi. Podczas redagowania notatek wykorzystano: – skrypt J. Tiuryna Wst˛ep do teorii mnogości i logiki – listy zadań M. Zakrzewskiego – materiały A. Kościelskiego i T. Wierzbickiego – podr˛eczniki wymienione w bibliografii na stronie xi Redakcja i skład: T. Wierzbicki Konsultacja merytoryczna: A. Kościelski Wydanie drugie, (nieznacznie) poprawione i rozszerzone Niniejsze notatki moga˛ być drukowane, powielane oraz rozpowszechniane w wersji elektronicznej i pa- pierowej, w cz˛eści badź ˛ w całości — bez konieczności uzyskania zgody autora — pod warunkiem nie- osiagania ˛ bezpośrednich korzyści finansowych z ich rozpowszechniania i z zachowaniem praw autorskich. W szczególności dodatkowe egzemplarze moga˛ być sprzedawane przez osoby trzecie jedynie po cenie uzyskania kopii (druku, wydruku, kserografowania itp.) Data utworzenia dokumentu: 15 września 2004 ISBN: 83–917081–7–9 Strona WWW zaj˛eć: http://www.ii.uni.wroc.pl/~pacholsk/logika.phtml Szanowni Państwo, Program wykładu logiki dla informatyków nie jest trudny — w nast˛epnych se- mestrach b˛edziecie Państwo słuchali dużo trudniejszych wykładów. Mimo to co roku znaczna cz˛eść studentów nie zdaje egzaminu z logiki. Jednym z powodów niepowodzenia na egzaminie jest to, że jest to dla Was pierw- szy w życiu wykład akademicki, w którym pojawia si˛e duża liczba nowych poj˛eć. Poj˛e- cia te, na ogół dosyć abstrakcyjne, pojawiaja˛ si˛e licznie na każdych zaj˛eciach. Trzeba si˛e ich wszystkich nauczyć. Nauczyć — to mało, gdyż matematyka nie polega na wy- konywaniu mniej lub bardziej skomplikowanych rachunków, lecz na przeprowadzaniu rozumowań. Dlatego jest bardzo ważne, byście nie tylko je znali, ale i dobrze rozu- mieli. Wykład ma Wam w tym pomóc, ale wielu z Was nie zdoła na samym wykładzie opanować całego materiału. Na wykładzie nie nauczycie si˛e też sprawnie posługi- wać wprowadzonymi poj˛eciami. Dlatego musicie systematycznie pracować w domu. Jeśli przed zaj˛eciami przypomnicie sobie wcześniej wprowadzone definicje, zwi˛ek- szycie swoje szanse na zrozumienie nowego materiału. Jeśli natomiast nie b˛edziecie znać wcześniej wprowadzonych poj˛eć, b˛edziecie z dużym prawdopodobieństwem sie- dzieć na wykładzie, jak na tureckim kazaniu. Jeżeli przyswojenie nowych poj˛eć spra- wia Wam trudność, radz˛e także przed wykładem przejrzeć podane w przygotowanych przez nas notatkach definicje, które dopiero zostana˛ na zaj˛eciach wprowadzone. Być może czytajac ˛ je po raz pierwszy przed wykładem nie potraficie ich w pełni zrozumieć, ale gdy je wcześniej przeczytacie, wyniesiecie z wykładu znacznie wi˛ecej. Poza tym b˛edziecie przed zaj˛eciami wiedzieć, czego nie rozumiecie i o co na wykładzie zapytać. Od wielu lat wszystkim studentom zaczynajacym ˛ studia powtarzam to, co napi- sałem w poprzednim paragrafie. Niestety z marnym skutkiem. Co roku w drugiej po- łowie semestru okazuje si˛e, że znaczna cz˛eść studentów nie rozumie wykładu, bo nie pami˛eta wcześniej wprowadzonych definicji i nie zna treści udowodnionych wcze- śniej twierdzeń. Co roku mniej niż połowa studentów zdaje egzamin z logiki. Bardzo nas to martwi. Chcielibyśmy, aby znaczna wi˛ekszość z Was mogła ukończyć studia. Dlatego aby Was zdyscyplinować i zmusić do systematycznej pracy wprowadzamy opisane w regulaminie zaj˛eć rygory (punktowy system zaliczania ćwiczeń, kartkówki, egzamin połówkowy itd.). Ich celem nie jest uprzykrzenie Wam życia, ale zwi˛ekszenie szansy na to, że zdacie egzamin. Leszek Pacholski  Spis treści A. Informacje ogólne ix A.1. Program wykładu....................................... ix A.2. Zapisy na zaj˛ecia....................................... ix A.3. Obsada zaj˛eć i konsultacje................................ x B. Literatura xi C. Zasady prowadzenia i zaliczania ćwiczeń xiii C.1. Wst˛ep............................................... xiii C.2. Szczegółowe zasady prowadzenia zaj˛eć...................... xiv D. Egzaminy xix D.1. Egzamin zasadniczy..................................... xx D.1.1. Egzamin połówkowy.............................. xxi D.1.2. Egzamin końcowy................................ xxi D.2. Egzamin poprawkowy................................... xxi 0. Zadania na dobry poczatek ˛ 1 1. Rachunek zdań i rachunek kwantyfikatorów 5 1.1. Składnia rachunku zdań.................................. 5 1.2. Wartości logiczne i znaczenie formuł zdaniowych............... 5 1.2.1. Metoda zero-jedynkowa............................ 7 1.2.2. Skrócona metoda zerojedynkowa..................... 7 1.2.3. Równoważność formuł............................. 11 1.2.4. Lemat o podstawianiu............................. 14 1.3. Formalizacja rozumowań w j˛ezyku rachunku zdań.............. 15 1.4. Własności formuł zdaniowych............................. 16 1.5. Postaci normalne formuł zdaniowych........................ 19 1.5.1. Usuwanie symbolu negacji.......................... 19 vi Spis treści 1.5.2. Dysjunkcyjna postać normalna....................... 21 1.5.3. Koniunkcyjna postać normalna....................... 21 1.6. Funkcje boolowskie i zupełne zbiory spójników................ 24 1.7. Składnia rachunku kwantyfikatorów......................... 25 1.8. Znaczenie formuł rachunku kwantyfikatorów.................. 26 1.9. Formalizacja wypowiedzi w j˛ezyku rachunku kwantyfikatorów..... 29 2. Zbiory 33 2.1. Działania na zbiorach.................................... 34 2.2. Operacje nieskończone na zbiorach......................... 38 3. Relacje 43 3.1. Para uporzadkowana ˛ i iloczyn (produkt) kartezjański............ 43 3.2. Relacje............................................... 44 3.3. Krotki (n-tki) uporzadkowane ˛ i relacje n-argumentowe........... 45 3.4. Złożenie relacji. Relacja odwrotna.......................... 45 4. Funkcje 47 4.1. Funkcje odwrotne i złożenie funkcji......................... 48 4.2. Obraz i przeciwobraz zbioru............................... 48 5. Relacje równoważności 51 6. Teoria mocy 57 6.1. Równoliczność zbiorów.................................. 57 6.2. Własności poj˛ecia równoliczności zbiorów.................... 59 6.3. Zbiory skończone....................................... 60 6.3.1. Wzór właczeń ˛ i wyłaczeń ˛........................... 62 6.4. Moce zbiorów nieskończonych............................. 63 6.5. Wyznaczanie mocy zbiorów............................... 66 6.6. Zbiory przeliczalne...................................... 68 7. Relacje porzadku ˛ 73 7.1. Przykłady porzadków ˛.................................... 74 7.2. Izomorfizm porzadkowy ˛.................................. 76 7.3. Zawieranie zbiorów jako relacja porzadku ˛.................... 78 7.4. Liczba relacji porzadku ˛.................................. 79 8. J˛ezyki formalne 81 Spis treści vii 9. Kresy zbiorów 83 9.1. Kraty................................................ 86 9.2. Porzadki ˛ zupełne....................................... 87 9.3. Twierdzenia o punkcie stałym.............................. 88 9.4. Relacje w zbiorze formuł zdaniowych........................ 89 10. Dobre porzadki ˛ i indukcja 93 10.1. Porzadki ˛ regularne...................................... 93 10.2. Indukcja.............................................. 95 11. Elementy algebry uniwersalnej 99 11.1. Algebra termów........................................ 99 11.1.1. Inna definicja zbioru termów. Drzewa.................. 100 11.1.2. Wartość termu................................... 101 11.2. Homomorfizmy........................................ 101 11.3. Problem unifikacji...................................... 104 12. Elementy logiki formalnej 107 12.1. System Hilberta dla rachunku zdań ze spójnikami implikacji i fałszu 107 12.2. System Hilberta dla rachunku zdań ze spójnikami alternatywy i ko- niunkcji.............................................. 108 12.3. Składnia j˛ezyka pierwszego rz˛edu.......................... 110 12.4. Semantyka j˛ezyka pierwszego rz˛edu......................... 110 12.5. Podstawienia.......................................... 111 12.6. Hilbertowski system dowodzenia dla rachunku I rz˛edu........... 112 13. Zadania egzaminacyjne z rozwiazaniami ˛ 115  A Informacje ogólne A.1. Program wykładu Ponieważ przedmiot Logika dla Informatyków jest obowiazkowy, ˛ jego program jest ustalony w Programie Studiów Informatycznych na Uniwersytecie Wrocławskim z 17 czerwca 1997 z późniejszymi zmianami, dost˛epnym m. in. w sekretariacie In- stytutu Informatyki, pok. 29 i — w wersji elektronicznej — pod adresem: http://www.ii.uni.wroc.pl/program/ A.2. Zapisy na zajecia ˛ W zaj˛eciach moga˛ uczestniczyć zarówno studenci studiów magisterskich, jak i li- cencjackich. Na zaj˛ecia należy si˛e zapisać w internetowym systemie Zapisy, dost˛ep- nym pod adresem zapisy.ii.uni.wroc.pl. Zadeklarowanie przedmiotu w syste- mie Zapisy jest forma˛ umowy pomi˛edzy studentem i uczelnia.˛ Student zobowiazuje ˛ si˛e ucz˛eszczać na zaj˛ecia, uczelnia zaś zobowiazuje ˛ si˛e je prowadzić i ocenić studenta po ich zakończeniu. Dlatego do egzaminu b˛eda˛ mogły przystapić ˛ jedynie osoby za- pisane na wykład, a zaliczenie ćwiczeń b˛eda˛ mogły uzyskać jedynie osoby zapisane na ćwiczenia. Chociaż w systemie Zapisy prowadzacy ˛ sa˛ dla porzadku˛ przypisani do poszcze- gólnych grup ćwiczeniowych, jednak w kolejnych tygodniach maja˛ zaj˛ecia z różnymi grupami. Dlatego przy wyborze grupy nie należy si˛e kierować nazwiskiem prowadza- ˛ cego, gdyż każdy student b˛edzie miał przeci˛etnie trzy ćwiczenia z każdym z prowa- dzacych. ˛ Jedna z grup ćwiczeniowych jest oznaczona jako grupa zaawansowana. Do tej grupy powinni si˛e zapisać studenci o wi˛ekszych zdolnościach i aspiracjach matema- tycznych. Rozwiazuje˛ si˛e w niej nieco trudniejsze (ale i ciekawsze) zadania i wymaga od studentów nieco wi˛ekszej samodzielności. Przytoczone na nast˛epnych stronach Zasady prowadzenia i zaliczania ćwiczeń dotycza˛ jedynie grup podstawowych. Spo- sób zaliczania ćwiczeń w grupie zaawansowanej jest ogłaszany przez prowadzacego ˛ x A.3. Obsada zaj˛eć i konsultacje te ćwiczenia i nie jest opisany w niniejszych notatkach. Rotacja prowadzacych ˛ nie obejmuje grupy zaawansowanej. A.3. Obsada zaje˛ ć i konsultacje Obsada zaj˛eć dydaktycznych jest ogłoszona w Terminarzu zaj˛eć na dany rok aka- demicki, dost˛epnym pod adresem http://www.ii.uni.wroc.pl/~pacholsk/logter.phtml Każdy student ma niepodważalne prawo do bezpośredniej rozmowy z prowadza- ˛ cymi na temat zaj˛eć, w których uczestniczy. Uważamy, że z takich spotkań, tj. kon- sultacji, studenci korzystaja˛ nawet zbyt mało. Serdecznie zapraszajac ˛ na konsultacje mamy jednak prośb˛e, by przestrzegać ustalonych przez prowadzacych˛ zasad. Każdy pracownik dydaktyczny wyznacza dwie godziny w tygodniu, w czasie których jest do dyspozycji studentów. Poszczególni prowadzacy ˛ ustalaja˛ także inne sposoby kon- sultacji. Pracownicy sp˛edzaja˛ w Instytucie znacznie wi˛ecej czasu, niż podane dwie godziny, ale poza dydaktyka˛ wykonuja˛ też wiele innych prac. Dlatego prosimy trak- tować ze zrozumieniem ogłoszenia typu „prosz˛e studentów o nieprzychodzenie poza godzinami konsultacji”. Prośba o respektowanie podanych terminów dotyczy szcze- gólnie spraw technicznych, takich jak reklamacje dotyczace ˛ rankingu, czy wpisy ocen do indeksów. Studentów zapisanych na przedmiot jest ponad stu, a prowadzacy ˛ — je- den. Nie chcemy, żeby studenci odnieśli wrażenie, że prowadzacy ˛ staraja˛ si˛e od nich izolować. Chodzi tylko o to, by nasze kontakty z duża˛ liczba˛ studentów przebiegały sprawnie i nie dezorganizowały naszej pracy w Instytucie. Godziny konsultacji można znaleźć m. in. w Terminarzu zaj˛eć i na stronach do- mowych prowadzacych. ˛ Poza prowadzacymi ˛ wykład, repetytorium i ćwiczenia, zaj˛ecia obsługuje także sekretarz dydaktyczny. Do jego zadań należy m. in. przygotowywanie rankingów ćwi- czeń i wyliczanie ocen końcowych. Wszelkie problemy techniczne dotyczace ˛ punk- tacji za zadania, zadania domowe i kartkówki prosz˛e wyjaśniać nie z prowadzacymi ˛ ćwiczenia, lecz bezpośrednio u sekretarza dydaktycznego w podanych przez niego terminach.  B Literatura Podstawowym podr˛ecznikiem do wykładu jest skrypt: 1. Jerzy Tiuryn, Wst˛ep do teorii mnogości i logiki, który można zakupić w sekre- tariacie Instytutu, pok. 29 lub wypożyczyć w bibliotece Instytutu (10 egzem- plarzy, sygnatury: S.3315, S.3316, S.3317, S.3318, S.3319, S.3320, S.3321, S.3322, S.3323, S.3324). Wersja elektroniczna jest dost˛epna pod adresem: http://www.mimuw.edu.pl/~tiuryn/ Spośród licznych podr˛eczników dost˛epnych w bibliotekach i ksi˛egarniach warto wymienić: 2. Kazimierz Kuratowski, Wst˛ep do teorii mnogości i topologii, PWN, Warszawa, 1982. Krótkie wprowadzenie do teorii mnogości. W bibliotece Instytutu jest 10 egzemplarzy, sygnatury: II 1310, II 1373, II 5874, II 4609, II 8355, S.3285, S.3382, S.3395, S.3410 oraz tłumaczenie angielskie: II 116. 3. Kazimierz Kuratowski, Andrzej Mostowski, Teoria mnogości, PWN, Warsza- wa, 1978. Obszerny wykład teorii mnogości. W bibliotece Instytutu sa˛ dwa egzemplarze, sygnatury: II 286, II 8358. 4. Wiktor Marek, Janusz Onyszkiewicz, Elementy logiki i teorii mnogości w za- daniach, PWN, Warszawa, 2000. Obszerny zbiór prostych, typowych zadań. W bibliotece Instytutu jest 12 egzemplarzy, sygnatury: II 2463, II 1180, II 6859, S.2752, II 8231, S.3156, S.3157, S.3158, S.3159, II 8334, S.3207, S.3208. 5. Helena Rasiowa, Wst˛ep do matematyki współczesnej, PWN, Warszawa, 1999. Klasyczny podr˛ecznik podstaw logiki i teorii mnogości. W bibliotece Insty- tutu jest 14 egzemplarzy, sygnatury: S.2529, S.2687, I 7767, I 8144, S.3127, S.3128, S.3129, S.3164, S.3165, S.3166, S.3204, S.3205, S.3206, S.3242. xii 6. Kenneth A. Ross, Charles R. B. Wright, Matematyka dyskretna, PWN, War- szawa, 1986. Wbrew tytułowi ksiażka ˛ zawiera sporo elementarnie wyłożonego materiału z logiki i teorii mnogości. W bibliotece Instytutu jest 16 egzempla- rzy, sygnatury: S. 2936, S. 2937, S. 3301, S. 3302, S. 3303, S. 3304, S. 3305, S. 3338, S. 3339, II 7922, II 8535, II 8582, II 8890, II 8891, II 8954 i II 8955, oraz oryginał angielski (Discrete Mathematics, Prentice Hall, 1988): II 7074 i II 7133. 7. Jerzy Słupecki, Ludwik Borkowski, Elementy logiki matematycznej i teorii mnogości, PWN, Warszawa, 1963. W bibliotece Instytutu sa˛ trzy egzemplarze, sygnatury: S. 804, S. 3571 i S. 3572.  C Zasady prowadzenia i zaliczania ćwiczeń Poniższy regulamin dotyczy jedynie zaj˛eć w grupach podstawowych i nie obej- muje grupy zaawansowanej. C.1. Wstep ˛ Zasadniczym celem ćwiczeń z przedmiotu Logika dla informatyków jest ułatwie- nie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego se- mestru. Ocena z ćwiczeń jest ocena˛ jakości i intensywności pracy studenta w trakcie semestru, w odróżnieniu od egzaminu z przedmiotu Logika dla informatyków, który ocenia stan wiedzy studenta w chwili zakończenia semestru. Wykładowca ogłasza z odpowiednim wyprzedzeniem numery zadań z niniejszego zbioru. Studenci rozwiazuj ˛ a˛ podane zadania samodzielnie w domu. Jeżeli student ma watpliwości ˛ i chciałby je skonsultować z prowadzacym, ˛ powinien to uczynić w czasie godzin konsultacji prowadzacego.˛ Zakłada si˛e przy tym, że studenci b˛eda˛ dażyć ˛ do pewnej samodzielności w pracy nad opanowaniem przedmiotu. Zach˛eca si˛e także studentów do wspólnej nauki. Podstawa˛ do wystawienia oceny jest liczba zadań, które student rozwiazał ˛ w trak- cie całego semestru i, pomijajac ˛ wyjatkowe ˛ przypadki, ocena zależy w sposób li- niowy od tej ilości. Prowadzacy ˛ spotyka si˛e ze studentami regularnie na ćwiczeniach, aby ustalić faktyczna˛ liczb˛e zadań rozwiazanych ˛ przez każdego studenta. Dlatego po- mimo iż na zaj˛eciach powinna panować swobodna atmosfera, nie należy zapominać, że każde ćwiczenia sa˛ w istocie sprawdzianem wiedzy studentów. Prezentowanie roz- wiazań ˛ na tablicy całej grupie studentów ma także walor dydaktyczny, pozwala bo- wiem osobom które nie poradziły sobie z zadaniem na poznanie jego wzorcowego rozwiazania ˛ (z określonych niżej zasad szczegółowych wynika, że rozwiazanie˛ pre- zentuja˛ jedynie studenci dobrze przygotowani). Ocena studenta jest bezwzgl˛edna, tj. niezależna od osiagni˛ ˛ eć innych uczestników zaj˛eć. xiv C.2. Szczegółowe zasady prowadzenia zaj˛eć Numery zadań obowiazuj ˛ acych ˛ na nast˛epny tydzień sa˛ ogłaszane na wykładzie. Sa˛ one także wymienione w Terminarzu zaj˛eć na dany rok. Podczas całego semestru jest prowadzony ranking ćwiczeń zawierajacy ˛ zestawienie aktualnie zdobytej liczby punktów przez każdego studenta i prognoz˛e oceny końcowej. Po zakończeniu seme- stru ranking zawiera ostateczne wyniki ćwiczeń. We wszelkich sprawach dotycza- ˛ cych liczby zdobytych punktów i zadań domowych studenci winni zgłaszać si˛e do sekretarza dydaktycznego w czasie jego godzin konsultacji. Na każde z około 13 zaj˛eć zadaje si˛e przeci˛etnie 8 zadań. W semestrze zadaje si˛e wi˛ec do rozwiazania ˛ około stu zadań. Niniejsze notatki zawieraja˛ 822 zadania, a wi˛ec spory nadmiar. Zach˛eca si˛e studentów do rozwiazywania ˛ także pozostałych zadań. Data ogłoszenia ocen z ćwiczeń jest podana w Terminarzu zaj˛eć. Tego samego dnia w podanych godzinach studenci winni przyjść do sekretarza dydaktycznego ce- lem uzyskania wpisów do indeksów. W tym terminie b˛edzie też można wyjaśniać wszelkie problemy dotyczace ˛ liczby zdobytych punktów z ćwiczeń. Wpisy zaliczeń do indeksów w innych terminach nie b˛eda˛ dokonywane. Pierwsze ćwiczenia w semestrze nie sa˛ punktowane. Na zaj˛eciach sa˛ rozwiazy- ˛ wane zadania z rozdziału 0 niniejszych notatek. C.2. Szczegółowe zasady prowadzenia zaje˛ ć 1. Co najmniej na trzy dni (zwykle na tydzień) przed zaj˛eciami jest ogłaszana (w trakcie wykładu, w gablocie w hallu, na stronie WWW wykładu itp.) li- sta numerów zadań z niniejszego zbioru. Na ćwiczeniach sa˛ rozwiazywane ˛ wybrane zadania z tej listy. Prowadzacemu ˛ pozostawia si˛e decyzj˛e odnośnie wyboru zadań do rozwiazania. ˛ W roku akademickim 2004/5 b˛edzie wdrażany elektroniczny system zgłaszania zadań. Decyzja o wyborze tego systemu lub powrocie do tradycyjnego sposobu de- klarowania zadań zostanie podj˛eta w odpowiedniej chwili i ogłoszona na wykładzie. W zależności od tej decyzji b˛edzie obowiazywał ˛ jeden z poniższych punktów 2a lub 2b. 2a. Przed rozpocz˛eciem zaj˛eć student wypełnia kupon wpisujac˛ numery zadań z li- ˛ 1 Kartka powinna być wypełniona czytelnie, zawie- sty, które potrafi rozwiazać. rać dat˛e, jednoznacznie wpisane numery zadań2 oraz imi˛e i nazwisko studenta. Bezpośrednio po wejściu do sali ćwiczeniowej prowadzacy˛ zaj˛ecia zbiera ku- pony. Gdy prowadzacy ˛ przychodzi do sali ćwiczeniowej, kupony powinny być już wypełnione przez studentów tak, by mogły być natychmiast zebrane i by 1 Gotowe kupony można wyciać ˛ z ostatnich stron niniejszej ksiażeczki. ˛ 2 Niedopuszczalne sa˛ sformułowania typu „pierwsza cz˛eść zadania 7” itp. Zadanie jest niepodzielna˛ całościa˛ a deklaracja studenta powinna być jednoznaczna: tak lub nie. C. Zasady prowadzenia i zaliczania ćwiczeń xv prowadzacy ˛ nie musiał opóźniać rozpocz˛ecia zaj˛eć oczekujac ˛ na wypełnienie kuponów. 2b. Przed rozpocz˛eciem zaj˛eć student łaczy ˛ si˛e przy pomocy przegladarki ˛ interne- towej z serwerem systemu deklaracji znajdujacym ˛ si˛e pod adresem http://www.ii.uni.wroc.pl/deklaracje/ i wypełnia elektroniczny formularz zgłoszenia zadań. Na pi˛eć minut przed roz- pocz˛eciem zaj˛eć przyjmowanie deklaracji zostaje wstrzymane, a prowadzacy ˛ otrzymuja˛ wydruk wypełnionych kuponów. 3. Po rozpocz˛eciu zaj˛eć dokonywanie jakichkolwiek zmian w treści złożonych deklaracji3 jest niemożliwe. 4. Rozwiazanie ˛ danego zadania na tablicy przedstawia jedna z osób, wybrana przez prowadzacego, ˛ która zgłosiła gotowość rozwiazania ˛ tego zadania.4 Pro- wadzacy ˛ ma prawo przerwać osobie referujacej ˛ w dowolnym momencie i po- prosić inne osoby, które zgłosiły gotowość rozwiazania ˛ danego zadania, o kon- tynuowanie.5 5. Na każdych zaj˛eciach student zdobywa liczb˛e punktów równa˛ sumie warto- ści zadań, które zgłosił do rozwiazania ˛ z listy przewidzianej na dane zaj˛ecia, z wyjatkiem ˛ przypadków opisanych w punktach 8 i 9. 6. W ciagu ˛ semestru student ma obowiazek ˛ dostarczyć rozwiazania ˛ dwóch za- dań domowych. Na każdych zaj˛eciach prowadzacy ˛ wyznaczaja˛ po około trzy osoby w każdej grupie ćwiczeniowej. Te osoby maja˛ obowiazek ˛ przynieść na nast˛epne ćwiczenia prac˛e pisemna,˛ napisana˛ czytelnie na arkuszu papieru for- matu A4 lub wydrukowana˛ na komputerze. Zadania domowe maja˛ rozwinać ˛ u studentów zdolność jasnego, precyzyjnego i czytelnego redagowania rozwia- ˛ zań zadań. Za prac˛e można otrzymać od 0 do 5 punktów. Oceniona praca jest zwracana autorom w kolejnym tygodniu. Zadania sprawdza sekretarz dydak- tyczny. 3 Np. prośby o wycofanie lub dopisanie jakiegoś zadania. 4 Niniejsze regulacje nie ustalaja˛ sposobu wyboru tej osoby. Może on być dokonany losowo. Prowa- dzacy ˛ może też np. cz˛eściej wybierać osoby, które w przeszłości nie poradziły sobie, mimo zadeklarowanej ch˛eci, z rozwiazaniem ˛ zadania na tablicy. Może również przedstawić rozwiazanie ˛ tego zadania samodziel- nie albo pozostawić to rozwiazanie ˛ ochotnikowi. 5 Niniejsze regulacje nie precyzuja˛ post˛epowania w sytuacji, gdy nast˛epna osoba stwierdzi, że jej sposób rozumowania jest zupełnie inny. Może wówczas rozpoczać ˛ referowanie rozwiazania ˛ od poczatku. ˛ Decyzja należy do prowadzacego. ˛ xvi C.2. Szczegółowe zasady prowadzenia zaj˛eć punkty ocena −∞ ÷ 74 ndst 75 ÷ 87 dst 88 ÷ 100 dst+ 101 ÷ 113 db 114 ÷ 126 db+ 127 ÷ +∞ bdb Tablica C.1. Sposób przeliczania liczby punktów na ocen˛e z ćwiczeń 7. Student powinien znać definicje wprowadzanych na wykładzie poj˛eć i sformu- łowania podstawowych twierdzeń. Oczekujemy, że przed każdym wykładem i każdymi ćwiczeniami studenci b˛eda˛ przypominać sobie wcześniej poznany materiał. Aby ułatwić studentom systematyczne powtarzanie wcześniej pozna- nego materiału, ćwiczenia moga˛ rozpoczynać si˛e od bardzo prostej kartkówki sprawdzajacej ˛ znajomość poj˛eć wprowadzanych na wykładzie oraz podstawo- wych faktów (według niniejszych notatek do wykładu). Za znajomość defini- cji i podstawowych twierdzeń — czyli za poprawna˛ odpowiedź na wszystkie pytania zadane w kartkówce — student otrzymuje 10 punktów. W semestrze odb˛edzie si˛e około czterech kartkówek. 8. Jeżeli podczas przedstawiania rozwiazania ˛ na tablicy okaże si˛e, że student po- pełnił bład ˛ (np. przeoczył trudność lub źle zrozumiał treść zadania) i nie jest w stanie rozwiazać ˛ poprawnie tego zadania, nie otrzymuje punktów za to za- danie i dodatkowo traci dwa razy tyle punktów, ile można było zdobyć za jego poprawne rozwiazanie. ˛ 9. Jeżeli okaże si˛e, że student oświadczył nieprawd˛e i nie umie w ogóle rozwia- ˛ zać zadania lub nawet nie rozumie jego treści, traci wszystkie punkty zdobyte danego dnia oraz dodatkowo 10 punktów.6 W ten sam sposób jest traktowany student, który nie przyniósł pracy domowej, opisanej w punkcie 6. 10. Liczba punktów uzyskana przez studenta w ciagu ˛ całego semestru jest suma˛ liczby punktów zadeklarowanych na ćwiczeniach (wraz z otrzymanymi punk- tami karnymi), punktów za zadania domowe i punktów z kartkówek. Ocena końcowa z zaj˛eć jest wystawiana na podstawie tej liczby, według tablicy C.1. 6 Z punktu widzenia interesów studenta okazuje si˛e krytyczne rozróżnienie mi˛edzy tym punktem i po- przednim. Niestety, mimo jasnego sformułowania, chodzi tu o kwesti˛e merytoryczna˛ co do której podanie ścisłego algorytmu post˛epowania jest niemożliwe. Rozróżnienie to pozostaje do decyzji prowadzacego. ˛ C. Zasady prowadzenia i zaliczania ćwiczeń xvii W ciagu ˛ semestru do rozwiazania ˛ zostana˛ przedstawione zadania o łacznej ˛ licz- bie punktów nie mniejszej niż 104. Oznacza to, że łacznie ˛ z punktami za zada- nia domowe (10) i za kartkówki (40) można uzyskać co najmniej 154 punkty. 11. Ocena końcowa nie podlega poprawianiu po zakończeniu semestru. Nie ma kolokwiów poprawkowych.7 12. Studenci po zapisaniu si˛e do grup ćwiczeniowych nie moga˛ ich zmieniać, mimo iż wszystkie zaj˛ecia odbywaja˛ si˛e w tym samym czasie. 13. Podczas referowania zadań przy tablicy student nie może mieć przy sobie no- tatek. 7 Student powinien mieć świadomość, że zaj˛eć można nie zaliczyć. W szczególności utrata punktów zgodnie z paragrafem 9 może jednoznacznie i nieodwołalnie skazać studenta na niezaliczenie zaj˛eć i ko- nieczność powtarzania przedmiotu w nast˛epnym roku lub skreślenie z listy studentów.  D Egzaminy Ocena,˛ jaka˛ student otrzymuje z przedmiotu, jest wynik egzaminu zasadniczego. W razie otrzymania oceny niedostatecznej student ma prawo przystapić ˛ do egzaminu poprawkowego. W razie przyłapania na ściaganiu ˛ podczas którejkolwiek cz˛eści egzaminu student otrzymuje ocen˛e niedostateczna.˛ Ocena ta jest ostateczna i nie podlega poprawianiu, a sprawa tego studenta jest kierowana do Dziekana. Na egzamin należy przynieść przybory do pisania (pióro, długopis) i dowolny dokument ze zdj˛eciem w celu potwierdzenia tożsamości (dowód osobisty, paszport, legitymacja studencka, indeks itp). W trakcie egzaminu indeksy nie b˛eda˛ zbierane. Używanie notatek i własnego papieru jest niedozwolone. Wnoszenie toreb, wierzch- nich okryć i wszelkich innych ruchomości na sal˛e egzaminacyjna˛ jest niedopusz- czalne. Studenci powinni pozostawić je np. w szafkach w szatni. Strój odświ˛etny na egzaminie nie jest wymagany. Zarówno za egzamin zasadniczy (dwucz˛eściowy), jak i poprawkowy (jednocz˛e- ściowy) można otrzymać od −100 do 100 punktów. Jeżeli punktacja za zadanie eg- zaminacyjne wynosi n, znaczy to, że za rozwiazanie ˛ tego zadania można otrzymać od −n do n punktów. Punkty ujemne b˛eda˛ przyznawane za umieszczenie w rozwiaza- ˛ niu odpowiedzi kompromitujaco ˛ fałszywych. Za brak rozwiazania ˛ zadania otrzymuje si˛e 0 punktów. Liczba punktów możliwych do zdobycia na egzaminie może zostać zwi˛ekszona poprzez dodanie zadań bonusowych. Do wyników egzaminu zasadniczego i poprawkowego dolicza si˛e punkty bonu- sowe za zaliczenie ćwiczeń. Liczba punktów bonusowych jest cz˛eścia˛ całkowita˛ ilo- razu: (C −75)/10, gdzie C oznacza całkowita˛ liczb˛e punktów uzyskanych na zalicze- nie ćwiczeń w semestrze bezpośrednio poprzedzajacym ˛ egzamin. Osobom, które za- liczyły ćwiczenia w poprzednich latach punktów bonusowych si˛e nie dolicza. Studen- tom odbywajacym˛ ćwiczenia w grupie zaawansowanej punktów bonusowych si˛e nie dolicza. Punkty z egzaminu zasadniczego i poprawkowego przeliczaja˛ si˛e na oceny zgodnie z tablica˛ D.2. Terminy egzaminów, miejsca ich przeprowadzenia, przydział studentów do sal, terminy ogłoszenia wyników oraz miejsca i terminy konsultacji poegzaminacyjnych xx D.1. Egzamin zasadniczy punkty ocena −100 ÷ 49 ndst 50 ÷ 59 dst 60 ÷ 69 dst+ 70 ÷ 79 db 80 ÷ 89 db+ 90 ÷ +∞ bdb Tablica D.2. Sposób przeliczania liczby punktów na ocen˛e z egzaminu sa˛ podane w Terminarzu zaj˛eć. Wszelkie watpliwości ˛ dotyczace ˛ sposobu oceniania egzaminu i otrzymanych ocen studenci powinni wyjaśniać w trakcie konsultacji po- egzaminacyjnych. W czasie konsultacji po egzaminie końcowym i poprawkowym studenci winni zgłosić si˛e z indeksami i kartami zaliczeń celem otrzymania wpisu oceny do indeksu. Wpisy do indeksów i konsultacje dotyczace ˛ wyników egzaminów w innych terminach nie b˛eda˛ dokonywane. Treść zadań egzaminacyjnych oraz wyniki egzaminów sa˛ ogłaszane w Terminarzu zaj˛eć po zakończeniu egzaminu. D.1. Egzamin zasadniczy Ocena z egzaminu zasadniczego jest wystawiana na podstawie sumy punktów z dwóch egzaminów — połówkowego i końcowego — i punktów bonusowych. Eg- zamin połówkowy odbywa si˛e w połowie semestru, egzamin końcowy zaś w sesji zimowej. Na egzaminie połówkowym można zdobyć do 40 punktów, na egzaminie zasadniczym zaś 60 punktów. Zakres materiału na egzaminie połówkowym obejmuje zaj˛ecia poprzedzajace ˛ egzamin. Zakres materiału na egzaminie końcowym obejmuje cały semestr. W razie nieobecności na egzaminie połówkowym lub końcowym spowodowa- nej choroba˛ student ma obowiazek ˛ dostarczyć egzaminatorowi (osobiście, poczta˛ lub przez osoby trzecie) zwolnienie lekarskie w ciagu ˛ trzech dni liczac ˛ od dnia egzaminu. Nieusprawiedliwiona w ten sposób nieobecność studenta na którejkolwiek cz˛eści eg- zaminu zasadniczego jest równoznaczna z uzyskaniem zerowej liczby punktów z tego egzaminu. W szczególnych przypadkach decyzj˛e o usprawiedliwieniu nieobecności na egzaminie może podjać ˛ Dziekan. D. Egzaminy xxi D.1.1. Egzamin połówkowy Wszyscy studenci zapisani na przedmiot Logika dla Informatyków maja˛ obowia- ˛ zek stawić si˛e na ten egzamin. W razie usprawiedliwionej nieobecności na egzaminie połówkowym całkowita˛ liczb˛e punktów z egzaminu zasadniczego oblicza si˛e na podstawie wyników egza- minu końcowego, mnożac ˛ liczb˛e zdobytych na nim punktów przez 10/6. D.1.2. Egzamin końcowy Do egzaminu końcowego moga˛ przystapić ˛ jedynie osoby, które uzyskały zalicze- nie ćwiczeń. Wszyscy studenci zapisani na przedmiot „Logika dla Informatyków”, którzy uzyskali zaliczenie ćwiczeń, maja˛ obowiazek ˛ stawić si˛e na ten egzamin. W razie usprawiedliwionej nieobecności na egzaminie końcowym egzaminator ustali dla danej osoby inny termin egzaminu w sesji zimowej. D.2. Egzamin poprawkowy W razie otrzymania oceny niedostatecznej z egzaminu zasadniczego student przy- st˛epuje do egzaminu poprawkowego w sesji poprawkowej. Nieobecność na egzaminie poprawkowym (niezależnie od przyczyn — usprawie- dliwionych badź ˛ nie) jest równoznaczna z uzyskaniem oceny niedostatecznej z tego egzaminu. Ocena z egzaminu poprawkowego nie podlega poprawianiu. xxii Notacja matematyczna Notacja matematyczna Matematycy używaja˛ liter pochodzacych ˛ z różnych krojów pisma i różnych alfa- betów. Poniżej sa˛ zebrane alfabety użyte w niniejszych notatkach. Pismo łacińskie, gotyckie, blokowe i kaligraficzne a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F GH I J K L MN O P Q R S T U VW X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z ABC D E F GH I J K L MN O P Q R S T U VW X YZ A B C D E F GH I J K LMN O P Q R S T U VWX Y Z AB C D E F G H I J K L MN O P Q R S T U V WX Y Z Alfabet grecki Niektóre małe litery greckie maja˛ dwa warianty pisowni. Przeważnie używa si˛e pierwszego z podanych. A α alfa I ι jota P ρ, % ro B β beta K κ kappa 6 σ, ς sigma 0 γ gamma 3 λ lambda T τ tau 1 δ delta M µ mi ϒ υ ypsilon E , ε epsilon N ν ni 8 φ, ϕ fi Z ζ dzeta 4 ξ ksi X χ chi H η eta O o omikron 9 ψ psi 2 θ, ϑ teta 5 π, $ pi  ω omega Alfabet hebrajski Z alfabetu hebrajskiego używamy pierwszej litery ℵ, która nazywa si˛e alef.  0 Zadania na dobry poczatek ˛ Zadania z bieżacego ˛ rozdziału sa˛ rozwiazywane ˛ na pierwszych ćwiczeniach w se- mestrze. Zadań tych nie deklaruje si˛e i nie sa˛ one punktowane. Zadanie 1. Oto przykłady trzech wnioskowań przez indukcj˛e: 1. Pokaż˛e, że wszystkie liczby naturalne sa˛ parzyste. Oczywiście 0 jest liczba˛ parzy- sta.˛ Niech n b˛edzie dowolna˛ liczba˛ naturalna˛ i załóżmy, że dla wszystkich k < n , k jest parzyste. Niech n 1 i n 2 b˛edzie dowolnym rozbiciem liczby n na sum˛e liczb mniejszych (tzn. n = n 1 + n 2 ). Ponieważ n 1 oraz n 2 sa˛ mniejsze od n , n 1 i n 2 sa˛ parzyste, a wi˛ec n jest parzyste jako suma dwóch liczb parzystych. 2. Pokaż˛e, że wszystkie dodatnie liczby naturalne sa˛ nieparzyste. Oczywiście 1 jest liczba˛ nieparzysta.˛ Niech n b˛edzie dowolna˛ liczba˛ naturalna˛ i załóżmy, że dla wszyst- kich k < n , k jest nieparzyste. Niech 1, n 1 i n 2 b˛edzie dowolnym rozbiciem liczby n na sum˛e trzech liczb mniejszych (tzn. n = n 1 + n 2 + 1). Ponieważ n 1 oraz n 2 sa˛ mniejsze od n , n 1 i n 2 sa˛ nieparzyste, a wi˛ec n jest nieparzyste jako suma dwóch liczb nieparzystych i liczby 1. 3. Pokaż˛e, że wszystkie proste na płaszczyźnie sa˛ równoległe. Rozważmy jedno- elementowy zbiór prostych na płaszczyźnie. Oczywiście wszystkie proste należace ˛ do tego zbioru sa˛ do siebie równoległe. Załóżmy, że w każdym n -elementowym zbiorze prostych wszystkie proste sa˛ do siebie równoległe. Rozważmy teraz n + 1- -elementowy zbiór prostych. Ustalmy w nim jedna˛ prosta˛ p. Na mocy założenia in- dukcyjnego wszystkie pozostałe n prostych jest do siebie równoległe. Ustalmy te- raz inna˛ prosta˛ q. Na mocy założenia indukcyjnego wszystkie pozostałe n prostych jest również do siebie równoległe. Ponieważ relacja równoległości prostych jest prze- chodnia, wszystkie n +1 prostych jest równoległe. Na mocy zasady indukcji matema- tycznej każdy zbiór prostych na płaszczyźnie zawiera wyłacznie ˛ proste równoległe. W szczególności dotyczy to zbioru wszystkich prostych na płaszczyźnie. Które z tych rozumowań jest poprawne? Wskaż bł˛edy popełnione w bł˛ednych rozu- mowaniach. 2 0. Zadania na dobry poczatek ˛ Zadanie to zostało tu zamieszczone po to, by pokazać, że matematyka jest nauka˛ ścisła.˛ Nie ma dowodów „prawie dobrych”. Nawet najdrobniejsza luka w rozumo- waniu powoduje, że staje si˛e ono bezwartościowe. Uprawiajac ˛ matematyk˛e musimy wypowiadać si˛e bardzo jasno i precyzyjnie, i zwracać baczna˛ uwag˛e, czy nasze ro- zumowania nie zawieraja˛ ukrytych bł˛edów. Wi˛ekszość zadań w niniejszym zbiorze zawiera prawdziwe twierdzenia. Dlatego bł˛edy w dowodach tych twierdzeń nie pro- wadza˛ do tak spektakularnych głupstw, jak w tym zadaniu. Nie oznacza to jednak, że możemy przedstawiać fałszywe dowody tych twierdzeń. Takie dowody sa˛ bowiem równie złe i bezużyteczne, jak fałszywe dowody fałszywych twierdzeń! Celem kolejnych zadań jest zwrócenie uwagi na fakt, że matematyka jest sztuka˛ przeprowadzania rozumowań a nie wykonywania rachunków. Wrażenie, że zadania te sa˛ mniej „matematyczne” niż np. ćwiczenia polegajace ˛ na wyznaczeniu całki nie- oznaczonej jest zupełnie bł˛edne. Przeciwnie, sposób ich rozwiazywania ˛ ma wi˛ecej wspólnego z metodami pracy matematyków niż sposoby rozwiazywania ˛ zadań ra- chunkowych. Zadanie 2. Rozważmy kwadrat o boku n, gdzie n ≥ 3, z którego usuni˛eto dwa na- przeciwległe narożniki o wymiarach 1 × 1, jak na poniższym rysunku: n 1 2 1 n 1 Dla jakich n można tak otrzymana˛ figur˛e pokryć prostokatami ˛ o wymiarach 1 × 2? (Prostokaty ˛ można obracać.) Zadanie 3. Jest rok 2036. Zbliża si˛e otwarcie nowego odcinka autostrady A3654, wysłano wi˛ec robotników drogowych, by ustawili znaki przy każdym z sześciu wy- jazdów z autostrady na 50-kilometrowym odcinku biegnacym ˛ na południe z Kuro- zw˛ek do Szczekocina, w tym przy wyjeździe do M˛ecikału. Przy każdym wyjeździe robotnicy maja˛ ustawić znak odległości do Szczekocina, znak z numerem drogi prze- cinajacej ˛ autostrad˛e przy danym wyjeździe (w tym znak z numerem drogi 197), znak z nazwa˛ miasta, do którego można dojechać wybierajac ˛ dany wyjazd i znak ozna- czajacy ˛ usługi lub ciekawe miejsca znajdujace ˛ si˛e przy danym wyjeździe. Nieszcz˛e- śliwie dla robotników projektant drogi, b˛edac˛ amatorem łamigłówek, przygotował instrukcj˛e rozstawienia znaków w postaci zagadki logicznej zamieszczonej poniżej. 0. Zadania na dobry poczatek ˛ 3 Robotnicy sa˛ bezradni. Czy mógłbyś im pomóc ustawić po cztery znaki przy każdym z sześciu wyjazdów z autostrady1 ? 1. Wyjazd do Strzebielina jest 20 kilometrów dalej od Szczekocina niż wyjazd, przy którym można kupić jedzenie. 2. Wyjazd do Leszczydołu jest dwa razy dalej na północ od Szczekocina niż wy- jazd do parku narodowego. 3. Znak „noclegi” nie jest ustawiony razem z kierunkowskazem do drogi 88. 4. Wyjazd do Bordziłówki jest 20 kilometrów bliżej Szczekocina niż wyjazd do drogi 770. 5. Wyjazd do Pieścirogów znajduje si˛e 5 kilometrów na południe od wyjazdu ze stacja˛ benzynowa.˛ 6. Nie, znak „ciekawe widoki” nie znajduje si˛e przy wyjeździe do Strzebielina. 7. Wyjazd do drogi 56 znajduje si˛e 20 kilometrów na południe od wyjazdu do Krzczonowa. 8. Znak „park narodowy” i kierunkowskaz do Bordziłówki znajduja˛ si˛e przy róż- nych wyjazdach. 9. Wyjazd do drogi 29 znajduje si˛e 5 kilometrów dalej od Szczekocina niż wyjazd na kemping. 10. Pierwszy wyjazd znajduje si˛e 10 kilometrów na południe od Kurozw˛ek, ostatni zaś — szósty — 5 kilometrów na północ od Szczekocina. 11. Wyjazd do drogi 213, który nie jest wyjazdem do Leszczydołu, nie stoi razem ze znakiem „noclegi”. 12. Ani Strzebielin, ani Leszczydół nie znajduja˛ si˛e przy drodze 770. 13. Bordziłówka nie znajduje si˛e przy drodze 56. Zadanie 4. Oto fragment raportu policji sporzadzony ˛ przez młodego aspiranta: Świadek nie był zastraszony lub też, jeśli Henry popełnił samobójstwo, to te- stament odnaleziono. Jeśli świadek był zastraszony, to Henry nie popełnił sa- mobójstwa. Jeśli testament odnaleziono, to Henry popełnił samobójstwo. Jeśli Henry nie popełnił samobójstwa, to testament odnaleziono. Co komendant policji może wywnioskować z powyższego raportu (poza oczywistym faktem, że należy zwolnić aspiranta)? Odpowiedz na pytania: Czy świadek był zastra- szony? Czy Henry popełnił samobójstwo? Czy testament odnaleziono? 1 Ta zagadka jest spolszczona˛ wersja˛ łamigłówki Randalla L. Whipkey’a pochodzacej ˛ ze strony www.crpuzzles.com. Nazwy miejscowości wybrano ze skorowidza „Atlasu samochodowego Polski”. 4 0. Zadania na dobry poczatek ˛ Rozumowania, które przeprowadzamy, sa˛ cz˛esto tak subtelne i skomplikowane, że musimy używać sformalizowanego j˛ezyka, by móc przedstawić nasze idee dosta- tecznie precyzyjnie. Symboliki matematycznej nie należy nadużywać, jednak sprawne posługiwanie si˛e notacja˛ matematyczna˛ jest niezb˛edna˛ umiej˛etnościa.˛ Trzy kolejne zadania dotycza˛ właśnie tego zagadnienia. Zadanie 5. Funkcja f : R → R jest ciagła, ˛ jeśli
∀x0 ∈R ∀>0 ∃δ>0 ∀x∈R |x − x0 | < δ ⇒ | f (x) − f (x0 )| < . Nie używajac ˛ znaku negacji zapisz formuł˛e „funkcja f nie jest ciagła.” ˛ Zadanie 6. Liczba g ∈ R jest granica˛ (w sensie Cauchy’ego) funkcji f : R → R w punkcie x0 , jeśli
∀>0 ∃δ>0 ∀x∈R 0 < |x − x0 | < δ ⇒ | f (x) − g| < . Nie używajac ˛ znaku negacji zapisz formuł˛e „liczba g nie jest granica˛ funkcji f w punkcie x0.” Zadanie 7. Liczba g ∈ R jest granica˛ (w sensie Heinego) funkcji f : R → R w punkcie y, jeśli
∀x∈RN ( lim xn = y ∧ ∀n∈N xn 6= y) ⇒ lim f (xn ) = g. n→∞ n→∞ Nie używajac ˛ znaku negacji zapisz formuł˛e „liczba g nie jest granica˛ funkcji f w punkcie y.”  1 Rachunek zdań i rachunek kwantyfikatorów 1.1. Składnia rachunku zdań Definicja 1. Formuły rachunku zdań budujemy ze zmiennych zdaniowych i spójni- ków logicznych (funktorów zdaniotwórczych): fałszu ⊥, prawdy >, negacji ¬, ko- niunkcji ∧, alternatywy ∨, implikacji ⇒ i równoważności ⇔ w nast˛epujacy ˛ sposób: 1. Symbole ⊥ i > sa˛ formułami rachunku zdań. 2. Każda zmienna zdaniowa jest formuła˛ rachunku zdań. 3. Jeżeli φ, φ1 i φ2 sa˛ formułami rachunku zdań, to sa˛ nimi także: (¬φ), (φ1 ∧φ2 ), (φ1 ∨ φ2 ), (φ1 ⇒ φ2 ) i (φ1 ⇔ φ2 ). 4. Wszystkie formuły rachunku zdań można zbudować przy pomocy reguł opisa- nych w punktach 1–3. Zmienne zdaniowe b˛edziemy oznaczać literami: p, q, r , s itd., cz˛esto z indek- sami: p1 , p2 itd. Formuły zdaniowe b˛edziemy oznaczać literami: φ, ψ, ρ itd., cz˛esto również z indeksami: φ1 , φ2 itd. Dla wi˛ekszej czytelności b˛edziemy w formułach opuszczać nawiasy, zakładajac ˛ nast˛epujac ˛ a˛ kolejność wiazania ˛ (od najsilniejszego do najsłabszego): ¬, ∧, ∨, ⇒, ⇔ i przyjmujac,˛ że ∧, ∨ i ⇔ łacz˛ a˛ w lewo, tj. np. p ∨r ∨s znaczy ( p ∨ r ) ∨ s, zaś ⇒ — w prawo, tj. np. p ⇒ r ⇒ s znaczy p ⇒ (r ⇒ s). Zatem np. p ∨ q ∨ r ∧ s oznacza ( p ∨ q) ∨ (r ∧ s). 1.2. Wartości logiczne i znaczenie formuł zdaniowych Definicja 2. Zbiór wartości logicznych B = {T, F} zawiera dwa elementy: T (praw- da) i F (fałsz).1 Niech V oznacza zbiór zmiennych zdaniowych. Wartościowanie zmiennych, to odwzorowanie σ : V → B. Nadaje ono wartości logiczne zmiennym zdaniowym. 1 Oznaczenia pochodza˛ od angielskich słów true i false. 6 1.2. Wartości logiczne i znaczenie formuł zdaniowych φ ψ φ∧ψ φ ¬φ F F F ⊥ > F T F T F F T T F T F F T T T φ ψ φ∨ψ φ ψ φ⇒ψ φ ψ φ⇔ψ F F F F F T F F T F T T F T T F T F T F T T F F T F F T T T T T T T T T Rysunek 1. Znaczenie spójników logicznych Wartość logiczna dowolnej formuły zdaniowej zależy jedynie od wartościowa- nia wyst˛epujacych ˛ w niej zmiennych i można ja˛ wyznaczyć korzystajac ˛ z tabelek z rysunku 1. Dlatego mówimy, że wartościowanie zmiennych nadaje wartość lo- giczna˛ formułom. Formalnie, wartościowanie zmiennych σ wyznacza wartościowa- nie formuł σ̂ , które przypisuje wartości logiczne dowolnym formułom w nast˛epujacy ˛ sposób: σ̂ (⊥) = F σ̂ (>) = T σ̂ ( p) = σ ( p)  T, gdy σ̂ (φ) = F σ̂ (¬φ) = F, gdy σ̂ (φ) = T  T, gdy σ̂ (φ1 ) = T i σ̂ (φ2 ) = T σ̂ (φ1 ∧ φ2 ) = F, w p.p.  T, gdy σ̂ (φ1 ) = T lub σ̂ (φ2 ) = T σ̂ (φ1 ∨ φ2 ) = F, w p.p.  F, gdy σ̂ (φ1 ) = T i σ̂ (φ2 ) = F σ̂ (φ1 ⇒ φ2 ) = T, w p.p.  T, gdy σ̂ (φ1 ) = σ̂ (φ2 ) σ̂ (φ1 ⇔ φ2 ) = F, w p.p. Wartość logiczna˛ σ̂ (φ) ∈ B nazywamy wartościa˛ logiczna˛ formuły φ przy wartościo- waniu σ. Ponieważ dla danego wartościowania zmiennych wartościowanie formuł jest określone jednoznacznie, znak ˆ b˛edziemy opuszczać i zarówno wartościowanie 1. Rachunek zdań i rachunek kwantyfikatorów 7 zmiennych, jak i wartościowanie formuł b˛edziemy oznaczać tym samym symbolem i nazywać po prostu wartościowaniem. Definicja 3. Formuła jest: spełniona przy danym wartościowaniu zmiennych, jeżeli przy tym wartościo- waniu ma ona wartość T; spełnialna, jeżeli istnieje wartościowanie zmiennych, dla którego ta formuła jest spełniona; prawdziwa (jest tautologia), ˛ jeśli jest spełniona dla każdego wartościowania zmiennych; sprzeczna, jeśli nie jest spełniona (ma wartość F) dla żadnego wartościowania zmiennych. O formule spełnionej przy danym wartościowaniu zmiennych b˛edziemy niekiedy mówić, że jest prawdziwa przy tym wartościowaniu. W analogicznej sytuacji, gdy formuła nie jest spełniona, b˛edziemy ja˛ nazywać fałszywa˛ przy tym wartościowaniu. Obecnie zajmiemy si˛e sposobami sprawdzania, czy dana formuła jest tautologia.˛ 1.2.1. Metoda zero-jedynkowa Przykładami tautologii sa˛ formuły ¬( p ∨ q) ⇔ ¬ p ∧ ¬q oraz ¬( p ∧ q) ⇔ ¬ p ∨ ¬q zwane prawami de Morgana. Aby si˛e o tym przekonać rysujemy tabelk˛e (rysunek 2) umieszczajac ˛ w kolumnach 1 i 2 wartości zmiennych zdaniowych p i q. W kolumnie 3 umieszczamy wartości formuły p ∨ q wyliczone z użyciem tabelki dla alternatywy. W kolumnie 4 obliczamy, w oparciu o tabelk˛e negacji, wartości formuły ¬( p ∨ q). Kolumny 5 i 6 wyznaczamy również w oparciu o tabelk˛e negacji. Aby wy- znaczyć wartości formuły (¬ p) ∧ (¬q) korzystamy z wartości zapisanych w kolum- nach 5 i 6 i z tabelki koniunkcji. Ostatnia,˛ ósma˛ kolumn˛e wyznaczamy przy użyciu tabelki dla równoważności z wartości logicznych zapisanych w kolumnach 4 i 7. Po skonstruowaniu tabelki zauważamy, że dla każdego z czterech możliwych wartościo- wań zmiennych p i q formuła ¬( p ∨ q) ⇔ (¬ p) ∧ (¬q) ma wartość logiczna˛ T, jest wi˛ec tautologia.˛ 1.2.2. Skrócona metoda zerojedynkowa Sprawdzenie czy formuła jest tautologia˛ można znacznie przyspieszyć, jeśli za- miast bezmyślnie sprawdzać wartość formuły dla wszystkich możliwych wartościo- wań zmiennych, b˛edziemy świadomie poszukiwać wartościowania, dla którego for- muła nie jest spełniona. Ustalenie takiego wartościowania przekona nas, że formuła nie jest tautologia,˛ dojście do sprzeczności zaś — że nia˛ jest. Rozważmy dla ustale- nia uwagi formuł˛e (¬ p ⇒ ¬q) ⇒ ((¬ p ⇒ q) ⇒ q). Formuła ta nie jest spełniona, 8 1.2. Wartości logiczne i znaczenie formuł zdaniowych φ = ¬( p ∨ q) ⇔ ¬ p ∧ ¬q 1 2 3 4 5 6 7 8 p q p∨q ¬( p ∨ q) ¬p ¬q ¬ p ∧ ¬q φ F F F T T T T T F T T F T F F T T F T F F T F T T T T F F F F T Rysunek 2. Tabelkowa metoda sprawdzenia, że formuła φ jest tautologia˛ φ =(¬ p⇒¬q )⇒((¬ p⇒q )⇒q ) F T F T F F F T Rysunek 3. Wartościowanie, dla którego formuła φ nie jest spełniona jeśli poprzednik implikacji ¬ p ⇒ ¬q jest prawdziwy przy pewnym wartościowa- niu, jej nast˛epnik (¬ p ⇒ q) ⇒ q zaś fałszywy przy tym wartościowaniu. Formuła (¬ p ⇒ q) ⇒ q jest fałszywa tylko wówczas, gdy ¬ p ⇒ q jest spełniona oraz σ (q) = F. Ale ¬ p ⇒ q jest spełniona dla σ (q) = F tylko wówczas, gdy ¬ p nie jest spełniona, tj. gdy σ ( p) = T. Zauważamy na koniec, że przy wartościowaniu σ ( p) = T i σ (q) = F nasza wyjściowa formuła istotnie nie jest spełniona, nie jest wi˛ec tautologia˛ (rysunek 3). Rozważmy teraz formuł˛e φ = p ⇒ (q ⇒ p). Aby φ nie była spełniona, musi być σ ( p) = T oraz powinna nie być spełniona formuła q ⇒ p. Formuła ostatnia nie jest spełniona tylko wówczas, gdy σ (q) = T oraz σ ( p) = F. Zatem aby φ nie była spełniona, musiałoby być jednocześnie φ( p) = T i φ( p) = F, co jest niemożliwe. Formuła φ jest zatem tautologia˛ (rysunek 4). Przykład 4. Przykładami tautologii sa˛ ( p ⇒ (q ⇒ r )) ⇒ (( p ⇒ q) ⇒ ( p ⇒ r )) (¬ p ⇒ ¬q) ⇒ ((¬ p ⇒ q) ⇒ p) W zadaniach 8–26 udowodnij, że podane formuły sa˛ tautologiami. Zadanie 8 (modus ponens). ( p ⇒ q) ∧ p ⇒ q Zadanie 9 (modus tollens). ( p ⇒ q) ∧ ¬q ⇒ ¬ p 1. Rachunek zdań i rachunek kwantyfikatorów 9 φ = p⇒(q ⇒ p) F T F T F sprzeczność Rysunek 4. Ilustracja dowodu nie wprost, iż formuła φ jest tautologia˛ Zadanie 10 (prawo kompozycji). ( p ∨ q ⇒ r ) ⇒ p ⇒ r Zadanie 11 (prawo kompozycji). ( p ∨ q ⇒ r ) ⇒ q ⇒ r Zadanie 12 (prawo symplifikacji). p ∧ q ⇒ p Zadanie 13 (prawo symplifikacji). q ⇒ p ∨ q Zadanie 14 (prawo symplifikacji). p ⇒ q ⇒ p Zadanie 15 (prawo Dunsa Szkota). ¬ p ⇒ p ⇒ q Zadanie 16 (prawo dylematu konstrukcyjnego). ( p ⇒ r )∧(q ⇒ r )∧( p∨q) ⇒ r Zadanie 17 (prawo eksportacji). ( p ∧ q ⇒ r ) ⇒ p ⇒ q ⇒ r Zadanie 18 (prawo importacji). ( p ⇒ q ⇒ r ) ⇒ p ∧ q ⇒ r Zadanie 19 (prawo redukcji do absurdu). ( p ⇒ ¬ p) ⇒ ¬ p Zadanie 20 (prawo sprzeczności). ¬( p ∧ ¬ p) Zadanie 21 (prawo wyłaczonego ˛ środka). p ∨ ¬ p Zadanie 22 (prawo sylogizmu hipotetycznego). ( p ⇒ q) ⇒ (q ⇒ r ) ⇒ p ⇒ r Zadanie 23 (prawo Pierce’a). (( p ⇒ q) ⇒ p) ⇒ p Zadanie 24 (Prawo Claviusa). (¬ p ⇒ p) ⇒ p Zadanie 25 (Prawo Claviusa). ( p ⇒ ¬ p) ⇒ ¬ p Zadanie 26 (prawo tożsamości). p ⇔ p Powyższe tautologie były od dawna badane przez logików, gdyż opisuja˛ typowe schematy przeprowadzania rozumowań. Ich zwyczajowe nazwy podano w nawia- sach. 10 1.2. Wartości logiczne i znaczenie formuł zdaniowych W zadaniach 27–62 sprawdź, które z podanych formuł sa˛ (a) tautologiami, (b) for- mułami spełnialnymi, (c) formułami sprzecznymi. Zadanie 27. p ∨ q ∨ r ⇒ ¬ p ⇒ (q ∨ r ) ∧ ¬ p Zadanie 28. ( p ⇒ q) ⇔ ( p ∧ q ⇔ p) Zadanie 29. ( p ∨ q ⇒ r ) ⇒ ( p ⇒ r ) ∨ (q ⇒ r ) Zadanie 30. ( p ⇒ q) ∧ (r ⇒ s) ⇒ p ∧ s ⇒ q ∨ r Zadanie 31. p ∨ q ∨ r ⇒ (( p ∨ q) ∧ ¬r ) ∨ (r ∧ p ∧ q) Zadanie 32. (( p ∨ q) ∧ ¬r ) ∨ (r ∧ p ∧ q) ⇒ p ∨ q ∨ r Zadanie 33. ( p ∨ q ⇔ r ∨ s) ⇒ (( p ⇔ r ) ∨ (q ⇔ s)) Zadanie 34. ( p ⇔ r ) ∨ (q ⇔ s) ⇒ ( p ∨ q ⇔ r ∨ s) Zadanie 35. ( p ∧ q ⇔ r ∧ s) ⇒ (( p ⇔ r ) ∧ (q ⇔ s)) Zadanie 36. ( p ⇒ q ⇒ r ) ⇒ (( p ⇒ q) ⇒ ( p ⇒ r )) Zadanie 37. ( p ∨ q) ∧ ¬ p ⇒ q Zadanie 38. ( p ⇒ q) ⇒ p ∧ r ⇒ q Zadanie 39. ( p ⇒ q) ⇒ p ⇒ q ∨ r Zadanie 40. p ⇒ ¬ p ∨ q Zadanie 41. ( p ∨ q) ∧ ( p ⇒ q) ⇒ q ⇒ p Zadanie 42. ¬( p ∧ (¬ p ∧ q)) Zadanie 43. p ⇒ ¬q ∧ q ⇒ r Zadanie 44. ( p ⇒ q) ∧ (q ⇒ p) ⇒ p ∨ q Zadanie 45. ( p ∨ q ⇒ p ∨ ¬q) ⇒ ¬ p ∨ q Zadanie 46. ( p ∧ q) ∨ ( p ⇒ q) ⇒ p ⇒ q Zadanie 47. ( p ⇒ q) ∧ (q ⇒ r ) ⇒ ( p ⇒ r ) Zadanie 48. ( p ⇒ q) ∧ (r ⇒ s) ⇒ p ∨ r ⇒ q ∨ s 1. Rachunek zdań i rachunek kwantyfikatorów 11 Zadanie 49. ( p ∧ q ⇒ r ) ⇒ ( p ⇒ r ) ∧ (q ⇒ r ) Zadanie 50. ( p ⇒ q) ∧ (r ⇒ s) ⇒ p ∧ r ⇒ q ∧ s Zadanie 51. ( p ∧ q ⇒ r ) ∧ ( p ∨ q ⇒ ¬r ) ⇒ p ∧ q ∧ r Zadanie 52. ¬( p ⇒ q) ∧ (q ⇒ p) ⇒ p ∧ ¬q Zadanie 53. (( p ⇒ q) ⇒ q ⇒ r ) ⇒ (r ⇒ p) ⇒ q ⇒ p Zadanie 54. ( p ⇒ q) ∨ ( p ⇒ r ) ∨ ( p ⇒ s) ⇒ p ⇒ q ∨ r ∨ s Zadanie 55. ( p ⇒ q) ∧ (r ⇒ q) ∧ (s ⇒ q) ⇒ p ∧ r ∧ s ⇒ q Zadanie 56. ( p ⇒ q) ∧ (r ⇒ q) ∧ (s ⇒ q) ⇒ p ∧ r ∧ ¬s ⇒ q Zadanie 57. ( p ∧ q ⇒ r ) ∧ ( p ∧ q ⇒ ¬r ) ⇒ ¬ p ∧ ¬q ∧ ¬r Zadanie 58. (¬ p ∧ q) ∨ ( p ∨ ¬q) ⇒ ( p ⇒ q ∨ r ) ⇒ p ⇒ r Zadanie 59. ( p ∨ q) ∧ (r ∨ s) ⇒ (( p ⇒ q) ∨ ( p ⇒ r )) ∧ ((q ⇒ s) ∨ (q ⇒ p)) Zadanie 60. ( p ⇒ q) ∧ (r ⇒ s) ∧ (t ⇒ u) ⇒ p ∧ r ∧ t ⇒ q ∧ s ∧ u Zadanie 61. ( p ⇔ q) ∧ p ⇒ q Zadanie 62. (¬ p ⇒ ¬q) ⇒ (¬ p ⇒ q) ⇒ p Zadanie 63. Niech symbole φ i ψ oznaczaja˛ formuły zdaniowe. Udowodnij poniż- sze stwierdzenia lub podaj przykłady świadczace ˛ o ich fałszywości: 1. Jeśli φ ⇒ ψ jest tautologia˛ i φ jest tautologia,˛ to ψ jest tautologia.˛ 2. Jeśli φ ⇒ ψ jest spełnialna i φ jest spełnialna, to ψ jest spełnialna. 3. Jeśli φ ⇒ ψ jest tautologia˛ i φ jest spełnialna, to ψ jest spełnialna. 4. Jeśli φ ⇒ ψ jest spełnialna i φ jest tautologia,˛ to ψ jest spełnialna. 1.2.3. Równoważność formuł Definicja 5. Mówimy, że formuły φ i ψ sa˛ równoważne, jeśli dla każdego wartościo- wania przyjmuja˛ t˛e sama˛ wartość logiczna˛ (tj. gdy formuła φ ⇔ ψ jest tautologia). ˛ Przykład 6. Formuły ¬( p ∨ q) i ¬ p ∧ ¬q sa˛ równoważne. Zadanie 64. Udowodnij, że a) dowolne dwie tautologie, b) dowolne dwie formuły sprzeczne sa˛ równoważne. Czy dowolne dwie formuły spełnialne sa˛ równoważne? 12 1.2. Wartości logiczne i znaczenie formuł zdaniowych W zadaniach 65–79 udowodnij, że podane formuły sa˛ równoważne. Zadanie 65 (prawo transpozycji prostej). p ⇒ q oraz ¬q ⇒ ¬ p Zadanie 66 (prawo transpozycji złożonej). p ∧ q ⇒ r oraz p ∧ ¬r ⇒ ¬q Zadanie 67 (prawo pochłaniania). p oraz p ∨ ( p ∧ q) Zadanie 68 (prawo pochłaniania). p oraz p ∧ ( p ∨ q) Zadanie 69 (prawo podwójnego przeczenia). ¬¬ p oraz p Zadanie 70 (prawo negowania fałszu). ¬⊥ oraz > Zadanie 71 (prawo negowania prawdy). ¬> oraz ⊥ Zadanie 72 (prawo de Morgana). ¬( p ∧ q) oraz ¬ p ∨ ¬q Zadanie 73 (prawo de Morgana). ¬( p ∨ q) oraz ¬ p ∧ ¬q Zadanie 74 (prawo negowania implikacji). ¬( p ⇒ q) oraz p ∧ ¬q Zadanie 75 (prawo negowania równoważności). ¬( p ⇔ q) oraz ¬ p ⇔ q Zadanie 76 (prawo negowania równoważności). ¬( p ⇔ q) oraz p ⇔ ¬q Zadanie 77. p ⇒ q oraz ¬ p ∨ q Zadanie 78. p ⇔ q oraz ( p ⇒ q) ∧ (q ⇒ p) Zadanie 79. p ⇔ q oraz ( p ∧ q) ∨ (¬ p ∧ ¬q) Równoważność przedstawionych powyżej formuł jest od dawna znana logikom, wykorzystuje si˛e ja˛ bowiem przeprowadzajac ˛ rozumowania. W nawiasach wymie- niono zwyczajowe nazwy podanych praw. W zadaniach 80–110 sprawdź, czy podane formuły sa˛ równoważne. Zadanie 80. p ∨ q ⇒ r oraz p ⇒ q ⇒ r Zadanie 81. p ∧ q ⇒ r oraz p ⇒ q ⇒ r Zadanie 82. ( p ⇔ q) ⇒ r oraz p ⇒ q ⇒ r Zadanie 83. p ∨ q oraz q ∨ p Zadanie 84. p ∧ q oraz q ∧ p 1. Rachunek zdań i rachunek kwantyfikatorów 13 Zadanie 85. p ⇒ q oraz q ⇒ p Zadanie 86. p ⇔ q oraz q ⇔ p Spójnik logiczny ⊕ jest przemienny, jeżeli formuły p ⊕ q i q ⊕ p sa˛ równoważne. W powyższych zadaniach sprawdza si˛e wi˛ec, które spośród spójników logicznych sa˛ przemienne. Zadanie 87. p ∨ (q ∨ r ) oraz ( p ∨ q) ∨ r Zadanie 88. p ∧ (q ∧ r ) oraz ( p ∧ q) ∧ r Zadanie 89. p ⇒ (q ⇒ r ) oraz ( p ⇒ q) ⇒ r Zadanie 90. p ⇔ (q ⇔ r ) oraz ( p ⇔ q) ⇔ r Spójnik logiczny ⊕ jest łaczny, ˛ jeżeli formuły p ⊕ (q ⊕ r ) i ( p ⊕ q) ⊕ r sa˛ równoważne. W powyższych zadaniach sprawdza si˛e wi˛ec, które spośród spójników logicznych sa˛ łaczne. ˛ Zadanie 91. p ∨ (q ∨ r ) oraz q ∨ ( p ∨ r ) Zadanie 92. p ∧ (q ∧ r ) oraz q ∧ ( p ∧ r ) Zadanie 93. p ⇒ (q ⇒ r ) oraz q ⇒ ( p ⇒ r ) Zadanie 94. p ⇔ (q ⇔ r ) oraz q ⇔ ( p ⇔ r ) Zadanie 95. p ∧ (q ∨ r ) oraz ( p ∧ q) ∨ ( p ∧ r ) Zadanie 96. p ∧ (q ∧ r ) oraz ( p ∧ q) ∧ ( p ∧ r ) Zadanie 97. p ∧ (q ⇒ r ) oraz ( p ∧ q) ⇒ ( p ∧ r ) Zadanie 98. p ∧ (q ⇔ r ) oraz ( p ∧ q) ⇔ ( p ∧ r ) Zadanie 99. p ∨ (q ∨ r ) oraz ( p ∨ q) ∨ ( p ∨ r ) Zadanie 100. p ∨ (q ∧ r ) oraz ( p ∨ q) ∧ ( p ∨ r ) Zadanie 101. p ∨ (q ⇒ r ) oraz ( p ∨ q) ⇒ ( p ∨ r ) Zadanie 102. p ∨ (q ⇔ r ) oraz ( p ∨ q) ⇔ ( p ∨ r ) Zadanie 103. p ⇒ (q ∨ r ) oraz ( p ⇒ q) ∨ ( p ⇒ r ) 14 1.2. Wartości logiczne i znaczenie formuł zdaniowych Zadanie 104. p ⇒ (q ∧ r ) oraz ( p ⇒ q) ∧ ( p ⇒ r ) Zadanie 105. p ⇒ (q ⇒ r ) oraz ( p ⇒ q) ⇒ ( p ⇒ r ) Zadanie 106. p ⇒ (q ⇔ r ) oraz ( p ⇒ q) ⇔ ( p ⇒ r ) Zadanie 107. p ⇔ (q ∨ r ) oraz ( p ⇔ q) ∨ ( p ⇔ r ) Zadanie 108. p ⇔ (q ∧ r ) oraz ( p ⇔ q) ∧ ( p ⇔ r ) Zadanie 109. p ⇔ (q ⇒ r ) oraz ( p ⇔ q) ⇒ ( p ⇔ r ) Zadanie 110. p ⇔ (q ⇔ r ) oraz ( p ⇔ q) ⇔ ( p ⇔ r ) Spójnik logiczny ⊕ jest lewostronnie rozdzielny wzgl˛edem spójnika ⊗, jeżeli for- muły p ⊕ (q ⊗ r ) i ( p ⊕ q) ⊗ ( p ⊕ r ) sa˛ równoważne. W powyższych zadaniach sprawdza si˛e wi˛ec, które spośród spójników logicznych sa˛ rozdzielne wzgl˛edem któ- rych. Zadanie 111. Spójnik logiczny ⊕ jest prawostronnie rozdzielny wzgl˛edem spójni- ka ⊗, jeżeli formuły ( p ⊗ q) ⊕ r i ( p ⊕ r ) ⊗ (q ⊕ r ) sa˛ równoważne. Które spośród spójników logicznych ∨, ∧, ⇒, ⇔ sa˛ prawostronnie rozdzielne wzgl˛edem których? 1.2.4. Lemat o podstawianiu Definicja 7. Podstawieniem formuły ψ w miejsce zmiennej zdaniowej p nazywamy przekształcenie, które formule φ przyporzadkowuje ˛ formuł˛e powstała˛ przez wstawie- nie formuły ψ w miejsce każdego wystapienia ˛ zmiennej p w formule φ. Formalnie: p[ p/ψ] = ψ q[ p/ψ] = q, dla q 6= p (¬φ)[ p/ψ] = ¬(φ[ p/ψ]) (φ1 ∨ φ2 )[ p/ψ] = (φ1 [ p/ψ]) ∨ (φ2 [ p/ψ]) (φ1 ∧ φ2 )[ p/ψ] = (φ1 [ p/ψ]) ∧ (φ2 [ p/ψ]) (φ1 ⇒ φ2 )[ p/ψ] = (φ1 [ p/ψ]) ⇒ (φ2 [ p/ψ]) (φ1 ⇔ φ2 )[ p/ψ] = (φ1 [ p/ψ]) ⇔ (φ2 [ p/ψ]) Przykład 8. ( p ⇒ p ∨ q)[ p/q ⇒ p] = (q ⇒ p) ⇒ (q ⇒ p) ∨ q. W podobny sposób definiujemy jednoczesne podstawienie formuł w miejsce kil- ku zmiennych zdaniowych [ p1 /ψ1 ,... , pn /ψn ]. Jest to odwzorowanie, które for- mule φ przyporzadkowuje ˛ formuł˛e powstała˛ przez wstawienie formuły ψi w miejsce każdego wystapienia ˛ zmiennej pi w formule φ, dla każdego i = 1,... , n. 1. Rachunek zdań i rachunek kwantyfikatorów 15 Lemat 9 (o podstawianiu). Jeżeli formuła φ jest tautologia,˛ to dla dowolnej zmien- nej p i dowolnej formuły ψ formuła φ[ p/ψ] jest tautologia.˛ Powyższy lemat ma bardzo duże znaczenie praktyczne, pozwala bowiem dowo- dzić, że skomplikowane formuły sa˛ tautologiami. Dla przykładu formuła (q ⇒ p) ⇒ (q ⇒ p) ∨ q z przykładu 8 jest tautologia,˛ gdyż jest wynikiem podstawienia formuły q ⇒ p w miejsce zmiennej p w tautologii p ⇒ p ∨ q. W zadaniach 112–115 zbadaj, czy podane formuły sa˛ tautologiami. Zadanie 112. (s ∧ u ∧ t ∧ ( p ∨ q ∨ r )) ⇒ (x ⇒ y ∧ ¬z) ⇔ (( p ∨ q ∨ r ) ⇒ (s ∧ u ∧ t) ⇒ (x ⇒ y ∧ ¬z)) Zadanie 113. ¬(( p ⇒ q ∧ (r ∨ s ⇔ ¬ p)) ∧ ¬(( p ⇒ q ∧ (r ∨ s ⇔ ¬ p)))) Zadanie 114. ( p ∧ ¬q) ∧ ((r ⇒ s) ∨ ( p ⇒ q ⇒ r ∨ ¬s)) ⇒ ¬(q ∨ ¬ p) Zadanie 115. (( p ⇒ q ∨ r ) ∨ s ∨ t) ∧ ¬( p ⇒ q ∨ r ) ⇒ s ∨ t Zadanie 116. Wskaż podstawienie [ p/φ1 , q/φ2 , r/φ3 ], dla którego formuła ( p ∨ (q ∧ r )) [ p/φ1 , q/φ2 , r/φ3 ] jest a) tautologia,˛ b) formuła˛ spełnialna,˛ c) formuła˛ sprzeczna.˛ 1.3. Formalizacja rozumowań w jezyku ˛ rachunku zdań Zadanie 117. Sformalizuj zadanie 3, tj. pokaż, jak znaleźć odpowiedzi na posta- wione w nim pytania korzystajac ˛ z rachunku zdań. Zadanie 118. Sformalizuj zadanie 4, tj. pokaż, jak znaleźć odpowiedzi na posta- wione w nim pytania korzystajac ˛ z rachunku zdań. Zadanie 119. Podczas pewnej kampanii wyborczej Olek, Józek i Kazik wygłosili nast˛epujace ˛ oświadczenia: Olek: Józek zawsze kłamie. Józek: Kazik zawsze kłamie. Kazik: Olek zawsze kłamie. Pokaż, że co najmniej dwóch spośród nich nie miało racji. Zadanie 120. Podczas tej samej kampanii wyborczej Basia, Hania, Kasia i Ola stwierdziły, że: Basia: Hania zawsze kłamie. 16 1.4. Własności formuł zdaniowych Hania: Kasia czasem mówi prawd˛e. Kasia: Ola czasem kłamie. Ola: Basia zawsze mówi prawd˛e. Ile pań powiedziało prawd˛e? Zadanie 121. Zbadaj zasadność poniższych rozumowań: 1. Jeśli stopa procentowa nie ulegnie zmianie, to wzrosna˛ wydatki rzadowe ˛ lub pojawi si˛e bezrobocie. Jeśli wydatki rzadowe ˛ nie wrosna,˛ to podatki zostana˛ obniżone. Jeśli podatki zostana˛ obniżone i stopa procentowa nie ulegnie zmia- nie, to bezrobocie si˛e nie pojawi. Zatem wydatki rzadowe ˛ wzrosna.˛ 2. Jeśli ceny wzrosna,˛ to spadnie popyt. Jeśli popyt spadnie, to spadna˛ ceny. Za- tem jeśli ceny wzrosna,˛ to spadna.˛ Zatem ceny spadna!˛ 1.4. Własności formuł zdaniowych Vn Wn Definicja 10. Napis i=1 φi oznacza φ1 ∧· · ·∧φn , zaś i=1 φi oznacza φ1 ∨· · ·∨φn. V0 W0 Przyjmujemy przy tym, że i=1 φi oznacza >, zaś i=1 φi oznacza ⊥. Definicja 11. Niech V b˛edzie zbiorem zmiennych zdaniowych. V -literałem nazy- wamy formuł˛e postaci p lub ¬ p, gdzie p ∈ V. Jeżeli zbiór zmiennych zdaniowych jest ustalony, to formuł˛e takiej postaci nazywamy po prostu literałem. Niekiedy do zbioru literałów zaliczamy też stałe logiczne > i ⊥. Zadanie 122. Dane sa˛ formuły φ1 ,... , φn , ψ1 ,... , ψn. Wykaż, że dla każdego n poniższa formuła zdaniowa jest tautologia:˛ ^ n    _ n  _ n  φi ⇒ ψi ⇒ φi ⇒ ψi. i=1 i=1 i=1 Zadanie 123. Dane sa˛ formuły φ1 ,... , φn , ψ. Wykaż, że dla każdego n poniższa formuła zdaniowa jest tautologia: ˛ _ n    ^ n   φi ⇒ ψ ⇒ φi ⇒ ψ. i=1 i=1 ∞ rachunku zdań, że ˛ formuł {φi }i=1 Zadanie 124. Czy istnieje taki nieskończony ciag wszystkie formuły φi+1 ⇒ φi sa˛ tautologiami rachunku zdań, zaś żadna z formuł φi ⇒ φi+1 nie jest tautologia? ˛ 1. Rachunek zdań i rachunek kwantyfikatorów 17 ∞ rachunku zdań, że ˛ formuł {φi }i=1 Zadanie 125. Czy istnieje taki nieskończony ciag wszystkie formuły φi ⇒ φi+1 sa˛ tautologiami rachunku zdań, zaś żadna z formuł φi+1 ⇒ φi nie jest tautologia? ˛ Zadanie 126. Udowodnij, że formuła rachunku zdań zbudowana wyłacznie ˛ ze zmiennych i spójnika równoważności „⇔” (oczywiście do jej zapisania można też używać nawiasów) jest tautologia˛ wtedy i tylko wtedy, gdy każda zmienna wyst˛epuje w niej parzysta˛ liczb˛e razy. Zadanie 127. Udowodnij, że jeśli p jest zmienna˛ zdaniowa,˛ a φ formuła˛ rachunku zdań, taka,˛ że p ⇒ φ i ¬φ ⇒ p sa˛ tautologiami, to φ jest tautologia.˛ Zadanie 128. Niech φ1 ,... , φn b˛eda˛ formułami zdaniowymi, w których nie wyst˛e- puja˛ zmienne zdaniowe p1 ,... , pn+1. Udowodnij, że formuła ^ n φi i=1 jest tautologia˛ wtedy i tylko wtedy, gdy tautologia˛ jest formuła _ n ¬ p1 ∨ (φi ∧ pi ∧ ¬ pi+1 ) ∨ pn+1. i=1 Zadanie 129. Udowodnij, że jeżeli formuła φ jest tautologia,˛ to dla dowolnych for- muł ψ1 ,... , ψn formuła ψ1 ⇒... ⇒ ψn ⇒ φ jest tautologia.˛ Zadanie 130. Udowodnij, że jeżeli φ jest formuła˛ sprzeczna,˛ to dla dowolnych for- muł ψ1 ,... , ψn formuła φ ⇒ ψ1 ⇒... ⇒ ψn jest tautologia.˛ Zadanie 131. Dla jakich n ≥ 1 formuła (... (( p ⇒ p) ⇒ p) ⇒...) ⇒ p, w której zmienna p wyst˛epuje n razy jest tautologia? ˛ Zadanie 132. Niech p 0 oznacza ¬ p oraz niech p 1 oznacza p. Dla jakich ciagów ˛ (i 1 ,... , i n ) ∈ {0, 1}n formuła (... (( pi1 ⇒ pi2 ) ⇒ pi3 ) ⇒...) ⇒ pin jest tautologia? ˛ 18 1.4. Własności formuł zdaniowych Zadanie 133. Niech p1 ,... , pn b˛eda˛ wszystkimi zmiennymi zdaniowymi wyst˛epu- jacymi ˛ w formule φ. Udowodnij, że formuła φ jest spełnialna wtedy i tylko wtedy, gdy istnieje podstawienie [ p1 /φ1 ,... , pn /φn ] takie, że formuła φ[ p1 /φ1 ,... , pn /φn ] jest tautologia.˛ Udowodnij, że formuła φ nie jest tautologia˛ wtedy i tylko wtedy, gdy istnieje podstawienie [ p1 /φ1 ,... , pn /φn ] takie, że formuła φ[ p1 /φ1 ,... , pn /φn ] jest sprzeczna. Zadanie 134. Dane sa˛ formuły φ1 ,... , φn , ψ. Czy formuły (... ((ψ ⇒ φ1 ) ⇒ φ2 ) ⇒...) ⇒ φn oraz ψ ⇒ (φ1 ∨ φ2 ∨... ∨ φn ) sa˛ równoważne? Zadanie 135. Dane sa˛ formuły φ1 ,... , φn , ψ. Czy formuły φ1 ⇒ (φ2 ⇒ (... ⇒ (φn ⇒ ψ)...)) oraz (φ1 ∧ φ2 ∧... ∧ φn ) ⇒ ψ sa˛ równoważne? Zadanie 136. Pokaż przez indukcj˛e, że każda formuła φ zbudowana ze zmiennych p i q oraz spójnika ⇒ jest równoważna dokładnie jednej z formuł z poniższego zbioru: {>, p, q, ( p ⇒ q), (q ⇒ p), ( p ∨ q)}. W poniższych zadaniach przyjmiemy nast˛epujace˛ oznaczenia. Niech φ b˛edzie formuła˛ rachunku zdań zbudowana˛ wyłacznie ˛ ze zmiennych zdaniowych oraz spój- ników ∨ oraz ∧ (oczywiście można używać nawiasów). Niech φ d oznacza formuł˛e powstała˛ z φ przez zastapienie ˛ każdego wystapienia ˛ spójnika ∨ spójnikiem ∧, zaś każdego wystapienia ˛ spójnika ∧ spójnikiem ∨. Niech φ n oznacza formuł˛e powstała˛ przez zastapienie ˛ każdego wystapienia ˛ zmiennej zdaniowej negacja˛ tej zmiennej. Zadanie 137. Udowodnij, że jeżeli formuły φ1 i φ2 sa˛ równoważne, to równoważne sa˛ także formuły φ1d i φ2d. Zadanie 138. Udowodnij, że jeżeli formuły φ1 i φ2 sa˛ równoważne, to równoważne sa˛ także formuły φ1n i φ2n. Zadanie 139. Udowodnij, że dla dowolnej formuły φ formuły ¬φ d oraz φ n sa˛ rów- noważne. 1. Rachunek zdań i rachunek kwantyfikatorów 19 Zadanie 140. Wykaż, że dla każdej formuły spełnialnej φ ze zmiennymi ze zbioru V = { p, q, r } istnieje formuła ψ postaci φ1 ∧ φ2 ∧ φ3 taka, że każde φi jest V -lite- rałem, φi sa˛ parami różne oraz ψ ⇒ φ jest tautologia.˛ Zadanie 141 (lemat interpolacyjny Craiga dla rachunku zdań). Niech V (φ) oz- nacza zbiór zmiennych zdaniowych wyst˛epujacych ˛ w formule φ. Przypuśćmy, że φ i ψ sa˛ takimi formułami rachunku zdań, że φ ⇒ ψ jest tautologia.˛ Udowod- nij, że istnieje formuła ρ, taka, że φ ⇒ ρ oraz ρ ⇒ ψ sa˛ tautologiami i V (ρ) ⊆ V (φ) ∩ V (ψ). Zadanie 142 (o zamkni˛etym układzie twierdzeń). Niech n b˛edzie ustalona˛ liczba˛ naturalna.˛ Przypuśćmy, że dla pewnego wartościowania sa˛ spełnione formuły: p1 ∨... ∨ pn , pi ⇒ qi , dla i = 1,... , n, ¬(qi ∧ q j ), dla 1 ≤ i < j ≤ n. Udowodnij, że wartościowanie to spełnia także formuły qi ⇒ pi , dla i = 1,... , n. Przez wartościowanie formuły φ b˛edziemy w poniższych zadaniach rozumieć od- wzorowanie przyporzadkowuj ˛ ace ˛ zmiennym wyst˛epujacym ˛ w tej formule wartości ˛ n różnych zmiennych ma wi˛ec 2n wartościowań. logiczne T i F. Formuła zawierajaca Zadanie 143. Wykaż, że formuła (... (( p1 ⇒ p2 ) ⇒ p3 ) ⇒... ⇒ pn−1 ) ⇒ pn jest fałszywa dla dokładnie 2n − (−1)n 3 wartościowań tej formuły. Dla ilu wartościowań jest fałszywa formuła pn ⇒ ( pn−1 ⇒ ( p3 ⇒... ⇒ ( p2 ⇒ p1 )...) ? Zadanie 144. Niech φ oraz ψ b˛eda˛ formułami rachunku zdań zbudowanymi wyłacz- ˛ nie ze zmiennych zdaniowych oraz spójników ∨ oraz ∧ (oczywiście można używać nawiasów). Pokaż, że formuła φ ⇔ ψ jest spełniona przez co najmniej dwa warto- ściowania. Podaj przykład formuł φ i ψ takich, że formuła φ ⇔ ψ jest spełniona przez dokładnie dwa wartościowania. 1.5. Postaci normalne formuł zdaniowych 1.5.1. Usuwanie symbolu negacji Formuły w których symbol negacji wyst˛epuje przed formuła˛ złożona˛ sa˛ cz˛esto trudne do zrozumienia (wyrażenie „nie prawda, że liczba n dzieli si˛e przez 2 lub 20 1.5. Postaci normalne formuł zdaniowych przez 3” jest bardziej skomplikowane, niż równoważne mu wyrażenie „liczba n nie dzieli si˛e przez 2 i nie dzieli si˛e przez 3”). Prawa negowania formuł zdaniowych z zadań 69–76 pozwalaja˛ znaleźć dla danej formuły formuł˛e jej równoważna,˛ w któ- rej negacja wyst˛epuje jedynie przed zmiennymi zdaniowymi. Istotnie, dla dowolnej formuły φ na mocy lematu o podstawianiu i prawa podwójnego przeczenia formuły ¬¬φ oraz φ sa˛ równoważne. Na mocy lematu o podstawianiu i prawa de Morgana dla dowolnych formuł φ1 i φ2 formuły ¬(φ1 ∧ φ2 ) oraz ¬φ1 ∨ ¬φ2 sa˛ równoważne. Podobnie post˛epujemy dla formuł dowolnej innej postaci. Możemy zatem zdefinio- wać odwzorowanie T przyporzadkowuj ˛ ace ˛ dowolnym formułom formuły, w których negacja wyst˛epuje jedynie przed zmiennymi zdaniowymi: T ( p) = p, dla p ∈ V T (⊥) = ⊥ T (>) = > T (φ1 ∨ φ2 ) = T (φ1 ) ∨ T (φ2 ) T (φ1 ∧ φ2 ) = T (φ1 ) ∧ T (φ2 ) T (φ1 ⇒ φ2 ) = T (φ1 ) ⇒ T (φ2 ) T (φ1 ⇔ φ2 ) = T (φ1 ) ⇔ T (φ2 ) T (¬ p) = ¬ p, dla p ∈ V T (¬⊥) = > T (¬>) = ⊥ T (¬(φ1 ∨ φ2 )) = T (¬φ1 ) ∧ T (¬φ2 ) T (¬(φ1 ∧ φ2 )) = T (¬φ1 ) ∨ T (¬φ2 ) T (¬(φ1 ⇒ φ2 )) = T (φ1 ) ∧ T (¬φ2 ) T (¬(φ1 ⇔ φ2 )) = T (¬φ1 ) ⇔ T (φ2 ) T (¬¬φ) = T (φ) Fakt 12. Dla dowolnej formuły φ, formuły φ oraz T (φ) sa˛ równoważne i w for- mule T (φ) negacja wyst˛epuje jedynie przed zmiennymi zdaniowymi. Zadanie 145–199. Zaneguj formuły z zadań 8–62 i — korzystajac ˛ z praw negowania formuł logicznych — znajdź formuły im równoważne, w których negacja wyst˛epuje jedynie przed zmiennymi zdaniowymi. (Zadanie nr i, dla i = 145,... , 199, dotyczy formuły z zadania i − 137.) Formuły, w których negacja wyst˛epuje jedynie przed zmiennymi zdaniowymi możemy określić jako formuły zbudowane z literałów przy pomocy spójników lo- gicznych alternatywy, koniunkcji, implikacji i równoważności. Zauważmy, że na mo- cy lematu o podstawianiu i zadań 77–79 każda formuła jest równoważna pewnej for- 1. Rachunek zdań i rachunek kwantyfikatorów 21 mule nie zawierajacej ˛ spójników implikacji i równoważności. Możemy wi˛ec rozpa- trywać formuły zbudowane z literałów jedynie przy pomocy spójników alternatywy i koniunkcji. Jeszcze w˛eższe klasy formuł rozważamy w nast˛epnych paragrafach. 1.5.2. Dysjunkcyjna postać normalna Definicja 13. Formuła ma dysjunkcyjna˛ postać normalna˛ (DNF, ang. Disjunctive Normal Form), jeśli ma postać   _ n mi ^  li j  , i=1 j=1 gdzie li j sa˛ literałami, dla i = 1,... , n oraz j = 1,... , m i. Mówiac ˛ skrótowo, dysjunkcyjna postać normalna, to alternatywa koniunkcji literałów. Zadanie 200. Udowodnij, że dla każdej formuły zdaniowej φ istnieje formuła ψ równoważna z φ i majaca ˛ dysjunkcyjna˛ postać normalna.˛ Zadanie 201–255. Znajdź formuły majace ˛ dysjunkcyjna˛ postać normalna˛ równo- ważne formułom z zadań 8–62. (Zadanie nr i, dla i = 201,... , 255, dotyczy formuły z zadania i − 193.) Zadanie 256. Znajdź formuły zdaniowe φ1 , φ2 , φ3 majace ˛ dysjunkcyjna˛ postać nor- malna,˛ zawierajace ˛ zmienne p, q i r i spełnione dla podanych niżej wartościowań: p q r φ1 φ2 φ3 T T T T F F T T F F F F T F T T T F T F F F T T F T T T F T F T F F F T F F T F F T F F F F F F 1.5.3. Koniunkcyjna postać normalna Definicja 14. Klauzula˛ nazywamy formuł˛e postaci _ m lj, j=1 gdzie l j sa˛ literałami, dla j = 1,... , m. Innymi słowy klauzula to alternatywa lite- rałów. 22 1.5. Postaci normalne formuł zdaniowych Definicja 15. Formuła ma koniunkcyjna˛ postać normalna˛ (CNF, ang. Conjunctive Normal Form), jeśli ma postać   ^ n mi _  li j  , i=1 j=1 gdzie li j sa˛ literałami, dla i = 1,... , n oraz j = 1,... , m i , tj. gdy jest koniunkcja˛ klauzul. Zadanie 257. Udowodnij, że dla każdej formuły zdaniowej φ istnieje formuła ψ równoważna z φ i majaca ˛ koniunkcyjna˛ postać normalna.˛ Zadanie 258–312. Znajdź formuły majace ˛ koniunkcyjna˛ postać normalna˛ równo- ważne formułom z zadań 8–62. (Zadanie nr i, dla i = 258,... , 312, dotyczy formuły z zadania i − 250.) Definicja 16. Formuła ma postać k-CNF, gdzie k jest liczba˛ naturalna,˛ jeżeli ma po- stać   ^n _k  li j  , i=1 j=1 gdzie li j sa˛ literałami, dla i = 1,... , n oraz j = 1,... , k, tj. gdy jest koniunkcja˛ klauzul zawierajacych˛ po k literałów. Zadanie 313. Wskaż przykład formuły, która nie jest równoważna z żadna˛ formuła˛ postaci 1-CNF. Zadanie 314. Dla dowolnego k ≥ 1 wskaż przykład formuły, która nie jest równo- ważna z żadna˛ formuła˛ postaci k-CNF. Definicja 17. Formuła ma postać CNF j , gdzie j jest liczba˛ naturalna,˛ jeżeli ma po- stać CNF i każda zmienna wyst˛epuje w niej co najwyżej j razy. Formuła ma postać k-CNF j , gdzie k i j sa˛ liczbami naturalnymi, jeżeli ma postać k-CNF i każda zmienna wyst˛epuje w niej co najwyżej j razy. Zadanie 315. Wskaż przykład formuły, która nie jest równoważna z żadna˛ formuła˛ postaci CNF1. Zadanie 316. Dla dowolnego k ≥ 1 wskaż przykład formuły, która nie jest równo- ważna z żadna˛ formuła˛ postaci CNFk. Definicja 18. Literał l jest pozytywny, jeżeli l = p dla pewnej zmiennej p ∈ V. Literał l jest negatywny, jeżeli l = ¬ p dla pewnej zmiennej p ∈ V. 1. Rachunek zdań i rachunek kwantyfikatorów 23 Definicja 19. Operacj˛e negowania literału definiujemy nast˛epujaco: ˛ p = ¬ p, ¬p = p, dla dowolnego p ∈ V. Wm Zadanie 317. Niech C = j=1 l j b˛edzie dowolna˛ klauzula˛ i niech P = { j ∈ {1,... , m} | literał l j jest pozytywny}, N = { j ∈ {1,... , m} | literał l j jest negatywny} oraz ^ _ C0 = lj ⇒ lj. j∈N j∈P Udowodnij, że formuły C oraz C 0 sa˛ równoważne. Na mocy powyższego zadania klauzule można zapisywać w postaci ^ m _ n pj ⇒ qj, j=1 j=1 gdzie p j i q j sa˛ zmiennymi zdaniowymi. W Definicja 20. Klauzula mj=1 l j jest klauzula˛ hornowska,˛ jeżeli co najwyżej jeden spośród literałów l1 ,... , lm jest pozytywny. Formuła ma postać hornowska,˛ jeżeli jest koniunkcja˛ klauzul hornowskich. Klauzule hornowskie można wi˛ec zapisać w postaci ^ m ^ m pj ⇒ q lub p j ⇒ ⊥, j=1 j=1 gdzie p j oraz q sa˛ zmiennymi zdaniowymi. Zadanie 318. Wskaż przykład formuły, która nie jest równoważna z żadna˛ formuła˛ w postaci hornowskiej. Zadanie 319–373. Które spośród formuł z zadań 8–62 można przedstawić w po- staci hornowskiej? Tam, gdzie to możliwe, podaj t˛e postać. (Zadanie nr i, dla i = 319,... , 373, dotyczy formuły z zadania i − 311.) 24 1.6. Funkcje boolowskie i zupełne zbiory spójników 1.6. Funkcje boolowskie i zupełne zbiory spójników Definicja 21. Funkcje f : B n → B, gdzie B = {T, F} i n ≥ 0, nazywamy n-argu- mentowymi funkcjami boolowskimi lub funkcjami logicznymi. Do tej pory zbiór spójników logicznych był ustalony (⊥, >, ∧, ∨, ⇒, ⇔). Nic jednak nie stoi na przeszkodzie, by rozważać różne zestawy spójników i wprowadzać nowe spójniki. Z każdym spójnikiem zwiazujemy ˛ jego znaczenie — funkcj˛e boolow- ska˛ określajac ˛ a˛ prawdziwość formuł zbudowanych przy użyciu tego spójnika. Tabelki funkcji boolowskich określajacych˛ prawdziwość spójników ⊥, >, ¬, ∨, ∧, ⇒ i ⇔ zostały przedstawione na rysunku 1. Definicja 22. Formuła φ zbudowana ze zmiennych p1 ,... , pn opisuje n-argumento- wa˛ funkcj˛e boolowska˛ f , jeżeli dla każdego wartościowania σ zmiennych p1 ,... , pn zachodzi: f (σ ( p1 ),... , σ ( pn )) = σ (φ). Jeżeli formuła φ zbudowana ze zmiennych p1 ,... , pn opisuje funkcj˛e f , to piszemy f ( p1 ,... , pn ) ≡ φ. Definicja 23. Zbiór spójników logicznych jest zupełny, jez