1 Podstawy logiki i teorii mnogościMarta Puc Martyna Rusek

2 Spójniki logiczne Koniunkcja Alternatywa p q p ∧ q 1 p q p ∨ q 11 p q p ∨ q 1 Implikacja Równoważność Negacja p q p ⇒ q 1 p q p ⇔ q 1 p ¬ p 1

3 1. Na podstawie informacji, że zdania p∨q i p ⇒ q są prawdziwe, ustal, które odpowiedzi są poprawne.a)Nie, bo może być q=1, p=0 b)Tak,bo gdyby q=0 to mamy dwa przypadki p=0 wtedy (p∨q )=0 - p=1 wtedy (p ⇒ q ) =0 c)Wiemy już, że q=1 (z (b)) Analizujemy dwa przypadki - p=1 wtedy (¬p)=0 i ((¬p) ⇒ q ) = 1 - p=0 wtedy (¬p)=1 i ((¬p) ⇒ q ) = 1 (a) Zdanie p jest prawdziwe. (NIE) (b) Zdanie q jest prawdziwe. (TAK) (c) Zdanie (¬p) ⇒ q jest prawdziwe. a)Nie, bo może być q=1, p=0 b)Tak,bo gdyby q=0 to mamy dwa przypadki - p=0 wtedy (p∨q )=0 - p=1 wtedy (p ⇒ q ) =0 c)Wiemy już, że q=1 (z (b)) Analizujemy dwa przypadki – p=1 wtedy (¬p)=0 i ((¬p) ⇒ q ) = 1 - p=0 wtedy (¬p)=1 i ((¬p) ⇒ q ) = 1

4 Koniunkcyjna postać normalna(DEFINICJA) Koniunkcyjna postać normalna : (i) Każda alternatywa elementarna jest formułą o koniunkcyjnej postaci normalnej; (ii) jeżeli A jest dowolną formułą o koniunkcyjnej postaci normalnej, zaś B jest dowolną alternatywą elementarną, to wyrażenie o postaci (A ∧ B) jest formułą o koniunkcyjnej postaci normalnej ; (iii) nie ma żadnych innych formuł o koniunkcyjnej postaci normalnej prócz tych, które są alternatywami elementarnymi lub też dają się zbudować wedle reguły (ii).

5 Alternatywy elementarne(DEFINICJA) Alternatywy elementarne (i) Każdy literał jest alternatywą elementarną; (ii)jeżeli A jest alternatywą elementarną i L jest literałem, to wyrażenie postaci (A ∨ L)jest alternatywą elementarną; (iii) nie ma żadnych innych alternatyw elementarnych poza tymi, które są wymienione w punkcie (i) i tymi, które można zbudować wedle reguły (ii).

6 Literały (DEFINICJA) Literałami nazywamy wyrażenia o postaci pi oraz¬pi ,gdzie pi jest zmienną zdaniową. Zmienna zdaniowa to litera, którą w danej nauce może oznaczać dowolne zdanie. Zmienna zdaniowa podobnie jak zdanie może przyjmować jedną z wartości logicznych.

7 2. Formuła w koniunkcyjnej postaci normalnej jest (zaznacz poprawną definicję):a)Nie bo to jest KONIUNKCJĄ skończenie wielu ALTERNATYW elementarnych (wynika z definicji) b)Tak (wynika z definicji) c)Nie, bo to nie każda formuła w koniunkcyjnej postaci normalnej jest c), chociaż c) jest formułą w koniunkcyjnej postaci normalnej (a) alternatywą skończenie wielu koniunkcji elementarnych. (NIE) (b) koniunkcją skończenie wielu alternatyw elementarnych. (TAK) (c) koniunkcją skończenie wielu literałów. Przykład formuły w koniunkcyjnej postaci normalnej: a)Nie bo to jest KONIUNKCJĄ skończenie wielu ALTERNATYW elementarnych (wynika z definicji) b)Tak (wynika z definicji) c)Nie, bo to nie będzie definicja formuły w koniunkcyjnej postaci normalnej

8 Formuła A logicznie wynika ze zbioru formuł S , jeżeli każde wartościowanie spełniające zbiór S spełnia formułę A. (Zbiór formuł nazywamy spełnialnym, jeżeli istnieje wartościowanie, które spełnia ten zbiór. Wartościowanie : dowolna funkcja w : V  {0,1}, Gdzie V- przeliczalny zbiór zmiennych zdaniowych Wartościowanie w spełnia formułę A, jeżeli w(A) = 1) Fakt . Formuła A logicznie wynika ze zbioru S wtw, gdy zbiór S U {¬A} nie jest spełnialny.

