Matematyka Dyskretna termin I

WSZ

Imię: Nazwisko:

Zadanie 1.

Które z poniższych zdań są prawdziwe (w miejsce kropek ... wpisz taką treść aby zdanie było prawdziwe)

[ ] Para uporządkowana <x, y> definiowana jest jako { {x}, {x,y}}

[ ] Jeśli dana jest rodzina zbiorów ℜ oraz prawdziwa jest równość
to co wiemy o zbiorach rodziny ℜ ....................... ..............................................................................................................

[ ] Obraz (f-obraz) zbioru przez funkcję może być zbiorem jednoelementowym (nie czynimy żadnych dodatkowych założeń co do funkcji i zbioru)

Zadanie 2.

Które z poniższych zdań są prawdziwe

[ ] Aby dwie klasy abstrakcji relacji równoważności R o różnych reprezentantach były identyczne wystarczy, że reprezentanty te są z sobą w relacji R.

[ ] Rodzina zbiorów R={ {a,b}, {c}, ∅ , {d} } jest podziałem zbioru X={a,b,c,d}

[ ] ............................ X determinuje, że relacja porządkująca R⊆X² posiada diagram Hassego

[ ] Stwierdzenie, że formuła jest spełniona w klasycznych rachunku zdań to stwierdzenie, że jest ona tautologią.

Zadanie 3. Które z poniższych zdań są prawdziwe ? (tam gdzie występują kropki wstaw taki tekst aby zdanie było prawdziwe)

[ ] Klasa decyzyjna to zbiór obiektów o tych samych wartościach atrybutów warunkowych

[ ] Implikant g funkcji Boolowskej f to funkcja Boolowska o takiej własności, że jeśli f przyjmuje wartość 1, to g również przyjmuje wartość 1

[ ] Załóżmy, że dana jest tablica decyzyjna DT=(U, A∪{d}) oraz zbiór B⊆A. Jeśli POS_B(d)=POS_A(d) to B jest zawsze reduktem relatywnym dla tablicy DT

Zadanie 4.

Które z poniższych zdań są prawdziwe:

[ ] Liniowe równanie rekurencyjne o stałych współczynnikach to równanie postaci a_n=b₁a_n-1+b₂a_n-2+…+b_ka_n-k

[ ]Ogólna postać rozwiązania liniowego równania rekurencyjnego postaci a_n=b₁a_n-1+b₂a_n-2 wyraża się wzorem a_n=

[ ] Metoda rozwiązywania równań rekurencyjnych głębokości jeden polega dokładnie na odgadnięciu ogólnego wzoru i sprawdzeniu czy jest on prawdziwy dla pierwszych wyrazów ciągu zdefiniowanego rekurencyjnie

Zadanie 5.

Utwórz drzewo dowodowe dla zapytania p(U,V) (Wykonaj dowód tak jakbyś „był (-a) maszyną” wnioskującą języka PROLOG).

p(X,Y)←s(X,ala).

p(X,Y)←q(ala, Y).

s(X,ala)←q(ala,X), d(X).

q(ala, ola).

q(ala, jozia).

q(ala, kot).

d(garfield).

d(kot).

Zadanie 6.

Udowodnij, że jeżeli R jest relacją równoważności określona w zbiorze X to dla każdego x,y∈X prawdziwa jest zależność

[x]_R=[y]_R ⇐ xRy

Zadanie 7.

Dany jest system informacyjny U={o₁,o₂,o₃,o₄} A={a,b,c}

a b c Wypisz wszystkie zbiory B⊆A, takie że każdy podzbiór

o₁ 1 0 0 zbioru U (poza oczywiście zbiorem pustym) jest

o₂ 1 1 0 B-definiowalny.

o₃ 0 1 0 Oblicz górne i dolne zbioru X={o₂,o₃} ze względu na zbiór

o₄ 2 1 0 atrybutów B={b,c}, czy zbiór X jest B-definiowalny.

---