- •1.Скласти таблиці істинності для формул.
- •2.Встановити еквівалентність формул за допомогою таблиць істинності.
- •5. Записати формули у вигляді , що містить лише операції .Ú, ù, ø над простими змінними
- •Побудувати поліном Жегалкіна для функцій.
- •Перевірити самодвоїстість функцій.
- •8. Перевірити монотонність функцій.
- •Перевірити повноту наступних систем.
- •10 Для функції синтезувати логічну схему
- •11 Провести аналіз логічної схеми
- •10.20. Складемо функцію провідності для схеми
10 Для функції синтезувати логічну схему
1 |
(x → y ) →( → ) |
10 |
x → ( ( y → z ) →x ) |
19 |
(x ∨ y ) ⊕ (x ∨ z ) |
2 |
(x→ y ) ⊕ (x → z ) |
11 |
( x ∨ y ) → ( x ∨ z ) |
20 |
x ∨ ( y → z ) |
3 |
( → x ) → y |
12 |
x ∧ (y→ z) |
21 |
x → ( y ∨ z) |
4 |
(x → y) ∧ ( x → z ) |
13 |
( → x ) → y |
22 |
(x → y ) →( → ) |
5 |
x → ( ( y → z ) →x ) |
14 |
(x ∨ y ) ⊕ (x ∨ z ) |
23 |
(x→ y ) ⊕ (x → z ) |
6 |
( x ∨ y ) → ( x ∨ z ) |
15 |
x ∨ ( y → z ) |
24 |
x ∧ (y→ z) |
7 |
x → ( y ∨ z) |
16 |
((x → y) ∧ ( x → z ) |
25 |
( → x ) → y |
8 |
(x → y ) →( → ) |
17 |
x → ( ( y → z ) →x ) |
26 |
(x ∨ y ) ⊕ (x ∨ z ) |
9 |
|
18 |
( x ∨ y ) → ( x ∨ z ) |
27 |
|
11 Провести аналіз логічної схеми
1 |
|
14 |
|
2 |
|
15 |
|
3 |
|
16 |
|
4 |
|
17 |
|
5 |
|
18 |
|
6 |
|
19 |
|
7 |
|
20 |
|
8 |
|
21 |
|
9 |
|
22 |
|
10 |
|
23 |
|
11 |
|
24 |
|
12 |
|
25 |
|
13 |
|
26 |
|
Решение задач 30-го варианта.
1.30. Складемо таблицю істинності для формули: :
y |
x |
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
Перевіримо еквівалентність формул і , склавши для них таблиці істинності.
x |
y |
|
|
|
|
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.30. Для спрощення формули використовуємо правило виключення імплікації: .
.
4.30. Використовуючи закони логіки наведемо формулу до вигляду, який містить тільки диз'юнкції елементарних кон'юнкцій. Отримана формула і буде шуканої ДНФ:
Для побудови ДДНФ складемо таблицю істинності для даної формули:
x |
y |
z |
xÙy |
(xÙy)Úz |
|
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". Для кожної такої рядки випишемо формулу, справжню на наборі змінних x, y, z цього рядка: рядок 1 – ; рядок 3 – ; рядок 5 – . Диз'юнкція цих трьох формул буде приймати значення "1" тільки на наборах змінних в рядках 1, 3, 5, а отже і буде шуканої досконалою диз'юнктивною нормальною формою (ДДНФ):
5.30. Для того, щоб записати формулу в наведеному вигляді, слід, користуючись формулою , виключити операцію імплікації, а потім "опустити" операцію заперечення на прості змінні:
6.30. Спосіб 1. (Метод невизначених коефіцієнтів). Складаємо таблицю істинності для функції x1 x2
x1 |
x2 |
x1 x2 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Записуємо поліном Жегалкина з невідомими коефіцієнтами x0, x1, x2, x12 для функції від двох змінних: x1 x2 = x0Å x1 x1Å x2 x2Å x12 x1 x2.
Підставляючи в це розкладання значення x1 і x2 з таблиці, визначаємо невідомі коефіцієнти: Підставляючи x1=0, x2=0, , отримуємо:
1= x0;
x1=0, x2=1 — 0=1Å x2 Þ x2=1;
x1=1, x2=0 — 0=1Å x1 Þ x1=1;
x1=1, x2=1— 1=1Å x12 Þ x12=0.
Поліном Жегалкина має вигляд: : x1~x2 = 1Å x1 Å x2.
Спосіб 2. (Еквівалентні перетворення).
Спочатку запишемо ДДНФ еквівалентності:
{т.к. } = { Оскільки } { далі, , тому }
7.30. Спочатку перетворимо вихідну формулу
; . . Нехай , тоді , , тому , отже функція несамодвоїста.
8.30. Функція немонотонна, т.к. , але но .
9.30. Щоб довести повноту системи необхідно перевірити, що система містить функцію що не зберігає 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 |
; ; ; ;
Функція нелінійна. Згідно теоремі про повноту – повна система.