Test GR2: Różnice pomiędzy wersjami

Wersja z 14:31, 15 sie 2006

Dla zainteresowanych Twierdzenie 3.2.

Niech

L \subset A^{*}

będzie dowolnym językiem.

1. Dla dowolnego języka

L \in ℛ ℰ 𝒞 (A^{*})

monoid przejść automatu minimalnego

𝒜_{L}

jest izomorficzny z monoidem syntaktycznym

M (L)

języka

L

, czyli

M (𝒜_{L}) \sim M (L) .

2. (tw. J.Myhill'a) Język

L \subset A^{*}

jest rozpoznawalny wtedy i tylko wtedy, gdy

M (L)

jest monoidem skończonym.

Dowód

Dla dowodu punktu 1 wykażemy, że

P_{L} = K e r_{τ_{𝒜_{L}}},

gdzie zgodnie z definicją dla dowolnych $w, u \in A^{*}$

τ_{𝒜_{L}} (w) ([u]_{P_{L}^{r}}) = f^{*} ([u]_{P_{L}^{r}}, w) = [u w]_{P_{L}^{r}} .

\begin{array}{c} (u, w) \in K e r_{τ_{𝒜_{L}}} \Leftrightarrow \forall v \in A^{*} τ_{𝒜_{L}} (u) ([v]_{P_{L}^{r}}) = τ_{𝒜_{L}} (w) ([v]_{P_{L}^{r}}) \Leftrightarrow [v u]_{P_{L}^{r}} = [v w]_{P_{L}^{r}} \Leftrightarrow \\ \Leftrightarrow \forall v, z \in A^{*} v u z \in L \Leftrightarrow v w z \in L \Leftrightarrow [u]_{P_{L}} = [w]_{P_{L}} \Leftrightarrow (u, v) \in P_{L} . \end{array}

Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ma postać:

RYSUNEK ja-lekcja4-w-rys1.pdf

czyli $M (𝒜_{L}) \sim M (L)$ .
Dla dowodu punktu 2 załóżmy, że język $L$ jest rozpoznawalny. Zatem

L = ⋃_{w \in L} [w]_{ρ},

gdzie

ρ

jest kongruencją o skończonym indeksie.

Z twierdzenia (patrz Twierdzenie 2.1.) wnioskujemy, że $ρ \subseteq P_{L} .$ Oznacza to, że indeks relacji $P_{L}$ jest niewiększy od indeksu $ρ,$ a co za tym idzie, $M (L) = A^{*} / P_{L}$ jest monoidem skończonym.

Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm

kanoniczny

k : A^{*} ⟶ A^{*} / P_{L} = M (L) .

Pokażemy, że

spełnia on warunki z punktu 4. twierdzenia 1.2 (patrz twierdzenie 1.2.). $M (L)$ jest skończony, więc pozostaje do wykazania równość

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

W tym celu wystarczy oczywiście udowodnić inkluzję

$k^{- 1} (k (L)) \subseteq L$ .

\begin{array}{c} v \in k^{- 1} (k (L)) \Rightarrow k (v) \in k (L) \Rightarrow \exists u \in L : k (v) = k (u) \in k (L) \Leftrightarrow \\ \Leftrightarrow \exists u \in L : [v]_{P_{L}} = [u]_{P_{L}} \Leftrightarrow \exists u \in L : v \in L \Leftrightarrow u \in L . \end{array}

Czyli $v \in L$ i $L = k^{- 1} (k (L))$ . i tutaj twierdzenie jsadhfouvnhter zsdkjrvnhr SFj v

Twierdzenie 3.2.

Niech $L \subset A^{*}$ będzie dowolnym językiem.

1. Dla dowolnego języka

L \in ℛ ℰ 𝒞 (A^{*})

monoid przejść automatu minimalnego

𝒜_{L}

jest izomorficzny z monoidem syntaktycznym

M (L)

języka

L

, czyli

M (𝒜_{L}) \sim M (L) .

2. (tw. J.Myhill'a) Język

L \subset A^{*}

jest rozpoznawalny wtedy i tylko wtedy, gdy

M (L)

jest monoidem skończonym.

Dowód

Dla dowodu punktu 1 wykażemy, że

P_{L} = K e r_{τ_{𝒜_{L}}},

gdzie zgodnie z definicją dla dowolnych $w, u \in A^{*}$

τ_{𝒜_{L}} (w) ([u]_{P_{L}^{r}}) = f^{*} ([u]_{P_{L}^{r}}, w) = [u w]_{P_{L}^{r}} .

\begin{array}{c} (u, w) \in K e r_{τ_{𝒜_{L}}} \Leftrightarrow \forall v \in A^{*} τ_{𝒜_{L}} (u) ([v]_{P_{L}^{r}}) = τ_{𝒜_{L}} (w) ([v]_{P_{L}^{r}}) \Leftrightarrow [v u]_{P_{L}^{r}} = [v w]_{P_{L}^{r}} \Leftrightarrow \\ \Leftrightarrow \forall v, z \in A^{*} v u z \in L \Leftrightarrow v w z \in L \Leftrightarrow [u]_{P_{L}} = [w]_{P_{L}} \Leftrightarrow (u, v) \in P_{L} . \end{array}

Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ma postać:

RYSUNEK ja-lekcja4-w-rys1.pdf

czyli $M (𝒜_{L}) \sim M (L)$ .
Dla dowodu punktu 2 załóżmy, że język $L$ jest rozpoznawalny. Zatem

L = ⋃_{w \in L} [w]_{ρ},

gdzie

ρ

jest kongruencją o skończonym indeksie.

Z twierdzenia (patrz Twierdzenie 2.1.) wnioskujemy, że $ρ \subseteq P_{L} .$ Oznacza to, że indeks relacji $P_{L}$ jest niewiększy od indeksu $ρ,$ a co za tym idzie, $M (L) = A^{*} / P_{L}$ jest monoidem skończonym.

Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm

kanoniczny

k : A^{*} ⟶ A^{*} / P_{L} = M (L) .

Pokażemy, że

spełnia on warunki z punktu 4. twierdzenia 1.2 (patrz twierdzenie 1.2.). $M (L)$ jest skończony, więc pozostaje do wykazania równość

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

W tym celu wystarczy oczywiście udowodnić inkluzję

$k^{- 1} (k (L)) \subseteq L$ .

\begin{array}{c} v \in k^{- 1} (k (L)) \Rightarrow k (v) \in k (L) \Rightarrow \exists u \in L : k (v) = k (u) \in k (L) \Leftrightarrow \\ \Leftrightarrow \exists u \in L : [v]_{P_{L}} = [u]_{P_{L}} \Leftrightarrow \exists u \in L : v \in L \Leftrightarrow u \in L . \end{array}

Czyli $v \in L$ i $L = k^{- 1} (k (L))$ .

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f (0) = 1$ $f (1) = 3$ $f (n) = n + 3; n \geq 2$	$f (0) = 2$ $f (1) = 3$ $f (n) = n + 1; n \geq 2$
Maszyna rozpoznająca $w w^{\leftarrow}$	$f (n) = 6 + 8 + \dots + (n + 3) + 2; n = 2 k + 1$ $f (n) = 5 + 7 + \dots + (n + 3) + 1; n = 2 k$	$f (n) = n + 1$

$\Rightarrow$	0	1	...	...
Cell1	Cell2

$\Rightarrow$	0	1
0	1	1
1	0	1

$p$	$\neg p$
0	1
1	0

$\land$	0	1
0	0	0
1	0	1

$\lor$	0	1
0	0	1
1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p} \wedge \textnormal{q}}	$\neg (p \land q)$	$\neg p$	$\neg q$	$\neg p \lor \neg q$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

