Примеры задач к экзамену по дискретной математике

(Предварительный вариант)

  1. Найти композицию отношений.

    1. Дано:
      f = cos x, g = |x|.
      Найти:
      f ∘ f ∘ g
    2. Дано:
      f = g = ex.
      Найти:
      f ∘ f ∘ g
    3. Дано:
      f = |x|, g = 1 + ln x.
      Найти:
      f ∘ f ∘ g
    4. Дано:
      f = ex, g = cos x.
      Найти:
      f ∘ f ∘ g
    5. Дано:
      f = |x|, g = 2 x − 1.
      Найти:
      f ∘ f ∘ g
    6. Дано:
      f = |x|, g = cos x.
      Найти:
      f ∘ g ∘ g
    7. Дано:
      f = cos x, g = |x|.
      Найти:
      f ∘ g ∘ g
    8. Дано:
      f = ex, g = |x|.
      Найти:
      f ∘ g ∘ g
    9. Дано:
      f = g = |x|.
      Найти:
      f ∘ f ∘ g
    10. Дано:
      f = cos x, g = ex.
      Найти:
      f ∘ f ∘ g
    11. Дано:
      f = ex, g = cos x.
      Найти:
      f ∘ g ∘ g
    12. Дано:
      f = 1 + ln x, g = |x|.
      Найти:
      f ∘ f ∘ g
    13. Дано:
      f = 2 x − 1, g = 3 arccos x.
      Найти:
      f ∘ f ∘ g
    14. Дано:
      f = g = 1 + ln x.
      Найти:
      f ∘ g ∘ g
    15. Дано:
      f = |x|, g = ex.
      Найти:
      f ∘ g ∘ g
    16. Дано:
      f = cos x, g = 3 arccos x.
      Найти:
      f ∘ f ∘ g
    17. Дано:
      f = |x|, g = cos x.
      Найти:
      f ∘ f ∘ g
    18. Дано:
      f = 1 + ln x, g = 2 x − 1.
      Найти:
      f ∘ f ∘ g
    19. Дано:
      f = cos x, g = 1 + ln x.
      Найти:
      f ∘ g ∘ g
    20. Дано:
      f = 2 x − 1, g = 1 + ln x.
      Найти:
      f ∘ f ∘ g
    21. Дано:
      f = ex, g = 2 x − 1.
      Найти:
      f ∘ f ∘ g
    22. Дано:
      f = 3 arccos x, g = |x|.
      Найти:
      f ∘ f ∘ g
    23. Дано:
      f = |x|, g = 1 + ln x.
      Найти:
      f ∘ g ∘ g
    24. Дано:
      f = 1 + ln x, g = 3 arccos x.
      Найти:
      f ∘ f ∘ g
    25. Дано:
      f = cos x, g = 1 + ln x.
      Найти:
      f ∘ f ∘ g
    26. Дано:
      f = cos x, g = 3 arccos x.
      Найти:
      f ∘ g ∘ g
    27. Дано:
      f = 1 + ln x, g = |x|.
      Найти:
      f ∘ g ∘ g
    28. Дано:
      f = 1 + ln x, g = 3 arccos x.
      Найти:
      f ∘ g ∘ g
    29. Дано:
      f = 1 + ln x, g = ex.
      Найти:
      f ∘ g ∘ g
    30. Дано:
      f = 3 arccos x, g = |x|.
      Найти:
      f ∘ g ∘ g

  2. Построить минимальную дизъюнктивную (конъюнктивную) нормальную форму для функции f (A, B, C, D).

    1. Функция f задана следующей таблицей истинности.

      1. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    1    1    0    1    0    ?    0  
      2. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     0    1    0    0    1    0    0    0  
      3. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     0    0    0    0    1    0    1    1  
      4. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    0    0    0    1    0    0    0  
      5. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    1    0    0    1    0    1    1  
      6. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    0    1    1    0    1    0    0  
      7. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    ?    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     0    0    0    0    0    0    0    0  
      8. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    ?    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    1    1    0    0    1    1    0  
      9. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    1    1    0    0    0    1    1  
      10. ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    0    0    0    0    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     1    0    0    1    0    0    ?    1

    2. Функция f задана следующим выражением.

      1. f = ¬D
      2. f = D
      3. f = ((D ⊕ B) ∧ ¬D)
      4. f = (B ∨ A)
      5. f = ((¬¬D ⊕ (((D ∨ D) → D) ⊕ C)) → A)
      6. f = (C ⊕ (D ↔ C))
      7. f = (¬C ∨ B)
      8. f = (B → D)
      9. f = (C ∧ (((D ∧ B) ∨ ((A ↔ A) ∧ C)) ⊕ A))
      10. f = (¬A ↔ ¬A)
      11. f = C
      12. f = B
      13. f = A
      14. f = (A ⊕ D)
      15. f = (B → (B ⊕ A))
      16. f = (¬B ↔ C)
      17. f = ((B ∨ ¬(B ↔ (A ⊕ D))) → ((A ∨ A) ⊕ (A ↔ ((A ∨ (B → ¬A)) ∨ B))))
      18. f = (B ⊕ D)
      19. f = (((A ∧ B) ∨ ((D ↓ (¬B ∧ D)) → B)) ↓ ¬C)
      20. f = (((D ↔ A) ↔ C) ∨ B)

    3. Функция f задана следующим уравнением. (Найти также область определения функции.)

      1. (¬A)(¬D) + f = (¬D) + A(¬B)(¬C)
      2. BfD(¬D)(¬C) = A
      3. (B + (¬C))f = ((¬A) + (¬C) + D)
      4. fB = D
      5. (¬A) + (¬C)D + (¬B)D + f + (¬D) = (¬B)C
      6. f + AC = (¬B) + (¬D)
      7. BC(¬D) + f + D = C + (¬B)
      8. f + (¬B)(¬D) = BCD
      9. Cf = (¬D)
      10. f + B = (¬B) + D

  3. Граф, или подобный объект, задан следующей матрицей смежности. Определить основные свойства (ориентированность, наличие петель и кратных ребер) и инварианты (количество вершин и ребер, минимальную и максимальную степени или полустепени.) Найти компоненты связности (принадлежащие им вершины; радиусы и длины диаметров.)

    1.   0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  1
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  1  0

    2.   0  1  1  1  1  0
  1  0  0  0  1  0
  0  0  0  1  1  0
  1  0  0  0  0  1
  0  0  0  0  0  0
  0  1  0  1  1  0

    3.   0  1  0  0  0  0
  1  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0

    4.   0  1  1  0
  1  0  0  1
  0  0  0  1
  0  0  0  0

    5.   0  0  0
  0  0  0
  0  0  0

    6.   0  3  2  1
  3  0  2  0
  2  2  0  1
  1  0  1  0

    7.   2  3  3
  3  4  1
  3  1  4

    8.   0  0  0  1  1
  1  0  0  0  0
  1  0  0  0  0
  0  0  0  0  1
  1  1  1  0  0

    9.   0  0  0
  1  1  1
  0  0  0

    10.   0  0  0  0  0  0
  0  0  1  0  2  1
  0  0  0  0  1  0
  0  0  0  1  0  0
  0  1  1  0  0  0
  0  0  0  0  0  0

    11.   0  1  0  0
  1  0  0  0
  0  0  0  0
  0  0  1  0

    12.   0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0

    13.   1  0  0  1  1  1
  0  0  1  0  0  1
  0  1  0  0  0  1
  1  0  0  0  1  0
  1  0  0  1  0  0
  1  1  1  0  0  0

    14.   0  2  4  0  1
  2  0  1  0  0
  4  1  0  1  0
  0  0  1  0  2
  1  0  0  2  0

    15.   0  0  0  1  0  0
  0  0  0  0  0  0
  0  1  0  1  1  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0

    16.   0  0  1  0  0
  0  0  0  0  1
  1  0  0  1  0
  0  0  1  1  0
  0  1  0  0  0

    17.   0  0  0
  1  0  1
  1  1  0

    18.   0  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0

    19.   0  0  0  0  0  0
  0  1  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0

    20.   0  0  0  0  0
  0  0  0  0  1
  0  0  0  0  1
  0  0  0  0  0
  0  1  1  0  0

    21.   0  0  1  1
  0  0  1  0
  1  1  0  0
  1  0  0  0

    22.   0  0  0  3
  0  0  0  0
  0  0  0  1
  3  0  1  0

    23.   0  0  0  1
  0  0  1  1
  0  1  0  0
  1  1  0  0

    24.   0  0  0  1  1  1
  0  0  1  0  0  1
  1  0  0  0  0  0
  0  0  1  0  0  0
  1  0  0  1  0  1
  0  1  0  1  1  0

    25.   2  0  0  0  0
  0  0  0  1  0
  0  0  2  0  3
  0  1  0  0  0
  0  0  3  0  0

    26.   0  1  1  1
  1  0  1  1
  1  1  0  1
  1  1  1  0

    27.   0  0  1  0
  0  0  0  0
  0  0  0  0
  0  0  0  0

    28.   0  0  0
  2  0  1
  1  1  1

    29.   0  0  0  0
  0  0  0  0
  0  0  0  0
  0  0  0  0

    30.   0  4  1  2
  4  0  5  4
  1  5  0  5
  2  4  5  0

  4. Сеть задана следующей матрицей пропускных способностей дуг. Найти сток и исток сети, ее максимальную пропускную способность.

    1.   5  1  1  5  7  0
  0  0  0  0  0  0
  6 11  3  9  3  0
  2  8  0  0  0  0
  0  1  6  8  5  0
  9  6  1  0 18  0

    2.   8  0  0  1  0  0
  3  4  3  0  0  0
  0  0  0  0  0  0
  0  0  3  1  2  0
  1  0  0  0  7  0
  5  1  4  0  0  0

    3.   4  0  0  4  4  0
  2  4  1  0  5  0
  0  0  0  0  0  0
  4  0  8 10  1  0
  3  4  4  4  4  0
  0  4  0  3  4  0

    4.   1  4  0  3  0  0
  1  0  0  7  0  0
  4  0  0  0  0  0
  0  0  0  0  0  0
  2  1  0  0  0  0
  0  3  0  3  5  3

    5.   0  0  0  0  3
  0  0  0  1  0
  0  0  0  0  1
  0  6  0  2  0
  0  0  0  0  0

    6.   0  0  0  0  0
 27 13  0  0  1
  3  8  0 12  0
  9 10  0  0  7
  7 12  0  8  5

    7.   0  0  0  0  0  0
  0  0  4  0  0  1
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0

    8.   0  0  0  0  3  0
  0  0  0  0  0  0
  0  0  0  1  0  0
  2  2  0  0  0  1
  2  0  0  0  0  0
  0  0  0  1  0  0

    9.   0  0  3  2  4
  0  0  0  0  0
  0  4  1 10  4
  0  2  4  1  0
  0  7  6  0  4

    10.   0  3  0  0  2  4
  0  3  0  3  0  3
  0  4  0  4  0  3
  0  4  0  0  9  0
  0  0  0  0  0  0
  0  1  0  1  0  2

    11.  10  5  5  5  0
  4  7 10  6  0
  7  3 15  0  0
  0  0  0  0  0
  5  5  8  0  0

    12.   0  0  0  0  0
  4  0  0  2  9
  2  0  0  2  4
  4 13  0  7 10
  9  2  0  7  1

    13.   6  2  5  3  0
  0  4  4  0  0
  4  4  6  4  0
  0  0  0  0  0
  0  0  3  0  0

    14.   0  0  0  0  0  0
  5  0  0  0  2  4
  3  0  4  1  5  0
  0  0  0  7  0  4
  4  0  0  5  1  0
  0  0  0  0  0  6

    15.   1  0  4  6  8
  8  0  4  8  3
  0  0  3 10 10
  0  0  0  0  0
  0  0 10  4  2

    16.   0  8  3  3  6
  0 13  3  7 12
  0  0  0  0  0
  0  0  6  2  1
  0  3  7 10  4

    17.   5  0  8  3  4  2
 12  0  9  3  2  0
  3  0  2  4  3  5
  0  0  5  0  0 10
  0  0  0  0  0  0
  3  0  3 10  0  7

    18.   1  3  3  0  8  3
  0  0  0  0  0  0
  8  2  3  0  5  5
  0  1  0  0  0  2
  0  6  0  0  3  4
  2  5  2  0  5  2

    19.   0  0  0  0  0
  0  0  0  2  0
  0  0  2  1  0
  6  0  0  0  0
  4  0  0  0  4

    20.   0  8  2  5  5  6
  0  2  9  2  1  0
  0  4 15  3  9  4
  0  0  0  1  1  2
  0  0  0  0  0  0
  0  0  5  2 12  5

  5. Восстановить исходное сообщение по коду Хэмминга. При наличии одиночной ошибки — указать номер ошибочного бита.

    1. 001111010011011
    2. 010001010000001
    3. 001000001000000
    4. 101011011101110
    5. 111101000010101
    6. 010100111010111
    7. 111110001001010
    8. 111110111101111
    9. 100011011111011
    10. 100111111110101