Test GR: Różnice pomiędzy wersjami

Wersja z 08:23, 8 sie 2006

{theor}{TWIERDZENIE}[section] {rem}{UWAGA}[section] {corol}{WNIOSEK}[section] {fact}{FAKT}[section] {ex}{PRZYKŁAD}[section] {defin}{DEFINICJA}[section] {lem}{LEMAT}[section]

{prf}{DOWÓD}

{algorithm}{Algorytm}

{ automat skończenie stanowy}

Wprowadzenie: W rozdziale tym zdefiniujemy automat - drugi, obok gramatyki, model

obliczeń. Określimy język rozpoznawany przez automat i podamy warunki równoważne na to, by język był rozpoznawany.

Słowa kluczowe: automat skończenie stanowy, język rozpoznawany, prawa kongruencja

automatowa, homomorfizm automatów, monoid przejść automatu.

AUTOMATY

Wprowadzimy teraz pojęcie automatu. Jak już wspomnieliśmy w wykładzie drugim automat to drugi, obok gramatyki, model obliczeń będący przedmiotem badań teorii języków i automatów. Model realizujący warunek efektywności analitycznej, czyli taki na podstawie którego możliwe jest sformułowanie algorytmu rozstrzygającego w skończonej liczbie kroków, czy dowolne słowo należy czy też nie należy do języka rozpoznawanego przez ten automat. Lub inaczej możemy powiedzieć, że taki automat daje algorytm efektywnie rozstrzygający czy dowolne obliczenie sformułowane nad alfabetem automatu jest poprawne.

Wprowadzony w tym wykładzie automat, zwany automatem skończenie stanowym, jest jednym z najprostszych modeli obliczeń. Jest to model z bardzo istotnie ograniczoną pamięcią. Działanie takiego automatu sprowadza się do zmiany stanu pod wpływem określonego zewnętrznego sygnału czy impulsu.

Pomimo tych ograniczeń urządzenia techniczne oparte o modele takich automatów spotkać możemy dość często. Jako przykład służyć mogą automatyczne drzwi, automaty sprzedające napoje, winda czy też urządzenia sterujące taśmą produkcyjną.

Ćwiczenie [Uzupelnij]

Drzwi automatycznie otwierane są sterowane automatem, którego działanie opisać można, przyjmując następujące oznaczenia. Fakt, że osoba chce wejść do pomieszczenia zamykanego przez takie drzwi, identyfikowany przez odpowiedni czujnik, opiszemy symbolem $W E$ . Zamiar wyjścia symbolem $W Y$ . Symbol $W E W Y$ będzie związany z równoczesnym zamiarem wejścia jakiejś osoby i wyjścia innej. Wreszcie symbol $B R A K$ oznaczał będzie brak osób, które chcą wejść lub wyjść. Zatem zbiór ${W E, W Y, W E W Y, B R A K}$ , to alfabet nad którym określimy automat o $2$ stanach: Parser nie mógł rozpoznać (błąd składni): {\displaystyle OTWARTE, ZAMKNIĘTE} poniższym grafem.

RYSUNEK ja-lekcja3-w-rys6

ANIMACJA ja-lekcja-w-rys7 działania drzwi

Automaty reagują więc na określone sygnały zewnętrzne reprezentowane przez litery alfabetu $A$ zmieniając swój stan. Jeśli ustalimy stan początkowy automatu oraz dopuszczalne stany końcowe, to automat będzie testował dowolne słowo z $A^{*}$ startując ze stanu początkowego. Jeśli rezultatem finalnym działania automatu (obliczenia) będzie stan końcowy, to słowo będzie rozpoznawane przez automat, a obliczenie określone takim słowem poprawne.

Podamy teraz definicję automatu. Niech $A$ oznacza dowolny alfabet. Od tego momentu wykładu zakładamy, że alfabet jest zbiorem skończonym.

Automatem nad alfabetem $A$ nazywamy system $𝒜 = (S, f)$ , w którym

$S$ - jest dowolnym skończonym zbiorem zwanym zbiorem stanów,

$f : S \times A \to S$ - jest funkcją przejść.

Automat będąc w stanie $s_{i}$ po przeczytaniu litery $a$ zmienia stan na $s_{j}$ zgodnie z funkcją przejścia $f (s_{i}, a) = s_{j}$ .

Funkcję przejść rozszerzamy na cały wolny monoid

A^{*}

do postaci

f : S \times A^{*} \to S

przyjmując:

dla każdego $s \in S f (s, 1) = s$ oraz

dla każdego $s \in S, a \in A$ i dla dowolnego $w \in A^{*}$

f (s, w a) = f (f (s, w), a) .

Działanie automatu pokazane jest na rysunku.

rys3.1

Zdefiniowany powyżej automat $𝒜$ nazywamy skończonym lub skończenie stanowym ze względu na założenie skończoności zbioru stanów $S$ .

Ćwiczenie [Uzupelnij]

Niech $A = {a, b}$ będzie alfabetem, a $𝒜 = (S, f)$ automatem takim, że

$S = {s_{0}, s_{1}, s_{2}}$ , a funkcja przejść zadana jest przy pomocy tabelki

{

Podamy teraz bardzo interesujący przykład zastosowania automatów skończonych. Przedstawimy mianowicie wykorzystanie tak zwanych automatów synchronizujących w przemyśle. Automat synchronizujący nad alfabetem $A$ to automat $(S, f)$ o następującej własności: istnieje stan $t \in S$ oraz słowo $w \in A^{*}$ takie, że dla każdego stanu $s$ tego automatu $f (s, w) = t$ . Istnieje więc pewne uniwersalne słowo $w$ , pod wpływem którego wszystkie stany przechodzą w jeden, ustalony stan automatu $t \in S$ . Mówimy, że następuje wtedy synchronizacja wszystkich stanów automatu.

Poniżej prezentujemy przykład zaczerpnięty z pracy Ananicheva i Volkova (D. S. Ananichev, M. V. Volkov, Synchronizing Monotonic Automata, Lecture Notes in Computer Science, 2710(2003), 111--121.), ukazujący ideę użycia automatów synchronizujących w tej dziedzinie.

Ćwiczenie [Uzupelnij]

RYSUNEK pojedynczego detalu - ja-lekcja3-w-rys-s1

Załóżmy, że pewna fabryka produkuje detale w kształcie kwadratu z "wypustką" na jednym boku (patrz rys. Uzupelnic ja-lekcja3-w-rys-s1|). Po wyprodukowaniu detale należy umieścić w opakowaniach w ten sposób, by wszystkie były w tej samej orientacji - mianowicie "wypustką" w lewo.

Załóżmy ponadto dla uproszczenia, że detale mogą przyjmować jedną z czterech orientacji (rys. Uzupelnic ja-lekcja3-w-rys-s2|): "wypustką" w górę, w dół, w lewo lub w prawo.

RYSUNEK ja-lekcja3-w-rys-s2

Należy zatem skonstruować takie urządzenie (orienter), które będzie ustawiało wszystkie detale w żądanej orientacji. Oczywiście istnieje wiele metod rozwiązania tego problemu, ale z praktycznego punktu widzenia potrzebne jest rozwiązanie najprostsze i najtańsze. Jednym z takich sposobów jest umieszczanie detali na pasie transmisyjnym z zamontowaną wzdłuż niego pewną ilością przeszkód dwojakiego rodzaju: niskich (low) oraz wysokich (HIGH). Wysoka przeszkoda ma tę własność, że każdy detal, który ją napotka zostanie obrócony o 90 stopni w prawo (zakładamy, że elementy jadą od lewej do prawej strony). Przeszkoda niska obróci o 90 stopni w prawo tylko te detale, które są ułożone "wypustką" w dół. Na rys. Uzupelnic ja-lekcja3-w-rys-s3| przedstawione zostały przejścia pomiędzy orientacjami detali w zależności od napotkania odpowiedniej przeszkody.

RYSUNEK ja-lekcja3-w-rys-s3

Można zauważyć, że automat z rysunku Uzupelnic ja-lekcja3-w-rys-s3| jest automatem synchronizującym. Słowem, które go synchronizuje jest następująca sekwencja przeszkód:

low-HIGH-HIGH-HIGH-low-HIGH-HIGH-HIGH-low.

Niezależnie od tego, w jakiej orientacji początkowej znajduje się detal, po przejściu przez powyższą sekwencję przeszkód zawsze będzie ułożony "wypustką" w lewo. Sytuację przedstawia poniższa animacja:

ANIMACJA ja-lekcja3-w-anim-s4

Rozszerzymy teraz wprowadzone pojęcie automatu w ten sposób by uzyskać możliwość efektywnego rozstrzygania czy dowolne słowo utworzone nad alfabetem $A$ reprezentuje poprawne obliczenie, czyli spełnia kryteria określone przez rozszerzony automat.

Język $L \subset A^{*}$ jest rozpoznawany (akceptowany) wtedy i tylko wtedy, gdy istnieje automat skończony $𝒜 = (S, f),$ stan $s_{0} \in S$ oraz zbiór $T \subset S$ takie, że

L = {w \in A^{*} : f (s_{0}, w) \in T} .

Stan

s_{0}

nazywamy stanem początkowym,

a $T$ zbiorem stanów końcowych automatu $𝒜$ .

Rozszerzony w powyższy sposób automat, poprzez dodanie stanu początkowgo i zbioru stanów końcowych, w dalszym ciągu nazywamy automatem i oznaczamy jako piątkę $𝒜 = (S, A, f, s_{0}, T)$ lub czwórkę $𝒜 = (S, f, s_{0}, T)$ , jeśli wiadomo, nad jakim alfabetem rozważamy działanie automatu.

Fakt, że język $L$ jest rozpoznawany przez automat $𝒜,$ zapisujemy jako

L = L (𝒜) .

Rodzinę wszystkich języków rozpoznawalnych nad alfabetem $A$ oznaczamy przez $ℛ ℰ 𝒞 (𝒜^{*})$ .

Podobnie jak w przypadku gramatyk nie ma jednoznacznej odpowiedniości pomiędzy językami rozpoznawalnymi a automatami. Wprowadza się więc relację, która identyfikuje automaty rozpoznające ten sam język.

Automaty $𝒜_{1}$ i $𝒜_{2}$ są równoważne, jeśli rozpoznają ten sam język, czyli

L (𝒜_{1}) = L (𝒜_{2}) .

W dalszych rozważaniach języków rozpoznawanych ograniczymy się do automatów $𝒜 = (S, A, f, s_{0}, T)$ , które spełniają warunek $f (s_{0}, A^{*}) = S .$ Nie zawęża to naszych rozważań. Jeśli bowiem język $L$ jest rozpoznawany przez pewien automat $𝒜 = (S, A, f, s_{0}, T)$ , to jest również rozpoznawany przez automat

ℬ = (f (s_{0}, A^{*}), A, f |_{f (s_{0}, A^{*}) \times A^{*}}, s_{0}, T \cap f (s_{0}, A^{*})),

który spełnia powyższy warunek. Zauważmy, że przyjmując to założenie upraszczamy strukturę automatu. Z punktu widzenia grafu automatu można powiedzieć, że nie występują w nim wierzchołki (stany) nieosiagalne ze z $s_{0}$ . Poniżej przedstawiamy algorytm usuwający z automatu stany nieosiągalne ze stanu początkowego.

{{UsuńStanyNieosiągalne} - usuwa z automatu $𝒜$ stany nieosiągalne} [1] Wejście: $𝒜 = (S, A, f, s_{0}, T)$ - automat

Wyjście: $𝒜^{'} = (S^{'}, A, f^{'}, s_{0}, T^{'})$ - automat równoważny automatowi $𝒜$ bez stanów nieosiągalnych.

procedure {Oznacz} $(x \in S)$

{Parser nie mógł rozpoznać (błąd składni): {\displaystyle p \in S:\ \exists a \in A\ f(x,a)=p \wedge \mbox{\textbf{zaznaczone}}[p]==0} }

zaznaczone $[p] \leftarrow 1$ ;

{Oznacz} $(p)$ ;

end procedure

{ $p \in S$ }

zaznaczone $[p] \leftarrow 0$ ;

zaznaczone $[s_{0}] \leftarrow 1$ ;

{Oznacz} $(s_{0})$ ;

Parser nie mógł rozpoznać (błąd składni): {\displaystyle S' = \{s \in S:\ \mbox{\textbf{zaznaczone}}[s]==1\}} ;

$T^{'} = T \cap S^{'}$ ;

jeśli istnieje przynajmniej jeden stan, dla którego funkcja przejścia $f$ nie jest określona dla jakiejś litery $a \in A$ , dodaj stan $s_{f}$ do $S^{'}$ i dla każdego stanu $s$ i litery $a$ jeśli $f (s, a)$ jest nieokreślone, to zdefiniuj $f (s, a) = s_{f}$ ;

$f^{'} \leftarrow f$ ;

$𝒜^{'} = (S^{'}, A, f^{'}, s_{0}, T^{'})$ ;

Powyższy algorytm, dla ustalonego alfabetu $A$ , posiada złożoność $O (| A | \cdot | S |)$ , czyli liniową względem liczby stanów.

Ćwiczenie [Uzupelnij]

Jeśli w przykładzie Uzupelnic ex.3.1.1| przyjmiemy stan $s_{0}$ jako stan początkowy, $T = {s_{2}}$ jako zbiór stanów końcowych, to automat $𝒜 = (S, A, f, s_{0}, T)$ rozpoznaje język

L (𝒜) = A^{*} {a^{2}}

złożony ze słów, kończących się na $a^{2}$ .
Słowo $a b a$ nie jest akceptowane. rys3.3
Słowo $a b a a$ jest akceptowane. rys3.4

Każdy automat $𝒜 = (S, A, f, s_{0}, T)$ wyznacza w wolnym monoidzie $A^{*}$ prawą kongruencję, nazywaną prawą kongruencją automatową, określoną w następujący sposób:
$\forall u, v \in A^{*}$

u \sim_{𝒜} v ⟺ f (s_{0}, u) = f (s_{0}, v) .

Dla automatu skończonego ( o skończonym zbiorze stanów), a takie rozważamy, relacja $\sim_{A}$ ma skończony indeks, czyli skończoną liczbę klas równoważności.

Ćwiczenie [Uzupelnij]

Automat z przykładu Uzupelnic ex.3.1.1| ze stanem $s_{0}$ jako początkowym wyznacza relację równoważności o trzech klasach:

$[1] = A^{*} {b} \cup {1} [a] = A^{*} {b a} \cup {a} [a^{2}] = A^{*} {a^{2}}$

Na odwrót, każda prawa kongruencja $ρ \subset (A^{*})^{2}$ wyznacza automat, zwany ilorazowym, w następujący sposób:

𝒜_{ρ} = (A^{*} /_{ρ}, f^{*}), g d z i e f^{*} ([w]_{ρ}, u) = [w u]_{ρ} .

𝒜

_Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest automatem ze stanem początkowym } [1]_

.

{A}_{ } Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest automatem skończonym wtedy i~tylko wtedy, gdy relacja ma skończony indeks.\\ Z definicji prawej kongruencji wynika, że funkcja przejść } f^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest określona poprawnie. \begindefin Niech } {A} =(S,f)

