Feladatok

1. Halmazok

1.1. Legalább, illetve legfeljebb hány eleme van egy m elemű és egy n elemű halmaz

– metszetének  – egyesítésének
– Descartes szorzatának  – különbségének?

1.2. Írjuk fel az A × B, A × C, C × B, (A × B) × C, és A × B × C halmazok elemeit, ha

A = {0, 1}, B = {1, 2, 3}, C = {p, q}! 1.3. Bizonyítsd be, hogy H ⊆ A × B esetén

– (∀(a, b), (c, d) ∈ H : (a, d) ∈ H) ⇔ (∃K ⊆ A : ∃L ⊆ B : H = K × L)

– ha H nem üres, akkor K és L egyértelmű!

2. Relációk

2.1. Az R ⊆ {1, 2, 3, 4, 5}×{1, 2, 3, 4, 5}. R = {(1, 2), (1, 4), (2, 1), (3, 4), (3, 3), (3, 5), (4, 5)}. a) Mi a reláció értelmezési tartománya és értékkészlete?

b) Determinisztikus-e, ill. függvény-e a reláció?

c) Mi R 0., 2., (−1). hatványa?

d) Mi a {4, 5} halmaz inverz képe, ill. ősképe?

e) Hány eleme van R értékkészlete hatványhalmazának? 2.2. Milyen összefüggés van egy H halmaz R relációra vonatkozó inverz képe és ősképe

között? És ha R függvény? 2.3. a) R ⊆ A × A. Mivel egyenlő R^{−1}(A)?

b) Megadható-e valamilyen összefüggés egy H halmaz inverz képének képe, és a H halmaz között?

c) Megadható-e valamilyen összefüggés egy H halmaz ősképe képe és a H halmaz között?

2.4. a) R = {((x, y), (x + y, y)) | x, y ∈ ℕ}. Mi a H = {(a, b)|a, b ∈ ℕ ∧ a + b < 5} halmaz inverz képe, ill. ősképe?

b) R = {((x, y), (x + y, y)) | x, y ∈ ℕ} ∪ {((x, y), (x − y, y))|x, y ∈ ℕ}. Mi a H = {(a, b) | a, b ∈ ℕ ∧ a + b < 5} halmaz inverz képe, ill. ősképe?

2.5. R = {((x, y), (f(x, y), y)) | x, y ∈ ℕ}, ahol f : ℕ × ℕ → ℕ.

Mi a H = {(a, b) | a, b ∈ ℕ ∧ a + b < 5} halmaz ősképe ill. inverz képe? 2.6. R ⊆ A × B, Q ⊆ B. Van-e valamilyen összefüggés az R^{−1}(B \ Q) halmaz és az A \

(R^{−1}(Q)) halmaz között? 2.7. Készíts olyan nem üres relációt, amelyre igaz, hogy értékkészlete minden valódi rész-

halmazának ősképe üres halmaz! 2.8. R ⊆ A × B, P, Q ⊆ B. Hogyan lehetne jellemezni az R^{−1}(P ∪ Q) és az R^{−1}(P ∩ Q)

halmazt az R^{−1}(P) és R^{−1}(Q) halmaz segítségével?

2.9. Legyen F, G ⊆ ℕ × ℕ, Y = {1, 2}. F = {(a, b) | b|a ∧ b ≠ 1 ∧ b ≠ a}. G = {(a, b) | 2|a ∧ a = 2 ∗ b}.

\begin{matrix}G ∘ F = ? & G ⊙ F = ? \\ F^{(−1)} ∘ G^{(−1)} = ? & F^{−1} ∘ G^{−1}(Y) = ? \\ (G ∘ F)^{−1}(Y) = ? & (G ∘ F)^{(−1)} = ? \end{matrix}

2.10. F ⊆ A × B, G ⊆ B × C. Igaz-e, hogy a) (G ∘ F)^{(−1)} = F^{(−1)} ∘ G^{(−1)}

b) ∀Y ⊆ C : (G ∘ F)^{−1}(Y) = F^{−1} ∘ G^{−1}(Y)

c) (G ⊙ F)^{(−1)} = F^{(−1)} ⊙ G^{(−1)}

d) ∀Y ⊆ C : (G ⊙ F)^{−1}(Y) = F^{−1} ⊙ G^{−1}(Y) Igazak-e az a)–d) állítások, ha G vagy F függvény?

2.11. Mi az összefüggés két reláció kompozíciójának értelmezési tartománya és ugyanezen

két reláció szigorú értelemben vett kompozíciójának értelmezési tartománya között? 2.12. Legyen R a 2.1. feladatban adott reláció. f ⊆ A×L. f = {(1, i), (2, i), (3, i), (4, h), (5, i)}.

Mi f, ill. (f ∘ R) igazsághalmaza? 2.13. Készíts olyan nem üres R relációt és f logikai függvényt, hogy f ∘ R igazsághalmaza

üres legyen! 2.14. R, Q ⊆ A × A. Igaz-e, hogy (R ⊙ Q)^{(−1)} = Q^{(−1)} ∘ R^{(−1)}? 2.15. R ⊆ A × A. Igaz-e, hogy (R^{(−1)})^{2} = (R^{2})^{(−1)}? 2.16. R ⊆ A × A. Igaz-e, hogy ∀H ⊆ A : R^{−1}(R^{−1}(H)) = (R^{2})^{−1}(H)? 2.17. P, Q ⊆ ℕ × ℕ. Q = {(a, b) | 2|a ∧ b|a ∧ prim(b)}.

a) P = {(a, b) | b|a ∧ b ≠ 1 ∧ b ≠ a}

b) P = {(a, b) | b|a}

Add meg a Q^{(−1)}, Q ∘ P és Q ⊙ P -t relációt! 2.18. H ⊆ A × B, G ⊆ B × C, F ⊆ C × D. Igazak-e az alábbi állítások?

a) Ha a ∈ D_{(G∘H)} ∩ D_{(G⊙H)}, akkor G ∘ H(a) = G ⊙ H(a).

b) D_{(G⊙H)} ⊆ D_{(G∘H)}.

c) (∀a ∈ D_{H} | |H(a)| = 1) ⇒ G ∘ H = G ⊙ H.

d) D_{G} = B ⇒ G ∘ H = G ⊙ H.

e) Asszociativitás:

\begin{aligned}(F ∘ G) ∘ H & = F ∘ (G ∘ H) \\ (F ⊙ G) ⊙ H & = F ⊙ (G ⊙ H) \end{aligned}

f) Q, R, S ⊆ A × A. Q ∘ R ⊆ S ⟺ Q^{(−1)} ∘ S̃ ⊆ R̃
g) Q, R, S ⊆ A × A. Q ⊙ R ⊆ S ⟺ Q^{(−1)} ⊙ S̃ ⊆ R̃
h) R ≠ ∅ ⇒ L ⊙ R ⊙ L = L, ahol L = A × A