9 3. Formuła B logicznie wynika ze zbioru formuł {A1,3. Formuła B logicznie wynika ze zbioru formuł {A1, , An} w klasycznym rachunku zdań wtedy i tylko wtedy, gdy (zaznacz poprawne warunki): (a) dla każdego wartościowania w, jeżeli w(Ai) = 1 dla wszystkich i =1, , n, to w(B) = 1. (TAK) (b) zbiór formuł {A1, , An,¬B} nie jest spełnialny. (c) zbiór formuł {A1, , An, B} jest spełnialny. (NIE) Z definicji Z faktu na poprzednim slajdzie |y|=|x| -przechodnia: |x|=|y| /\ |y|=|z| => |x|=|z| (a) xRy ⇔ 3|(x + y) (NIE) (b) xRy ⇔ (x < 0 ∧ y < 0) V (x ≥­ 0 ∧ y ≥­ ­ 0) (TAK) (c) xRy ⇔ |x| = |y| a) NIE, bo nie jest zwrotna. Np. x = 2, a nieprawdą jest, że 3|(2+2) b) Czyli xRy  x i y są tego samego znaku. TAK. zwrotna: x jest tego samego znaku co x. Symetryczna: jeśli x jest tego samego znaku co y, to y ma ten sam znak co x. Przechodnia: jeśli x ma ten sam znak co y, a y ma ten sam znak co z, to x ma ten sam znak co z. c) TAK, -zwrotna: |x|=|x| -symetryczna: |x|=|y| => |y|=|x| -przechodnia: |x|=|y| /\ |y|=|z| => |x|=|z|", "width": "800" } 30 14. Które z poniższych zbiorów są przeliczalne?(a) zbiór wszystkich skończonych ciągów binarnych (TAK) (b) zbiór wszystkich nieskończonych ciągów binarnych (NIE) (c) zbiór wszystkich nieskonczonych ciagów binarnych, stałych od pewnego miejsca a)Zbiór n-elementowych ciągów binarnych jest przeliczalny, zbiór liczb naturalnych też, zatem zbiór wszystkich skończonych ciągów binarnych jest sumą przeliczalnie wielu zbiorów przeliczalnych, czyli jest przeliczalny. c)Tak, bo jeżeli ciągi są stałe od pewnego miejsca można je uznać za skończone (patrz pkt a). a)Zbiór n-elementowych ciągów binarnych jest przeliczalny, zbiór liczb naturalnych też, zatem zbiór wszystkich skończonych ciągów binarnych jest sumą przeliczalnie wielu zbiorów przeliczalnych, czyli jest przeliczalny. c)Tak, bo jeżeli ciągi są stałe od pewnego miejsca można je uznać za skończone (patrz pkt a). { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/30/14.+Kt%C3%B3re+z+poni%C5%BCszych+zbior%C3%B3w+s%C4%85+przeliczalne.jpg", "name": "14. Które z poniższych zbiorów są przeliczalne", "description": "(a) zbiór wszystkich skończonych ciągów binarnych (TAK) (b) zbiór wszystkich nieskończonych ciągów binarnych (NIE) (c) zbiór wszystkich nieskonczonych ciagów binarnych, stałych od pewnego miejsca a)Zbiór n-elementowych ciągów binarnych jest przeliczalny, zbiór liczb naturalnych też, zatem zbiór wszystkich skończonych ciągów binarnych jest sumą przeliczalnie wielu zbiorów przeliczalnych, czyli jest przeliczalny. c)Tak, bo jeżeli ciągi są stałe od pewnego miejsca można je uznać za skończone (patrz pkt a). a)Zbiór n-elementowych ciągów binarnych jest przeliczalny, zbiór liczb naturalnych też, zatem zbiór wszystkich skończonych ciągów binarnych jest sumą przeliczalnie wielu zbiorów przeliczalnych, czyli jest przeliczalny. c)Tak, bo jeżeli ciągi są stałe od pewnego miejsca można je uznać za skończone (patrz pkt a).", "width": "800" } 31 Zbiór X jest równoliczny ze zbiorem Y wtw gdy istnieje bijekcja f:X→YZbiór X jest równoliczny ze zbiorem Y wtw gdy istnieje bijekcja f:X→Y. Równoliczność oznaczamy X~Y { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/31/Zbi%C3%B3r+X+jest+r%C3%B3wnoliczny+ze+zbiorem+Y+wtw+gdy+istnieje+bijekcja+f%3AX%E2%86%92Y.jpg", "name": "Zbiór X jest równoliczny ze zbiorem Y wtw gdy istnieje bijekcja f:X→Y", "description": "Zbiór X jest równoliczny ze zbiorem Y wtw gdy istnieje bijekcja f:X→Y. Równoliczność oznaczamy X~Y.", "width": "800" } 32 Zbiór przeliczalny Zbiór A ≠ 0 jest przeliczalny wtedy i tylko wtedy, gdy jest on zbiorem wyrazów pewnego ciągu nieskończonego, czyli wtedy i tylko wtedy, gdy istnieje funkcja f przekształcająca zbiór wszystkich liczb naturalnych na zbiór A. Zbiór przeliczalny zatem to zbiór skończony lub równoliczny ze zbiorem wszystkich liczb naturalnych. Zbiory przeliczalne nieskończone są równej mocy. Moc zbiorów przeliczalnych nieskończonych oznaczamy symbolem ℵ0(czytaj: alef zero). Przykłady zbiorów przeliczalnych: - podzbiór zbioru przeliczalnego jest zbiorem przeliczalnym, - suma dowolnej skończonej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym, - produkt kartezjański zbiorów przeliczalnych jest zbiorem przeliczalnym, - zbiór wszystkich liczb całkowitych jest zbiorem przeliczalnym, - zbiór wszystkich liczb wymiernych jest zbiorem przeliczalnym, - zbiór wszystkich ciągów skończonych o wyrazach należących do ustalonego zbioru przeliczalnego jest zbiorem przeliczalnym, - zbiór wszystkich wielomianów jednej zmiennej o współczynnikach wymiernych jest przeliczalny, - zbiór wszystkich liczb algebraicznych jest przeliczalny. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/32/Zbi%C3%B3r+przeliczalny.jpg", "name": "Zbiór przeliczalny", "description": "Zbiór A ≠ 0 jest przeliczalny wtedy i tylko wtedy, gdy jest on zbiorem wyrazów pewnego ciągu nieskończonego, czyli wtedy i tylko wtedy, gdy istnieje funkcja f przekształcająca zbiór wszystkich liczb naturalnych na zbiór A. Zbiór przeliczalny zatem to zbiór skończony lub równoliczny ze zbiorem wszystkich liczb naturalnych. Zbiory przeliczalne nieskończone są równej mocy. Moc zbiorów przeliczalnych nieskończonych oznaczamy symbolem ℵ0(czytaj: alef zero). Przykłady zbiorów przeliczalnych: - podzbiór zbioru przeliczalnego jest zbiorem przeliczalnym, - suma dowolnej skończonej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym, - produkt kartezjański zbiorów przeliczalnych jest zbiorem przeliczalnym, - zbiór wszystkich liczb całkowitych jest zbiorem przeliczalnym, - zbiór wszystkich liczb wymiernych jest zbiorem przeliczalnym, - zbiór wszystkich ciągów skończonych o wyrazach należących do ustalonego zbioru przeliczalnego jest zbiorem przeliczalnym, - zbiór wszystkich wielomianów jednej zmiennej o współczynnikach wymiernych jest przeliczalny, - zbiór wszystkich liczb algebraicznych jest przeliczalny.", "width": "800" } 33 Zbiór nieprzeliczalnyZbiór nieprzeliczalny to zbiór, który nie jest przeliczalny. Zbiór liczb rzeczywistych przedziału <0, 1> jest zbiorem nieprzeliczalnym, gdyż nie istnieje ciąg o wyrazach z przedziału <0, 1>, taki że każda liczba rzeczywista z tego przedziału jest wyrazem ciągu. Jeżeli zbiór A jest nieprzeliczalny i A ⊂ B, to B jest również zbiorem nieprzeliczalnym. Z twierdzenia tego wynika, że zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny. Moc zbioru wszystkich liczb rzeczywistych nazywamy continuum i oznaczamy symbolicznie ℭ. Zbiór wszystkich liczb niewymiernych jest zbiorem nieprzeliczalnym Zbiór wszystkich liczb przestępnych jest nieprzeliczalny. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/33/Zbi%C3%B3r+nieprzeliczalny.jpg", "name": "Zbiór nieprzeliczalny", "description": "Zbiór nieprzeliczalny to zbiór, który nie jest przeliczalny. Zbiór liczb rzeczywistych przedziału jest zbiorem nieprzeliczalnym, gdyż nie istnieje ciąg o wyrazach z przedziału , taki że każda liczba rzeczywista z tego przedziału jest wyrazem ciągu. Jeżeli zbiór A jest nieprzeliczalny i A ⊂ B, to B jest również zbiorem nieprzeliczalnym. Z twierdzenia tego wynika, że zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny. Moc zbioru wszystkich liczb rzeczywistych nazywamy continuum i oznaczamy symbolicznie ℭ. Zbiór wszystkich liczb niewymiernych jest zbiorem nieprzeliczalnym Zbiór wszystkich liczb przestępnych jest nieprzeliczalny.", "width": "800" } 34 15. Które z poniższych zbiorów są równoliczne ze zbiorem wszystkich liczb rzeczywistych z przedziału [0, 1] ? (a) zbiór wszystkich dodatnich liczb rzeczywistych (TAK) (b) zbiór wszystkich liczb rzeczywistych, których kwadrat jest liczba wymierna (NIE) (c) rodzina wszystkich podzbiorów zbioru liczb naturalnych a)Mocy contInuum b)Tych liczb jest 2*tyle co liczb wymiernych(liczny wymierne są przeliczalne) c)  TWIERDZENIE (Cantora)Każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy. Zbiór liczb naturalnych ma moc alef zero. a)Mocy continuum b)Tych liczb jest 2*tyle co liczb wymiernych(liczny wymierne są przeliczalne) c)  TWIERDZENIE (Cantora)Każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy. Zbiór liczb naturalnych ma moc alef zero. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/34/15.+Kt%C3%B3re+z+poni%C5%BCszych+zbior%C3%B3w+s%C4%85+r%C3%B3wnoliczne+ze+zbiorem+wszystkich+liczb+rzeczywistych+z+przedzia%C5%82u+%5B0%2C+1%5D.jpg", "name": "15. Które z poniższych zbiorów są równoliczne ze zbiorem wszystkich liczb rzeczywistych z przedziału [0, 1]", "description": "(a) zbiór wszystkich dodatnich liczb rzeczywistych (TAK) (b) zbiór wszystkich liczb rzeczywistych, których kwadrat jest liczba wymierna (NIE) (c) rodzina wszystkich podzbiorów zbioru liczb naturalnych a)Mocy contInuum. b)Tych liczb jest 2*tyle co liczb wymiernych(liczny wymierne są przeliczalne) c) TWIERDZENIE (Cantora)Każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy. Zbiór liczb naturalnych ma moc alef zero. a)Mocy continuum. b)Tych liczb jest 2*tyle co liczb wymiernych(liczny wymierne są przeliczalne) c) TWIERDZENIE (Cantora)Każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy. Zbiór liczb naturalnych ma moc alef zero.", "width": "800" } 35 Automaty i Języki FormalneMarta Puc Martyna Rusek { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/35/Automaty+i+J%C4%99zyki+Formalne.jpg", "name": "Automaty i Języki Formalne", "description": "Marta Puc Martyna Rusek.", "width": "800" } 36 Domknięcie Kleene’go { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/36/Domkni%C4%99cie+Kleene%E2%80%99go.jpg", "name": "Domknięcie Kleene’go", "description": "Domknięcie Kleene’go", "width": "800" } 37 Wyrażenia regularne { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/37/Wyra%C5%BCenia+regularne.jpg", "name": "Wyrażenia regularne", "description": "Wyrażenia regularne", "width": "800" } 38 Język regularny { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/38/J%C4%99zyk+regularny.jpg", "name": "Język regularny", "description": "Język regularny", "width": "800" } 39 Języki regularne - operacje { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/39/J%C4%99zyki+regularne+-+operacje.jpg", "name": "Języki regularne - operacje", "description": "Języki regularne - operacje", "width": "800" } 40 Zbiór A jest podzbiorem właściwym zbioru B, gdy: { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/40/Zbi%C3%B3r+A+jest+podzbiorem+w%C5%82a%C5%9Bciwym+zbioru+B%2C+gdy%3A.jpg", "name": "Zbiór A jest podzbiorem właściwym zbioru B, gdy:", "description": "Zbiór A jest podzbiorem właściwym zbioru B, gdy:", "width": "800" } 41 Operacje na językach { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/41/Operacje+na+j%C4%99zykach.jpg", "name": "Operacje na językach", "description": "Operacje na językach", "width": "800" } 42 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_43.jpg", "name": "", "description": "", "width": "800" } 43 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_44.jpg", "name": "", "description": "", "width": "800" } 44 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_45.jpg", "name": "", "description": "", "width": "800" } 45 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_46.jpg", "name": "", "description": "", "width": "800" } 46 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_47.jpg", "name": "", "description": "", "width": "800" } 47 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_48.jpg", "name": "", "description": "", "width": "800" } 48 POSTAĆ NORMALNA CHOMSKY’EGOGramatyka jest w postaci normalnej Chomsky’ego, jeśli wszystkie produkcje w gramatyce są postaci: A->BC lub A->a HIERARCHIA CHOMSKY’EGO { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/48/POSTA%C4%86+NORMALNA+CHOMSKY%E2%80%99EGO.jpg", "name": "POSTAĆ NORMALNA CHOMSKY’EGO", "description": "Gramatyka jest w postaci normalnej Chomsky’ego, jeśli wszystkie produkcje w gramatyce są postaci: A->BC lub A->a. HIERARCHIA CHOMSKY’EGO.", "width": "800" } 49 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_50.jpg", "name": "", "description": "", "width": "800" } 50 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_51.jpg", "name": "", "description": "", "width": "800" } 51 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_52.jpg", "name": "", "description": "", "width": "800" } 52 Możliwa jest zmiana stanu bez czytania litery z wejścia. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/52/Mo%C5%BCliwa+jest+zmiana+stanu+bez+czytania+litery+z+wej%C5%9Bcia..jpg", "name": "Możliwa jest zmiana stanu bez czytania litery z wejścia.", "description": "Możliwa jest zmiana stanu bez czytania litery z wejścia.", "width": "800" } 53 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_54.jpg", "name": "", "description": "", "width": "800" } 54 Klasa języków generowanych przez gramatyki lewostronnie (prawostronne) jest zamknięta na operację odbicia zwierciadlanego. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/54/Klasa+j%C4%99zyk%C3%B3w+generowanych+przez+gramatyki+lewostronnie+%28prawostronne%29+jest+zamkni%C4%99ta+na+operacj%C4%99+odbicia+zwierciadlanego..jpg", "name": "Klasa języków generowanych przez gramatyki lewostronnie (prawostronne) jest zamknięta na operację odbicia zwierciadlanego.", "description": "Klasa języków generowanych przez gramatyki lewostronnie (prawostronne) jest zamknięta na operację odbicia zwierciadlanego.", "width": "800" } 55 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_56.jpg", "name": "", "description": "", "width": "800" } 56 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_57.jpg", "name": "", "description": "", "width": "800" } 57 Problemy rozstrzygalne { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/57/Problemy+rozstrzygalne.jpg", "name": "Problemy rozstrzygalne", "description": "Problemy rozstrzygalne", "width": "800" } 58 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_59.jpg", "name": "", "description": "", "width": "800" } 59 Domknięcie Kleene’go { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/59/Domkni%C4%99cie+Kleene%E2%80%99go.jpg", "name": "Domknięcie Kleene’go", "description": "Domknięcie Kleene’go", "width": "800" } 60 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/8/2345871/slides/slide_61.jpg", "name": "", "description": "", "width": "800" } 61 Budujemy deterministyczny automat równoważny niedeterministycznemu. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/2345871/8/images/61/Budujemy+deterministyczny+automat+r%C3%B3wnowa%C5%BCny+niedeterministycznemu..jpg", "name": "Budujemy deterministyczny automat równoważny niedeterministycznemu.", "description": "Budujemy deterministyczny automat równoważny niedeterministycznemu.", "width": "800" } 62

