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.