i) Monotonitás:

\begin{aligned}R ⊆ S & ⇒ R ⊙ Q ⊆ S ⊙ Q \\ R ⊆ S & ⇒ Q ⊙ R ⊆ Q ⊙ S \end{aligned}

2.19. Legyen R és Q két reláció a természetes számok halmazán! R egy természetes számhoz rendeli önmagát és a kétszeresét, Q egy páros természetes számhoz a felét.

a) Írd fel a két relációt, és add meg az értelmezési tartományukat!

b) Írd fel az R reláció k. hatványát (k ≥ 1) és ennek az értelmezési tartományát!

c) Írd fel a Q ∘ R relációt és az értelmezési tartományát!

d) F = Q ⊙ R! Írd fel az F relációt és az értelmezési tartományát! 2.20. F ⊆ A × B, G ⊆ B × C. Igaz-e, hogy:

a) D_{(G⊙F)} = F^{−1}(D_{G})

b) D_{(G∘F)} = F^{−1}(D_{G})

3. Reláció lezártja

3.1. R ⊆ {1, 2, 3, 4, 5}×{1, 2, 3, 4, 5}. R = {(1, 2), (1, 4), (2, 1), (3, 4), (3, 3), (3, 5), (4, 5)}. Mi

lesz R lezártja és korlátos lezártja? 3.2. P ⊆ ℕ_{0} × ℕ_{0}. P = {(a, b) | b|a ∧ b ≠ 1 ∧ b ≠ a}. Mi lesz P lezártja? 3.3. Mutassunk példát olyan relációra, aminek lezártja és korlátos lezártja különböző! 3.4. P ⊆ Z × Z.

P (a) = \{ \begin{matrix}\{a − 1\}, & ha a > 0 \\ \{b|b ∈ ℕ\}, & ha a < 0 \end{matrix}

Mi P lezártja és korlátos lezártja? 3.5. A = {1, 2, 3, 4, 5}, R ⊆ A × A. R = {(1, 2), (1, 5), (2, 5), (3, 2), (3, 4), (5, 2)}.

[π] = {1, 2, 3, 4}. Írjuk fel a reláció feltételre vonatkozó lezártját! 3.6. R ⊆ ℕ × ℕ. R = {(a, b) | b|a ∧ b ≠ 1 ∧ b ≠ a}. [π] = {x | x kettőhatvány }. Írjuk fel

az R|_{π} relációt, lezártját és korlátos lezártját! 3.7. Adjunk példát olyan nem üres relációra, amelynek lezártja üres halmaz és van olyan

π feltétel, hogy a reláció feltételre vonatkozó lezártjának értelmezési tartománya megegyezik az eredeti reláció értelmezési tartományával!

3.8. R ⊆ A × A. Tegyük fel, hogy az R értelmezési tartománya egyenlő az R értelmezési

tartományának R-re vonatkozó ősképével. Mit mondhatunk R lezártjáról? 3.9. Van-e olyan nem üres reláció és π feltétel, hogy a reláció lezártja üres halmaz, és a π

feltételre vonatkozó lezártja azonos a relációval? 3.10. R ⊆ ℕ_{0} × ℕ_{0}.

R(a) = \{ \begin{matrix}\{a − 2\}, & ha a > 1 \\ \{2^{k} | k ∈ ℕ\}, & ha a = 1 \end{matrix}

Mi az R reláció lezártja és korlátos lezártja?

3.11. R ⊆ ℕ_{0} × ℕ_{0}.

R(a) = \{ \begin{matrix}\{a − 3\}, & ha a > 2 \\ \{3 ∗ k | k ∈ ℕ\}, & ha a = 1 \end{matrix}

Mi az R reláció lezártja és korlátos lezártja? 3.12. R ⊆ ℕ × ℕ. Az R reláció minden összetett számhoz a legnagyobb valódi osztóját

rendeli. Legyen q

a) egy rögzített összetett természetes szám!

b) egy rögzített prímszám! Legyen P_{q}(a) = (∃k ∈ ℕ | a = q^{k})! Mi lesz az R reláció P_{q} feltételre vonatkozó lezártjának értelmezési tartománya?

3.13. R ⊆ ℕ_{0} × ℕ_{0}.

R(x) = \{ \begin{matrix}\{b | ∃k ∈ ℕ_{0} : b = 2 ∗ k + 1\}, & ha x ≠ 0 ∧ x páros \\ \{x − 7\}, & ha x ≥ 7 ∧ x páratlan \\ \{0\}, & ha x = 1 \\ \{7\}, & ha x = 0 \end{matrix}

Mi lesz R lezártja és korlátos lezártja? 3.14. R legyen a 3.11. feladatban adott reláció. π(k) = (k páratlan szám). Add meg az R|_{π}

relációt, lezártját és korlátos lezártját! 3.15. Igazak-e az alábbi állítások?

a) Ha a ∈ D\overline{R} ∩ D\overline{\overline{R}}, akkor \overline{R}(a) = \overline{\overline{R}}(a).

b) D\overline{\overline{R}} ⊆ D\overline{R}.

* c) Ha az A halmaz véges és R ⊆ A × A, akkor \overline{R} = \overline{\overline{R}}. ** d) Ha A megszámlálhatóan végtelen, R ⊆ A × A, és

∀a ∈ A : (∃n(a) ∈ ℕ_{0} : |R(a)| ≤ n(a)) ⇒ \overline{R} = \overline{\overline{R}}.

3.16. Legyen R ⊆ ℕ_{0} × ℕ_{0}, R értelmezési tartománya ℕ!

R(x) = \{ \begin{matrix}\{b|b > 0 ∧ b < x ∧ 2|b\}, & ha x páratlan \\ \{x − 1\}, & ha x páros \end{matrix}

π(x) = (x páros természetes szám). Mi az R reláció π feltételre vonatkozó lezártja és korlátos lezártja?

4. Projekció, redukált

4.1. W = N_{1} × N_{2} × N_{3}. α ∈ W^{∗∗}, ahol N_{i} = ℕ (i = 1, 2, 3). α_{1} = (1, 1, 1). Az α sorozat további elemeit úgy kapjuk meg, hogy a pontok koordinátáit az első koordinátával kezdve ciklikusan 1-gyel növeljük. pr_{N_{1}×N_{3}}(red(α)) =?

4.2. Legfeljebb ill. legalább milyen hosszú egy m és egy n hosszúságú sorozat redukáltjának konkatenációja, ill. konkatenációjának redukáltja?

4.3. Igaz-e, hogy egy α sorozat redukáltjának projekciója ugyanolyan hosszú, mint az α

sorozat redukáltja? 4.4. Igaz-e, hogy egy α sorozat projekciójának redukáltja ugyanolyan hosszú, mint az α

sorozat redukáltja? 4.5. Legyen A = N_{1} × N_{2} × N_{3} × N_{4}, B = N_{4} × N_{1}, ahol ∀i ∈ [1, 4] : N_{i} = ℕ.

α =< (1, 1, 1, 1), (1, 2, 1, 1), (1, 2, 3, 1), (1, 2, 3, 4), (5, 2, 3, 4), (5, 7, 3, 4), (5, 7, 10, 4),… >.

a) pr_{B}(α) =?

