Доведення теоретико-математичних тотожностей і тверджень (стр. 5 из 5)
9)
– перший закон Моргана.10)
– другий закон Моргана.11)
– закон подвійного заперечення.12)
– закон протиріччя.13)
– закон виключення третіх.14)
.15)
.16)
.Тотожності, що містять константи:
17)
.18)
.19)
.20)
.21)
.22)
.23)
.24)
.25)
.26)
.5.2. Завдання:
Звести до ДНФ таке висловлювання.
Розв‘язок:F=
6. Побудова досконалої диз'юнктивної нормальної форми (ДДНФ)
6.1. Теоретичні відомості
Визначення. Нехай
– деяка множина логічних змінних. Елементарна кон’юнкція, в яку входять усі логічні змінні, називається повною елементарною кон’юнкцією щодо множини 
.Визначення. Нехай
є повною елементарною кон’юнкцією щодо множини 
. Тоді 
містить у таблиці істинності лише одну одиницю, причому на наборі 
. І навпаки, якщо в таблиці істинності висловлення 
є лише одна одиниця на наборі 
, то є повною елементарною кон’юнкцією, причомуВизначення. Нехай
– висловлення. Позначимо через 
множину всіх наборів , на яких 
. називається множиною істинності висловлення . Можна записати, що 
.Теорема. Якщо
, то 
.Визначення. Диз'юнктивна нормальна форма називається досконалою (ДДНФ), якщо всі складові її елементарної кон’юнкції є повними.
Теорема. Нехай
– висловлення, що не є тотожно хибним, тобто 
,тоді 
6.2.Завдання:
Звести до ДНФ таке висловлювання.
;Розв‘язок:
| X | Y | Z | W |  |  |  |  |  |  |  |  |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| X | Y | Z | W |  |  |  |  |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
7. Графи
7.1. Теоретичні відомості
Матриця інциденцій для орієнтованого графа:
1, якщо вершина vi інцидентна ребру ej і є його кінцемH[i,j]= 2, якщо вершина vi і ребро не інцидентні ej
-1, якщо вершина vi інцидентна ребруej і є йогопочатком
Задан ориентированний граф у графиічноїеской формі.Побудовати
Нехай, v1 iv2 – вершини, e = (v1,v2) – ребро, що їх з’єднує. Тоді вершина v1 iребро е – інцидентні, ребро eiвершина v2 також інцидентні.
Завдання:Побудовати таблицу иіцидентности данного графа
Розв‘язок: таблицу иіцидентности данного графа.
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | |
| e1 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | 0 |
| e2 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 |
| e3 | 0 | 0 | 1 | 0 | -1 | 0 | 0 | 0 |
| e4 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 |
| e5 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
| e6 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 |
| e7 | 0 | 0 | 0 | 1 | 0 | -1 | 0 | 0 |