Numer funkcji	$p = 0$ $q = 0$	$p = 0$ $q = 1$	$p = 1$ $q = 0$	$p = 1$ $q = 1$
0	0	0	0	0	$F$
1	0	0	0	1	$\land$
2	0	0	1	0	$\neg (p \Rightarrow q)$
3	0	0	1	1	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}
4	0	1	0	0	$\neg (q \Rightarrow p)$
5	0	1	0	1	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}
6	0	1	1	0	$X O R$
7	0	1	1	1	$\lor$
8	1	0	0	0	$N O R$
9	1	0	0	1	$\Leftrightarrow$
10	1	0	1	0	$\neg q$
11	1	0	1	1	$q \Rightarrow p$
12	1	1	0	0	$\neg p$
13	1	1	0	1	$p \Rightarrow q$
14	1	1	1	0	$N A N D$
15	1	1	1	1	$T$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$(p \leftrightarrow q)$	$(p \leftrightarrow q) \leftrightarrow r$	$(q \leftrightarrow r)$	$p \leftrightarrow (q \leftrightarrow r)$
0	0	0	1	0	1	0
0	0	1	1	1	0	1
0	1	0	0	1	0	1
0	1	1	0	0	1	0
1	0	0	0	1	1	1
1	0	1	0	0	0	0
1	1	0	1	0	0	0
1	1	1	1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$\circ (p, q, r)$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$f_{p \to_{(} q \to r)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

$\Rightarrow$	0	1	2
0	2	2	2
1	0	2	2
2	0	1	2

$\hat{σ} (f (t_{0}, . ., t_{n})) = I (f) (\hat{σ} (t_{0}), . ., \hat{σ} (t_{n}))$

X^{*} = {1} \cup X \cup X^{2} \cup . . . \cup X^{n} \cup \dots = ⋃_{i = 0}^{\infty} X^{i}

John Arthur Todd (1908-1994)
Zobacz biografię

Donald Ervin Knuth (1938-)
Zobacz biografię

Plik:Nagroda.jpeg

Nagroda Turinga
Zobacz Nagroda Turinga

Kurt Goedel (1906-1978)
Zobacz biografię

Noam Avram Chomsky (1928-)
Zobacz biografię

Stephen Cole Kleene (1909-1994)
Zobacz biografię

Alonso Church (1903-1995)
Zobacz biografię

Sheila Greibach (1939-)
Zobacz biografię

Emil Leon Post (1897-1954)
Zobacz biografię

Pafnutij Lwowicz Czebyszew (1821-1894)
Zobacz biografię

Andriej Nikołajewicz Kołmogorow (1903-1987)
Zobacz biografię

Andriej Markow (1856-1922)
Zobacz biografię

Jakob Bernoulli (1654-1705)
Zobacz biografię

Félix Édouard Justin Émile Borel (1871-1956)
Zobacz biografię

Carl Friedrich Gauss (1777-1855)
Zobacz biografię

Henri Léon Lebesgue (1875-1941)
Zobacz biografię

Siméon Denis Poisson (1781-1840)
Zobacz biografię

Nagroda Goedla
Zobacz Nagroda Goedla]]