i

{B} =(T,g)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będą dowolnymi automatami. Odwzorowanie } :S T Parser nie mógł rozpoznać (błąd składni): {\displaystyle nazywamy \textbf{homomorfizmem automatów}\index{homomorfizm automatów} wtedy i~tylko wte\-dy, jeśli } s S, w A^*(f(s,w)) = g((s),w).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Homomorfizm automatów oznaczamy } :{A} {B} Parser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle . \enddefin \begintheor Prawdziwe są następujące fakty: # Dla dowolnej prawej kongruencji } (A^*)^2

_{{A}_{ }}= ,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle # Dowolny automat } {A} = (S,A,f,s_0,T)

j e s t i z o m o r f i c z n y z a u t o m a t e m

{A}_{ _Szablon:A} Parser nie mógł rozpoznać (błąd składni): {\displaystyle , # Dla dowolnych automatów } {A}_1= (S_1,A,f_1,s^1_0,T_1)

i

{A}_2 = (S_2,A,f_2,s^2_0,T_2)Parser nie mógł rozpoznać (błąd składni): {\displaystyle prawdziwa jest równoważność {\par\centering } _{{A}_1} _{{A}_2}

i s t n i e j e e p i m o r f i z m

:{A}_1 {A}_2 Parser nie mógł rozpoznać (błąd składni): {\displaystyle taki, że } (s^1_0) = s^2_0Parser nie mógł rozpoznać (nieznana funkcja „\par”): {\displaystyle . \par} \endtheor \beginprf \hfill # Identyczność relacji wynika wprost z~defi\-ni\-cji automatu ilorazowego } {A}

_{ρ}

oraz prawej kongruencji

\sim_{A_{ρ}}

.

Rozważmy automat $𝒜 = (S, A, f, s_{0}, T)$ i odwzorowanie

ψ : 𝒜 ⟶ 𝒜_{\sim_{𝒜}},

gdzie $\forall s \in S$

ψ (s) = [w]_{\sim_{𝒜}} dla w \in A^{*} i f (s_{0}, w) = s .

Istnienie słowa $w$ wynika z faktu, że $s_{0}$ jest stanem początkowym, natomiast z definicji relacji $\sim_{𝒜}$ wynika, że odwzorowanie $ψ$ jest poprawnie określone.
Odwzorowanie $ψ$ ma być homomorfizmem, czyli dla każdego stanu $s \in S$ i dowolnego słowa $w \in A^{*}$ spełniać warunek

ψ (f (s, w)) = f^{*} (ψ (s), w) .

Warunek ten wynika z następujących równości

\begin{array}{c} f^{*} (ψ (s), w) = f^{*} ([u]_{\sim_{𝒜}}, w) = [u w]_{\sim_{𝒜}} = \\ = {v \in A^{*} : f (s_{0}, u w) = f (s_{0}, v)} = \\ {v \in A^{*} : f (f (s_{0}, u), w) = f (s_{0}, v)} = \\ = {v \in A^{*} : f (s, w) = f (s_{0}, v)} = ψ (f (s, w)) \end{array}

gdzie $f (s_{0}, u) = s$ .

Z prostych obserwacji wynika, że $ψ$ jest suriekcją i iniekcją.

Dowód implikacji " $\Rightarrow$ "

Załóżmy, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2 } } . Niech

φ : 𝒜_{1} ⟶ 𝒜_{2}

będzie odwzorowaniem takim, że

\forall s \in S_{1}

φ (s) = f_{2} (s_{0}^{2}, w), gdzie w \in A^{*} i f_{1} (s_{0}^{1}, w) = s .

Stąd, że $s_{0}^{1}$ jest stanem początkowym automatu $𝒜_{1},$ wynika, że istnieje słowo $w \in A^{*}$ potrzebne do określenia epimorfizmu $φ$ .
Z założenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2} } wynika, że $φ$ jest poprawnie zdefiniowaną funkcją.
Uzasadnienie faktu, że $φ$ jest homomorfizmem, jest analogiczne jak w punkcie Uzupelnic tb| dla $ψ$ .
$φ$ jest suriekcją, gdyż $s_{0}^{2}$ jest stanem początkowym automatu $𝒜_{2}$ .
$φ (s_{0}^{1}) = s_{0}^{2},$ ponieważ $f_{1} (s_{0}^{1}, 1) = s_{0}^{1}$ .
Dowód implikacji " $\Leftarrow$ "
Niech $φ : 𝒜_{1} ⟶ 𝒜_{2}$ będzie epimorfizmem takim, że $φ (s_{0}^{1}) = s_{0}^{2}$ .
Wówczas prawdziwy jest następujący ciąg wnioskowań.

\begin{array}{c} u \sim_{𝒜_{1}} v \Leftrightarrow f_{1} (s_{0}^{1}, u) = f_{1} (s_{0}^{1}, v) \Rightarrow \\ \Rightarrow φ (f_{1} (s_{0}^{1}, u)) = φ (f_{1} (s_{0}^{1}, v)) \Rightarrow f_{2} (s_{0}^{2}, u) = f_{2} (s_{0}^{2} v) \Leftrightarrow u \sim_{𝒜_{2}} v \end{array}

To oznacza, że $\sim_{𝒜_{1}} \subseteq \sim_{𝒜_{2}}$ .

$♢$

Symbolem $S^{S}$ oznaczamy rodzinę wszystkich funkcji określonych na zbiorze $S$ i przyjmujących wartości w $S$ . Łatwo zauważyć, iż rodzina ta wraz ze składaniem odwzorowań jest monoidem $(S^{S}, \circ)$ .

Niech $𝒜 = (S, f)$ będzie dowolnym automatem. Reprezentacją automatu $𝒜$ nazywamy funkcję $τ_{𝒜} : A^{*} ⟶ S^{S}$ określoną dla dowolnych $w \in A^{*}$ i $s \in S$ równością

τ_{𝒜} (w) (s) = f (s, w) .

Reprezentacja automatu jest homomorfizmem monoidu $A^{*}$ w monoid $S^{S}$ , bowiem dla dowolnych $v, w \in A^{*}$ spełnione są warunki

\begin{array}{c} τ_{𝒜} (v w) = τ_{𝒜} (w) \circ τ_{𝒜} (v), \\ τ_{𝒜} (1) = i d_{S} . \end{array}

Niech

𝒜

= (S,f)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będzie dowolnym automatem. \textbf{Monoidem przejść}\index{monoid przejść} automatu } {A}

n a z y w a m y m o n o i d

{M}({A})= _Szablon:A(A^{*}) S^{S}.

Parser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle \enddefin Następujace wnioski są konsekwencjami rozważań przeprowadzonych powyżej. \begincorol \vspace{-5truemm}\\ # Monoid przejść automatu } {A}

j e s t p o d m o n o i d e m m o n o i d u

S^S Parser nie mógł rozpoznać (błąd składni): {\displaystyle i zbiór } _Szablon:A(a):a A Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest zbiorem generatorów tego monoidu. }

{M}({A})= _Szablon:A(a):a A ^{*}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Wynika to z faktu, że } _Szablon:A Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest epimorfizmem i z twierdzenia~[[##tw:z|Uzupelnic tw:z|]]. # Monoid przejść automatu skończonego jest skończony. # Monoid przejść automatu } {A}

j e s t i z o m o r f i c z n y z m o n o i d e m i l o r a z o w y m

A^{*}/_{Ker_{ _Szablon:A}} Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jest to wniosek z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ilustruje poniższy diagram. rys3.5 \endcorol {{cwiczenie|[Uzupelnij]|| Określimy monoid przejść dla automatu z przykładu [[##ex.3.1.1|Uzupelnic ex.3.1.1|]]. Wypisujemy kolejne funkcje } _Szablon:A(w)

d l a

w a,b^{*} Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zauważmy, że ze względu na występujące w tabelce powtórzenia będace wynikiem równości, np. } _Szablon:A(b^2)= _Szablon:A(b), Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie ma potrzeby określać funkcji } _Szablon:A(b^{n})

d l a

n 3 Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Podobna obserwacja ma miejsce w innych przypadkach, co sprawia, że tabelka zawiera skończoną liczbę różnych funkcji. \vspace{0.3cm} {\centering \begintabular {|c||c|c|c|} \hline & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline \hline } _Szablon:A(1) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(a) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(b) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(a^{2}) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(ab) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(ba) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(b^{2}) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(aba) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline ...& ...& ...& ...\\ \hline \endtabular \par} \vspace{0.3cm} }

M({A})= _Szablon:A(1), _Szablon:A(a), _Szablon:A(b),

_Szablon:A(a^2), _Szablon:A(b), _Szablon:A(ba), _Szablon:A(aba)

.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} Poniżej zamieszczamy algorytm obliczający monoid przejść dla automatu skończenie stanowego. \beginalgorithm \caption{\textsc{WyznaczMonoidPrzejść} - wyznacza monoid przejść dla automatu} \beginalgorithmic [1] \STATE Wejście: } {A}=(S, A, f, s_0, T)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle - automat \STATE Wyjście: } MParser nie mógł rozpoznać (błąd składni): {\displaystyle - monoid przejść dla } {A}Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle \STATE } L

;

LParser nie mógł rozpoznać (błąd składni): {\displaystyle jest listą \STATE } M Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle ; \FOR{} a A 1Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{insert}} (L, _Szablon:A(a))

; g d z i e

_Szablon:A(a)(s)=f(s, a)Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla każdego } s SParser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle \ENDFOR \WHILE{} L = Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ;} \STATE } _Szablon:A(w) first(L)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } M M _Szablon:A(w)Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle ; \FOR{} a AParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } s S'_Szablon:A(wa)(s)=f(_Szablon:A(w)(s),a)Parser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle ; \IF{} '_Szablon:A(wa) L MParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{insert}} (L, '_Szablon:A(wa))Parser nie mógł rozpoznać (nieznana funkcja „\ENDIF”): {\displaystyle ; \ENDIF \ENDFOR \ENDWHILE \RETURN } MParser nie mógł rozpoznać (nieznana funkcja „\endalgorithmic”): {\displaystyle ; \endalgorithmic \endalgorithm \eject Procedura \textbf{insert}} (L, x)Parser nie mógł rozpoznać (błąd składni): {\displaystyle wkłada na koniec listy } L

e l e m e n t

x

. F u n k c j a first

(L)Parser nie mógł rozpoznać (błąd składni): {\displaystyle wyjmuje pierwszy element znajdujący się na liście } LParser nie mógł rozpoznać (błąd składni): {\displaystyle i zwraca go. Algorytm działa w następujący sposób: najpierw na listę } LParser nie mógł rozpoznać (błąd składni): {\displaystyle wkładane są elementy monoidu przejść } _Szablon:A(a)Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla każdej litery } a A 1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Te funkcje można obliczyć bezpośrednio z tabelki reprezentującej funkcję przejścia automatu } {A}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Następnie z listy po kolei ściągane są poszczególne funkcje } _Szablon:A(w)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Każda z nich dodawana jest do zbioru } MParser nie mógł rozpoznać (błąd składni): {\displaystyle , a następnie algorytm sprawdza dla każdej litery } a A

, c z y f u n k c j a

_Szablon:A(wa)Parser nie mógł rozpoznać (błąd składni): {\displaystyle istnieje już na liście } L

l u b w z b i o r z e

MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli nie, to funkcja ta dodawana jest do listy. Procedura powyższa trwa do czasu, gdy lista } LParser nie mógł rozpoznać (błąd składni): {\displaystyle zostanie pusta. Wtedy wszystkie elementy monoidu przejść znajdą się w zbiorze } MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Przeanalizujmy działanie algorytmu dla automatu z przykładu [[##ex.3.1.1|Uzupelnic ex.3.1.1|]]. Na początku na listę } LParser nie mógł rozpoznać (błąd składni): {\displaystyle włożone zostaną funkcje } _Szablon:A(1)

,

_Szablon:A(a)

o r a z

_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Z listy zdejmujemy funkcję } _Szablon:A(1)Parser nie mógł rozpoznać (błąd składni): {\displaystyle i dodajemy ją do zbioru } MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ } a A_Szablon:A(1a)=_Szablon:A(a)

, a f u n k c j e

_Szablon:A(a)

o r a z

_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle znajdują się już na liście, zatem nie dodajemy ich do } L

. B i e r z e m y k o l e j n y e l e m e n t l i s t y,

_Szablon:A(a)

, d o d a j e m y g o d o

M

i o b l i c z a m y f u n k c j e

_Szablon:A(aa)

o r a z

_Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ } _Szablon:A(aa)Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie jest tożsama z żadną funkcją ze zbioru } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do listy. Funkcja } _Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle również nie jest równa żadnej z funkcji należących do zbioru } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle , zatem wstawiamy ją na koniec listy. Na liście } LParser nie mógł rozpoznać (błąd składni): {\displaystyle mamy zatem teraz następujące elementy: } _Szablon:A(b)

,

_Szablon:A(a^2)

o r a z

_Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zdejmujemy z listy funkcję } _Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do } M

i o b l i c z a m y

_Szablon:A(ba)

o r a z

_Szablon:A(bb)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Pierwsza z tych funkcji jest nowa, tzn. nie jest tożsama z żadną funkcją ze zbioru } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle więc dodajemy ją na koniec listy. Druga z nich równa jest funkcji } _Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc nie dodajemy jej do listy. W tym momencie zbiór } MParser nie mógł rozpoznać (błąd składni): {\displaystyle zawiera następujące elementy: } _Szablon:A(1)

,

_Szablon:A(a)

,

_Szablon:A(b)

, n a t o m i a s t l i s t a z a w i e r a e l e m e n t y

_Szablon:A(a^2)

,

_Szablon:A(ab)

,

_Szablon:A(ba)

. Z d e j m u j e m y z

LParser nie mógł rozpoznać (błąd składni): {\displaystyle funkcję } _Szablon:A(a^2)

, d o d a j e m y j a d o

MParser nie mógł rozpoznać (błąd składni): {\displaystyle i ponieważ } _Szablon:A(a^2a)=_Szablon:A(a^2)

i

_Szablon:A(a^2b)=_Szablon:A(b)

n i c n i e d o d a j e m y d o

LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Zdejmujemy teraz z listy funkcję } _Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do } MParser nie mógł rozpoznać (błąd składni): {\displaystyle i ponieważ } _Szablon:A(aba)Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie należy do } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle dodajemy ją do listy. } _Szablon:A(abb)=_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc tej funkcji nie dodajemy do } L

. Z

LParser nie mógł rozpoznać (błąd składni): {\displaystyle ściągamy } _Szablon:A(ba)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do } MParser nie mógł rozpoznać (błąd składni): {\displaystyle i widzimy, że } _Szablon:A(baa)=_Szablon:A(a^2)