10 TAUTOLOGIA Tautologia jest to formuła spełniona przez każde wartościowanie.

11 4. Wskaż, które własności ma następująca formuła klasycznego rachunku zdań: ((¬p) ∨ (¬q)) ⇒ ¬(p ∨ q)(a) Formuła jest prawdziwa dla pewnego wartościowania. (TAK) (b) Formuła jest tautologią klasycznego rachunku zdań. (NIE) (c) Formuła jest fałszywa dla pewnego wartościowania. Tak np. p=1, q=1 (¬p) =0; p=1 (¬q)=0, q=1 ((¬p) ∨ (¬q)) =0 (p ∨ q)=1 ¬(p ∨ q)=0 (((¬p) ∨ (¬q)) ⇒ ¬(p ∨ q) ) = 1 b)Nie, bo np. p=0, q=1 (¬p)=1 (¬q)=0 ((¬p) ∨ (¬q)) =1 ¬(p ∨ q)=0 (((¬p) ∨ (¬q)) ⇒ ¬(p ∨ q) ) = 0 c)p=0,q=1 Tak np. p=1, q=1 (¬p) =0; p=1 (¬q)=0, q=1 ((¬p) ∨ (¬q)) =0 (p ∨ q)=1 ¬(p ∨ q)=0 ((¬p) ∨ (¬q)) ⇒ ¬(p ∨ q) = 1 b)p=0 q=1 (¬p)=1 (¬q)=0 ((¬p) ∨ (¬q)) =1 ¬(p ∨ q)=0 c)p=0,q=1