b) red(pr_{B}(α)) =?

5. Feladat, program, programfüggvény, megoldás

5.1. A_{1} = {1, 2}, A_{2} = {1, 2}, A_{3} = {1, 2, 3, 4, 5}. A = A_{1} × A_{2} × A_{3}.

F = {(a, b, c) | c = a + b}. Miért hibás az F feladat leírása? 5.2. A_{1} = {1, 2}, A_{2} = {1, 2}, A_{3} = {1, 2, 3, 4, 5}, A = A_{1} × A_{2} × A_{3}.

F = {((a, b, c), (d, e, f)) | f = a + b}. F (1, 1, 1) =? Hány olyan pontja van az állapottérnek, amelyekhez a feladat ugyanazokat a pontokat rendeli, mint (1, 1, 1)-hez?

5.3. Helyes-e a következő meghatározás? Az S ⊆ A × A^{∗∗} reláció program, ha 1. ha α ∈ R_{S}, akkor α egyenlő a redukáltjával,

2. S értelmezési tartománya A,

3. ha α az állapottér egy a pontjához rendelt sorozat, akkor α első eleme a. 5.4. Legyen A = {1, 2, 3, 4, 5}, S ⊆ A × A^{∗∗}.

S = { 1→ 1251 1→ 14352  1→ 132 … 2→ 21
2→ 24  3→ 333333 … 4→ 41514 4→ 431251
4→ 41542 5→ 524 5→ 534 5→ 5234}

F = {(2, 1) (4, 4) (4, 1) (4, 2) (4, 5)}.

a) Adjuk meg p(S)-t!

b) Megoldja-e S a feladatot? 5.5. Legyen S program, F olyan feladat, hogy S megoldása F -nek. Igaz-e, hogy

a) ha F nem determinisztikus, akkor S sem az?

b) ha F determinisztikus, akkor S is az?

c) ha F nem determinisztikus, akkor p(S) sem az?

d) ha p(S) determinisztikus, akkor F is az?

e) ha F determinisztikus, akkor p(S) is az?

f) ha S nem determinisztikus, akkor p(S) sem az? 5.6. Igaz-e, hogy programok uniójának programfüggvénye megegyezik a programfüggvé-

nyek uniójával? 5.7. Fejezzük ki a programok uniójának programfüggvényét a programok programfüggvé-

nyeivel!

5.8. S ⊆ A × A^{∗∗}. Igaz-e, hogy p(S) = {(a, b) ∈ A × A | ∃α ∈ A^{∗} : (a, α) ∈ S ∧ b = τ(α)}? 5.9. Legyen F_{1} és F_{2} egy–egy feladat ugyanazon az állapottéren! Igaz-e, ha minden prog-

ram, ami megoldása F_{1}-nek, az megoldása F_{2}-nek is, és minden program, ami megoldása F_{2}-nek, az megoldása F_{1}-nek is, akkor F_{1} és F_{2} megegyeznek?

5.10. Igaz-e, hogy p(S) értelmezési tartománya éppen A^{∗} ősképe S-re nézve? 5.11. Mondhatjuk-e, hogy az S program megoldja az F feladatot, ha igaz a következő állítás:

q ∈ D_{F} ⇒ S(q) ⊆ A^{∗} ∧ p(S)(q) ⊆ F (q). 5.12. F_{1} ⊆ F_{2}. Az S program megoldja F_{2}-t. Igaz-e, hogy S megoldja F_{1}-et is? 5.13. S_{1} ⊆ S_{2}. S_{2} megoldja az F feladatot. Igaz-e, hogy S_{1} megoldja F -et? 5.14. A = ℕ × ℕ, F_{1} = {((u, v), (x, y)) | y|u}, F_{2} = {((u, v), (x, y)) | x = u ∧ y|u}. Ekviva-

lens-e a két feladat? (Van-e valamilyen összefüggés közöttük?) 5.15. F ⊆ A × A. S_{1}, S_{2} programok A-n. Az S_{1} és az S_{2} is megoldja az F feladatot. Igaz-e,

hogy az S = (S_{1} ∪ S_{2}) program is megoldja az F feladatot? 5.16. Legyen F a 2.19.-es feladat d) pontjának relációja! S ⊆ ℕ × ℕ^{∗∗}.

S ={(a, < aaa… >) | a ≡ 1 mod(4)} ∪ {(b, < b >), (b, < b, b/2 >) | b ≡ 2 mod(4)}
∪{(c, < c, 2 ∗ c >) | c ≡ 3 mod(4)} ∪ {(d, < d, d/2 >) | d ≡ 0 mod(4)}

Add meg p(S) értelmezési tartományát! Megoldja-e S az F feladatot? 5.17. Tekintsük a következő szövegesen megadott feladatot: Adott egy sakktábla, és két

rajta lévő bástya helyzete. Helyezzünk el a táblán egy harmadik bástyát úgy, hogy az mindkettőnek az ütésében álljon! Készítsük el a modellt: írjuk fel az állapotteret és az F relációt!

5.18. Tudjuk, hogy S megoldja F -et (az A állapottéren).

Igaz-e, hogy (a ∈ A ∧ (S(a) ⊈ A^{∗} ∨ p(S)(a) ⊈ F (a))) ⇒ a ∉ D_{F}? 5.19. Legyen F ⊆ A × A egy feladat és S ⊆ A × A^{∗∗} egy program. Jelöljük F P -vel azt a

relációt, amely F és p(S) metszeteként áll elő. Igaz-e, hogy

a) ha D_{F P} = D_{F}, akkor S megoldja F -et?

b) ha S megoldja F -et, akkor D_{F P} = D_{F}?

6. Feladat és program kiterjesztése

6.1. a) B = {1, 2, 3} × {1, 2, 3}, A = {1, 2, 3}. F ⊆ A × A. F = {(1, 2), (1, 3)}. Mi az F kiterjesztettje B × B-re?

b) A = ℕ, B = ℕ × ℕ. F ⊆ A × A.F = {(q, q + 1) | q ∈ ℕ}. Mi az F kiterjesztettje B-re?