o r a z

_Szablon:A(bab)=_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc nic nie dodajemy do } LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Na liście pozostała funkcja } _Szablon:A(aba)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ściągamy ją z listy i dodajemy do } MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Widzimy, że } _Szablon:A(abaa)=_Szablon:A(a^2)

i

_Szablon:A(abab)=_Szablon:A(b)

, z a t e m n i c n i e d o d a j e m y d o l i s t y

LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Lista jest w tym momencie pusta i działanie algorytmu zakończyło się. Ostatecznie mamy }

M({A})= _Szablon:A(1),_Szablon:A(a),

_Szablon:A(b),_Szablon:A(a^2),_Szablon:A(ab),

_Szablon:A(ba),_Szablon:A(aba).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Co zgadza się z wynikiem otrzymanym w przykładzie. Twierdzenie poniższe zbiera dotychczas uzyskane charakteryzacje języków rozpoznawanych. \begintheor Niech } L A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle będzie dowolnym językiem. Równoważne są następujące warunki: # Język } L Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozpoznawalny, # Język } L Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest sumą wybranych klas równoważności pewnej prawej kongruen\-cji na } A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle o skończonym indeksie: }

L = _{w L}[w]_.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle # Język } L Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest sumą wybranych klas równoważności pewnej kongruencji na } A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle o skończonym indeksie: }

L = _{w L}[w]_.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle # Istnie\-je skończony monoid } M Parser nie mógł rozpoznać (błąd składni): {\displaystyle i istnie\-je epimorfizm } : A^* MParser nie mógł rozpoznać (błąd składni): {\displaystyle taki, że }

L = ^{-1}( (L)).

Parser nie mógł rozpoznać (nieznana funkcja „\endtheor”): {\displaystyle \endtheor \beginprf Dowód równoważności czterech powyższych warunków przeprowa\-dzi\-my zgodnie z następującym schematem: }

Parser nie mógł rozpoznać (błąd składni): {\displaystyle [[##tg|Uzupelnic tg|]] [[##tf|Uzupelnic tf|]] Dany jest homomorfizm }

: A^* M,

g d z i e

MParser nie mógł rozpoznać (błąd składni): {\displaystyle jest skończonym monoidem.\\ Określamy relację na } A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle , przyjmując dla dowolnych } u, v A^*

u v (u) = (v).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Tak określona relacja jest kongruencją. Natomiast jej skończony indeks wynika z faktu, że monoid } M Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest skończony. Pokażemy teraz, że: }

L = _{w L}[w]_ .

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Inkluzja jest oczywista.\\ Inkluzja w przeciwną stronę (} L _{w L}[w]_,Parser nie mógł rozpoznać (błąd składni): {\displaystyle ) oznacza, że każda klasa równoważności relacji albo cała zawiera się w języku } LParser nie mógł rozpoznać (błąd składni): {\displaystyle , albo cała zawiera się w uzupełnieniu języka } LParser nie mógł rozpoznać (błąd składni): {\displaystyle .\\ Załóżmy, że } u [w]_

d l a p e w n e g o

w L. Parser nie mógł rozpoznać (błąd składni): {\displaystyle Oznacza to, że }

