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 