SPIS TREŚCI

W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15

W1 Zbiory

  1. Dlaczego Ćą { Ć }?
  2. Ile elementów ma zbiór P(A), jeśli A={1,2}, a ile jeśli A= P({1,2})?
  3. Które z operacji na zbiorach nie są przemienne: \, Ç , Ĺ , Č ?
  4. Która z zależności jest prawdziwa, jeśli wiadomo, że A Í B ?
    1. -A Í -B
    2. -B Í -A
  5. Niech A i B będą podzbiorami pewnego uniwersum U. Czy zawsze A\B = A Ç (-B)?
  6. Udowodnić, że A Č B jest najmniejszym zbiorem zawierającym A i zawierającym B.
  7. Udowodnić, że A Ç B jest największym zbiorem, który jest zawarty jednocześnie w A i w B.
  8. Czy dla dowolnych zbiorów A, B zachodzi wzór A\(A\B) = A Ç B?
  9. Jaka jest wartość wyrażenia (A Ĺ B) Ĺ B ?
  10. Czy mozna zdefiniować pozostałe operacje teoriomnogościowe przy pomocy operacji sumy i różnicy ?
  11. Zaproponować algorytm wyliczania sumy (iloczynu, różnicy) zbiorów skończonych A, B
Spis Tresci

    W2 Relacje

    1. Jaki warunek musi być spełniony by zachodziła równoważność A Ě B wttw A ´ C Ě B ´ C?
    2. Niech r będzie relacją pustą w produkcie X ´Y. Co to za relacja r -1?
    3. Niech r1 będzie relacją przeciwzwrotną, a r2 relacją zwrotną. Czy relacja r jest zwrotna czy przeciwzwrotna?
    4. Ile można utworzyć relacji symetrycznych r Í X ´ X ?
    5. Udowodnić, że złożenie relacji r1 i r2 jest relacją zwrotną wtedy i tylko wtedy gdy obie relacje r1 i r2 są relacjami zwrotnymi.
    6. Czy można podać przykład niepustej relacji r, która byłaby jednocześnie symetryczna, przechodnia i przeciwzwrotna?
    7. Niech r, r1, r2 będą relacjami binarnymi określonymi na X ´ X. Jakie zależności muszą spełniać relacje r1 i r2 na to by r o r1 Í r o r2 ?
    8. Czy operacja składania relacji jest przemienna?
    9. Czy operacja składania relacji binarnych jest łączna?
    10. Czy z tego, że relacja r nie jest przeciwzwrotna wynika, że jest ona zwrotna?
    11. Niech A = {0,1,2,3,4,5,6, 7} oraz r1 i r2 są dwiema relacjami binarnymi w A

      12. r1 = {(x,y) Î A´ A : y = (x+4) mod 6 } a r2 = {(x,y)Î A´ A : x jest najmniejszą liczbą nieparzystą większą niż y}.
      Narysować grafy tych relacji. Czy w grafie relacji złożonej r1o r2 istnieje droga zamknięta od 1 do 1?
    12. Zaproponować algorytm sprawdzania czy relacja dana w postaci tablicy incydencji jest symetryczna.

    Spis Tresci

    W3 Funkcje

    1. Czy złożenie funkcji f o g jest określone dla dowolnych funkcji f, g?
    2. Podaj przykład funkcji f takich, że f o f = f.
    3. Co można powiedzieć o funkcji f jeśli wiadomo, że jest ona różnowartościowa oraz f o f = f.
    4. Czy relacja r = {(x,y) ÎR+ ´R+ : x2 = y2 } jest funkcją?
    5. Czy dla dowolnych zbiorów A,B zachodzi równość f(A Ç B) = f(A) Ç f(B)?
    6. Jaki jest warunek konieczny i dostateczny na to by relacja odwrotna do danej relacji była funkcją?
    7. Zdefiniuj funkcję odwrotną (o ile to możliwe) do
    8. Czy składanie funkcji jest
    9. Czy jeśli ciąg jest nieskończony, to zbiór wyrazów tego ciągu jest też nieskończony?
    10. Czy mozna podać przykład zbioru X i funkcji f : X --> X, która jest 'na' ale nie jest różnowartościowa?

      11. Rozważyć dwa przypadki :

    Spis Tresci

    W4 Relacje Równoważności

    1. Która z wymienionych relacji jest relacją równoważności? Jeśli r jest relacja równoważności,

      2. to ile klas abstrakcji ma ta relacja?
    2. Czy można zdefiniować( i jeśli tak, to jak), relację równoważności r, której klasami abstrakcji są zbiory Ai ={x Î R+ : iŁ x < i+1} dla i Î N.
    3. Udowodnić, że przecięcie dowolnych dwóch różnych klas abstrakcji pewnej relacji równoważności jest zbiorem pustym.
    4. Niech f będzie funkcją różnowartościową f : X --> X. Rozwazmy relację równoważności w X, określoną następująco:

      5. x r y wttw f(x) = f(y) dla dowolnych x, y Î X
      Z ilu elementów składają się klasy abstrakcji tej relacji?
    5. Udowodnić, że zbiór wszystkich relacji rownoważności w pewnym niepustym zbiorze X jest zamknięty na przecięcie
      6. tzn.udowodnić, że przecięcie dowolych dwóch relacji równoważności jest relacją równoważności w X.
    6. Czy suma relacji równoważności w X jest też relacją równoważności w X? Czy relacją odwrotna do relacji równoważności jest relacja równoważności?
    7. W zbiorze liczb rzeczywistych określono relację r nastepująco : x r y wttw x-y jest liczbą wymierną.

      8. Udowodnić, że r jest relacją równoważności.
    8. Ile różnych relacji równoważności można utworzyć w zbiorze n elementowym?
    Spis Tresci

    W5 Zbiory uporządkowane

    1. Ile co najwyżej elementów minimalnych może posiadać zbiór uporządkowany n-elementowy?
    2. Czy jest możliwe podanie takiego zbioru uporządkowanego, który ma jeden element minimalny a nie posiada elementu najmniejszego?
    3. Czy dla danego zbioru X (niepustego) można tak określić relację porządku, by była ona równocześnie relacją równoważności w X?
    4. Które z poniższych zdań jest prawdziwe?
    5. Czy jest możliwe aby ten sam element był minimalny i maksymalny w zbiorze uporządkowanym?
    6. Czy istnieja zbiory skończone, częściowo uporządkowane, które nie mają elementów maksymalnych?
    7. Udowodnić, że każdy łańcuch ma co najwyżej jeden element minimalny i co najwyżej jeden element maksymalny.
    8. Czy jeden podzbiór zbioru częściowo uporządkowanego może mieć wiele różnych ograniczeń górnych? Podać stosowne przyklady.
    9. Rozważmy zbiór uporządkowany <N,|>. Zbadać,
    10. Udowodnić, że dla dowolnej relacji r w zbiorze n elementowym, relacja (r Č r or Č r oro r Č...Č r n-1) jest relacją przechodnią.
    11. Narysować diagram Hassego relacji r w zbiorze {1,2,3} ´ {1,2,3}, gdzie (a1,b1) r (a2,b2) wttw a1 Ł a2 i b1 Ł b2 (tu relacja Ł relację porządku w zbiorze liczb naturalnych ograniczoną do zbioru {1,2,3})
    12. Napisać program, który dla danego zbioru par definiującego relację porządku, bada ile krawędzi będzie miał diagram Hasse tej relacji.

    Spis Tresci


    W6 Rachunek zdań

    1. Ile można określić różnych, ekstensjonalnych funktorów zdaniotwórczych jedno-argumentowych? dwuargumentowych?
    2. Czy koniunkcja zdania sprzecznego i tautologii jest sprzeczna, czy też jest tautologią? A alternatywa?
    3. Określić równoważność za pomocą koniunkcji, alternatywy i negacji.
    4. Jakie funktory zdaniotwórcze można zdefiniować za pomocą funktora Sheffer'a o(Def.: 1 o1 = 0, 1o0 = 0o0 = 0o1 = 1 )?
    5. Podać przykłady reguł wnioskowania, na których opierają się rozumowania "nie wprost".
    6. Sformułować i uzasadnić regułę wnioskowania, na podstawie której, z założeń

      7. (|a|>|b| => a2>b2) , (( c>0 a 2 >b2 ) => ca2>cb2 )
      wynika, że ((c>0 i |a|>|b| ) => ca2>cb 2).
    7. Przeanalizować rozumowanie zawarte w dowodzie równości A\(B\C) = (A\B) Č (A Ç C). Wskazać użyte prawa logiki i reguły wnioskowania

    Spis Tresci

    W7 Rachunek predykatów

    1. Zapisać, używając kwantyfikatorow i spojników logicznych, definicję porządku liniowego.
    2. Podać formułę rachunku predykatów prawdziwą wtedy i tylko wtedy gdy x = sup(A), gdzie A jest podzbiorem pewnego zbioru częściowo uporządkowanego <X, Ł >.
    3. Czy nastepująca formuła rachunku kwantyfikatorów jest czy nie jest prawdziwa w strukturze N? A w R?
    4. Podać przykład funkcji zdaniowej opisującej właśności struktury stosów (kolejek).
    5. Co można powiedzieć o formule otrzymanej z tautologii rachunku zdań, w której zmienne zdaniowe został
      6. zastąpione przez pewne funkcje zdaniowe określone w strukturze STR.
    6. Czy jest prawdziwe twierdzenie: " Niech a będzie tautologią rachunku zdań, w której występują dwie zmienne p i q. Wówczas formuła otrzymana z a przez zastąpienie zmiennych p i q przez formuły przez b i c odpowiednio, jest tautologią wtedy i tylko wtedy, gdy b i c są też tautologiami"?
    7. Czy następujące formuły są czy nie są tautologiami rachunku predykatów?
    8. Przeanalizować dowód następującej własności : f( UAi ) Í Uf(Ai ) i ÎN, gdzie f jest dowolną funkcją z X w X, a Ai są podzbiorami zbioru X.
      9. (Wskazać prawa rachunku predykatów, które zostały zastosowane w dowodzie)
    9. Czy zachodzi równoważność " ( "x)(a(x) ->b(x)) jest prawdziwa w X wttw (X \ {x: a(x) i x należy do X})Č { x : b(x) x należy do X }= X "?

    Spis Tresci

    W8 Indukcja i rekursja


    1. Sformułować zasadę indukcji jako formułę rachunku predykatów. Przekształcić otrzymane zdanie zgodnie z prawami logiki, tak by powstaly inne równoważne mu zdania.
    2. Udowodnić przez indukcję ze względu na n, że Suma{i : 0<i<n+1} = n (n+1)/2.
    3. Znaleźć funkcję f, jeżeli dana jest jej definicja rekurencyjna : f(1)=1; f(n+1) = 2 f(n)
    4. Zdefiniować funkcję rekurencyjną opisującą koszt algorytmu binarnego wyszukiwania w zbiorze liniowo uporządkowanym X, którego liczba elementów jest potęgą 2.
    5. Udowodnić, że dla dowolnego n
    6. Znaleźć niezmiennik podanego algorytmu


    Spis Tresci

    W9 Moce zbiorów


    1. Niech będzie rodzina podzbiorów pewnego zbioru X. Rozważmy relację r w P(X) określoną następująco: A r B wttw zbiór A jest równoliczny z B. Zbadać własności relacji r.
    2. Wykazać, że następujące zbiory A i B są równoliczne:
    3. Jaka jest moc zbioru
    4. Jeśli a jest formułą rachunku zdań z n zmiennymi zdaniowymi, to jaka jest moc zbioru {v : v |= a}
    5. Udowodnij, że jest niekończenie wiele różnych liczb kardynalnych.