c) Adott az L × L állapottéren az F = {((l, k), (l′, k′)) | k′ = (l ∧ k)} feladat, és az A′ = L × L × V állapottéren (V = {1, 2}) a következő program:

S = { ii1 → ii1, ih2, hi2  ii2 → ii2, hh1, ii1
ii2 → ii2, ih2, hi1, hi2 ih1 → ih1
ih2 → ih2, ii1, hh1  hi1 → hi1, hh2
hi2 → hi2, hi1, ih1  hi2 → hi2, hh1, hh2
hh1→ hh1, ih1  hh2→ hh2}

Megoldja-e S az F A′-re való kiterjesztettjét? 6.2. A = A_{1} × A_{2} ×… × A_{n}. Mondjunk példát olyan programra, amelynek egyetlen valódi

altérre vett projekciója sem program. (A_{k} = ℕ, k = 1,…, n). 6.3. Igaz-e?

a) ha F = pr_{A×A}(F′′), akkor F′′ az F kiterjesztettje?

b) F′ = pr_{A×A}^{(−1)}(F) ? ill. F′ = pr_{A×A}^{−1}(F) ? 6.4. Legyen F ⊆ A × A, F′ ⊆ B × B, F′′ ⊆ C × C, F′′′ ⊆ D × D, ahol B = A × A_{1},

C = A × A_{2}, D = A × A_{1} × A_{2}, és legyen F′, F′′, F′′′ az F kiterjesztése rendre B × B, C × C, D × D-re. Igaz-e, hogy F′′′ az F′′ kiterjesztése D × D-re? Add meg az F′ és az F′′ közötti kapcsolatot a projekció és a kiterjesztés fogalmának segítségével!

6.5. Igaz-e, ha S ⊆ B × B, A altere B-nek, akkor a) D_{pr_{A×A}(p(S))} = pr_{A}(D_{p(S)})?

b) S A × A-ra történő projekciójának kiterjesztése B × B-re azonos S-sel? 6.6. Megfordíthatóak-e a kiterjesztési tételek? Azaz, igaz-e, hogy

a) ha S megoldja az F feladatot, akkor S_{1} megoldja F′-t? (ahol S_{1} ⊆ A × A^{∗∗} ekvivalens S ⊆ B × B^{∗∗}-gal A alterén, B-n, és F′ az F ⊆ B × B kiterjesztése A × A-ra)

b) ha S megoldja a G feladat B × B-re vett projekcióját, G_{1}-et, akkor S′ megoldja

G-t? (ahol S′ az S kiterjesztése)

6.7. B és C altere A-nak. F ⊆ A × A, F_{1} ⊆ B × B, F_{2} ⊆ C × C. F_{1} az F projekciója B-re. F az F_{2} kiterjesztése A-ra. Igaz-e, hogy az F_{1} feladat A-ra való kiterjesztettjének C-re vett projekciója megegyezik F_{2}-vel?

7. Vegyes feladatok

7.1. Keressük meg egy természetes szám egy osztóját!

A = ℕ, F = {(u, v) ∈ ℕ × ℕ | v osztója u-nak}. S_{1} = {(a, < a, 1 >) ∈ A × a^{∗∗} | a > 1} ∪ {(1, < 1 >)} S_{2} = {(1, < 1 >), (2, < 2, 1, 2 >)} ∪ {(a, α) ∈ A × A^{∗∗} | α_{1} = a ∧ τ(α) = (a legkisebb 1-nél nagyobb osztója )}.

a) Megoldja-e S_{1} ill. S_{2} a feladatot?

b) Ekvivalens-e S_{1} és S_{2}? 7.2. Számítsuk ki a (−1)^{i} függvény értékeinek összegét az [m, n] intervallumon

(m, n ∈ ℕ)!

A = ℕ × ℕ × Z, A_{1} = A × L, F ⊆ A × A, F′ az F kiterjesztése A_{1} × A_{1}-re. S_{1}, S_{2} ⊆ A × A^{∗∗}, S_{3} ⊆ A_{1} × A_{1}^{∗∗}.

F = {((m, n, b), (m_{1}, n_{1}, b_{1})) | b_{1} = ∑_{m}^{n} (−1)^{i} ∧ m ≤ n}.

S_{1} ={(m, n, x) → ((m, n, x), (m, n, (−1)^{m}), (m, n, (−1)^{m} + (−1)^{m+1}),…

…, (m, n, (−1)^{m} + … + (−1)^{n}))}

