Примеры задач

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

Иван Шмаков

2017-01-15

Найти суперпозицию функций.
1. Дано
  f = g = 2 x − 1.
  Найти
  f ∘ g ∘ f
2. Дано
  f = 3 arccos x, g = cos x.
  Найти
  g ∘ g ∘ f
3. Дано
  f = 1 + ln x, g = 2 x − 1.
  Найти
  g ∘ g ∘ f
Построить минимальную дизъюнктивную (конъюнктивную) нормальную форму для функции f (A, B, C, D).
1. Функция f задана следующей таблицей истинности.
  1. ```
  ABCD 0000 0001 0010 0011 0100 0101 0110 0111
  f     0    0    0    0    1    1    1    0  
  ABCD 1000 1001 1010 1011 1100 1101 1110 1111
  f     1    0    0    0    0    0    0    1  
```
2. ```
ABCD 0000 0001 0010 0011 0100 0101 0110 0111
f     0    1    0    0    ?    0    0    0  
ABCD 1000 1001 1010 1011 1100 1101 1110 1111
f     0    0    0    0    1    ?    1    0  
```
2. Функция f задана следующим выражением.
  1. f = (C ⊕ (D ↔ C))
  2. f = (((D ↔ A) ↔ C) ∨ B)
  3. f = ((C → (B ∨ A)) ∧ A)
  4. f = ((D ⊕ B) ∧ ¬D)
3. Функция f задана следующим уравнением. (Найти также область определения функции.)
  1. fD(¬A) = B(¬D)
  2. fA = A
  3. D + f = CD
  4. f(B + (¬C) + (¬D)) = (¬C)
  5. Bf = (C + D)
Граф, или подобный объект, задан следующей матрицей смежности. Определить основные свойства (ориентированность, наличие петель и кратных дуг) и инварианты (количество вершин и ребер, минимальную и максимальную степени.) Найти компоненты связности (принадлежащие им вершины; радиусы и длины диаметров.)
1. ```
  0  0  1
  1  0  1
  1  1  0
```
2. ```
  0  0  0
  0  0  0
  0  0  0
```
3. ```
  0  1  0
  1  2  0
  0  0  0
```
4. ```
  0  1  1  0
  1  0  0  0
  1  0  0  1
  0  0  1  0
```
Сеть задана следующей матрицей пропускных способностей дуг. Найти сток и исток сети, ее максимальную пропускную способность.
1. ```
  2  4  0 10  5
  0  0  0  0  0
  0  7  0  4  1
  3  2  0  6  3
  3  3  0  7  9
```
2. ```
  6  0  4  7  0
  9  3  1  5  0
  3  3  4  3  0
  0  0  0  0  0
  4  6  0  2  0
```
Восстановить исходное сообщение по коду Хэмминга. При наличии одиночной ошибки — указать номер ошибочного бита.
1. 001010011111110
2. 011011010000011
3. 110110111101101