Spis Tresci

W10 Systemy algebraiczne



  1. Czy zbiór
    (a) NP jest zamknięty na operację potęgowania?
    (b) {2i : dla wszystkich i naturalnych} tworzy algebrę z operacją dodawania?
  2. Czy istnieje izomorfizm między strukturą <N,+,*> a < R,+,*> ? Uzasadnić odpowiedź.
  3. Wskaż zbiór generatorów wymienionej algebry
    (a) <P, +,*>
    (b) <NP,*>
    (c) <X, suma, przeciecie>, gdzie X jest rodziną wszystkich skończonych podzbiorów danego xbioru XX.
  4. Czy relacja r jest kongruencją w A, jeśli
    (a) A= <Z,+,*> oraz x r y wttw x mod 5 = y mod 5
    A = < 2X, suma , przecięcie> oraz dla dowolnych podzbiorów A,B zbioru X mamy A r B wttw card(A) = card(B)
  5. Czy struktury stosów i kolejek z tym samym zbiorem elementów są podobne? Czy są izomorficzne?
  6. Podaj przykłady
    (a) dwu grafów izomorficznych,
    (b) dwu grafów, w których izomorfizm nie jest możliwy,
    (c) dwu grafów między, którymi nie da się określić homomorfizmu.

Spis Tresci