S_{2} ={(m, n, x) → ((m, n, x), (m, n, ((−1)^{m} + (−1)^{n})/2)
S_{3} ={(m, n, x, l) → ((m, n, x, l), (m, n, f(m, p(m) = p(n)), p(m) = p(n)))

p(m) = \{ \begin{matrix}0, & ha m páros \\ 1, & különben \end{matrix} f(m, l) = \{ \begin{matrix}(−1)^{m}, & ha l \\ 0, & különben \end{matrix}

a) Megoldja-e S_{1} és S_{2} F -et?

b) Megoldja-e S_{3} F′-t?

c) Mely programok ekvivalensek A-n? 7.3. A = ℕ × ℕ × ℕ. S ⊆ A × A^{∗∗}.S az (1,1,2) pontból kiindulva előállítja a 10. Fibonacci

számot az u(n) = u(n − 1) + u(n − 2) rekurzív összefüggés alapján. A koordináták rendre u(n − 2)-nek, u(n − 1)-nek, u(n)-nek felelnek meg. Írd fel azt a sorozatot, amelyet S az (1,1,2) ponthoz rendel! Mit rendel p(S) az (1,1,2) ponthoz?

7.4. Számítsuk ki egy valós szám természetes kitevőjű hatványát!

A = R × ℕ_{0} × R, F ⊆ A × A. F = {((x, n, k), (y, z, x^{n})) | k = 1}. S_{1}, S_{2} ⊆ A × A^{∗∗}

S_{1}((x, n, h)) ={< (x, n, h), (x, n − 1, h ∗ x),…, (x, 0, h ∗ x^{n}) >}
S_{2}((x, n, h)) ={< (a_{1}),…, (a_{m}) > | (a_{1}) = (x, n, h) ∧ Legendre(a_{m}) = ∅∧
∀i ∈ (1, n] : (Legendre(a_{i−1}) ≠ ∅ ∧ (a_{i}) ∈ Legendre(a_{i−1}))}

ahol Legendre ⊆ A × A

Legendre(x, n, h) = \{ \begin{matrix}(x^{2}, n/2, h), & ha 2|n ∧ n ≠ 0 \\ (x, n − 1, x ∗ h), & ha ¬(2|n) ∧ n ≠ 0 \end{matrix}

. Megoldja-e S_{1} ill. S_{2} az F feladatot? Ekvivalensek-e A-n? Van-e olyan altere A-nak, ahol S_{1} és S_{2} ekvivalens?

8. Leggyengébb előfeltétel

8.1. Tekintsük az 5.4. feladatban adott programot! [R] = {1, 2, 5}. Írd fel az [lf(S, R)] halmazt!

8.2. Mivel egyenlő lf(S, igaz) ill. lf(S, hamis)? 8.3. Igaz-e, ha ∀i ∈ ℕ: Q(i) ⇒ Q(i + 1), akkor

* (∃n ∈ ℕ : lf(S, Q(n))) = lf(S, (∃n ∈ ℕ : Q(n)))? 8.4. Igaz-e, hogy lf(S_{1}, R) = lf(S_{2}, R) ⟺ lf(S_{1} ∪ S_{2}, R) = lf(S_{1}, R) ∨ lf(S_{2}, R)? 8.5. Igaz-e, ha ∀y, x ∈ A : x ∈ [lf(S_{1}, P ({y}))] ⇔ x ∈ [lf(S_{2}, P ({y}))], akkor

D_{p(S_{1})} = D_{p(S_{2})}? (P ({y}) az az állítás, amelynek igazsághalmaza {y}) 8.6. [H_{1}], [H_{2}] ⊆ A. Igaz-e, ha minden S ⊆ A × A^{∗∗} programra [lf(S, H_{1})] = [lf(S, H_{2})],

akkor [H_{1}] = [H_{2}]? 8.7. S_{1}, S_{2} ⊆ A × A^{∗∗} programok. Igaz-e, ha ∀[H] ⊆ A : [lf(S_{1}, H)] = [lf(S_{2}, H)], akkor

S_{1} ekvivalens S_{2}-vel? 8.8. Milyen összefüggés van lf(S, igaz ∧ (¬R)) és (igaz ∧(¬lf(S, R))) között? 8.9. Igaz-e, hogy [lf(S, R)] = p(S)^{−1}([R])? 8.10. A = ℕ. Legyen S az 5.16. feladat programja! H(x) = (x páros szám). [lf(S, H)] =?

9. Típus

9.1. Adjunk típusspecifikációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) a következő típusra: a lehetséges értékek: [0, 99999]. A műveletek a következő és az előző 100000 szerinti maradékkal. Az elemi értékek a decimális számjegyek {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Mutasd meg, hogy a típus megfelel a típusspecifikációnak!

9.2. A típusértékek halmaza legyen a magyar abc magánhangzói! { a, á, e, é, i, í, o, ó, ö, ő, u, ú, ü, ű }. Szeretnénk tudni, hogy egy adott magánhangzónak melyik a (rövid ill. hosszú) párja. Legyen egy olyan típusműveletünk, amely erre a kérdésre választ tud adni. Az elemi típusértékek halmaza legyen a {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} halmaz! Add meg a típusspecifikációt és készíts el egy olyan típust, ami megfelel a specifikációnak!

9.3. E = {0, 1, 2}, T_{S} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, 𝔽 = {F }.

F = {((a, b, c), (d, e, f)) | f + k ∗ 10 = a + b és k egész }. Készíts el egy olyan típust, ami megfelel a specifikációnak!

9.4. Legyen T_{S} = (T, I_{S}, 𝔽) egy típusspecifikáció. 𝔽 = {F }.

T_{1} = (ϱ_{1}, I_{1}, 𝕊_{1}) és T_{2} = (ϱ_{2}, I_{2}, 𝕊_{2}). 𝕊_{1} = {S_{1}}, 𝕊_{2} = {S_{2}}, ϱ_{1} = ϱ_{2}, [I_{1}] = [I_{2}], és S_{2} ⊆ S_{1}. Igaz-e, ha T_{1} megfelel T_{S}-nek, akkor T_{2} is?

9.5. Legyen T_{S_{1}} = (T_{1}, I_{S_{1}}, 𝔽_{1}), T_{S_{2}} = (T_{2}, I_{S_{2}}, 𝔽_{2}) két típusspecifikáció!

1. állítás: Minden T típusra: T megfelel T_{S_{1}}-nek ⇔ T megfelel T_{S_{2}}-nek .

2. állítás: [I_{S_{1}}] = [I_{S_{2}}] és 𝔽_{1} = 𝔽_{2}. Ekvivalens-e a két állítás?

9.6. Legyen T_{S} = (T, I_{S}, 𝔽) egy típusspecifikáció. T_{1} = (ϱ_{1}, I_{1}, 𝕊_{1}) és T_{2} = (ϱ_{2}, I_{2}, 𝕊_{2}).

a) Legyen [I_{1}] = [I_{2}], 𝕊_{1} = 𝕊_{2} és ϱ_{1}([I_{1}]) = ϱ_{2}([I_{2}]) és ∀α ∈ E^{∗} : ϱ_{2}(α) ⊆ ϱ_{1}(α), valamint T_{1} feleljen meg T_{S}-nek! b) Legyen [I_{2}] ⊆ [I_{1}], 𝕊_{1} = 𝕊_{2} és ϱ_{1}([I_{1}]) = ϱ_{2}([I_{2}]), és ∀α ∈ E^{∗} : ϱ_{2}(α) = ϱ_{1}(α),

valamint T_{1} feleljen meg T_{S}-nek! Igaz-e, hogy T_{2} is megfelel T_{S}-nek?

9.7. Legyen T_{S} = (T, I_{S}, 𝔽) a következő típusspecifikáció:

I_{S} ≡ igaz, T = ℕ_{0}, 𝔽 = {F_{1}, F_{2}}. F_{1} specifikációja:

A = {ℕ_{0} \atop x}  B = {ℕ_{0} \atop x′}  Q_{x′} = (x = x′)
R_{x′} = (∃z ∈ ℤ : x′ = 8 ∗ z + x ∧ 0 ≤ x < 8)

F_{2} specifikációja:

A = {ℕ_{0} \atop x} × {ℕ_{0} \atop y} × 𝕃 l B = {ℕ_{0} \atop x′} × {ℕ_{0} \atop y′}

Q_{x′,y′} = (x = x′ ∧ y = y′)

R_{x′,y′} = (l = (x′ = y′) ∧ x = x′ ∧ y = y′)

T = (ϱ, I, 𝕊), E = {0, 1, 2, 3, 4, 5, 6, 7}, ∀e ∈ E^{∗} : ϱ(e) = ∑_{i=1}^{|e|}(e_{i} ∗ 8^{|e|})

a) I(e) = (|e| ≥ 1 ∧ (e_{1} = 0 → |e| = 1))