u w (u) = (w) (L) u ^{-1}( (u)) ^{-1}( (L)) = L.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Implikuje to ostatecznie, że } u LParser nie mógł rozpoznać (błąd składni): {\displaystyle . [[##tf|Uzupelnic tf|]] [[##te|Uzupelnic te|]] Każda kongruencja jest prawą kongruencją. [[##te|Uzupelnic te|]] [[##td|Uzupelnic td|]] Niech będzie prawą kongruencją o skończonym indeksie na } A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle taką, że }

L = _{w L}[w]_ .

A u t o m a t

{A}_{ } = (A^*/,f^*,[1]_,T),Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla którego }

f^*([w]_,u) =[wu]_ , T = [w]_ : w L

Parser nie mógł rozpoznać (błąd składni): {\displaystyle akceptuje język } LParser nie mógł rozpoznać (błąd składni): {\displaystyle . [[##td|Uzupelnic td|]] [[##tg|Uzupelnic tg|]] Niech język } L=L({A})

, g d z i e

{A} = (S,f,s_0,T)Parser nie mógł rozpoznać (błąd składni): {\displaystyle .\\ Określamy odwzorowanie }

:A^{*} A^{*}/_{Ker _Szablon:A},

Parser nie mógł rozpoznać (błąd składni): {\displaystyle przyjmując dla każdego } v A^{*}

(v)=[v]_{Ker _Szablon:A}.

J e s t t o o d w z o r o w a n i e k a n o n i c z n e m o n o i d u

A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle na monoid ilorazowy, a więc jest to epimorfizm.\\ } A^{*}/_{Ker _Szablon:A} Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest monoidem skończonym, ponieważ } S Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest zbiorem skończonym. Dla dowodu równości } L = ^{-1}( (L))Parser nie mógł rozpoznać (błąd składni): {\displaystyle wystarczy udowodnić inkluzję } L ^{-1}( (L))

. (I n k l u z j a

L ^{-1}( (L))Parser nie mógł rozpoznać (błąd składni): {\displaystyle wynika z~definicji przeciwobrazu.) \\ Niech } u ^{-1}( (L)) .Parser nie mógł rozpoznać (błąd składni): {\displaystyle Oznacz to, że }

{c}

(u) (L) v L : (u)= (v) v L : [u]_{_{Ker _Szablon:A}}=[v]_{_{Ker _Szablon:A}}
v L : _Szablon:A(u)= _Szablon:A(v) , v L : s S f(s,u)=f(s,v)

Parser nie mógł rozpoznać (błąd składni): {\displaystyle W szczególności }

f(s_0,u) = f(s_0,v) T,

c z y l i

u L.Parser nie mógł rozpoznać (nieznana funkcja „\begincenter”): {\displaystyle \begincenter \endcenter \endprf}

Test GR: Różnice pomiędzy wersjami

Wersja z 08:23, 8 sie 2006

AUTOMATY

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-==Wprowadzenie==
+{theor}{TWIERDZENIE}[section]
+{rem}{UWAGA}[section]
+{corol}{WNIOSEK}[section]
+{fact}{FAKT}[section]
+{ex}{PRZYKŁAD}[section]
+{defin}{DEFINICJA}[section]
+{lem}{LEMAT}[section]
-Logika zdaniowa jest językiem, który pozwala opisywać zależności
+{prf}{DOWÓD}
-pomiędzy zdaniami. Przykładem może być zdanie:
+{algorithm}{Algorytm}
-<center>Jeśli <math>\textnormal{n}</math> jest liczbą pierwszą to <math>\textnormal{n}</math> jest liczbą nieparzystą lub <math>\textnormal{n}</math> jest równe '''2'''.</center>
+{ automat skończenie stanowy}
-W powyższym zdaniu spójniki '''jeśli [..] to, lub''' mówią o związkach które zachodzą pomiędzy zdaniami:
+; Wprowadzenie
+:  W rozdziale tym zdefiniujemy automat - drugi, obok gramatyki, model
+obliczeń. Określimy język rozpoznawany przez automat i podamy warunki równoważne na to,
+by język był rozpoznawany.
-. ''<math>\textnormal{n}</math> jest liczbą pierwszą,''
+; Słowa kluczowe
+:  automat skończenie stanowy, język rozpoznawany, prawa kongruencja
+automatowa, homomorfizm automatów, monoid przejść automatu.
-. ''<math>\textnormal{n}</math> jest liczbą nieparzystą,''
+==AUTOMATY==
-. ''<math>\textnormal{n}</math> jest równe 2.''
+Wprowadzimy teraz pojęcie automatu. Jak już wspomnieliśmy w wykładzie drugim
+automat to drugi, obok gramatyki, model obliczeń będący przedmiotem badań
+teorii języków i automatów. Model realizujący  warunek efektywności analitycznej,
+czyli taki na podstawie którego możliwe jest sformułowanie algorytmu rozstrzygającego
+w skończonej liczbie kroków, czy dowolne słowo należy
+czy też nie należy do  języka rozpoznawanego przez ten automat. Lub inaczej możemy
+powiedzieć, że taki automat daje algorytm efektywnie rozstrzygający   czy dowolne
+obliczenie sformułowane nad alfabetem automatu jest poprawne.
-Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
+Wprowadzony w tym wykładzie automat, zwany automatem skończenie stanowym, jest jednym
-kolejności). Używając symboli, które zwyczajowo odpowiadają
+z najprostszych modeli obliczeń. Jest to model z bardzo istotnie ograniczoną pamięcią.
-potocznemu rozumieniu spójników '''jeśli [..] to, lub''' oraz powyższych oznaczeń otrzymamy formułę
+Działanie takiego automatu sprowadza się do zmiany stanu  pod
+wpływem określonego zewnętrznego sygnału czy impulsu.
+Pomimo tych ograniczeń urządzenia techniczne oparte o modele takich automatów spotkać
+możemy dość często. Jako przykład służyć mogą automatyczne drzwi, automaty sprzedające
+napoje, winda czy też urządzenia sterujące taśmą produkcyjną.
-<center><math>
+{{cwiczenie|[Uzupelnij]||
-p \Rightarrow (q \vee r).
-</math></center>
-Jeśli powyższą formułę uznamy za prawdziwą to może nam ona posłużyć
-do otrzymania nowych wniosków. Na przykład jeśli o jakiejś liczbie <math>\textnormal{n}</math> będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest nieparzysta to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt że liczba <math>\textnormal{n}</math> jest równa '''2'''. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:
-. <math> p \Rightarrow (q \vee r) </math>,
-. <math>p </math>,
-. <math> \neg q </math> (przez <math>\neg</math> oznaczamy negację)
-to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań
-powinniśmy uznać za prawdziwe zdanie <math>\textnormal{r}</math>, czyli ''<math>\textnormal{n}</math> jest równe '''2'''''. Powyższy schemat wnioskowania można również opisać formułą
-<center><math>
-\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right)\Rightarrow q.
-</math></center>
-W powyższej formule spójnik symbol <math>\wedge</math> odpowiada spójnikowi <math>\textnormal{i}</math> (oraz).
-Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy
-wnioskowania i zdania złożone oraz oceniać ich prawdziwość.
-==Język logiki zdaniowej==
-Zaczniemy od definicji języka logiki zdaniowej. Składa się on z
-formuł zdefiniowanych następująco:
-{{definicja|2.1 [Formuła logiki zdaniowej]||
-''1. zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy
-zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)''
-''2. jeśli <math>{\phi}</math> oraz <math>{\psi}</math> są formułami to <math>(\phi \Rightarrow \psi)</math> jest formułą (spójnik <math>\Rightarrow</math> nazywamy implikacją)''
-''3. jeśli <math>{\phi}</math> jest formułą to <math>\neg \phi</math> jest formułą (spójnik <math>\neg</math> nazywamy negacją)''
-''4. nic innego nie jest formułą.''
-Powyższa definicja mówi, że formułami nazywamy te napisy które dają
-się skonstruować ze zmiennych zdaniowych przy pomocy spójników
-<math>\Rightarrow</math> oraz <math>\neg</math>.
-'''Uwaga 2.2.''' Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>, gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać <math>(p\Rightarrow q)</math> możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.
-}}
-{{przyklad|2.3 Poniższe napisy nie są formułami||
-* <math>p \Rightarrow \Rightarrow q</math>
-* <math>\neg \neg \neg</math>
-* ten napis na pewno nie jest formułą
-* <math>(p \Rightarrow \neg q))</math>
-''Poniższe napisy są formułami''
-* <math>(p \Rightarrow (r \Rightarrow q))</math>
-* <math>\neg \neg \neg q</math>
-* <math>(p \Rightarrow \neg q)</math>
-}}
-{{cwiczenie|2.3||
-Rozmiarem formuły nazwiemy ilość występujących w niej spójników.
-Na przykład formuła <math>\neg \neg q</math> ma rozmiar '''2''', a formuła <math>(p\Rightarrow q)</math> ma rozmiar '''1'''. Przypuśćmy, że jedyną zmienną zdaniową jaką wolno nam użyć jest <math>p</math>. Ile można skonstruować rożnych formuł o rozmiarze '''3'''?
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>\textnormal{n}</math> (czyli liczbę formuł w których jest <math>\textnormal{n}</math> spójników). Interesuje nas <math>f_3</math>. Każda formuła o rozmiarze '''3''' powstaje albo z dwóch formuł o rozmiarach '''1''' poprzez połączenie ich spójnikiem <math>\Rightarrow</math> albo z jednej formuły o rozmiarze '''2''' poprzez dodanie do niej spójnika <math>\neg</math>. Co więcej każda taka formuła powstaje tylko w jeden sposób. Wynika stąd następująca zależność:
-<center><math>
-f_3= f_2 + (f_1)^2
-</math></center>
-Wiemy, że są tylko dwie formuły o rozmiarze '''1''', są to <math>\neg p</math> oraz <math>p \Rightarrow p</math>. Stąd mamy <math>f_1=2</math>. Dla formuł o rozmiarze '''2''' możemy zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z
-dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar '''1''' a druga '''0'''  za pomocą <math>\Rightarrow</math>, albo jest zbudowana z formuły o rozmiarze '''1''' za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze '''0''', jest to <math>\textnormal{p}</math>. Mamy więc następujący wzór dla <math>f_2</math>
-<center><math>
-f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1
-</math></center>
-Z dwóch ostatnich wzorów otrzymujemy
-<center><math>
-f_3= 3 \cdot f_1 + (f_1)^2= 6+4 = 10
-</math></center>
-Skoro jest ich niewiele to możemy wszystkie wypisać
-:1. <math>\neg \neg \neg p</math>
-:2. <math>\neg \neg (p \Rightarrow p)</math>
-:3. <math>\neg (p \Rightarrow \neg p)</math>
-:4. <math>\neg (p \Rightarrow (p\Rightarrow p))</math>
-:5. <math>\neg (\neg p \Rightarrow  p)</math>
-:6. <math>\neg ((p\Rightarrow p) \Rightarrow  p)</math>
-:7. <math> (\neg p)\Rightarrow  (\neg p)</math>
+Drzwi automatycznie otwierane są sterowane automatem, którego działanie opisać
+można, przyjmując następujące oznaczenia. Fakt, że osoba chce wejść do pomieszczenia
+zamykanego przez takie drzwi, identyfikowany przez odpowiedni czujnik, opiszemy symbolem
+<math>WE</math>. Zamiar wyjścia symbolem <math>WY</math>. Symbol <math>WEWY</math> będzie związany z równoczesnym zamiarem
+wejścia jakiejś osoby i wyjścia innej. Wreszcie symbol <math>BRAK</math> oznaczał będzie brak osób, które
+chcą wejść lub wyjść. Zatem zbiór <math>\{ WE, WY,WEWY,BRAK \}</math>, to alfabet nad którym określimy automat
+o <math>2</math> stanach: <math>OTWARTE, ZAMKNIĘTE</math> poniższym grafem.
-:8. <math> (\neg p)\Rightarrow  (p \Rightarrow p)</math>
+RYSUNEK  ja-lekcja3-w-rys6
-:9. <math> (p \Rightarrow p) \Rightarrow  (\neg p)</math>
+ANIMACJA ja-lekcja-w-rys7 działania drzwi
-:10. <math> (p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>
-</div></div>
 }}
-'''Uwaga 2.4''' Język logiki zdaniowej można równoważnie zdefiniować nie
+Automaty reagują więc na określone sygnały zewnętrzne reprezentowane przez
-używając nawiasów za pomocą Odwrotnej Notacji Polskiej
+litery alfabetu <math>A</math> zmieniając swój
-<u>'''Odwrotna Notacja Polska.'''</u>
+stan.  Jeśli ustalimy  stan początkowy automatu oraz dopuszczalne stany
+końcowe, to automat będzie testował dowolne słowo z <math>A^{*} </math>  startując ze
+stanu początkowego. Jeśli rezultatem finalnym działania automatu (obliczenia)
+będzie stan końcowy, to słowo będzie
+rozpoznawane przez automat, a obliczenie określone takim słowem poprawne.
-==Aksjomatyka Klasycznego Rachunku Zdań==
+Podamy teraz definicję automatu. Niech <math>A</math> oznacza dowolny alfabet.
+Od tego momentu wykładu zakładamy, że alfabet jest zbiorem skończonym.
-Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie
+'''Automatem''' nad alfabetem <math>A </math> nazywamy system <math>\mathcal{A} =(S,f)</math>,
-wszystkie formuły opisują prawdziwe schematy wnioskowania, lub
+w którym
-zdania które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale
-skupimy się na tym które spośród wszystkich formuł zdaniowych
-wyróżnić jako prawdziwe.
-===Aksjomaty===
+<math>S</math> - jest dowolnym skończonym zbiorem zwanym zbiorem stanów,
-Wielu matematyków zgadza się dzisiaj co do tego że zdania pasujące
+<math>f: S \times A \rightarrow S</math> - jest funkcją przejść.
-do poniższych schematów powinny być uznane za prawdziwe:
-{{definicja|3.1 Aksjomaty klasycznego rachunku zdań||
+Automat będąc w stanie <math>s_{i} </math> po przeczytaniu litery <math>a </math> zmienia
+stan na <math>s_{j} </math> zgodnie z funkcją przejścia <math>f(s_{i},a)=s_{j} </math>.
-''1. <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>  formuła ta jest nazywana aksjomatem K)
+Funkcję przejść rozszerzamy na cały wolny monoid <math>A^{*} </math> do postaci <center><math>f: S \times A^* \rightarrow S</math></center> przyjmując:
-''2. <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) \right)</math>(formuła ta jest nazywana aksjomatem S)
+dla każdego <math> s \in S\;\;\;f(s,1) = s </math> oraz
-''3. <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi</math>
+dla każdego <math>s \in S,\;\;a \in A</math> i dla dowolnego <math>w \in A^*</math>
-}}
-Zdania pasujące do powyższych schematów to wszystkie zdania które
-można otrzymać podstawiając w miejsce <math>\phi, \nu, \psi</math> dowolne
-formuły.
-===Reguła dowodzenia===
-Przyglądnijmy się teraz jak posługujemy się implikacją we
-wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała
-konstrukcji językowej:
-<center>'''jeśli''' <math>{\phi}</math> '''to''' <math>{\psi}</math>.</center>
-W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie
-prawdziwe oraz jeśli zdanie <math>{\phi}</math> jako prawdziwe to powinniśmy
-także zaakceptować <math>{\psi}</math>. Przedstawiony sposób wnioskowania nosi
-nazwę reguły ''Modus Ponens'' (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest
-skrótowo notowany w poniższy sposób
 <center><math>
+f(s,wa) = f(f(s,w),a).
-\frac{\phi \Rightarrow \psi, \phi}{\psi}.
 </math></center>
-Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów  o
+Działanie automatu pokazane jest na rysunku.
-ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby
-precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych
-aksjomatów definiujemy poniżej pojęcie dowodu.
-{{definicja|3.2||
-''Ciąg formuł <math>\phi_0, \dots ,\phi_n</math> jest dowodem formuły <math>{\psi}</math>
-''wtedy i tylko wtedy, gdy:''
-''1. <math>\phi_n</math> jest formułą <math>{\psi}</math>''
-''2. dla każdego <math>i\leq n</math> formuła <math>\phi_i</math> jest aksjomatem
-lub istnieją <math>j,k <i</math> takie, że formuła <math>\phi_i</math>
-jest wynikiem zastosowania reguły modus ponens do
-formuł <math>\phi_j, \phi_k</math>.''
-}}
-W drugim punkcie powyższej definicji jeśli formuła <math>\phi_i</math> nie jest
-aksjomatem (a więc powstaje przez zastosowanie MP) to formuły
-<math>\phi_j,\phi_k</math> muszą pasować do przesłanek reguły MP, a więc
-<math>\phi_j</math> musi być postaci <math>\phi_k \Rightarrow \phi_i</math> lub <math>\phi_k</math> postaci
-<math>\phi_j \Rightarrow \phi_i</math>.
-{{definicja|3.3||
-Formułę nazywamy twierdzeniem klasycznego rachunku zdań
-''jeśli istnieje jej dowód  z aksjomatów klasycznego rachunku
-zdań 3.1''
-}}
-===Przykład===
-Zastanówmy się na formułą postaci <math>\phi \Rightarrow \phi</math>. Intuicja
-podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów użyliśmy
-nawiasów kwadratowych dla nawiasów, które pochodzą ze  schematów.
-. <math>[\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow\phi]]</math> formuła ta jest aksjomatem zgodnym ze schematem S
-. <math>\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi]</math> aksjomat zgodny ze
-schematem K
-. <math>(\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi)</math> z modus ponens z formuł 1 i 2.
+rys3.1
-. <math>\phi \Rightarrow [q \Rightarrow \phi]</math> aksjomat zgodny ze schematem K
+Zdefiniowany powyżej automat <math>\mathcal{A} </math> nazywamy '''skończonym''' lub
+'''skończenie stanowym''' ze względu na założenie skończoności zbioru stanów <math>S</math>.<br>
-. <math>(\phi \Rightarrow \phi)</math> z modus ponens z formuł '''3''' i '''4'''
+{{cwiczenie|[Uzupelnij]||
-===Podsumowanie===
+Niech <math>A=\left\{ a,b\right\}  </math> będzie alfabetem, a <math>\mathcal{A}=(S,f) </math>
+automatem takim, że
-Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za
+<math>S=\left\{ s_{0},s_{1},s_{2}\right\}  </math>, a funkcja przejść zadana jest przy
-prawdziwe zdefiniowaliśmy wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły modus ponens.
+pomocy tabelki
-Warto zwrócić uwagę, że pomimo tego iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.
-'''Uwaga 3.4.''' Warto przyglądnąć się przyjętym aksjomatom i zastanowić się
+{
-jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni
-uznać je za prawdziwe. Pomocne może być interpretowanie formuł
-postaci <math>\phi \Rightarrow (\nu \Rightarrow \psi)</math> jako „jeśli prawdziwe jest
-<math>{\phi}</math> i prawdziwe jest <math>\nu</math> to prawdziwe jest <math>{\psi}</math>”. W
-kolejnych rozdziałach przekonamy się że taka interpretacja jest uzasadniona.
-==Matryca boolowska==
+{| border=1
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+|-
+|
+<math>f </math> ||
+<math>s_{0} </math> ||
+<math>s_{1} </math> ||
+<math>s_{2} </math>
+|-
+|
-W poprzednim rozdziale zdefiniowaliśmy klasyczny rachunek zdań jako
+<math>a </math> ||
-teorię aksjomatyczną. Jeśli pozwolimy sobie na używanie skończonych
+<math>s_{1} </math> ||
-zbiorów i funkcji, możemy równoważnie zdefiniować klasyczny rachunek
+<math>s_{2} </math> ||
-zdań za pomocą tzw. matrycy boolowskiej.
+<math>s_{2} </math>
+|-
+|
+<math>b </math> ||
+<math>s_{0} </math> ||
+<math>s_{0} </math> ||
+<math>s_{0} </math>
+|-
+|
-{{definicja|4.1||
+|}
-Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy
+}
-<math>\mathbb{B}=\{0,1\}</math> w którym '''1''' jest wyróżnioną wartością prawdy, wraz z
-dwoma funkcjami odpowiadającymi za interpretacje spójników
-<math>\Rightarrow</math> oraz <math>\neg</math> zdefiniowanymi następująco
-tabelka.........
+Automat możemy również jednoznacznie określić przy pomocy grafu.<br>
-}}
-{{definicja|4.2||
+rys3.2
-Wartościowaniem nazywamy funkcję która przypisuje zmiennym
-zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
-można rozszerzyć na wartościowanie formuł interpretując spójniki
-<math>\Rightarrow</math> oraz <math>\neg</math> jako funkcje zgodnie z tabelami 4.1.
 }}
-{{przyklad|4.3||
-Niech <math>v</math> będzie wartościowaniem zmiennych takim, że <math>v(p)=0,v(q)=1, v(r)=0</math>. Wtedy
-* formuła <math>q \Rightarrow p</math> jest wartościowana na '''0''' (będziemy to zapisywać jako <math>v(q \Rightarrow p)=0</math>),
+Podamy teraz bardzo interesujący przykład zastosowania automatów  skończonych.
+Przedstawimy mianowicie wykorzystanie  tak zwanych
+automatów synchronizujących w przemyśle. Automat synchronizujący nad alfabetem <math>A</math> to
+automat <math>(S,f)</math>  o
+następującej własności: istnieje stan <math>t \in S</math> oraz słowo <math>w \in
+A^*</math> takie, że dla każdego stanu <math>s</math> tego automatu <math>  f(s, w)=t</math>. Istnieje więc pewne uniwersalne
+słowo <math>w</math>, pod wpływem którego wszystkie stany przechodzą w jeden,
+ustalony stan automatu <math>t \in S</math>. Mówimy, że następuje wtedy synchronizacja
+wszystkich stanów automatu.
-* formuła <math>r \Rightarrow (q \Rightarrow p)</math> jest wartościowana na '''1''' (czyli <math>v(r \Rightarrow (q \Rightarrow p))=1</math>)
+Poniżej prezentujemy przykład zaczerpnięty z pracy Ananicheva i
+Volkova (D. S. Ananichev, M. V. Volkov, Synchronizing Monotonic
+Automata, ''Lecture Notes in Computer Science'', 2710(2003),
+--121.), ukazujący ideę użycia automatów synchronizujących w tej
+dziedzinie.
-* formuła <math>\neg p \Rightarrow r</math> jest wartościowana na  '''0''' (czyli <math>v(\neg p \Rightarrow r)=0</math>)
+{{cwiczenie|[Uzupelnij]||
-}}
+RYSUNEK pojedynczego detalu - ja-lekcja3-w-rys-s1
-{{cwiczenie|4.1||
+Załóżmy, że pewna fabryka produkuje detale w kształcie kwadratu z
+"wypustką" na jednym boku
+(patrz rys. [[##ja-lekcja3-w-rys-s1|Uzupelnic ja-lekcja3-w-rys-s1|]]).
+Po wyprodukowaniu detale należy umieścić w opakowaniach w ten sposób,
+by wszystkie były w tej samej orientacji - mianowicie "wypustką" w
+lewo.
-Przy wartościowaniu <math>v</math> z przykładu 4.3 jakie wartości przyjmują następujące formuły
+Załóżmy ponadto dla uproszczenia, że detale mogą przyjmować jedną z
+czterech orientacji (rys. [[##ja-lekcja3-w-rys-s2|Uzupelnic ja-lekcja3-w-rys-s2|]]): "wypustką" w
+górę, w dół, w lewo lub w prawo.
-. <math>p \Rightarrow (q \Rightarrow r)</math>
+RYSUNEK ja-lekcja3-w-rys-s2
-. <math>p \Rightarrow (p \Rightarrow q)</math>
+Należy zatem skonstruować takie urządzenie (orienter), które będzie
+ustawiało wszystkie detale w żądanej orientacji. Oczywiście istnieje
+wiele metod rozwiązania tego problemu, ale z praktycznego punktu
+widzenia potrzebne jest rozwiązanie najprostsze i najtańsze. Jednym
+z takich sposobów jest umieszczanie detali na pasie transmisyjnym z
+zamontowaną wzdłuż niego pewną ilością przeszkód dwojakiego rodzaju:
+niskich (''low'') oraz wysokich (''HIGH''). Wysoka
+przeszkoda ma tę własność, że każdy detal, który ją napotka zostanie
+obrócony o 90 stopni w prawo (zakładamy, że elementy jadą od lewej
+do prawej strony). Przeszkoda niska obróci o 90 stopni w prawo tylko
+te detale, które są ułożone "wypustką" w dół. Na rys.
+[[##ja-lekcja3-w-rys-s3|Uzupelnic ja-lekcja3-w-rys-s3|]] przedstawione zostały przejścia pomiędzy
+orientacjami detali w zależności od napotkania odpowiedniej
+przeszkody.
-. <math>\neg \neg q \Rightarrow p</math>
+RYSUNEK ja-lekcja3-w-rys-s3
-. <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
+Można zauważyć, że automat z rysunku [[##ja-lekcja3-w-rys-s3|Uzupelnic ja-lekcja3-w-rys-s3|]] jest
+automatem synchronizującym. Słowem, które go synchronizuje jest
+następująca sekwencja przeszkód:
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+low-HIGH-HIGH-HIGH-low-HIGH-HIGH-HIGH-low.
-:
-:1. <math>v(p \Rightarrow (q \Rightarrow r))=1</math>
+Niezależnie od tego, w jakiej orientacji początkowej znajduje się
+detal, po przejściu przez powyższą sekwencję przeszkód zawsze będzie
+ułożony "wypustką" w lewo. Sytuację przedstawia poniższa animacja:
-:2. <math>v(p \Rightarrow (p \Rightarrow q))=1</math>
+ANIMACJA ja-lekcja3-w-anim-s4
-:3. <math>v(\neg \neg q \Rightarrow p)=0</math>
-:4. <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
-</div></div>
 }}
-{{cwiczenie|4.2||
+Rozszerzymy teraz wprowadzone pojęcie automatu w ten sposób by uzyskać możliwość
+efektywnego rozstrzygania czy dowolne słowo utworzone nad alfabetem <math>A</math>
-. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na '''0'''
+reprezentuje poprawne obliczenie,
+czyli spełnia kryteria określone przez rozszerzony automat.
-:(a) <math>p \Rightarrow (q \Rightarrow r)</math>
-:(b) <math>(\neg p \Rightarrow q)</math>
-:(c) <math>(p\Rightarrow q) \Rightarrow q</math>
-. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na '''1'''
-:(a) <math>\neg (p \Rightarrow q)</math>
-:(b) <math>\neg (\neg p \Rightarrow  \neg q)</math>
-:(c) <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Wartościowania będziemy oznaczać przez <math>v</math>
-:1. (a) <math>v(p)=1, v(q)=1, v(r)=0</math>
-: &nbsp;&nbsp;&nbsp;&nbsp;(b) <math>v(p)=0,v(q)=0</math>
-: &nbsp;&nbsp;&nbsp;&nbsp;(c) <math>v(p)=0,v(q)=0</math>
+'''Język''' <math>\; L~\subset A^* \;</math> jest '''rozpoznawany''' ('''akceptowany''')
+wtedy i tylko wtedy, gdy istnieje automat skończony <math>\mathcal{A} = (S,f) , \;</math> stan <math>\; s_0 \in S \;</math> oraz zbiór <math>\; T \subset S \;</math> takie, że
+<center><math>L = \{ w \in A^* \; : \; f(s_0,w) \in T \}. </math></center> Stan <math>s_0 \;</math> nazywamy '''stanem początkowym''',
+a <math>\; T \;</math> '''zbiorem stanów końcowych''' automatu <math>\mathcal{A} </math>.
-:2. (a) <math>v(p)=1,v(q)=0</math>
+Rozszerzony w powyższy sposób automat, poprzez dodanie stanu początkowgo i zbioru stanów końcowych, w dalszym ciągu
+nazywamy automatem i oznaczamy jako piątkę <math>\mathcal{A} = (S,A,f,s_0,T)</math> lub czwórkę <math>\mathcal{A} =(S,f,s_0,T)</math>, jeśli
+wiadomo, nad jakim alfabetem rozważamy działanie automatu.
-: &nbsp;&nbsp;&nbsp;&nbsp;(b) <math>v(p)=0,v(q)=1)</math>
+Fakt, że język <math>\; L \;</math> jest rozpoznawany przez automat <math>\mathcal{A}, </math> zapisujemy jako
-: &nbsp;&nbsp;&nbsp;&nbsp;(c) <math>v(q)=1</math>
+<center><math>L=L(\mathcal{A}). </math></center>
-</div></div>
-}}
-===Twierdzenie o pełności===
+Rodzinę wszystkich języków rozpoznawalnych nad alfabetem <math>A</math>
+oznaczamy przez <math>\mathcal{REC}(\mathcal{A}^{*}) </math>.
-Zauważmy, że istnieją formuły, które dla każdego wartościowania
+Podobnie jak w przypadku gramatyk nie ma jednoznacznej odpowiedniości pomiędzy językami
-zmiennych zdaniowych zawsze przyjmują wartość '''1''' (np. <math>p \Rightarrow p</math>).
+rozpoznawalnymi a automatami. Wprowadza się więc relację, która identyfikuje
-Takie formuły będziemy nazywać '''tautologiami'''.
+automaty rozpoznające ten sam język.
-{{cwiczenie|4.3||
+Automaty <math>\mathcal{A}_{1} </math> i <math>\mathcal{A}_{2} </math> są '''równoważne''',
+jeśli rozpoznają ten sam język, czyli
-Sprawdź czy poniższe formuły są tautologiami
+<center><math>L(\mathcal{A}_{1})=L(\mathcal{A}_{2}).</math></center>
-. <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
+W dalszych rozważaniach języków rozpoznawanych ograniczymy się do automatów
+<math>\mathcal{A} = (S,A,f,s_0,T)</math>,
+które spełniają warunek  <math>f(s_0,A^*) = S.</math>
+Nie zawęża to naszych rozważań. Jeśli bowiem język <math>\; L \;</math> jest rozpoznawany
+przez pewien automat <math>\mathcal{A} = (S,A,f,s_0,T)</math>, to jest również
+rozpoznawany przez automat
-. <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
+<center><math>\mathcal{B}=\left( f(s_{0},A^{*}),A,f|_{f(s_{0},A^{*})\times A^{*}},s_{0},T\cap f(s_{0},A^{*})\right) ,</math></center>
-(\phi \Rightarrow \nu) \right)</math>
-. <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
+który spełnia powyższy warunek. Zauważmy, że przyjmując to założenie upraszczamy strukturę
-\psi) \Rightarrow \phi</math>
+automatu. Z punktu widzenia grafu automatu można powiedzieć, że nie występują w nim
+wierzchołki (stany) nieosiagalne ze z <math>s_0</math>.  Poniżej przedstawiamy algorytm usuwający
+z automatu stany nieosiągalne ze stanu początkowego.
-. <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>
+{{UsuńStanyNieosiągalne} - usuwa z automatu
+<math>\mathcal{A}</math> stany nieosiągalne}
+[1]
+Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź 1 </span><div class="mw-collapsible-content" style="display:none">
+Wyjście: <math>\mathcal{A}'=(S', A, f', s_0, T')</math> - automat
+równoważny automatowi <math>\mathcal{A}</math> bez stanów nieosiągalnych.
-Spróbuj poszukać wartościowań dla których formuła przyjmuje wartość '''0'''
-</div></div>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź 2 </span><div class="mw-collapsible-content" style="display:none">
-Można też sprawdzić wszystkie możliwości wartościowań.
-</div></div>
-; Solution.
-}}
-Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań 3.1. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik <u>'''Emil Post.'''</u>
+'''procedure''' {Oznacz}<math>(x \in S)</math>
-{{twierdzenie|4.4 [Post 1921 Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.]||
+{<math>p \in S:\ \exists a \in A\ f(x,a)=p \wedge
+\mbox{\textbf{zaznaczone}}[p]==0</math>}
+'''zaznaczone'''<math>[p] \leftarrow 1</math>;
-}}
+{Oznacz}<math>(p)</math>;
-Dowód powyższego twierdzenia jest przedstawiony na wykładzie <u>'''Logika dla informatyków'''</u>
-Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać czy dana formuła jest twierdzeniem klasycznego rachunku zdań sprawdzając czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które
-wartościuje formułę na '''0'' (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).
-{{cwiczenie|4.4||
+'''end procedure'''
-Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
+{<math>p \in S</math>}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź 1 </span><div class="mw-collapsible-content" style="display:none">
+'''zaznaczone'''<math>[p] \leftarrow 0</math>;
-Pokazaliśmy już w zadaniu 4.1, że aksjomaty są tautologiami. Zacznij od pokazania, że zastosowanie reguły MP  do tautologii daje tautologię.
+'''zaznaczone'''<math>[s_0] \leftarrow 1</math>;
-</div></div>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź 2 </span><div class="mw-collapsible-content" style="display:none">
-Udowodnij, twierdzenie przez indukcję ze względu na długość dowodu.
+{Oznacz}<math>(s_0)</math>;
-</div></div>
-; Solution.
-}}
-===Inne spójniki===
+<math>S' = \{s \in S:\ \mbox{\textbf{zaznaczone}}[s]==1\}</math>;
-Do tej pory jedynymi rozważanymi spójnikami była implikacja i
+<math>T' = T \cap S'</math>;
-negacja. W analogiczny sposób do 4.1 możemy wprowadzać kolejne spójniki. Często używane spójniki to koniunkcja (spójnik '''i''') oznaczana przez <math>\wedge</math> oraz
-alternatywa (spójnik '''lub''') oznaczana przez <math>\vee</math>, które będziemy interpretować w następujący sposób:
-Tabelka......
+jeśli istnieje przynajmniej jeden stan, dla którego funkcja
+przejścia <math>f</math> nie jest określona dla jakiejś litery <math>a \in A</math>, dodaj
+stan <math>s_f</math> do <math>S'</math> i dla każdego stanu <math>s</math> i litery <math>a</math> jeśli <math>f(s,
+a)</math> jest nieokreślone, to zdefiniuj <math>f(s,a)=s_f</math>;
+<math>f' \leftarrow f</math>;
-Zgodnie z intuicją koniunkcja <math>\phi \wedge\psi</math> jest wartościowana
+<math>\mathcal{A}'=(S', A, f', s_0, T')</math>;
-na '''1''' wtedy i tylko wtedy gdy zarówno <math>{\phi}</math> jak i <math>{\psi}</math> są
-wartościowane na '''1'''. Alternatywa <math>\phi \vee \psi</math> jest wartościowana
-na '''1''' jeśli przynajmniej jedna z formuł <math>\phi, \psi</math> jest
-wartościowana na '''1'''.
-{{definicja|4.5||
+Powyższy algorytm, dla ustalonego alfabetu <math>A</math>, posiada złożoność <math>O(|A|
+\cdot |S|)</math>, czyli liniową względem liczby stanów.
-Formuły <math>{\phi}</math> oraz <math>{\psi}</math> są ''równoważne'' (oznaczamy ten fakt
+{{cwiczenie|[Uzupelnij]||
-przez <math>\phi \equiv \psi</math> wtedy i tylko wtedy gdy dla każdego wartościowania formuła <math>{\phi}</math> przyjmuje tą samą wartość co formuła <math>{\psi}</math>.
-}}
-{{cwiczenie|4.5||
-Udowodnij, że następujące formuły są równoważne
+Jeśli w przykładzie [[##ex.3.1.1|Uzupelnic ex.3.1.1|]] przyjmiemy stan <math>s_{0} </math> jako stan
+początkowy, <math>T=\left\{ s_{2}\right\}  </math> jako zbiór stanów końcowych, to
+automat <math>\mathcal{A} = (S,A,f,s_0,T)</math>  rozpoznaje język
-. <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi </math>
+<center><math>L(\mathcal{A})= A^{*}\left\{ a^2\right\}</math></center>
-. <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</math>
+złożony ze słów, kończących się na <math>a^2 </math>.<br>
+Słowo <math>aba</math> nie jest akceptowane.
+rys3.3<br>
+Słowo <math>abaa</math>  jest akceptowane.
+rys3.4
 }}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-:1. Lewa strona jest fałszywa jedynie gdy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''0'''. Prawa strona jest fałszywa wtedy i tylko wtedy kiedy <math>\neg \phi</math> jest wartościowane na '''1''' oraz <math>{\psi}</math> jest wartościowane na '''0''' (to jedyna możliwość aby implikacja była fałszywa). Wobec tego prawa strona jest fałszywa wtedy i tylko wtedy kiedy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''0''', a więc jest równoważna lewej.
+Każdy automat <math>\mathcal{A} = (S,A,f,s_0,T)</math> wyznacza w wolnym monoidzie <math>A^*</math>
+prawą kongruencję, nazywaną '''prawą kongruencją automatową''', określoną w następujący
+sposób:<br>
+<math>\forall u,v \in A^*</math>
-:2. Lewa strona jest prawdziwa jedynie gdy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''1'''. Prawa strona jest prawdziwa wtedy i tylko wtedy kiedy <math>\neg (\phi \Rightarrow \neg \psi)</math> jest wartościowane na '''1''', więc wtedy gdy <math>(\phi \Rightarrow \neg \psi)</math> jest wartościowane na '''0'''. To z kolei zdarzyć się może jedynie gdy <math>{\phi}</math> jest wartościowane na '''1''' i <math>\neg \psi</math> na '''0''', a więc wtedy gdy zarówno <math>{\phi}</math> jak i <math>{\psi}</math> są wartościowane na '''1'''. Wobec tego obie formuły są równoważne.
+<center><math>u\sim _{\mathcal{A}}v\Longleftrightarrow f(s_{0},u)=f(s_{0},v).</math></center>
-Równie dobrym rozwiązaniem jest sprawdzenie wszystkich
+Dla automatu skończonego ( o skończonym zbiorze stanów), a takie rozważamy,
-możliwości wartościowań i porównanie wyników.
+relacja <math>\sim _{A} </math> ma
-</div></div>
+skończony indeks, czyli skończoną liczbę klas równoważności.
-Z powyższego zadania wynika, że każdą formułę w której występują
+{{cwiczenie|[Uzupelnij]||
-spójniki <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą w
-której jedynymi spójnikami są <math>\Rightarrow</math> oraz <math>\neg</math>. Tak naprawdę
-więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi
-skrótami w zapisywaniu formuł.
-Aby się oswoić z własnościami spójników prześledzimy szereg ich
-praw.
-{{cwiczenie|4.6||
+Automat z przykładu [[##ex.3.1.1|Uzupelnic ex.3.1.1|]] ze stanem <math>s_{0} </math> jako początkowym wyznacza
+relację równoważności o trzech klasach:
-Udowodnij następujące równoważności
+<math>[1]=A^*\left\{ b \right\}\cup \left\{ 1\right\}[a]=A^*\left\{ ba\right\}  \cup \left\{ a\right\} [a^2]=A^*\left\{ a^2 \right\}  </math>
-. <math>\neg \neg p \equiv p</math>
-. <math>p\Rightarrow q \equiv \neg p \vee q</math>
-. <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>
-. <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>
-. <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>
-. <math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r)</math>
-. <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r)</math>
-. <math>(p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</math>
 }}
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Przedstawiamy przykładowe dowody kilku pierwszych równoważności.
+Na odwrót, każda prawa kongruencja <math>\;\rho \subset (A^*)^2\;</math> wyznacza automat, zwany
+'''ilorazowym''', w następujący sposób:
-:1. Jeśli <math>\textnormal{p}</math> jest wartościowane na '''1''', to zgodnie z tabelą dla negacji 4.1 <math>\neg p</math> jest wartościowane na '''0''' i <math>\neg \neg p</math> jest wartościowane na '''1'''. Jeśli <math>\textnormal{p}</math> jest wartościowane na '''0''' to <math>\neg p</math> jest wartościowane na '''1''' i <math>\neg \neg p</math> jest wartościowane na '''0'''. Formuły przyjmują te same wartości dla każdego wartościowania więc są równoważne.
+<center><math>\mathcal{A}_{\rho }=(A^{*}/_{\rho },f^{*}),\; \; gdzie\; \; f^{*}([w]_{\rho },u)=[wu]_{\rho }.</math></center>
-:2. Jedyną możliwością aby lewa strona była fałszywa jest aby <math>\textnormal{p}</math> było wartościowane na '''1''', a <math>\textnormal{q}</math> na '''0'''. Prawa stona jest fałszywa jedynie gdy <math>\neg p</math> oraz <math>\textnormal{q}</math> są wartościowane na '''0'''. Czyli prawa strona jest fałszywa jedynie gdy <math>\textnormal{p}</math> jest wartościowane na '''1''' i <math>\textnormal{q}</math> na '''0'''. Formuły są więc równoważne.
+<math>\mathcal{A} </math></center>_<math> jest automatem ze stanem początkowym </math>[1]_<math>. </math>{A}_{ } <math> jest automatem skończonym
+wtedy i~tylko wtedy, gdy relacja  ma skończony indeks.\\
+Z definicji prawej kongruencji wynika, że funkcja przejść </math>f^*<math> jest określona poprawnie.
-:3. Analogicznie do poprzedniego punktu łatwo się przekonać, że jedynym wartościowaniem które falsyfikuje lewą stronę jest takie które wartościuje <math>\textnormal{p}</math> i <math>\textnormal{q}</math> na '''1''' oraz <math>\textnormal{r}</math> na '''0'''. Tą samą własność ma formuła po prawej stronie, więc formuły są równoważne.
+\begindefin
-:4. Przykład rozwiązania przez rozważenie wszystkich możliwości
+Niech </math>{A} <nowiki>=</nowiki>(S,f)<math> i </math> {B} <nowiki>=</nowiki>(T,g)<math> będą dowolnymi automatami.
+Odwzorowanie </math> :S T <math>
+nazywamy \textbf{homomorfizmem automatów}\index{homomorfizm automatów}
+wtedy i~tylko
+wte\-dy, jeśli </math></center> s  S,  w  A^*(f(s,w))  <nowiki>=</nowiki>  g((s),w).<center><math> Homomorfizm
+automatów oznaczamy </math> :{A} {B} <math>.
+\enddefin
+\begintheor
-tabelka........
+Prawdziwe są następujące fakty:
+#  Dla dowolnej prawej kongruencji </math>     (A^*)^2 </center> _{{A}_{ }}<nowiki>=</nowiki> ,<center><math>
-:W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych <math>\textnormal{p}</math> i <math>\textnormal{q}</math> a w pozostałych odpowiadające im wartościowania formuł zbudowanych z tych zmiennych. Ponieważ kolumna '''4''' i '''7''' są identyczne to formuły z zadania są równoważne.
+#  Dowolny automat </math>{A} <nowiki>=</nowiki> (S,A,f,s_0,T)<math> jest izomorficzny z automatem </math>{A}_{ _{{A}}} <math>,
-:5. W równoważności z poprzedniego punktu, podstawiąjąc za <math>\textnormal{p}</math> formułę <math>\neg p</math> oraz za <math>\textnormal{q}</math> formułę <math>\neg q</math> otrzymamy równoważność
+#  Dla dowolnych automatów </math>{A}_1<nowiki>=</nowiki> (S_1,A,f_1,s^1_0,T_1)<math>
+i </math>{A}_2 <nowiki>=</nowiki> (S_2,A,f_2,s^2_0,T_2)<math>  prawdziwa jest równoważność
-<center><math>
+{\par\centering </math> _{{A}_1}    _{{A}_2}     <math>
+istnieje epimorfizm </math> :{A}_1 {A}_2 <math> taki,
-\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg\neg q. </math></center>
+że </math>(s^1_0) <nowiki>=</nowiki> s^2_0<math>. \par}
-:Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony otrzymujemy
+\endtheor
-<center><math>
+\beginprf \hfill
-\neg( \neg p \wedge \neg q) \equiv  p \vee     q.
+# Identyczność relacji wynika wprost z~defi\-ni\-cji automatu ilorazowego </math>{A} <center><math>_\rho</math> oraz prawej kongruencji <math>\sim _{A_{\rho }} </math>.
-</math></center>
-:Negując tą równoważność obustronnie otrzymamy
+# Rozważmy automat <math>\mathcal{A} = (S,A,f,s_0,T)</math> i  odwzorowanie
-<center><math>
+<center><math>\psi :\mathcal{A}\longrightarrow \mathcal{A}_{\sim _{\mathcal{A}}}, </math></center>
-\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee     q).
+gdzie
-</math></center>
+<math>\forall s\in S </math>
-:Stosując równoważność z pierwszego punktu do lewej strony otrzymamy szukaną równoważność.
+<center><math>\psi (s)=[w]_{\sim _{\mathcal{A}}} \;\;\text{dla}\;\;  w\in A^{*} \;\;\text{i} \;\; f(s_{0},w)=s. </math></center>
-</div></div>
+Istnienie słowa <math>w</math> wynika z faktu, że <math>s_0</math> jest stanem początkowym, natomiast z definicji relacji <math>\sim _{\mathcal{A}}</math> wynika, że odwzorowanie <math>\psi</math> jest poprawnie określone.<br>
+Odwzorowanie <math>\psi</math> ma być homomorfizmem, czyli dla każdego stanu <math>s\in S </math> i dowolnego
+słowa <math>w\in A^{*} </math> spełniać warunek
-{{cwiczenie|4.7||
+<center><math>\psi (f(s,w))=f^{*}(\psi (s),w). </math></center>
-Sprawdź które z następujących formuł są tautologiami
+Warunek ten wynika z następujących równości
-. <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>
+<center><math>\begin{array} {c}
+f^{*}(\psi (s),w)=f^{*}([u]_{\sim_{\mathcal{A}}},w)=[uw]_{\sim _{\mathcal{A}}}=\\
+=\left\{ v\in A^{*}:f(s_{0},uw)=f(s_{0},v)\right\} = \\
+\left\{ v\in A^{*}:f(f(s_{0},u),w)=f(s_{0},v)\right\} = \\
+=\left\{ v\in A^{*}:f(s,w)=f(s_{0},v)\right\} =\psi (f(s,w))
+\end{array} </math></center>
-. <math>(p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r)) </math>
+gdzie <math>f(s_0,u)=s</math>.
-. <math>( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow(p \wedge q)</math>
+Z prostych  obserwacji wynika, że <math>\psi </math> jest suriekcją i iniekcją.
-. <math>(p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r))</math>
+# Dowód implikacji "<math>\Rightarrow</math>" <br>
-}}
+Załóżmy, że <math>\: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2 } </math>. Niech
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-:1. Spróbujmy znaleźć wartościowanie które falsyfikuje tą formułę. Skoro implikacja ma być fałszywa to formuła <math>(p \vee q)</math> (czyli następnik) musi być fałszywa. Tak jest tylko wtedy kiedy zarówno <math>\textnormal{p}</math> jak i <math>\textnormal{q}</math> są fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji, czyli formułą
+<center><math>\varphi :\mathcal{A}_1\longrightarrow \mathcal{A}_2 </math></center>
-<center><math>
+będzie odwzorowaniem takim, że<br>
+<math>\forall  s\in S_1 </math> <center><math> \varphi (s) = f_2(s^2_0,w),\;\;\text{gdzie}\;\;  w\in A^{*}\;\; i \;\; f_1(s^1_0,w) = s.</math></center>
+Stąd, że <math>s^1_0 </math> jest stanem początkowym automatu <math>\mathcal{A}_1, </math>
+wynika, że istnieje słowo <math>\; w \in A^* \;</math> potrzebne do określenia epimorfizmu <math> \varphi</math>.<br>
+Z założenia <math>\: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2} </math>
+wynika, że <math>\varphi \;</math> jest poprawnie zdefiniowaną funkcją. <br>
+Uzasadnienie faktu, że <math>\varphi</math> jest
+homomorfizmem, jest analogiczne jak w punkcie [[##tb|Uzupelnic tb|]] dla <math>\psi</math>.<br>
+<math>\varphi</math> jest suriekcją, gdyż <math>\; s^2_0 \; </math>
+jest stanem początkowym automatu <math>\mathcal{A}_2 </math>.<br>
+<math>\; \varphi (s^1_0) = s^2_0, \;</math> ponieważ <math>\; f_1(s^1_0,1) = s^1_0</math>. <br>
+Dowód implikacji "<math>\Leftarrow</math>" <br>
+Niech <math>\varphi :\mathcal{A}_1\longrightarrow \mathcal{A}_2 </math> będzie epimorfizmem
+takim, że <math>\; \varphi (s^1_0) = s^2_0 \;</math>.<br>
+Wówczas prawdziwy jest następujący ciąg wnioskowań.
-(p \vee r)\wedge( q \vee \neg r).
+<center><math>\begin{array} {c}
+u\sim _{\mathcal{A}_1}v \Leftrightarrow f_1(s^1_0,u)=f_1(s^1_0,v)
+\Rightarrow\\
+\Rightarrow \varphi (f_1(s^1_{0},u))=\varphi (f_1(s^1_{0},v))\Rightarrow f_2(s^2_{0},u)=f_2(s^2_{0}v)\Leftrightarrow
+u\sim _{\mathcal{A}_2}v
+\end{array}
 </math></center>
-:Jeśli teraz ustalimy <math>\textnormal{r}</math> na fałsz to <math>(p \vee q)</math> będzie fałszywe a jeśli ustalimy <math>r</math> na prawdę to <math>( q \vee \neg r)</math> będzie fałszywe. W obu tych przypadkach cały poprzednik jest fałszywy. Wynika stąd, że nie da się dobrać takiego wartościowania że poprzednik jest prawdziwy, a następnik fałszywy więc rozważana formuła jest tautologą.
+To oznacza, że <math>\sim _{\mathcal{A}_1}\subseteq \sim _{\mathcal{A}_2} </math>.
-:2 Formuła nie jest tautologią. Wystarczy wartościować <math>\textnormal{p}</math> i <math>\textnormal{r}</math> na prawdę i <math>\textnormal{q}</math> na fałsz.
-:3. Formuła nie jest tautologią. Wystarczy wartościować <math>\textnormal{p}</math> i <math>\textnormal{r}</math> na prawdę i <math>\textnormal{q}</math> na fałsz.
+<math>\diamondsuit</math>
-:4. Przykład rozwiązania przez rozważenie wszystkich możliwości
+Symbolem <math>S^S</math> oznaczamy rodzinę wszystkich funkcji określonych na zbiorze <math>S</math> i przyjmujących
+wartości w <math>S</math>. Łatwo zauważyć, iż  rodzina ta wraz ze składaniem odwzorowań jest
+monoidem  <math>(S^S,\circ)</math> .
+Niech <math>\mathcal{A} = (S,f)</math> będzie dowolnym automatem.
+'''Reprezentacją automatu''' <math>\mathcal{A} </math> nazywamy funkcję
+<math>\tau _{\mathcal{A}}:A^{*}\longrightarrow S^{S} </math>
+określoną dla dowolnych <math> w \in A^*</math> i <math>\; s \in S \;</math> równością
-tabelka.......
+<center><math>\tau _{\mathcal{A}}(w)(s)=f(s,w). </math></center>
+Reprezentacja automatu jest
+homomorfizmem monoidu <math>A^*</math> w monoid <math>S^S</math>, bowiem dla dowolnych <math> v,w \in A^* </math>
+spełnione są warunki
-:W kolumnie odpowiadającej badanej formule są same '''1''', więc jest ona tautologią.
+<center><math>\begin{array} {c}
-</div></div>
+\tau _{\mathcal{A}}(vw)=\tau _{\mathcal{A}}(w)\circ \tau _{\mathcal{A}}(v),\\
+\tau _{\mathcal{A}}(1)=id_{S}.
+\end{array} </math></center>
+Niech <math>\mathcal{A} </math></center><nowiki>=</nowiki> (S,f)<math> będzie dowolnym automatem. \textbf{Monoidem przejść}\index{monoid przejść}
+automatu </math>{A} <math> nazywamy monoid
-Binarne spójniki logiczne interpretowaliśmy jako funkcje z <math>\mathbb{B}\times \mathbb{B} \rightarrow \mathbb{B}</math>. Nie trudno przekonać się że takich funkcji jest dokładnie '''16'''. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze
+</math></center>{M}({A})<nowiki>=</nowiki> _{{A}}(A^{*}) S^{S}.<center><math>
-zwyczajowymi oznaczeniami odpowiadających im spójników.
-{{definicja|4.6||
+\enddefin
-W poniższej tabeli przedstawiamy wszystkie spójniki binarne.
+Następujace wnioski są konsekwencjami rozważań przeprowadzonych powyżej.
+\begincorol  \vspace{-5truemm}\\
+# Monoid przejść automatu </math>{A} <math> jest podmonoidem monoidu </math> S^S <math> i  zbiór
+</math>  _{{A}}(a):a A  <math> jest zbiorem generatorów tego monoidu.
-tabelka....
+</math></center>{M}({A})<nowiki>=</nowiki>  _{{A}}(a):a A ^{*} <center><math>
+Wynika to z faktu, że </math> _{{A}} <math> jest epimorfizmem i z twierdzenia~[[##tw:z|Uzupelnic tw:z|]].
-Spójnik binarny <math>\circ</math> będziemy nazywać ''przemiennym'' jeśli zachodzi
+# Monoid przejść automatu skończonego jest skończony.
-następująca równoważność
-<center><math>
+# Monoid przejść automatu </math>{A} <math> jest izomorficzny z monoidem ilorazowym </math>A^{*}/_{Ker_{ _{{A}}}} <math>.
+Jest to wniosek z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ilustruje poniższy diagram.
-p \circ q \equiv q \circ p
+rys3.5
-</math></center>
+\endcorol
-}}
-{{cwiczenie|4.8||
+{{cwiczenie|[Uzupelnij]||
-Sprawdź następujące równoważności
+Określimy monoid przejść dla automatu z przykładu [[##ex.3.1.1|Uzupelnic ex.3.1.1|]]. Wypisujemy kolejne
+funkcje </math> _{{A}}(w) <math> dla </math>w a,b^{*} <math>. Zauważmy,
+że ze względu na występujące w tabelce powtórzenia będace wynikiem równości,
+np. </math> _{{A}}(b^2)<nowiki>=</nowiki> _{{A}}(b), <math> nie ma potrzeby
+określać funkcji </math> _{{A}}(b^{n}) <math> dla </math>n 3 <math>. Podobna
+obserwacja ma miejsce w innych przypadkach, co sprawia, że tabelka zawiera skończoną
+liczbę różnych funkcji.
-. <math>x NAND y \equiv \neg (x \wedge y)</math>
+\vspace{0.3cm}
+{\centering \begintabular {|c||c|c|c|}
+\hline
+&
+</math>s_{0} <math>&
+</math>s_{1} <math>&
+</math>s_{2} <math>\\
+\hline
+\hline
+</math> _{{A}}(1) <math>&
+</math>s_{0} <math>&
+</math>s_{1} <math>&
+</math>s_{2} <math>\\
+\hline
+</math> _{{A}}(a) <math>&
+</math>s_{1} <math>&
+</math>s_{2} <math>&
+</math>s_{2} <math>\\
+\hline
+</math> _{{A}}(b) <math>&
+</math>s_{0} <math>&
+</math>s_{0} <math>&
+</math>s_{0} <math>\\
+\hline
+</math> _{{A}}(a^{2}) <math>&
+</math>s_{2} <math>&
+</math>s_{2} <math>&
+</math>s_{2} <math>\\
+\hline
+</math> _{{A}}(ab) <math>&
+</math>s_{0} <math>&
+</math>s_{0} <math>&
+</math>s_{2} <math>\\
+\hline
+</math> _{{A}}(ba) <math>&
+</math>s_{1} <math>&
+</math>s_{1} <math>&
+</math>s_{1} <math> \\
+\hline
+</math> _{{A}}(b^{2}) <math>&
+</math>s_{0} <math>&
+</math>s_{0} <math>&
+</math>s_{0} <math>\\
+\hline
+</math> _{{A}}(aba) <math>&
+</math>s_{1} <math>&
+</math>s_{1} <math>&
+</math>s_{2} <math>\\
+\hline
+...&
+...&
+...&
+...\\
+\hline
+\endtabular \par}
+\vspace{0.3cm}
-. <math>x NOR y \equiv \neg (x \vee y)</math>
+</math></center>M({A})<nowiki>=</nowiki>  _{{A}}(1), _{{A}}(a), _{{A}}(b),
+_{{A}}(a^2), _{{A}}(b),  _{{A}}(ba),  _{{A}}(aba)
+.<center><math>
-. <math>x XOR y \equiv \neg (x \Leftrightarrow y)</math>
 }}
-; Solution.
-{{cwiczenie|4.9||
-Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
-:Wygodnie jest reprezentować spójniki binarne w tabeli kwadratowej. Na przykład alternatywę zdefiniowaliśmy jako
-tabelka......
-:Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był przemienny?
-</div></div>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-:Dla przemienności spójnika <math>\circ</math> istotne jest aby <math> 1\circ 0 =  0 \circ 1</math>. Dla pozostałych przypadków wartościowań równoważnośc 4.3 jest zawsze spełniona. Każdy spójnik binarny możemy zdefiniować za pomocą tabelki kwadratowej, np. alternatywę zdefiniowaliśmy jako
-tabelka.......
-:Warunek przemienności oznacza, że wartość w polu o współrzędnych <math>(0,1)</math> jest równa wartości w polu o współrzędnych <math>(1,0)</math>. Takich tabel jest '''8''', więc mamy '''8''' spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli 4.6. Są to
-:1. <math>F</math>
+Poniżej zamieszczamy algorytm obliczający monoid przejść dla automatu skończenie stanowego.
-:2. <math>\wedge</math>
+\beginalgorithm
+\caption{\textsc{WyznaczMonoidPrzejść} - wyznacza monoid przejść dla
+automatu}
+\beginalgorithmic [1]
+\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> - automat
-:3. <math>XOR</math>
+\STATE Wyjście: </math>M<math> - monoid przejść dla </math>{A}<math>
-:4. <math>\vee</math>
+\STATE </math>L  <math>; </math>  L<math> jest listą
-:5. <math>NOR</math>
+\STATE </math>M  <math>;
-:6. <math>\Leftrightarrow</math>
+\FOR{</math>a  A  1<math>}
-:7. <math>NAND</math>
+\STATE \textbf{insert}</math>(L, _{{A}}(a))<math>;  gdzie
+</math>_{{A}}(a)(s)<nowiki>=</nowiki>f(s, a)<math> dla każdego </math>s  S<math>
-:8. <math>T</math>
+\ENDFOR
-</div></div>
+\WHILE{</math>L  <nowiki>=</nowiki> <math>;}
-}}
-:Spójnik binarny <math>\circ</math> będziemy nazywać ''łącznym'' jeśli zachodzi
+\STATE </math>_{{A}}(w)  '''first'''(L)<math>;
-następująca równoważność
-<center><math>
+\STATE </math>M  M  _{{A}}(w)<math>;
-p \circ (q \circ r) \equiv     (p \circ q) \circ r.
+\FOR{</math>a  A<math>}
-</math></center>
-Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
+\STATE </math> s  S'_{{A}}(wa)(s)<nowiki>=</nowiki>f(_{{A}}(w)(s),a)<math>;
-jedynie ze spójników <math>\circ</math> są równoważne jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.
-{{cwiczenie|4.10||
+\IF{</math>'_{{A}}(wa)   L  M<math>}
-Udowodnij, że następujące spójniki są łączne
+\STATE \textbf{insert}</math>(L, '_{{A}}(wa))<math>;
-. <math>\vee</math>
+\ENDIF
-. <math>\wedge</math>
+\ENDFOR
-. <math>\Leftrightarrow</math>
+\ENDWHILE
-. <math>XOR</math>
+\RETURN </math>M<math>;
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
+\endalgorithmic
+\endalgorithm
-:1. Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie wtedy gdy <math>\textnormal{p}</math>,<math>\textnormal{q}</math> i <math>\textnormal{r}</math> są wartościowane na fałsz. Tak samo jest dla formuły <math>p \vee( q \vee r )</math> więc są one równoważne.
+\eject
-:2. Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie wtedy gdy <math>\textnormal{p}</math>,<math>\textnormal{q}</math> i <math>\textnormal{r}</math> są wartościowane na prawdę. Tak samo jest dla formuły <math>p \wedge( q \wedge r )</math> więc są one równoważne.
+Procedura \textbf{insert}</math>(L, x)<math> wkłada na koniec listy </math>L<math> element
+</math>x<math>. Funkcja \textbf{first}</math>(L)<math> wyjmuje pierwszy element znajdujący
+się na liście </math>L<math> i zwraca go. Algorytm działa w następujący sposób:
+najpierw na listę </math>L<math> wkładane są elementy monoidu przejść
+</math>_{{A}}(a)<math> dla każdej litery </math>a  A  1<math>. Te
+funkcje można obliczyć bezpośrednio z tabelki reprezentującej
+funkcję przejścia automatu </math>{A}<math>. Następnie z listy po kolei
+ściągane są poszczególne funkcje </math>_{{A}}(w)<math>. Każda z
+nich dodawana jest do zbioru </math>M<math>, a następnie algorytm sprawdza dla
+każdej litery </math>a  A<math>, czy funkcja </math>_{{A}}(wa)<math>
+istnieje już na liście </math>L<math> lub w zbiorze </math>M<math>. Jeśli nie, to funkcja
+ta dodawana jest do listy. Procedura powyższa trwa do czasu, gdy
+lista </math>L<math> zostanie pusta. Wtedy wszystkie elementy monoidu przejść
+znajdą się w zbiorze </math>M<math>.
-:3. Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math> i <math> p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
+Przeanalizujmy działanie algorytmu dla automatu z przykładu
+[[##ex.3.1.1|Uzupelnic ex.3.1.1|]].
+Na początku na listę </math>L<math> włożone zostaną funkcje
+</math>_{{A}}(1)<math>, </math>_{{A}}(a)<math> oraz
+</math>_{{A}}(b)<math>. Z listy zdejmujemy funkcję
+</math>_{{A}}(1)<math> i dodajemy ją do zbioru </math>M<math>. Ponieważ
+</math> a  A_{{A}}(1a)<nowiki>=</nowiki>_{{A}}(a)<math>, a
+funkcje </math>_{{A}}(a)<math> oraz </math>_{{A}}(b)<math>
+znajdują się już na liście, zatem nie dodajemy ich do </math>L<math>. Bierzemy
+kolejny element listy, </math>_{{A}}(a)<math>, dodajemy go do </math>M<math> i
+obliczamy funkcje </math>_{{A}}(aa)<math> oraz
+</math>_{{A}}(ab)<math>. Ponieważ </math>_{{A}}(aa)<math> nie jest
+tożsama z żadną funkcją ze zbioru </math>L  M<math>, dodajemy ją do listy.
+Funkcja </math>_{{A}}(ab)<math> również nie jest równa żadnej z
+funkcji należących do zbioru </math>L  M<math>, zatem wstawiamy ją na
+koniec listy. Na liście </math>L<math> mamy zatem teraz następujące elementy:
+</math>_{{A}}(b)<math>, </math>_{{A}}(a^2)<math> oraz
+</math>_{{A}}(ab)<math>. Zdejmujemy z listy funkcję
+</math>_{{A}}(b)<math>, dodajemy ją do </math>M<math> i obliczamy
+</math>_{{A}}(ba)<math> oraz </math>_{{A}}(bb)<math>. Pierwsza z
+tych funkcji jest nowa, tzn. nie jest tożsama z żadną funkcją ze
+zbioru </math>L  M<math> więc dodajemy ją na koniec listy. Druga z nich
+równa jest funkcji </math>_{{A}}(b)<math>, więc nie dodajemy jej do
+listy. W tym momencie zbiór </math>M<math> zawiera następujące elementy:
+</math>_{{A}}(1)<math>, </math>_{{A}}(a)<math>,
+</math>_{{A}}(b)<math>, natomiast lista zawiera elementy
+</math>_{{A}}(a^2)<math>, </math>_{{A}}(ab)<math>,
+</math>_{{A}}(ba)<math>. Zdejmujemy z </math>L<math> funkcję
+</math>_{{A}}(a^2)<math>, dodajemy ja do </math>M<math> i ponieważ
+</math>_{{A}}(a^2a)<nowiki>=</nowiki>_{{A}}(a^2)<math> i
+</math>_{{A}}(a^2b)<nowiki>=</nowiki>_{{A}}(b)<math> nic nie dodajemy do
+</math>L<math>. Zdejmujemy teraz z listy funkcję </math>_{{A}}(ab)<math>,
+dodajemy ją do </math>M<math> i ponieważ </math>_{{A}}(aba)<math> nie należy
+do </math>L  M<math> dodajemy ją do listy.
+</math>_{{A}}(abb)<nowiki>=</nowiki>_{{A}}(b)<math>, więc tej funkcji
+nie dodajemy do </math>L<math>. Z </math>L<math> ściągamy </math>_{{A}}(ba)<math>,
+dodajemy ją do </math>M<math> i widzimy, że
+</math>_{{A}}(baa)<nowiki>=</nowiki>_{{A}}(a^2)<math> oraz
+</math>_{{A}}(bab)<nowiki>=</nowiki>_{{A}}(b)<math>, więc nic nie
+dodajemy do </math>L<math>. Na liście pozostała funkcja
+</math>_{{A}}(aba)<math>. Ściągamy ją z listy i dodajemy do </math>M<math>.
+Widzimy, że </math>_{{A}}(abaa)<nowiki>=</nowiki>_{{A}}(a^2)<math> i
+</math>_{{A}}(abab)<nowiki>=</nowiki>_{{A}}(b)<math>, zatem nic nie
+dodajemy do listy </math>L<math>. Lista jest w tym momencie pusta i działanie
+algorytmu zakończyło się. Ostatecznie mamy
+</math></center>M({A})<nowiki>=</nowiki> _{{A}}(1),_{{A}}(a),
+_{{A}}(b),_{{A}}(a^2),_{{A}}(ab),
+_{{A}}(ba),_{{A}}(aba).<center><math>
+Co zgadza się z wynikiem otrzymanym w przykładzie.
-tabelka.......
+Twierdzenie poniższe zbiera dotychczas uzyskane charakteryzacje języków rozpoznawanych.
+\begintheor
-:Kolumna '''4''' i '''6''' są identyczne więc odpowiadające im formuły są równoważne. Spójnik <math>\Leftrightarrow</math> jest więc łączny.
+Niech </math> L  A^* <math> będzie dowolnym językiem. Równoważne są następujące warunki:
-:4. ...
+#  Język </math> L <math> jest rozpoznawalny,
-</div></div>
-}}
-Możemy również rozważać spójniki '''3''' i więcej argumentowe. Spójnik <math>k</math>-argumetowy powinien odpowiadać funkcji <math>\mathbb{B}^k \rightarrow \mathbb{B}</math>.
+#  Język </math> L <math> jest sumą wybranych klas równoważności pewnej prawej
+kongruen\-cji  na </math> A^* <math> o skończonym indeksie: </math></center>L <nowiki>=</nowiki> _{w L}[w]_.<center><math>
-{{przyklad|4.7||
+#  Język </math> L <math> jest sumą wybranych klas równoważności pewnej
+kongruencji  na </math> A^* <math> o skończonym indeksie: </math></center>L <nowiki>=</nowiki> _{w L}[w]_.<center><math>
-W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego
-tabelka........
+#  Istnie\-je skończony monoid </math> M <math> i istnie\-je epimorfizm </math> : A^*  M<math> taki,
-}}
+że </math></center>L <nowiki>=</nowiki> ^{-1}( (L)).<center><math>
+\endtheor
-{{cwiczenie|4.11||
+\beginprf
-Udowodnij, że różnych spójników <math>k</math>-argumentowych jest dokładnie
+Dowód równoważności czterech powyższych warunków przeprowa\-dzi\-my zgodnie z następującym schematem:
-<math>2^{2^k}</math>.
-; Solution.
+</math></center>[[##tg|Uzupelnic tg|]][[##tf|Uzupelnic tf|]][[##te|Uzupelnic te|]][[##td|Uzupelnic td|]]  [[##tg|Uzupelnic tg|]]<center><math>
-}}
-==Systemy funkcjonalnie pełne==
+[[##tg|Uzupelnic tg|]] [[##tf|Uzupelnic tf|]]
-Każda formuła odpowiada pewnej funkcji przekształcającej
+Dany jest homomorfizm </math></center>: A^*  M, <center><math> gdzie </math>M<math> jest skończonym monoidem.\\
-wartościowania zmiennych w niej występujących w element zbioru
+Określamy relację  na </math>A^*<math>, przyjmując dla dowolnych </math> u, v  A^* </center>u    v     (u) <nowiki>=</nowiki>  (v).<center><math>
-<math>\mathbb{B}</math>. Na przykład formuła <math>p \Rightarrow (q\Rightarrow r)</math> wyznacza funkcję
+Tak określona relacja jest kongruencją.  Natomiast jej skończony indeks wynika z faktu, że monoid </math> M <math> jest skończony.
-<math>f_{p \Rightarrow (q\Rightarrow r)}</math> opisaną poniższą tabelą
+Pokażemy teraz, że:
+</math></center>L <nowiki>=</nowiki> _{w L}[w]_ .<center><math> Inkluzja  jest oczywista.\\
+Inkluzja w przeciwną stronę (</math>L  _{w L}[w]_,<math>) oznacza, że każda klasa równoważności relacji
+ albo cała zawiera się w języku </math>L<math>, albo cała zawiera się w uzupełnieniu języka </math>L<math>.\\
+Załóżmy, że </math> u  [w]_<math> dla pewnego </math> w  L. <math>
+Oznacza to, że
+</math></center>u    w   (u) <nowiki>=</nowiki>  (w)   (L)
+u  ^{-1}( (u))   ^{-1}( (L)) <nowiki>=</nowiki> L.<center><math>
+Implikuje to ostatecznie, że </math>u  L<math>.
-Tabelka.........
+[[##tf|Uzupelnic tf|]] [[##te|Uzupelnic te|]]
+Każda kongruencja jest prawą kongruencją.
-Mówimy, wtedy że formuła <math>{\phi}</math> definuje funkcję <math>f_{\phi}</math>.
+[[##te|Uzupelnic te|]] [[##td|Uzupelnic td|]]
-{{definicja|5.1||
+Niech  będzie prawą kongruencją o skończonym indeksie na </math> A^* <math> taką, że
+</math></center>L <nowiki>=</nowiki> _{w L}[w]_ .<center><math>
+Automat </math>{A}_{ } <nowiki>=</nowiki> (A^*/,f^*,[1]_,T),<math> dla którego
-Skończony zbiór funkcji boolowskich <math>{\Gamma}</math> nazywamy funkcjonalnie pełnym, jeśli każdą funkcję boolowską da się zdefiniować przy pomocy formuły zbudowanej wyłącznie ze spójników odpowiadających funkcjom ze zbioru <math>{\Gamma}</math>.
+</math></center>f^*([w]_,u) <nowiki>=</nowiki>[wu]_ ,  T <nowiki>=</nowiki>  [w]_  :  w  L <center><math> akceptuje język </math>L<math>.
-}}
-{{twierdzenie|5.2||
+[[##td|Uzupelnic td|]] [[##tg|Uzupelnic tg|]]
-Zbiór <math>\{\wedge, \vee, \neg\}</math> jest funkcjonalnie pełny.
+Niech język </math> L<nowiki>=</nowiki>L({A}) <math>, gdzie  </math>{A} <nowiki>=</nowiki> (S,f,s_0,T)<math>.\\
-}}
+Określamy odwzorowanie
-{{dowod|||
+</math></center> :A^{*} A^{*}/_{Ker _{{A}}}, <center><math>
-}}
+przyjmując dla każdego </math>v A^{*} </center> (v)<nowiki>=</nowiki>[v]_{Ker _{{A}}}. <center><math>
-{{twierdzenie|5.3||
+Jest to odwzorowanie kanoniczne monoidu </math> A^* <math> na monoid ilorazowy, a więc jest to epimorfizm.\\
+</math>A^{*}/_{Ker _{{A}}} <math> jest monoidem skończonym, ponieważ </math> S <math> jest zbiorem skończonym.
-Zbiory <math>\{\wedge,  \neg\}</math>, <math>\{\vee,  \neg\}</math> są funkcjonalnie pełne.
+Dla dowodu równości </math>L <nowiki>=</nowiki> ^{-1}( (L))<math> wystarczy udowodnić
-}}
+inkluzję </math>L  ^{-1}( (L))<math>. (Inkluzja </math> L  ^{-1}( (L))<math>
+wynika z~definicji przeciwobrazu.) \\
+Niech </math> u  ^{-1}( (L)) .<math> Oznacz to, że
-{{dowod|||
+</math></center> {c}
+(u)  (L)   v L : (u)<nowiki>=</nowiki> (v)
-}}
+v L : [u]_{_{Ker _{{A}}}}<nowiki>=</nowiki>[v]_{_{Ker _{{A}}}}  <br>
+v L :   _{{A}}(u)<nowiki>=</nowiki> _{{A}}(v) ,
-'''Zadanie 5.4''' Udowodnij, że zbiór <math>\{\Rightarrow,  \neg\}</math> jest funkcjonalnie
+v L :  s  S f(s,u)<nowiki>=</nowiki>f(s,v)
-pełny.
-{{twierdzenie|5.5||
-Zbiór <math>\{NOR\}</math> jest funkcjonalnie pełny.
-}}
-'''Zadanie 5.6''' Udowodnij, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.
-{{cwiczenie|5.1||
-Zdefiniuj alternatywę przy pomocy samej implikacji.
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Łatwo sprawdzić że formuła <math>p \Rightarrow (p \Rightarrow q)</math> jest równoważna formule <math>p\vee q</math>.
-</div></div>
-}}
-'''Zadanie 5.7''' Jakie funkcje binarne da się zdefiniować przy pomocy samej implikacji?
-{{cwiczenie|5.2||
-Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne
-. <math>\{\wedge\}</math>
-. <math>\{\vee\}</math>
-. <math>\{\Leftrightarrow\}</math>
-. <math>\{XOR\}</math>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-:1. Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez <math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość '''1''', jeśli jej zmienne są wartościowane na '''1'''. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika <math>\wedge</math> w formule. Dowód będzie indukcyjny ze względu na rozmiar formuły.
-:Baza indukcji: Każda formuła z <math>F_\wedge</math> o rozmiarze '''0''' jest postaci <math>\textnormal{x}</math>, gdzie <math>\textnormal{x}</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na '''1''' formuła <math>\textnormal{x}</math> też jest wartościowana na '''1'''. A więc każda formuła o rozmiarze '''0''' ma postulowaną własność.
-:Krok indukcyjny: Ustalmy dowolne <math>n>0</math> i przyjmijmy, że wszystkie formuły o mniejszym rozmiarze mają postulowaną własność. Niech <math>\nu</math> będzie dowolną formułą z <math>F_\wedge</math> o rozmiarze <math>\textnormal{n}</math>. Skoro <math>n>1</math> to <math>\nu</math> musi być postaci <math>\phi\wedge \psi</math>. Rozważmy wartościowanie które wszyskim zmiennym przypisuje wartość '''1'''. Ponieważ rozmiary <math>{\phi}</math> oraz <math>{\psi}</math> są silnie mniejsze od <math>\textnormal{n}</math> to z założenia indukcyjnego otrzymujemy, że dla naszego wartościowania obie przyjmują wartość '''1'''. Wobec tego zgodnie z tabelą 4.2 cała formuła <math>\phi\wedge \psi</math> też przyjmuje wartość '''1'''. Dowiedliśmy więc, że każda formuła o rozmiarze <math>\textnormal{n}</math> ma postulowaną własność.
-:Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość '''1''', jeśli jej zmienne są wartościowane na '''1'''. Wobec tego niemożliwe jest zdefiniowanie np. spójnika <math>F</math> gdyż definująca go formuła musiałby przyjąć wartość '''0''' na takim wartościowaniu.
-:2. Dowód analogiczny do poprzedniego.
-</div></div>
-}}
-{{cwiczenie|5.3||
-Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
-Przyjrzyj się formułom zbudowanym z <math>\Leftrightarrow</math>
-</div></div>
-}}
-{{cwiczenie|5.4||
-(z wykładu prof. P.M.Idziaka) Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>\textnormal{n}</math> argumetnowych, a <math>P_n</math> ilość boolowskich funkcji <math>\textnormal{n}</math> argumentowych, takich że przy pomocy każdej z nich da się zdefiniować dowolną funkcję boolowską (czyli jeśli <math>\circ</math> jest takim spójnikiem to zbiór <math>\{\circ\}</math> jest funkcjonalnie pełny). Udowdnij istenienie poniższej granicy i wyznacz jej wartość
-<center><math>
-\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
-</math></center>
-; Solution.
-}}
-==Postacie normalne==
-{{definicja|6.1||
-Literałem nazywamy formułę która jest zmienną zdaniową lub negacją zmiennej zdaniowej.
-}}
-Zauważmy, że formuła konstruowana w dowodzie twierdzenia 5.2 jest w pewnej standartowej postaci - formuła jest alternatywą formuł które są koniunkcjami literałów. Przypomnijmy, że dla <math>p \Rightarrow q</math> zbudujemy formułę
-<center><math>
-(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).
-</math></center>
-{{definicja|6.2||
-Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy gdy jest postaci
-<center><math>
-\phi_1\vee \dots \vee \phi_n
-</math></center>
-oraz każda z formuł <math>\phi_i</math> jest koniunkcją literałów, czyli jest postaci
-<center><math>
-l_1^i \wedge \dots \wedge l_k^i
-</math></center>
-dla pewnych literałów <math>l_1^i, \dots,l_k^i</math>
-}}
-{{twierdzenie|6.3||
-Dla każedej formuły istnieje równoważna formuła w DNF.
-}}
-{{dowod|||
-Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia 5.2.
-}}
-{{definicja|6.4||
-Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są
-alternatywami literałów.
-}}
-{{twierdzenie|6.5||
-Dla każdej formuły istnieje równoważna formuła w CNF.
-}}
-{{dowod|||
-}}
-{{cwiczenie|[6.1||
-Jak sprawdzić, czy formuła w CNF jest tautologią?
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-:Niech rozważaną formułą będzie
 <center><math>
-\phi_1\wedge \dots \wedge \phi_n
+W szczególności  </math></center> f(s_0,u) <nowiki>=</nowiki> f(s_0,v)  T, <center><math> czyli  </math>u  L.<math>
-</math></center>
-:Aby była tautologią konieczne jest aby każda z formuł <math>\phi_i</math> była tautologią. Ponieważ każda z formuł <math>\phi_i</math> jest alternatywą literałów to jest tautologią jedynie wtedy jeśli istnieje taki literał który występuje w <math>\phi_i</math> zarówno pozytywnie (czyli jako zmienna) jak i negatywnie (czyli jako zanegowana zmienna).
-</div></div>
-}}
-{{cwiczenie|6.2||
-Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w CNF
-. <math>p \Leftrightarrow q</math>
-. <math>p \Rightarrow (q \Rightarrow p)</math>
-. <math>(p \Rightarrow q) \Rightarrow p</math>
-. <math>(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge(r \vee \neg b \vee \neg c) \wedge (c \vee p))</math>
-. <math>(p \wedge q) \vee (r \wedge s)</math>
-; Solution.
-}}
-===Spełnialność===
-Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.
-{{definicja|6.6||
-Formuła jest spełnialna jeśli istenieje takie wartościowanie które wartościuje tą formułę na '''1'''.
-:Formuły spełnialne są w ścisłym związku z tautologiami.
-}}
-{{twierdzenie|6.7||
-Formuła <math>{\phi}</math> jest tautologią wtedy i tylko wtedy kiedy formuła <math>\neg \phi</math> nie jest spełnialna.
-}}
-{{dowod|||
-Przypuśćmy, że formuła <math>{\phi}</math> jest tautologią. Wtedy dla każdego wartościowania <math>v</math> mamy <math>v(\phi)=1</math>. Stąd otrzymujemy że dla każdego wartościowania <math>v</math> mamy<math>v(\neg \phi)=0</math>, a więc
-nie istnieje wartościwanie, które spełnia <math>\neg \phi</math>, czyli formuła ta nie jest spełnialna.
-Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>\textnormal{v}</math> takie, że <math>v(\neg \phi)=0</math>. Wynika stąd, że dla każdego wartościowania mamy <math>v(\phi)=1</math>, a więc <math>{\phi}</math> jest tautologią.
-}}
-{{cwiczenie|6.3||
-Sprawdź spełnialność następujących formuł
-. <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
-. <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee  p)</math>
-; Solution.
-}}
-==Logika intuicjonistyczna==
-Niektórzy logicy mają wątpliwości co do tego czy powinniśmy przyjmować schemat dowodu nie wprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające
-związki z teorią obliczeń (<u>'''izomorfizm Curry-Howard'''</u>).
-Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez <math>I_\Rightarrow</math> to zbiór tych formuł które da się dowodnić przy pomocy reguły MP z aksjomatów S i K.
-{{definicja|7.1||
-Aksjomaty <math>I_\Rightarrow</math>
-. <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
-aksjomatem K)
-. <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana aksjomatem S)
-}}
-W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników <math>\wedge, \vee</math> oraz <math>\neg</math>. Dla uproszczenia zajmiemy  się jedynie formułami w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej w którym jedynymi spójnikami są <math>\Rightarrow</math> da się udowodnić przy pomocy aksjomatów 7.1. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest
-bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.
-{{twierdzenie|7.2||
-Każde twierdzenie logiki intuicjonistycznej jest twierdzeniem klasycznego rachunku zdań.
-}}
-{{dowod|||
-Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem twierdzenia klasycznego rachunku zdań.
-}}
-Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math> pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:
-<center><math>
-((p \Rightarrow q) \Rightarrow p ) \Rightarrow p
-</math></center>
-W zadaniu 4.1 pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta 4.4 również twierdeniem klasycznego rachunku zdań.<br/>
-W poniższych zadaniach wykażemy poniższe twierdzenie
-{{twierdzenie|7.3||
-Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.
-}}
-Zauważmy, że oznacza to również że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 3.1, a więc wymaga używania spójnika <math>\neg</math>.<br/>
-Aby udowodnić twierdzenie 7.3 zdefiniujemy jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do 4.1 zdefiniujemy matrycę tym razem 3-elementową.
-{{definicja|7.4||
-Matrycą <math>\mathbb{M}_3</math> będziemy nazywać zbiór trójelementowy <math>M_3=\{0,1,2\}</math> w którym '''2''' jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje <math>\Rightarrow</math> zdefiniowaną następująco
-tabelka.......
-}}
-W przypadku rozważanej matrycy <math>\mathbb{M}_3</math> wartościowanie będzie funkcją przypisującą zmiennym zdaniowym elementy zbioru <math>M_3</math>. Podobnie jak dla logiki klasycznej wartościowanie zmiennych rozszzerzamy na wartościowanie formuł zgodnie z tabelą 7.4.
-{{przyklad|7.5||
-Dla wartościowania <math>v</math> takiego, że <math>v(p)=2, v(q)=1, v(r)=0</math> formuła
-<center><math>
-(p \Rightarrow q) \Rightarrow r
-</math></center>
-przyjmuje wartość '''0'''.
-}}
-{{definicja|7.6||
-Tautologią logiki <math>I_3</math> będziemy nazywać każdą formułę implikacyjną,
-która przy każdym wartościowaniu zmiennych w <math>M_3</math> przyjmuje wartość '''2'''.
-}}
-{{cwiczenie|7.1||
-Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</math>.
-; Solution.
-}}
-{{cwiczenie|7.2||
-Udowodnij, że jeśli formuła postaci <math>\phi \Rightarrow \psi</math> oraz formuła <math>{\phi}</math> są tautologiami <math>I_3</math> to formuła <math>{\psi}</math> jest tautologią <math>I_3</math>.
-; Solution.
-}}
-{{cwiczenie|7.3||
-Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest tautologią <math>I_3</math>.
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
-: Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu. Pomocne będą poprzednie zadania.
-</div></div>
-}}
-; Solution.
-{{cwiczenie|7.4||
-Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
-: Nie jest.
-</div></div>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-: Dla wartościowania <math>v</math> takiego, że <math>v(p)=1</math> i <math>v(q)=0</math> kolejne fomruły przyjmują następujace wartości
-:1. <math>v(p\Rightarrow q) =0</math>
-:2. <math>v((p\Rightarrow q)\Rightarrow p) =2</math>
-:3. <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>
-:Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math> gdyż wyróżnioną wartością prawdy <math>I_3</math> w jest '''2'''. </div></div>
-}}
-Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <math>I_3</math>
-taką, że każda twierdzenie intuicjonizmu jest tautologią <math>I_3</math>.
-Skoro prawo Pierce'a nie jest tautologią <math>I_3</math> to nie jest też
-twierdzeniem <math>I_\Rightarrow</math>.
-UWAGA! W dalszej części będziemy się posługiwać wyłącznie '''logiką klasyczną'''.
+\begincenter   \endcenter  \endprf</math>