W11 Elementy kombinatoryki

  1. Na ile sposobów można rozsadzić na egzaminie studentów, jeśli grupa liczy 15 osób a w sali jest 25 miejsc?
  2. Ktora z liczb jest większa
  1. Czy zbiory A i B określone jak poniżej są równoliczne?
  1. Na ile sposobów można wyjąć jednocześnie 5 różnych kart z talii o 52 kartach.
  2. Na siatce kwadratowej porusza się mrówka, której zadaniem jest przejść z lewego dolnego rogu siatki do prawego górnego rogu. Ile jest możliwych dróg , które mogłyby mrówkę doprowadzić do celu, jeśli mrówka nigdy się nie cofa?
  3. Ile wartościowań formuły zdaniowej z n zmiennymi trzeba sprawdzić, żeby się przekonać, czy jest to tautologia rachunku zdań?
  4. Niech X będzie n-elementowym zbiorem kobiet, a Y m-elementowym zbiorem mężczyzn. Na ile sposobów można utworzyć grupy koedukacyjne, jeśli w każdej grupie musi być k kobiet i l mężczyzn?
    Spis Tresci

W12 Kombinatoryka (c.d.)


  1. Jaka jest moc zbioru relacji zwrotnych i symetrycznych równocześnie?
  2. Ile jest funnkcji f: X->Y różnowartościowych i 'na' , jeśli |X|=n a |Y|=m?
  3. Jaka jest liczba podziałów zbioru 10 elementowego na 4 części?
  4. Ile różnych relacji równoważności można utworzyć w zbiorze 5 elementowym?
  5. Ile jest różnych przedstawień liczby 10 jako sumy trzech liczb dodatnich?
  6. Powiedzmy, że od 5 losowo wybranych osób zebrano portmonetki i że suma pieniędzy w nich zawarta wynosi 200zl.
    Czy jest prawdą, że przynajmniej w dwóch portmonetkach jest łącznie co najmniej 80 złotych?


Spis Tresc i

W13 Elementy rachunku prawdopodobieństw

  1. Niech Si oznacza zdarzenie, że student o numerze i zdał egzamin z MAD, i = 1...150. Zapisać zdarzenia 
  1. Czy wyłączanie się pewnych zdarzeń ( zakładam, że nie są niemożliwe) implikuje ich  niezależność?
  2. Co jest bardziej prawdopodobne zdarzenie A czy zdarzenie (A i B) ?
  3. Jakie jest prawdopodobieństwo, że zaproponowana przez studenta funkcja ze zbioru  X, card(X)=4 w zbiór X jest różnowartościowa?

Spis Tresci

    • W14 Rachunek prawdopodobieństwa

    Spis Tresc

    • W15


    Spis Tresc