12 Prawem Klasycznego Rachunku Predykatów (KRP) nazywamy formułę, która jest prawdziwa we wszystkich interpretacjach danego języka. Prawa KRP są też nazywane tautologiami KRP.

13 5. Które z poniższych formuł są prawami klasycznego rachunku predykatów?Prawo rozdzielności względem koniunkcji Nie ma takiego prawa Przeniesienie kwantyfikatora egzystencjalnego za ogólny  (a) ∀x(A ∧ B) ⇔ (∀xA ∧ ∀xB) (TAK) (b) ∀x∃yA ⇔ ∃y∀xA (NIE) (c) ∃x∀yA ⇒ ∀y∃xA

14 6. Formuła ∀ 𝑥:𝑊 𝐴 jest równoważna formule (wskaż poprawne odpowiedzi):(a) ∀x(W ∧ A) . (NIE) (b) ∀x(W ⇒ A) . (TAK) (c) ∀x(¬W ∨ A) . b)Z definicji oznaczenia c)Kolejny slajd b)Z definicji oznaczenia c)Kolejny slajd

15 W A W ⇒ A 1 W A ¬W ∨ A 1 W ¬ W 1

16 ¬∀x ⇔ ∃x ¬ ∃x ⇔ ∀x ¬(A ∧ B) ⇔(¬A v ¬B) ⇔ ( A ⇒ ¬ B) (¬B v ¬A) ⇔ ( B ⇒ ¬A) Ostatnie przejście wynika z wcześniejszego slajdu

