Материал: Zadanie_po_diskretnoy_matematike
е) найти число таких троек (X; Y; Z), ÷òî X U, Y U, Z U,
X (Y ∩ Z) = X Y , |X| ≥ 1, |Y | ≥ 1, |Z| ≤ 1.
5) Задача мажордома. К обеду за круглым столом приглашены n пар враждующих рыщарей (n ≥ 2). Требуется рассадить их так, чтобы
∑ |
|
( ) |
|
|
|
никакие два врага не сидели рядом. Показать, что это можно сделать |
|||||
n |
k |
n |
k+1 |
(2n − k − 1)! способами. |
|
k=0(−1) |
k |
n · 2 |
|||
6) |
Задача |
î |
супружеских парах. |
Сколькими способами можно |
|
расположить за круглым столом шесть супружеских пар так, чтобы мужчины и женщины чередовались и никакие двое супругов не сидели рядом?
24
Домашнее задание 10
1)Сумма цифр шестизначного кода для кодового замка равна 38. Сколько вариантов придется перебрать в худшем случае, чтобы найти нужную комбинацию.
2)Найти число решений системы в неотрицательных целых числах.
à) x1 + x2 + x3 ≤ 51, |
4 ≤ x3 |
≤ 21; |
||
2 ≤ x1 |
≤ 20; |
3 ≤ x2 ≤ 16; |
||
á) x1 + x2 + x3 ≤ 40, |
3 ≤ x3 |
≤ 17; |
||
2 ≤ x1 |
≤ 13; |
4 ≤ x2 ≤ 11; |
||
â) x1 + x2 + x3 ≤ 44, |
3 ≤ x3 |
≤ 10; |
||
7 ≤ x1 |
≤ 18; |
2 ≤ x2 ≤ 11; |
||
ã) x1 + x2 + x3 ≤ 55, |
3 ≤ x3 |
≤ 15; |
||
0 ≤ x1 |
≤ 21; |
3 ≤ x2 ≤ 13; |
||
ä) x1 + x2 + x3 + x4 ≤ 82, |
|
|
||
2 ≤ x1 ≤ 18; 0 ≤ x2 ≤ 17; 1 ≤ x3 ≤ 21; 2 ≤ x4 ≤ 20:
3)Найти число решений системы в неотрицательных целых числах. а) x1 + x2 + x3 ≥ 25,
7 ≤ x1 |
≤ 15; |
15 ≤ x2 ≤ 33; |
9 ≤ x3 |
≤ 20; |
á) x1 + x2 + x3 ≥ 20, |
8 ≤ x3 |
≤ 15; |
||
7 ≤ x1 |
≤ 25; |
17 ≤ x2 ≤ 30; |
||
â) x1 + x2 + x3 ≥ 18, |
3 ≤ x3 |
≤ 23; |
||
8 ≤ x1 |
≤ 16; |
17 ≤ x2 ≤ 35; |
||
ã) x1 + x2 + x3 ≥ 15, |
10 ≤ x3 ≤ 24; |
|||
13 ≤ x1 ≤ 23; |
12 ≤ x2 ≤ 31; |
|||
ä) x1 + x2 + x3 + x4 ≥ 20, |
|
|
||
3 ≤ x1 ≤ 20; 13 ≤ x2 ≤ 25; 13 ≤ x3 ≤ 24: 2 ≤ x4 ≤ 18:
26
Домашнее задание 11
1)Построитü таблицы функций, реализуемых следующими формулами: а) ((x y) (x z)) (y | z);
á) ((x y) ↓ (x | y)) (z y);
â) (x ≡ y) (y z) ↓ ((x z) y); ã) x y ((x z) ≡ y) z;
ä) (x y) ((x ↓ y) | z) ↓ y;
å) (x ≡ y) (x z y) x z; æ) (((x ↓ y) | z) | x) ↓ y;
ç) ((x y) (x y z)) | (x ↓ y).
2) С помощью функций f(x1; x2) è g(x1; x2), заданных векторами значений, построить вектор значений функции h:
à) f = (0010), g = (1000), h(x1; x2; x3) = f(x1; x3) g(x2; x1);
á) f = (0100), g = (1101), h(x1; x2) = f(x1; g(x2; x1)) g(x2; f(x1; x1)); â) f = (1001), g = (1110), h(x1; x2; x3; x4) = f(x1; x3) g(x2; f(x1; x4)); ã) f = (0110), g = (1011), h(x1; x2; x3) = f(g(x1; x3); f(x2; x1));
ä) f = (1101), g = (0111), h(x1; x2) = f(g(x1; x2); x2) g(x2; f(x2; x1)); å) f = (1000), g = (0110), h(x1; x2; x3; x4) = (f(x1; f(x2; x1))
g(f(x1; x2); g(x1; x3))) f(g(x3; x4); f(x2; x2)).
3)Доказать выполнимость формул: а) ¬(A ¬A);
á) ((A B) (B A));
â) ((B (A C)) ¬((A C) B)).
4) При каких значениях переменных x; y; z; u; v; w ложны следующие
формулы:
à) (((x (y z)) (y x)) y);
á) ((x y) (x z) (y z) (u v) (u w) (v w) (x u)); â) (((x y) z) ((x y) (x z)));
ã) (((x y) ((y z) (z x))) ((x y) z)); ä) ((x y) ((x y) (x y))).
5) Доказать, что если формулы A è (A B) тождественно истинны, то
28
формула B тождественно истинна.
6) Доказать, что:
а) если формулы (A B) è (¬A C) тождественно истинны, то формула (B C) тождественно истинна;
б) если формулы (A B), (A C) è (B D) тождественно истинны, то формула (C D) тождественно истинна;
в) если формулы (¬A B) è (¬C ¬B) тождественно истинны, то формула (A ¬B) тождественно истинна.
29
Домашнее задание 12
1) Построив таблицы соответствующих функций, выяснить, эквивалентны ли U и B:
à) U = (x → y) ((y → z) → x · y), B = y · z → x; á) U = (x y) ↓ (x → (y → z)), B = y → (x z);
â) U = x → ((y → z) → y · z), B = (x (y → z)) · (x y); ã) U = (x ↓ y) (x ≡ z) | (x y · z), B = x · (y · z) x → z;
ä) U = ((x y) ·z → ((x ≡ z) y)) ·((x y) ·z), B = (x → yz) x → y); å) U = (x y) → ((y | z) → (x ≡ x · z)), B = xy (x → xy → z);
æ) U = (x | y) → ((y ↓ z) → (x z)), B = x · (y · z) (x → z);
ç) U = (((x | y) ↓ z) | y) ↓ (y → z), B = ((x | y) ↓ (y | z))·(x → (y → z)); è) U = (x ·y → z) ((x ↓ y) | z), B = ((x ↓ y ·z) (x ≡ y)) (y → x ·z); ê) U = x y · z · y → x · z · (x ↓ y), B = (x · y → (y ↓ z)) x · z · z.
2) Построив таблицы для соответствующих функций, убедиться в справедливости следующих эквивалентностей:
à) x y = (x → y) → y;
á) x ≡ y = (x → y) (y → x);
â) x ↓ y = ((x | x) | (y | y)) | ((x | x) | (y | y)); ã) x (y ≡ z) = (x y) ≡ (x z);
ä) x (y ≡ z) = ((x y) ≡ (x z)) ≡ x; å) x → (y ≡ z) = (x → y) ≡ (x → z); æ) x (y → z) = (x y) → (x z);
ç) x (y → z) = (x → y) → (x z); è) x → (y z) = (x → y) (x → z); ê) x → (y z) = (x → y) (x → z); ë) x → (y → z) = (x → y) → (x → z).
3) Используя основные тождества алгебры логики и соотношения из предыдущих заданий, доказать эквивалентность формул U и B:
à) U = (x → y) → (x · y ≡ (x y)), B = (x · y → x) → y;
á) U = (x · y (x → y · z)) ≡ ((x → y) → z), B = (x → y) (y z); â) U = (x y · z) → (x → (y → z)), B = x → ((y → z) → x);
ã) U = (x → (y → (x ≡ z))) · (x ≡ (y → (z (x → y)))), B = (x → (y → z)) → x;
31