Nagroda Turinga
Zobacz Nagroda Turinga

Nagroda Knutha
Zobacz Nagroda Knutha

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle g(C)=\begincases C\cup \{f(C')\} C \endcases }

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle g(C)=\left\{\aligned C\cup \{f(C')\}\\C\endaligned \right}

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d, (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land \left\{\aligned \forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz }\\ \forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \endaligned \right}

@@ Linia 1: / Linia 1: @@
+{|width=100% border="0" cellpadding="5" cellspacing="20"
+|- style="background-color:#abcdef;"
+| <span style="font-variant:small-caps">Dla zainteresowanych Twierdzenie 3.2.</span>
+|-
+| Niech <math>L\subset A^{*} </math> będzie dowolnym językiem.
+:1. Dla dowolnego języka <math>L\in \mathcal{REC}(A^{*}) </math> monoid przejść automatu minimalnego <math>\mathcal{A}_{L} </math> jest izomorficzny z monoidem syntaktycznym <math> M(L) </math> języka <math>L</math>, czyli
+<center><math>M(\mathcal{A}_{L})\sim M(L). </math></center>
+:2. (tw. J.Myhill'a) Język <math>\; L \subset A^* \;</math> jest rozpoznawalny wtedy i tylko wtedy, gdy <math>\; M(L) \;</math> jest monoidem skończonym.
+|}
+{|width=100% border="0" cellpadding="5" cellspacing="20"
+|- style="background-color:#abcdef;"
+| <span style="font-variant:small-caps">Dowód</span>
+|-
+| Dla dowodu punktu 1 wykażemy, że
+<center><math>P_{L}=Ker_{\tau
+_{\mathcal{A}_{L}}}, </math></center>
+gdzie zgodnie z definicją dla dowolnych <math>w,u\in A^{*} </math>
+<center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
+<center><math>\begin{array} {c}
+(u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
+\tau _{\mathcal{A}_{L}}(u)([v]_{P^{r}_{L}})=\tau _{\mathcal{A}_{L}}(w)([v]_{P^{r}_{L}})\Leftrightarrow
+[vu]_{P^{r}_{L}}=[vw]_{P^{r}_{L}}\Leftrightarrow\\
+\Leftrightarrow \forall v,z \in A^*\;\;vuz\in L\Leftrightarrow vwz\in L \Leftrightarrow[u]_{P_{L}}=[w]_{P_{L}}
+\Leftrightarrow (u,v) \in P_L.\\
+\end{array} </math></center>
+Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku
+ma postać:  <br>
+'''RYSUNEK ja-lekcja4-w-rys1.pdf'''<br>
+czyli <math>M(\mathcal{A}_{L})\sim M(L) </math>. <br>
+Dla dowodu punktu 2 załóżmy, że język <math>\; L \;</math> jest rozpoznawalny.
+Zatem
+<center><math>L = \bigcup_{w \in L} [w]_\rho ,</math></center> gdzie <math>\; \rho \;</math> jest kongruencją o skończonym indeksie.
+Z twierdzenia (patrz [[#twierdzenie_2_1|Twierdzenie 2.1.]]) wnioskujemy, że <math>\rho \subseteq P_L .</math> Oznacza to, że indeks relacji <math>\; P_L \;</math> jest niewiększy od indeksu <math>\; \rho, \;</math> a co za tym idzie, <math>\; M(L) = A^*/P_L \;</math> jest monoidem skończonym.
+Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm
+kanoniczny <center><math>k : A^* \longrightarrow A^*/P_L = M(L).</math></center> Pokażemy, że
+spełnia on warunki z punktu 4. twierdzenia 1.2 (patrz [[Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy#twierdzenie_1_2|twierdzenie 1.2.]]).  <math>M(L)
+\;</math> jest skończony, więc pozostaje do wykazania
+równość
+<center><math>\; L = k^{-1}(k(L)). \;</math></center> W tym celu wystarczy oczywiście udowodnić inkluzję
+<math>\; k^{-1}(k(L)) \subseteq L</math>. <br>
+<center><math>\begin{array} {c}
+v \in k^{-1}(k(L))\Rightarrow k(v) \in k(L)\Rightarrow\exists u \in L:k(v) = k(u) \in k(L)\Leftrightarrow\\
+\Leftrightarrow \exists u \in L:[v]_{P_L} = [u]_{P_L}\Leftrightarrow\exists u \in L:v \in L\Leftrightarrow u\in L.\\
+\end{array}
+</math></center>
+Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>.
+i tutaj twierdzenie jsadhfouvnhter zsdkjrvnhr SFj v
+|}
+{{twierdzenie|3.2.||
+Niech <math>L\subset A^{*} </math> będzie dowolnym językiem.
+:1. Dla dowolnego języka <math>L\in \mathcal{REC}(A^{*}) </math> monoid przejść automatu minimalnego <math>\mathcal{A}_{L} </math> jest izomorficzny z monoidem syntaktycznym <math> M(L) </math> języka <math>L</math>, czyli
+<center><math>M(\mathcal{A}_{L})\sim M(L). </math></center>
+:2. (tw. J.Myhill'a) Język <math>\; L \subset A^* \;</math> jest rozpoznawalny wtedy i tylko wtedy, gdy <math>\; M(L) \;</math> jest monoidem skończonym.
+}}
+{{dowod|||
+Dla dowodu punktu 1 wykażemy, że
+<center><math>P_{L}=Ker_{\tau
+_{\mathcal{A}_{L}}}, </math></center>
+gdzie zgodnie z definicją dla dowolnych <math>w,u\in A^{*} </math>
+<center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
+<center><math>\begin{array} {c}
+(u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
+\tau _{\mathcal{A}_{L}}(u)([v]_{P^{r}_{L}})=\tau _{\mathcal{A}_{L}}(w)([v]_{P^{r}_{L}})\Leftrightarrow
+[vu]_{P^{r}_{L}}=[vw]_{P^{r}_{L}}\Leftrightarrow\\
+\Leftrightarrow \forall v,z \in A^*\;\;vuz\in L\Leftrightarrow vwz\in L \Leftrightarrow[u]_{P_{L}}=[w]_{P_{L}}
+\Leftrightarrow (u,v) \in P_L.\\
+\end{array} </math></center>
+Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku
+ma postać:  <br>
+'''RYSUNEK ja-lekcja4-w-rys1.pdf'''<br>
+czyli <math>M(\mathcal{A}_{L})\sim M(L) </math>. <br>
+Dla dowodu punktu 2 załóżmy, że język <math>\; L \;</math> jest rozpoznawalny.
+Zatem
+<center><math>L = \bigcup_{w \in L} [w]_\rho ,</math></center> gdzie <math>\; \rho \;</math> jest kongruencją o skończonym indeksie.
+Z twierdzenia (patrz [[#twierdzenie_2_1|Twierdzenie 2.1.]]) wnioskujemy, że <math>\rho \subseteq P_L .</math> Oznacza to, że indeks relacji <math>\; P_L \;</math> jest niewiększy od indeksu <math>\; \rho, \;</math> a co za tym idzie, <math>\; M(L) = A^*/P_L \;</math> jest monoidem skończonym.
+Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm
+kanoniczny <center><math>k : A^* \longrightarrow A^*/P_L = M(L).</math></center> Pokażemy, że
+spełnia on warunki z punktu 4. twierdzenia 1.2 (patrz [[Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy#twierdzenie_1_2|twierdzenie 1.2.]]).  <math>M(L)
+\;</math> jest skończony, więc pozostaje do wykazania
+równość
+<center><math>\; L = k^{-1}(k(L)). \;</math></center> W tym celu wystarczy oczywiście udowodnić inkluzję
+<math>\; k^{-1}(k(L)) \subseteq L</math>. <br>
+<center><math>\begin{array} {c}
+v \in k^{-1}(k(L))\Rightarrow k(v) \in k(L)\Rightarrow\exists u \in L:k(v) = k(u) \in k(L)\Leftrightarrow\\
+\Leftrightarrow \exists u \in L:[v]_{P_L} = [u]_{P_L}\Leftrightarrow\exists u \in L:v \in L\Leftrightarrow u\in L.\\
+\end{array}
+</math></center>
+Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>.
+}}
 {| border="1" cellspacing="0"
 ! !! Złożoność czasowa !! Złożoność pamięciowa

Test GR2: Różnice pomiędzy wersjami

Wersja z 14:31, 15 sie 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1