17 7. Które z poniższych formuł są logicznie równoważne formule: ¬ ∀x∃y (A∧B)?(a) ∃x∀y(A ⇒ ¬B) (TAK) (b) ∀x∃y(¬A ∨ ¬B) (NIE) (c) ∃x∀y(B ⇒ ¬A)

18 PRAWA RACHUNKU ZBIORÓWprzemienność sumy zbiorów A ∪ B = B ∪ A przemienność iloczynu zbiorów A ∩ B = B ∩ A łączność sumy zbiorów (A ∪ B) ∪ C = A ∪ (B ∪ C) łączność iloczynu zbiorów (A ∩ B) ∩ C = A ∩ (B ∩ C) rozdzielność iloczynu względem sumy zbiorów A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) rozdzielność sumy względem iloczynu zbiorów A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) prawa de Morgana dla zbiorów (A ∩ B)' = A' ∪ B' (A ∪ B)' = A' ∩ B'

19 8. Które z poniższych równości są prawami algebry zbiorów?(a) A − (B ∩ C) = (A − B) ∪ (A − C) (TAK) (b) A − (B ∩ C) = (A − B) ∩ C (NIE) (c) A − (B ∩ C) = (A − B) ∪ (A − (A ∩ C)) rysunki

20 A − (B ∩ C) = (A − B) ∪ (A − C) (TAK)Tak, bo jest to prawo De Morgana dla różnicy zbiorów Prawa dla różnicy zbiorów: A - A = ∅ ∅ - A = ∅ A - ∅ = A (A∪ B) - C = (A - C)∪ (B - C) (A∩ B) - C=(A - C) ∩ (B - C) Prawa De Morgana dla różnicy zbiorów: A - (B ∪ C) = (A - B) ∩ (A - C) A - (B ∩ C) = (A - B)∪ (A - C)

