Predikaatloogika ülesanded

Helger Lipmaa

March 7, 1995

Definitsioon. Olgu M — mittetühi hulk ja P (x_{1}, …, x_{n}) hulgal M defineeritud predikaat. Valem A(x_{1}, …, x_{n}) väljendab predikaati P, kui suvaliste m_{1}, …, m_{n} ∈ M korral kehtib

A(m_{1}, …, m_{n}) = t ⇔ P (m_{1}, …, m_{n}) = t

1. M = N, σ = ⟨0, 1 ; +, · ; =⟩. Väljendada predikaadid:

1. x = 2,

2. y = 4x + 3,

3. z = x − y,

4. z = x/y,

5. u = x − y/z,

6. x ≤ y,

7. x < y,

8. x on paarisarv,

9. x on paaritu,

10. x jagub y-ga (y|x),

11. z on x/y täisosa,

12. z on jääk x jagamisel y-ga,

13. x on täisruut,

14. x on algarv,

15. x on y ja z suurim ühistegur (x = gcd(y, z)),

16. x on y ja z väikseim ühiskordne (x = lcm(y, z)),

17. x on arvu 2 aste,

18. x^{y} = z.

2. M = (R), σ = ⟨0, 1 ; +, · ; =⟩. Väljendada predikaadid:

1. x ≥ 0,

2. x ≤ y,

3. x < y,

4. x ∈ N.

3. M = P(N), σ = ⟨ ; ; =, ⊆⟩. Väljendada predikaadid:

1. X = ∅,

2. X = N,

3. X ∪ Y = Z,

4. X ∩ Y = Z,

5. X ∪ (Y ∩ Y) = Z,

6. X ∩ Y = ∅,

7. X′ = Z,

8. X \ Y = Z,

9. |X| = 1,

10. |X| = 2.

4. M = P(N), σ = ⟨ ; ∪, ∩ ; =⟩. Väljendada predikaadid:

1. X = ∅,

2. X = N,

3. X ⊆ Y,

4. X′ = Y,

5. X \ Y = Z.

Analoogiliselt hulgal M defineeritud predikaatidele saab valemitega väljendada ka hulga M alamhulkade, hulgal M defineeritud seoste, hulgal M defineeritud funktsioonide jms. kohta käivaid väiteid.

5. Olgu fikseeritud hulk M ja olgu A, B, C ⊆ M, D ⊆ M × M. Tähistagu A(x), B(x) ja C(x) vastavalt x ∈ A, x ∈ B ja x ∈ C, D(x, y) aga (x, y) ∈ D. Signatuur koosnegu predikaatsümbolitest A, B, C, D ja võrdusmärgist. Väljendada:

1. A = B,

2. A ⊆ B, 3. A ⊂ B,

4. A ∪ B = C,

5. A ∩ B = C,

6. A \ B = C,

7. A′ = B,

8. A = ∅,

9. A = M,

10. A ∩ B = ∅,

11. |A| = 1,

12. |A| = 2,

13. A × B ⊆ D,

14. D ⊆ A × B,

15. A × B = D.

6. Olgu fikseeritud hulk M ja olgu R hulgal M defineeritud binaarne seos. Signatuur koosnegu kahekohalisest predikaatsümbolist R ja võrdusmärgist. Väljendada:

1. R on refleksiivne,

2. R on sümmeetriline,

3. R on transitiivne,

4. R on ekvivalentsisiseos,

5. R on antisümmeetriline,

6. R on mitterange järjestusseos,

7. R on irrefleksiivne,

8. R on range järjestusseos.

7. Olgu R hulgal M defineeritud ekvivalentsiseos, A ⊆ M. Kasutades sümboleid ülesannete 5 ja 6 signatuuridest, väljendada:

1. A on elemendi x ekvivalentsiklass R järgi,

2. A on ekvivalentsiklass (R järgi),

3. kui x ja y on seoses R, siis nende ekvivalentsiklassid ühtivad,

4. x ja y ei ole seoses R, siis nende ekvivalentsiklassid ei lõiku.

8. Tähistagu R(x, y), et kehtib x R y, kus R on mitterange järjestusseos hulgal M. Väljendada:

1. x ja y on mittevõrreldavad R mõttes (x ≍ y),

2. R on lineaarne järjestus,

3. x on suurim element järjestuse R mõttes,

4. x on maksimaalne element R mõttes,

5. R on tihe järjestus,

6. x on hulga A ülemine tõke,

7. x on hulga A supreemum,

8. x on hulga A infiimum.

9. Väljendada eelmise ülesande väited kui R on range järjestusseos.

10. Olgu A, B ⊆ M, f : M → M, σ = ⟨ ; f ; A, B, =⟩. Väljendada:

1. f väärtuste piirkond on B (Im f = B),

2. f(A) ⊆ B,

3. f(A) = B,

4. f on üksühene,

5. f kujutab hulga A üksüheselt hulgale B.

11. Olgu M = R, σ = ⟨0 ; +, f ; =, <⟩, kus f on ühekohaline funktsionaalsümbol. Väljendada:

1. y = −x,

2. f on paarisfunktsioon,

3. f on paaritu funktsioon,

4. f on perioodiline funktsioon,

5. f on kasvav funktsioon,

6. f on monotoonselt kasvav funktsioon,

7. f on ülalt tõkestatud,

8. f on tõkestatud,

9. f on pidev punktis x,

10. f on vasakult (paremalt) pidev punktis x.

11. f on pidev lõigul [a, b] (vahemikus (a, b)),

12. f on ühtlaselt pidev lõigul [a, b],

13. M on funktsiooni f maksimaalne väärtus lõigul [a, b],

14. M on funktsiooni f supreemum lõigus [a, b].

12. Olgu M — mingi hulk, A, B ⊆ M, f : A → B, σ = ⟨0, 1 ; f, +, · ; =⟩, kus ‘+’ ja ‘·’ on binaarsed seosed hulgal M. Väljendada:

1. M on poolrühm,

2. M on monoid,

3. M on rühm,

4. M on Abeli rühm,

5. f on poolrühmade homomorfism,

6. M on korpus ja A on M alamkorpus (A ≤ M),

7. f on korpuste homomorfism (eeldada, et A ja B on korpused).

8. A ja B on isomorfsed (sama eeldus).