b) I(e) = (|e| ≥ 1)

S_{1} ⊆ (E^{∗}) × (E^{∗})^{∗∗}

\begin{matrix}∀e ∈ E^{∗} : S_{1}(e) = & \{α ∈ (E^{∗})^{∗} | |α| = |e| ∧ ∀i ∈ [1, |α|] : |α_{i}| = |α| − i + 1∧ \\ ∀i ∈ [2, |α|] : ∀j ∈ [1, |α_{i}|]α_{i_{j}} = α_{i−1_{j+1}})\} \end{matrix}

S_{2} ⊆ (E^{∗} × E^{∗} × 𝕃) × (E^{∗} × E^{∗} × 𝕃)^{∗∗} ∀e, d ∈ E^{∗} : ∀l ∈ 𝕃

S_{2}(e, d, l) ={β ∈ (E^{∗})^{∗} | |β| = min(|e|, |d|) + 1 ∧ ∀i ∈ [2, |β|] : β_{i} = (ee, dd, ll)∧
ll = (∀j ∈ [1, i − 1] : ee_{j} = dd_{j}) ∧ |ee| = i − 1 ∧ |dd| = i − 1)∧
∀j ∈ [1, i − 1] : (ee_{i−j} = e_{|e|−j+1} ∧ dd_{i−j} = d_{|d|−j+1}))}

Írd le szavakkal az F_{1}, F_{2} feladatot, a ϱ relációt, és az S_{1}, S_{2} programfüggvényét! Megfelel-e a típus a specifikációnak az a) ill. a b) esetben?

9.8. Specifikáld azt a típust, melynek értékei egy 128 elemű halmaz részhalmazai, típusműveletei pedig két rész halmaz metszetének ill. uniójának képzése, ill. annak megállapítása, hogy egy elem eleme-e egy részhalmaznak. Adj meg egy típust, amely megfelel a specifikációnak! (Az elemi típus a bit típus.)

10. Paramétertér, specifikáció

10.1. Adott az A = V × V × 𝕃 állapottér (V = {1, 2, 3}) és a B = V × V paramétertér, továbbá az F_{1} és F_{2} feladatok. F_{1} = {((a_{1}, a_{2}, l), (b_{1}, b_{2}, k)) | k = (a_{1} > a_{2})} F_{2} specifikációja:

A = {V \atop a_{1}} × {V \atop a_{2}} × 𝕃 l B = {V \atop a′_{1}} × {V \atop a′_{2}}

Q_{a′_{1},a′_{2}} = (a_{1} = a′_{1} ∧ a_{2} = a′_{2}) R_{a′_{1},a′_{2}} = (Q_{a′_{1},a′_{2}} ∧ l = (a′_{1} > a′_{2}))

Azonosak-e az F_{1} és F_{2} feladatok!

10.2. A = ℤ x × ℤ y B = {ℤ \atop x′}

F_{1}, F_{2} ⊆ A × A F_{1} : Q_{x′} = (x = x′)

R_{x′} = (Q_{x′} ∧ x = |y ∗ y|). F_{2} = {((a, b), (c, d)) | c = a ∧ |d| ∗ d = c}. Megadható-e valamilyen összefüggés F_{1} és F_{2} között?

10.3. Írd le szövegesen az alábbi feladatot:

A = V x × ℕ l B = V x V = vekt([1, n], ℤ)

Q_{x′} = (x = x′)

R_{x′} = (x = x′ ∧ l = ∑_{i=1}^{n}(g(x′, i)))

ahol g : V × [1, n] → {0, 1}

g(x′, i) = \{ \begin{matrix}1 & ha ∃m ∈ ℤ : (x′(i) = m ∧ ∀j ∈ [1, n] : a(j) ≤ m) \\ 0, & egyébként \end{matrix}

10.4. Specifikáljuk a következő feladatot:

A = 𝕃 × 𝕃, F ⊆ A × A, F = {((l, k), (l′, k′)) | k′ = k ∧ l′ = (l ∧ k)} 10.5. Igaz-e a specifikáció tételének megfordítása?

(Ha S megoldja F -et, akkor ∀b ∈ B : Q_{b} ⇒ lf(S, R_{b}))

10.6. A = ℤ k × ℤ p B = {ℤ \atop k′}

Q_{k′} = (k = k′ ∧ 0 < k) R_{k′} = (k = k′ ∧ prim(p) ∧ ∀i > 1 : prim(i) ⇒ |k − i| ≥ |k − p|)

ahol prim(x) = (x prímszám). Mit rendel a fent specifikált feladat az a = (10, 1) és a b = (9, 5) pontokhoz? Fogalmazd meg szavakban a feladatot!

10.7. A = ℕ x × ℕ y × ℕ z B = {ℕ \atop x′} × {ℕ \atop y′}

F_{1}, F_{2} ⊆ A × A F_{1} specifikációja:

Q_{x′,y′} = (x = x′ ∧ y = y′)

R_{x′,y′} = (x = x′ ∧ y = y′ ∧ x′|z ∧ y′|z ∧ ∀j ∈ ℕ : (x′|j ∧ y′|j) ⇒ z|j) F_{2} = {((a, b, c), (d, e, f)) | a = d ∧ b = e ∧ f|a ∗ b ∧ a|f ∧ b|f} Megadható-e valamilyen összefüggés F_{1} és F_{2} között?

10.8. Adott egy f : ℤ → ℤ függvény.

A = ℤ m × ℤ n × ℤ i B = {ℤ \atop m′} × {ℤ \atop n′}

F_{1}, F_{2} ⊆ A × A F_{1} specifikációja:

Q_{m′,n′} =(m = m′ ∧ n = n′)
R_{m′,n′} =(m = m′ ∧ n = n′ ∧ i ∈ [m, n] ∧ ∀j ∈ [m, i) : f(j) < f(i)∧
∀j ∈ [i, n] : f(j) ≤ f(i))

F_{2} specifikációja:

Q_{m′,n′} = (m = m′ ∧ n = n′)

R_{m′,n′} = (i ∈ [m′, n′] ∧ ∀j ∈ [m′, n′] : f(j) ≤ f(i)).

Azonos-e a két feladat? 10.9. Specifikáljuk a következő feladatot: A = V × ℕ V = vekt([1, n] : {0, 1}).

F ⊆ A × A, F = {((v, s), (v′, s′)) | v′ = v ∧ s′ = ∑_{k=1}^{n} v(k)}

10.10. Írd le szövegesen az alábbi feladatot:

A = V x B = {V \atop x′} V = vekt([1, n] : ℤ)

Q_{x′} = (x = x′) R_{x′} = (∀i, j ∈ [1, n] : (i < j ⇒ x(i) ≤ x(j)) ∧ x ∈ perm(x′))

ahol perm(x′) az x′ vektor permutációinak a halmaza.

11. Elemi programok

11.1. A = {1, 2, 3}, B = {a, b}, C = A × B.

Legyen S program A-n, S = {1 →< 1 >, 2 →< 2222 … >, 3 →< 31 >}. Legyen S_{1} az S kiterjesztése C-re, M pedig olyan program C-n, hogy M ekvivalens S-sel A-n.

a) elemi program-e S?

b) elemi program-e S_{1} és biztosan elemi program-e M?

11.2. A = ℕ x × ℕ y

Mi az (x, y) := F (x, y), F = (F_{1}, F_{2}), F_{1}(x, y) = y, F_{2}(x, y) = x, azaz az F (p, q) = {b ∈ A | x(b) = q ∧ y(b) = p} értékadás és az R = (x < y) utófeltétel leggyengébb előfeltétele?

12. Programkonstrukciók, levezetési szabályok

12.1. A = {1, 2, 3, 4, 5, 6}. [π_{1}] = {1, 2, 3, 4}. [π_{2}] = {1, 3, 4, 5}.

S_{1} = {1→ 14 1→ 12222 … 2→ 2132  3→ 36
4→ 463 4→ 451 5→ 563 6→ 612}
S_{2} = {1→ 134 1→ 121  2→ 213222 … 3→ 36
4→ 463 4→ 45111 … 5→ 5632  6→ 61222 …}

Add meg az (S_{1}; S_{2}), IF (π_{1} : S_{1}, π_{2} : S_{2}), DO(π_{1}, S_{1}) programokat és a programfüggvényeiket!

12.2. A = {1, 2, 3, 4, 5, 6}, [π_{1}] = {1, 2, 3, 4}, [π_{2}] = {2, 3, 4}, [π_{3}] = {1, 4, 6}.

S_{1} = {1→ 1222 … 2→ 23  3→ 3456
4→ 463  5→ 53  6→ 62}
S_{2} = {1→ 12  2→ 24  3→ 333 …
4→ 43  5→ 5  6→ 61}
S_{3} = {1→ 12  2→ 222 … 3→ 31
4→ 432  5→ 555 … 6→ 6333 …}

IF (π_{1} : S_{1}, π_{2} : S_{2}, π_{3} : S_{3}) =? D_{p(IF)} =? p(IF) =? 12.3. Fejezzük ki a SKIP ill. az ABORT programot egy tetszőleges S program és a prog-

ramkonstrukciók segítségével! 12.4. Legyen S_{1} és S_{2} egy-egy program az A állapottéren. Igaz-e, hogy S_{2}∘τ ∘S_{1} megegyezik

(S_{1}; S_{2})-vel? 12.5. S = (S_{1}; S_{2}). Igaz-e, hogy

a) D_{p(S)} = [lf(S_{1}, P (D_{p(S_{2})})]

b) tetszőleges R utófeltételre: lf((S_{1}; S_{2}), R) = lf(S_{1}, lf(S_{2}, R))? 12.6. Van-e olyan program, ami felírható szekvenciaként is, elágazásként is, és felírható

ciklusként is? 12.7. Igaz-e, hogy minden program felírható szekvenciaként is, elágazásként is, és felírható

ciklusként is?

12.8. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). Igaz-e, hogy D_{p(IF)} = ⋃_{k=1}^{n}([π_{k}] ∩ D_{p(S_{k})})?

12.9. Legyen S_{1}, S_{2},…, S_{n} program A-n! IF = (π_{1} : S_{1},…, π_{n} : S_{n}). S = S_{1} ∪S_{2} ∪…∪S_{n}.

Keressünk olyan π_{k} feltételeket és S_{k} programokat, hogy D_{p(IF)} = A és D_{p(S)} = ∅! 12.10. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). S = S_{1} ∪ S_{2} ∪… ∪ S_{n}. Igaz-e, hogy p(IF) része p(S)-nek?

12.11. Igaz-e? Ha IF = (π_{1} : S_{1}, π_{2} : S_{2}), akkor D_{p(IF)} = ([π_{1}] ∩ [π_{2}] ∩ D_{p(S_{1})} ∩ D_{p(S_{2})}) ∪

(D_{p(S_{1})} ∩ ([π_{1}] \ [π_{2}])) ∪ (D_{p(S_{2})} ∩ ([π_{2}] \ [π_{1}]))? 12.12. A = {1, 2, 3, 4}.

6truecm : 3truecm : i = 1; =¿ i := 2 ∗ i; i ≤ 2; =¿ SKIP; .

Milyen sorozatokat rendel S_{1}, S_{2}, IF az állapottér egyes pontjaihoz? 12.13. S = (S_{1}; S_{2}). S_{1} megoldja F_{1}-et és S_{2} megoldja F_{2}-t. Megoldja-e S az

a) F = F_{2} ∘ F_{1}

b) F = F_{2} ⊙ F_{1} feladatot?

12.14. S = (S_{1}; S_{2}). S megoldása az (F_{2} ⊙ F_{1}) feladatnak.

Megoldja-e S_{1} az F_{1}-et ill. S_{2} az F_{2}-t? 12.15. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). F ⊆ A × A feladat. ∀k ∈ [1, n] : S_{k} megoldja az F |_{[π_{k}]}

feladatot.

a) IF megoldja-e az F feladatot?

b) IF megoldja-e az F feladatot, ha π_{1} ∨ π_{2} ∨… ∨ π_{n} = igaz?

c) IF megoldja-e az F feladatot, ha D_{F} ⊆ [π_{1} ∨ π_{2} ∨… ∨ π_{n}]?

12.16. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). F ⊆ A × A feladat. IF megoldja az F feladatot. Igaz-e,

hogy ∀k ∈ [1, n] : S_{k} megoldja az F |_{[π_{k}]} feladatot? 12.17. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). F_{1},…, F_{k} ⊆ A × A feladat. ∀k ∈ [1, n] : S_{k} megoldja az

F_{k} feladatot. Megoldja-e IF az F = F_{1} ∪… ∪ F_{n} feladatot? 12.18. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). F ⊆ A × A feladat. IF megoldja az F feladatot és

[π_{1}] ∪… ∪ [π_{n}] ⊆ D_{F}. Igaz-e, hogy ∀k ∈ [1, n] : S_{k} megoldja az F |_{[π_{k}]} feladatot. 12.19. IF = (π_{1} : S_{1},…, π_{n} : S_{n}). F_{1},…, F_{n} ⊆ A × A feladat. ∀k ∈ [1, n] : D_{F_{k}} ⊆ [π_{k}] és