21 A − (B ∩ C) = (A − B) ∩ C (NIE)

22 A − (B ∩ C) = (A − B) ∪ (A − (A ∩ C)) (TAK)

23 9. Rodzina tych wszystkich podzbiorów zbioru A, do których należą ustalone, różne elementy x, y ∈ A, ma 32 elementy. Ile elementów ma zbiór A ? (a) 5 (NIE) (b) 6 (c) 7 (TAK) 2^5 = 32 5 + 2 = 7 2^5 = 32 5 + 2 = 7

24 10. Które warunki są równoważne warunkowi A c B ∧ A ≠ B ?(a) A − B = ∅ ∧ B − A ≠∅ ; (TAK) (b) A ∩ B = A ∧ A \ B ≠B (c) A − B c B − A ∧ A − B ≠ B − A b) A c B ⇔ A ∩ B = A A c B ∧ A ≠ B ⇒ A \ B ≠B c)A c B ⇒ A − B = ∅ B − A ∧ A − B = ∅ B − A ≠∅ b) A c B ⇔ A ∩ B = A A c B ∧ A ≠ B ⇒ A \ B ≠B c)A c B ⇒ A − B = ∅ B − A ∧ A − B = ∅ B − A ≠∅

25 11. Wskaz, które własności ma następująca relacja na zbiorze liczb rzeczywistych: x R y , |x − y| < 1. (a) Relacja R jest zwrotna. (TAK) (b) Relacja R jest przechodnia. (NIE) (c) Relacja R jest symetryczna.

