- •1.Скласти таблиці істинності для формул.
- •2.Встановити еквівалентність формул за допомогою таблиць істинності.
- •5. Записати формули у вигляді , що містить лише операції ., , над простими змінними
- •Побудувати поліном Жегалкіна для функцій.
- •Перевірити самодвоїстість функцій.
- •8. Перевірити монотонність функцій.
- •Перевірити повноту наступних систем.
- •Розв'язок типового варіанту.
-
Побудувати поліном Жегалкіна для функцій.
1. |
16. |
2. |
17. |
3. |
18. |
4. |
19. |
5. |
20. |
6. |
21. |
7. |
22. |
8. |
23. |
9. |
24. |
10. |
25. |
11. |
26. |
12. |
27. |
13. |
28. |
14. |
29. |
15. |
30. |
-
Перевірити самодвоїстість функцій.
1. |
16. |
2. |
17. |
3. |
18. |
4. |
19. |
5. |
20. |
6. |
21. |
7. |
22. |
8. |
23. |
9. |
24. |
10. |
25. |
11. |
26. |
12. |
27. |
13. |
28. |
14. |
29. |
15. |
30. |
8. Перевірити монотонність функцій.
1. |
16. |
2. |
17. |
3. |
18. |
4. |
19. |
5. |
20. |
6. |
21. |
7. |
22. |
8. (0000) |
23. |
9. |
24. |
10. |
25. |
11. |
26. |
12. |
27. |
13. |
28. |
14. |
29. |
15. |
30. |
-
Перевірити повноту наступних систем.
1. |
16. |
2. |
17. |
3. |
18. |
4. |
19. |
5. |
20. |
6. |
21. |
7. |
22. |
8. |
23. |
9. |
24. |
10. |
25. |
11. |
26. |
12. |
27. |
13. |
28 |
14. |
29. |
15. |
30. |
10. Спростити схеми.
1.
2.
Розв'язок типового варіанту.
1. Складемо таблицю істинності для формули :
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
-
Перевіремо еквивалентність формул и , складемо для них таблиці істиності.
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
Формулы не еквивалентні, так як 3-й и 6-й стовбці таблиці не співпадають.
3. Для спрощення формули використаємо правило виключення імплікації
.
.
4. Використовуючи закони логіки приведемо формулу до виду, який містить тільки диз'юнкції елементарних кон'юнкцій. Отримана формула і буде шуканою ДНФ:
Для побудови ДДНФ складемо таблицю істинності для даної формули:
A |
B |
C |
AB |
(AB)C |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Позначаємо ті рядки таблиці, в яких формула (останній рядок) приймає значення "1". Для кожної такої рядка випишемо формулу, справжню на наборі змінних A, B, C цього рядка: рядок 1 -; рядок 3 -; рядок 5 -. Диз'юнкція цих трьох формул буде приймати значення "1" тільки на наборах змінних в рядках 1, 3, 5, а отже і буде шуканої досконалої дізьюнктівной нормальною формою (ДДНФ): Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение “1”. Для каждой такой строки выпишем формулу, истинную на наборе переменных A,B,C данной строки: строка 1 – ; строка 3 – ; строка 5 – . Дизъюнкция этих трех формул будет принимать значение “1” только на наборах переменных в строках 1, 3, 5, а следовательно и будет искомой совершенной дизьюнктивной нормальной формой (СДНФ):
5.
Для того, щоб записати формулу в наведеному вигляді, необхідно, користуючись формулою, виключити операцію імплікації, а потім "опустити" операцію заперечення на прості змінні:.
6.
Спосіб 1. (Метод невизначених коефіцієнтів). Складаємо таблицю істинності для функції x1x2
x1 |
x2 |
x1x2 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Запишемо поліном Жегалкіна з невідомими коефіцієнтами a0, a1, a2, a12, для функції від двох змінних: x1x2 = a0 a1 x1 a2 x2 a12 x1 x2.
Підставляючи в це розкладання значення x1 і x2 з таблиці, визначаємо невідомі коефіцієнти: Підставляючи x1=0, x2=0, отримаємо: 1= a0; x1=0, x2=1 — 0=1 a2 a2=1;
x1=1, x2=0 — 0=1 a1 a1=1;
x1=1, x2=1— 1=1 a12 a12=0.
Поліном Жегалкіна має вигляд: x1~x2 = 1 x1 x2.
Спосіб 2. (Еквівалентні перетворення). Спочатку запишемо ДДНФ еквівалентності: {т.к. } =
{ оскільки } { далі , , тому }
7.
Спочатку трансформуємо вихідну формулу:; .. ;.. Нехай , тоді , , тому , отже функція несамодвоїста.
8.
Функція немонотонна, тому що , Але.. 9.
Щоб довести повноту системи необхідно перевірити, що система містить функцію не зберігає 0, функцію не зберігає 1, немонотонної функцію, несамодвойственную функцію і нелінійну функцію. Доведемо повноту системи. Позначимо і випишемо її таблицю істинності
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Функція f1 не зберігає 0. З'ясуємо, чи є f1 самодвоїстою.
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
Оскільки, то f1 несамодвоїста. Функція немонотонна, і не зберігає 1. Знайдемо поліном Жегалкіна для = ;
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
; ; ; ;
Функція нелінійна. Згідно теоремі про повноту - повна система.
10.
Складемо функцію провідності для схеми
: