Wrocław, 29 października 2012

Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków

Zadania – lista 4

1. Niech X oraz Y będą zbiorami skończonymi. Ile jest funkcji o sygnaturze f : X



Y, które są:

a) częściowo określone,
b) całkowicie określone.

2. Niech ≼ będzie relacją częściowego porządku na zbiorze A oraz niech B



A. Mówimy, że a



A

jest:

– elementem najmniejszym w zbiorze B, jeśli



b



B



a ≼ b,

– elementem największym w zbiorze B, jeśli



b



B



b ≼ a,

– elementem minimalnym w zbiorze B, jeśli



b



B





(b ≼ a),

– elementem maksymalnym w zbiorze B, jeśli



b



B





(a ≼ b).

Niech X będzie podzbiorem liczb naturalnych X = {1, 2, 3, 4, 5, 6}, oraz niech B będzie
podzbiorem zbioru A = 2

X

, do którego należą tylko te podzbiory, których suma elementów jest

mniejsza od 7. Do B należy na przykład zbiór {1, 2, 3}, którego suma elementów wynosi 6.
Rozpatrzmy porządek częściowy określony na zbiorze B przez inkluzję. Narysować graf Haase
ilustrujący ten porządek oraz wyznaczyć w B elementy:

a) najmniejszy,
b) największy,
c) minimalny,
d) maksymalny.

3. Rozważmy zbiór liczb naturalnych Nat uporządkowany przez relację dzieli zdefiniowaną nastę-

pująco: <n, m>



dzieli wtedy i tylko wtedy, gdy n dzieli m. Niech A = {2, 3, 4, 5, 6, 8, 10, 12, 15}.

Narysować diagram Haase dla relacji dzieli ograniczonej do zbioru A. W zbiorze A wyznaczyć te
same rodzaje elementów jak w zadaniu 2.

4. Niech ≼ będzie relacją częściowego porządku na zbiorze A oraz niech B



A. Wykazać, że w

zbiorze B istnieje co najwyżej jeden element największy i co najwyżej jeden element najmniejszy.