26 REALCJE Relacja R może być: - zwrotna, gdy ∀ x∈X (xRx) - symetryczna, gdy ∀ x,y∈X ( xRy ⇒ yRx ) - przechodnia, gdy ∀ x,y,z∈X (xRy ∧ yRz ⇒ xRz ) - przeciwzwrotna, gdy ∀ x∈X ￢( xRx ) - antysymetryczna, gdy ∀ x,y∈X ( xRy ∧ yRx ⇒ x=y ) - spójna, gdy ∀ x,y∈X ( xRy v yRx ) - przeciwsymetryczna, gdy ∀ x,y∈X ( xRy ⇒ ￢ yRx ) - słabospójna, gdy ∀ x,y∈X ( xRy v yRx v x=y)

27 Relację , która jest zwrotna, symetryczna i przechodnia, nazywamy relacją rónoważności.Relację , która jest zwrotna, antysymetryczna i przechodnia, nazywamy relacją porządkującą. Relację porządkującą oznaczamy zazwyczaj symbolem ≼. Relację R ⊂ X × X nazywamy relacją porządku (częściowego porządku), jeśli jest ona: Zwrotna ∀x∈X x≼x Antysymetryczna ∀x,y∈X x≼y ∧ y≼x x=y Przechodnia ∀x,y,z∈X x≼y ∧ y≼z x≼z  Parę (X,≼) nazywamy zbiorem częściowo uporządkowanym lub po prostu zbiorem uporządkowanym . Jeśli dodatkowo zachodzi: Spójna ∀x,y∈X x≼y ∨ y≼x ∨ x=y to relację nazywamy porządkiem liniowym, a parę (X,≼) zbiorem uporządkowanym liniowo.

28 12. Relacje R na zbiorze X, która jest zwrotna, antysymetryczna i przechodnia, nazywamy (wskaz poprawne terminy): (a) relacja liniowo porządkująca zbiór X. (NIE) (b) relacja równoważności na zbiorze X. (c) relacja częściowo porządkująca zbiór X. (TAK) A)Nie, bo nie wiemy czy jest spójna B)Nie, bo jest antysymetryczna , a powinna być symetryczna C) Z definicji A)Nie, bo nie wiemy czy jest spójna B)Nie,bo jest antysymetryczna , a powinna być symetryczna C) Z definicji

29 13. Które z poniższych relacji na zbiorze liczb całkowitych są relacjami równoważności?a) NIE, bo nie jest zwrotna. Np. x = 2, a nieprawdą jest, że 3|(2+2) b) Czyli xRy  x i y są tego samego znaku TAK zwrotna: x jest tego samego znaku co x Symetryczna: jeśli x jest tego samego znaku co y, to y ma ten sam znak co x Przechodnia: jeśli x ma ten sam znak co y, a y ma ten sam znak co z, to x ma ten sam znak co z. c) TAK, -zwrotna: |x|=|x| -symetryczna: |x|=|y| => |y|=|x| -przechodnia: |x|=|y| /\ |y|=|z| => |x|=|z| (a) xRy ⇔ 3|(x + y) (NIE) (b) xRy ⇔ (x < 0 ∧ y < 0) V (x ≥­ 0 ∧ y ≥­ ­ 0) (TAK) (c) xRy ⇔ |x| = |y| a) NIE, bo nie jest zwrotna. Np. x = 2, a nieprawdą jest, że 3|(2+2) b) Czyli xRy  x i y są tego samego znaku TAK zwrotna: x jest tego samego znaku co x Symetryczna: jeśli x jest tego samego znaku co y, to y ma ten sam znak co x Przechodnia: jeśli x ma ten sam znak co y, a y ma ten sam znak co z, to x ma ten sam znak co z. c) TAK, -zwrotna: |x|=|x| -symetryczna: |x|=|y| => |y|=|x| -przechodnia: |x|=|y| /\ |y|=|z| => |x|=|z|

30 14. Które z poniższych zbiorów są przeliczalne?(a) zbiór wszystkich skończonych ciągów binarnych (TAK) (b) zbiór wszystkich nieskończonych ciągów binarnych (NIE) (c) zbiór wszystkich nieskonczonych ciagów binarnych, stałych od pewnego miejsca a)Zbiór n-elementowych ciągów binarnych jest przeliczalny, zbiór liczb naturalnych też, zatem zbiór wszystkich skończonych ciągów binarnych jest sumą przeliczalnie wielu zbiorów przeliczalnych, czyli jest przeliczalny. c)Tak, bo jeżeli ciągi są stałe od pewnego miejsca można je uznać za skończone (patrz pkt a). a)Zbiór n-elementowych ciągów binarnych jest przeliczalny, zbiór liczb naturalnych też, zatem zbiór wszystkich skończonych ciągów binarnych jest sumą przeliczalnie wielu zbiorów przeliczalnych, czyli jest przeliczalny. c)Tak, bo jeżeli ciągi są stałe od pewnego miejsca można je uznać za skończone (patrz pkt a).

