Matematyka Dyskretna – Egzamin – Teoria – Termin I; (z dnia 17.01.2008)

1. Które z poniższych zdań są prawdziwe?
[ ] Para uporządkowana <x,y> definiowana jest jako {{x}, {x,y}}
[ ] Jeżeli dana jest rodzina zbiorów R oraz prawdziwa jest równość (UR) \ (∩R) = UR to
zbiory rodziny R są puste
[ ] Dla dowolnych zbiorów A,B

⊆

X oraz funkcji f:X

→

Y prawdziwa jest następująca

własność f(A

∪

B) = f(A)

∪

f(B)

[ ] Relacja częściowego porządku jest zwrotna, symetryczna i przechodnia

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ą ze sobą w relacji R
[ ] Rodzina zbiorów R = {{a,b}, {c},

∅

, {d} } jest podziałem zbioru X = {a, b , c, d}

[ ] Skończoność zbioru X determinuje, że relacja porządkująca R

⊆

X

2

posiada diagram

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

3. Które z poniższych zdań są prawdziwe?
[ ] Poniższe warunki definiują zbiór wszystkich formuł Klasycznego Rachunku Zdań:

•

Zbiór formuł KRZ – S, to najmniejszy w sensie inkluzji zbiór spełniający warunki:

i) każde zdanie jest formułą
ii)

∀

L

∈

S

⇒

¬

L

∈

S

iii) L,B

∈

S

⇒

L

∨

B

∈

S, L

∧

B

∈

B, L

→

B

∈

S,

[ ] zbiór formuł X w KRZ jest niesprzeczny jeśli nie istnieje taka formuła L, że
X |-L i X| -

¬

L

[ ] Przykładem dowodu indukcyjnego może być dowód przeprowadzony według reguły:
reductio ad absurdum.
[ ] Reguła wnioskowania opuszczania koniunkcji jest postaci (kreska ukośna zastępuje
zwyczajowo stosowaną kreskę poziomą) B

∧¬

L / L

4. Które z poniższych zdań są prawdziwe?
[ ] Klasa decyzyjna to zbiór obiektów o tych samych wartościach atrybutów warunkowych
[ ] Dla danej tablicy decyzyjnej DT = (U,A

∪

{d}), zbioru {a

1

, a

2

, … , a

k

}

⊆

A, zmiennych

Boolowskich a

1

*, a

2

*, …, a

k

*, odpowiadających atrybutom a

1

, a

2

, …, a

k

, następujące warunki

są równoważne:

1. {a

1

, a

2

, … , a

k

} jest reduktem relatywnym dla obiektu x

∈

U w tablicy DT

2. a

1

*

∧

a

2

*

∧

..

∧

a

k

* jest implikantem pierwszym funkcji odróżnialności modulo d dla

tablicy decyzyjnej.

[ ] Jeśli tablica decyzyjna jest niesprzeczna to możemy jednoznacznie przyporządkować,
każdy obiekt do odpowiadającej mu klasy decyzyjnej.

Reszty brak – strona 2 nie skopiowana 