S_{k} megoldja az F_{k} feladatot. F = F_{1} ∪… ∪ F_{n}. Megoldja-e IF az F feladatot? 12.20. Igaz-e, hogy IF_{1} = (π_{1} : S_{1}, π_{2} : S_{2}) és IF_{2} = (π_{1} : S_{1}, π_{1} ∧ π_{2} : S_{1} ∪ S_{2}, π_{2} : S_{2})

a) egyenlő?

b) ekvivalens?

12.21. Legyen IF_{34} = (π_{3} : S_{3}, π_{4} : S_{4}), IF_{1} = (π_{1} : S_{1}, π_{2} : IF_{34}), IF_{2} = (π_{1} : S_{1}, π_{2} ∧ π_{3} : S_{3}, π_{2} ∧ π_{4} : S_{4})! Igaz-e, hogy IF_{1} és IF_{2}

a) egyenlő?

b) ekvivalens?

12.22. F ⊆ A × A feladat. S_{0} program A-n. S_{0} megoldja F -et. Megoldja-e a DO(π, S_{0})

program az F feladat π-re vonatkozó lezártját? 12.23. Legyen DO = (π, S)! Igaz-e, hogy

a) p(DO) ⊆ p(S)?

b) p(S) ⊆ p(DO)?

12.24. A = {ℕ_{0} \atop i} × {ℕ_{0} \atop n}

S = ((i := 0; DO(i ≠ n, IF ( 2|i : i := i + 1, 2 |̸i : i := i + 2)))) 7truecm : i := 0; i ≠ n; DO 3.2truecm : 2|i; =¿ i := i + 1; 2 |̸i; =¿ i := i + 2; . Milyen sorozatokat rendel S a (2, 4) ill. a (3, 7) ponthoz?

12.25. Tegyük fel, hogy teljesül a ciklus levezetési szabályának mind az öt feltétele, és Q igazsághalmaza nem üres. Lehet-e üres a

a) [P ∧ R]

b) [P ∧ ¬π ∧ R] halmaz?

12.26. Tegyük fel, hogy teljesül a ciklus levezetési szabályának mind az öt feltétele, és (Q∧π) igazsághalmaza nem üres. Lehet-e üres a lf(S_{0}, P) és lf(DO, R) igazsághalmazának metszete?

12.27. Tegyük fel, hogy teljesül a ciklus levezetési szabályának mind az öt feltétele. Legyen g = p(S_{0}) ∩ ([π] × A) és q ∈ [P] ∩ [π]. Igaz-e, hogy

a) ∀k ∈ ℕ_{0} : g^{k}(q) ⊆ [P]

b) b ∈ g^{k}(q) ∩ [π] ∩ [P] ⇒ t(b) ≤ t(q) − k?

c) g|_{π} = p(S_{0})|_{π}?

d) ∃k ∈ ℕ_{0} : k ≤ t(q) ∧ g^{k}(q) ⊆ [¬π]?

12.28. Legyen S = (S_{1}; S_{2}) és Q, Q′ és R olyan állítások, amelyekre Q ⇒ lf(S, R), Q′ ⇒ lf(S_{2}, R), Q ⇒ lf(S_{1}, Q′). Lehetséges-e, hogy [Q] ∩ [R] = ∅ ∧ [Q] ∩ [Q′] ≠ ∅ ∧ [Q′] ∩ [R] ≠ ∅? Indokd, ha nem, és írj rá példát, ha igen!

12.29. A = ℤ z × {ℕ_{0} \atop y} B = {ℤ \atop z′} × {ℕ_{0} \atop y′}

Q_{x′,y′} = (x = x′ ∧ y = y′) R_{x′,y′} = (x = x′ − y′ ∧ y = 0)

S_{0} ={((x, y), < (x, y), (x − 1, y), (x − 1, y − 1) >) | x ∈ ℤy ∈ ℕ}∪
{((x, 0), < (x, 0) >) | x ∈ ℤ}
DO ={((x, y), < (x, y), (x − 1, y), (x − 1, y − 1), (x − 2, y − 1),
(x − 2, y − 2),…, (x − y + 1, 1), (x − y, 1)(x − y, 0) >) | x ∈ ℤ ∧ y ∈ N_{0}}

Megjegyzés: Az (x, 0) párhoz 1 hosszúságú, az (x, 1) párhoz 3 hosszúságú, az (x, 2) párhoz 5 hosszúságú sorozatot rendel a program.

Tudjuk, hogy DO = (π; S_{0}) valamilyen π-re. Igaz-e, hogy található olyan P állítás és t : A → ℤ függvény, hogy a ciklus levezetési szabályának feltételei teljesülnek, és ha igen, adj meg egy megfelelő π-t, P -t és t-t!

12.30. A = ℤ k × ℤ x × ℤ i × ℤ a × ℤ b B = {ℤ \atop a′} × {ℤ \atop b′}

S = (k := 5; ((a > b : x := a − b, a ≤ b : x := b − a); i := i + 1)) Q_{a′,b′} = (a = a′ ∧ b = b′ ∧ i ∈ [0, 1] ∧ |a − b| > 10) R_{a′,b′} = (a = a′ ∧ b = b′ ∧ k ∗ i ≤ x) Bizonyítsuk be, hogy Q ⇒ lf(S, R)!

13. Típuskonstrukciók

13.1. T = it(T_{0}), q ∈ T, e ∈ T_{0}.

1. def.: e ∈ q ⇔ ∃α ∈ T_{0}^{∗} : (q ∈ ψ_{I}(α) ∧ ∃i ∈ [1, |α|] : α_{i} = e).

2. def.: e ∈ q ⇔ ∀α ∈ T_{0}^{∗} : (q ∈ ψ_{I}(α) ∧ ∃i ∈ [1, |α|] : α_{i} = e).

Ekvivalens-e a két definíció, ha az iterált kombináció, halmaz, sorozat, ill. általában? 13.2. T = it(T_{0}), t ∈ T. Ekvivalens-e a következő két definició, ha az iterált halmaz, sorozat,

ill. általában? Mit ad meg f_{1}(t), f_{2}(t)?

1. def.: f_{1}(t) = max_{(α,t)∈ψ_{I}}( ⋃_{i=1}^{|α|} α_{k})

2. def.: f_{2}(t) = | ⋃_{(α,t)∈ψ_{I}} ( ⋃_{i=1}^{|α|} α_{k})|

13.3. Specifikáljunk egy olyan típust, ahol a típusértékhalmaz egy bolt vásárlóinak számláit tartalmazza! Egy számla a vásárolt cikkek (megnevezés, mennyiség, egységár) felsorolásából és egy végösszegből áll. Adjunk meg egy olyan specifikációs invariánst, ami csak a helyesen kitöltött számlákra igaz!