31 Zbiór X jest równoliczny ze zbiorem Y wtw gdy istnieje bijekcja f:X→YZbiór X jest równoliczny ze zbiorem Y wtw gdy istnieje bijekcja f:X→Y. Równoliczność oznaczamy X~Y

32 Zbiór przeliczalny Zbiór A ≠ 0 jest przeliczalny wtedy i tylko wtedy, gdy jest on zbiorem wyrazów pewnego ciągu nieskończonego, czyli wtedy i tylko wtedy, gdy istnieje funkcja f przekształcająca zbiór wszystkich liczb naturalnych na zbiór A. Zbiór przeliczalny zatem to zbiór skończony lub równoliczny ze zbiorem wszystkich liczb naturalnych. Zbiory przeliczalne nieskończone są równej mocy. Moc zbiorów przeliczalnych nieskończonych oznaczamy symbolem ℵ0(czytaj: alef zero). Przykłady zbiorów przeliczalnych: - podzbiór zbioru przeliczalnego jest zbiorem przeliczalnym, - suma dowolnej skończonej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym, - produkt kartezjański zbiorów przeliczalnych jest zbiorem przeliczalnym, - zbiór wszystkich liczb całkowitych jest zbiorem przeliczalnym, - zbiór wszystkich liczb wymiernych jest zbiorem przeliczalnym, - zbiór wszystkich ciągów skończonych o wyrazach należących do ustalonego zbioru przeliczalnego jest zbiorem przeliczalnym, - zbiór wszystkich wielomianów jednej zmiennej o współczynnikach wymiernych jest przeliczalny, - zbiór wszystkich liczb algebraicznych jest przeliczalny.

33 Zbiór nieprzeliczalnyZbiór nieprzeliczalny to zbiór, który nie jest przeliczalny. Zbiór liczb rzeczywistych przedziału <0, 1> jest zbiorem nieprzeliczalnym, gdyż nie istnieje ciąg o wyrazach z przedziału <0, 1>, taki że każda liczba rzeczywista z tego przedziału jest wyrazem ciągu. Jeżeli zbiór A jest nieprzeliczalny i A ⊂ B, to B jest również zbiorem nieprzeliczalnym. Z twierdzenia tego wynika, że zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny. Moc zbioru wszystkich liczb rzeczywistych nazywamy continuum i oznaczamy symbolicznie ℭ. Zbiór wszystkich liczb niewymiernych jest zbiorem nieprzeliczalnym Zbiór wszystkich liczb przestępnych jest nieprzeliczalny.

34 15. Które z poniższych zbiorów są równoliczne ze zbiorem wszystkich liczb rzeczywistych z przedziału [0, 1] ? (a) zbiór wszystkich dodatnich liczb rzeczywistych (TAK) (b) zbiór wszystkich liczb rzeczywistych, których kwadrat jest liczba wymierna (NIE) (c) rodzina wszystkich podzbiorów zbioru liczb naturalnych a)Mocy contInuum b)Tych liczb jest 2*tyle co liczb wymiernych(liczny wymierne są przeliczalne) c)  TWIERDZENIE (Cantora)Każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy. Zbiór liczb naturalnych ma moc alef zero. a)Mocy continuum b)Tych liczb jest 2*tyle co liczb wymiernych(liczny wymierne są przeliczalne) c)  TWIERDZENIE (Cantora)Każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy. Zbiór liczb naturalnych ma moc alef zero.

35 Automaty i Języki FormalneMarta Puc Martyna Rusek

36 Domknięcie Kleene’go

37 Wyrażenia regularne

38 Język regularny

39 Języki regularne - operacje

40 Zbiór A jest podzbiorem właściwym zbioru B, gdy:

41 Operacje na językach

42

43

44

45

46

47

48 POSTAĆ NORMALNA CHOMSKY’EGOGramatyka jest w postaci normalnej Chomsky’ego, jeśli wszystkie produkcje w gramatyce są postaci: A->BC lub A->a HIERARCHIA CHOMSKY’EGO

49

50

51

52 Możliwa jest zmiana stanu bez czytania litery z wejścia.

53

54 Klasa języków generowanych przez gramatyki lewostronnie (prawostronne) jest zamknięta na operację odbicia zwierciadlanego.

55

56

57 Problemy rozstrzygalne

58

59 Domknięcie Kleene’go

60

61 Budujemy deterministyczny automat równoważny niedeterministycznemu.

62