Дан ориентированный граф D 1 Определить вид графа мультиграф или псевдограф

Вид: псевдограф (есть петли)
VD=8,
AD=11.
0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 0, 1, 1, 0, 0, 0,
0, 0, 0, 1, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0
-1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0
0, 0, 0, -1, 0, 1, 1, 0, -1, 0, 0
0, 0, 0, 0, -1, 0, 0, 0, 0, 1, -1
0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0
0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1
Максимальная степень вершины графа 4
Вид: псевдограф (есть петли)
VG =8, EG =9.
0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
1, 1, 0, 1, 1, 0, 0, 0,
0, 0, 1, 1, 0, 1, 1, 0,
0, 0, 1, 0, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0, 1, 0,
0, 0, 0, 1, 0, 1, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0
0, 0, 1, 0, 0, 0, 0, 0, 0
0, 1, 1, 1, 1, 0, 0, 0, 0
1, 0, 0, 1, 0, 0, 1, 0, 1
0, 0, 0, 0, 1, 1, 0, 0, 0
0, 0, 0, 0, 0, 0, 1, 1, 0
0, 0, 0, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 1, 0, 0, 0
Максимальная степень вершины графа 4
ИДЗ 6. Таблицы истинности булевых функций
Построить таблицы истинности булевых функций
Вариант 5

a) x↓y∧x
б) x↓y⊕x∼y
в) x→y→y∨x
а) x|y⊕z
б) x∨y|y∧z
в) x∼y∼z⊕x∧z
А)
x y yx x↓(yx)
0 0 0 1
0 1 0 1
1 0 0 0
1 1 1 0

Б)
x y ⌐x y⊕(⌐x) x↓(y⊕(⌐x)) (x↓(y⊕(⌐x))) ~ y
0 0 1 1 0 1
0 1 1 0 1 1
1 0 0 0 0 1
1 1 0 1 0 0
В)
x y ⌐y y→(⌐y) x→(y→(⌐y)) (x→(y→(⌐y)))vx
0 0 1 1 1 1
0 1 0 0 1 1
1 0 1 1 1 1
1 1 0 0 0 1
А)
x y z y⊕z
x|(y⊕z)
0 0 0 0 1
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 0 1
Б)
x y z ⌐y xv(⌐y) yz (xv(⌐y))|(yz)
0 0 0 1 1 0 1
0 0 1 1 1 0 1
0 1 0 0 0 0 1
0 1 1 0 0 1 1
1 0 0 1 1 0 1
1 0 1 1 1 0 1
1 1 0 0 1 0 1
1 1 1 0 1 1 0
В)
x y z y ~ z x ~ (y ~ z) xz (x ~ (y ~ z))⊕(xz)
0 0 0 1 0 0 0
0 0 1 0 1 0 1
0 1 0 0 1 0 1
0 1 1 1 0 0 0
1 0 0 1 1 0 1
1 0 1 0 0 1 1
1 1 0 0 0 0 0
1 1 1 1 1 1 0
ИДЗ 7. Совершенные нормальные формы
Построить СДНФ и СКНФ для булевых функций (варианты согласно ИДЗ 6).
А) СДНФ:
СКНФ:
Б)СДНФ:
СКНФ:
В)СДНФ:
СКНФ: F=0
А)СДНФ:
СКНФ:
Б)СДНФ:
СКНФ:
В)СДНФ:
СКНФ:
ИДЗ 8. Алгебра Жегалкина
Построить полиномы Жегалкина для булевых функций (варианты согласно ИДЗ 6).
А) Представим функцию в виде полинома по модулю два:f(x,y)=a0⊕a1x⊕a2yПодставляя значения функции и переменных из набора №0, получим:1=a0⊕a10⊕a20откуда a0=1Используя аналогичным образом набор №1, получим (с учетом того, что a0=1):1=1⊕a10⊕a21откуда a2=0Из набора №2:0=1⊕a11⊕0*0откуда a1=1Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №3, получим:0=1⊕1*1⊕0*1что является истиной.Отсюда следует, что функция линейна и может быть представлена как:f(x,y)=1⊕x⊕y
Б) Представим функцию в виде полинома по модулю два:f(x,y)=a0⊕a1x⊕a2yПодставляя значения функции и переменных из набора №0, получим:1=a0⊕a10⊕a20откуда a0=1Используя аналогичным образом набор №1, получим (с учетом того, что a0=1):1=1⊕a10⊕a21откуда a2=0Из набора №2:1=1⊕a11⊕0*0откуда a1=0Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №3, получим:0=1⊕0*1⊕0*1что является ложью.Следовательно, функция нелинейна.
В) Представим функцию в виде полинома по модулю два:f(x,y)=a0⊕a1x⊕a2yПодставляя значения функции и переменных из набора №0, получим:1=a0⊕a10⊕a20откуда a0=1Используя аналогичным образом набор №1, получим (с учетом того, что a0=1):1=1⊕a10⊕a21откуда a2=0Из набора №2:1=1⊕a11⊕0*0откуда a1=0Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №3, получим:1=1⊕0*1⊕0*1что является истиной.Отсюда следует, что функция линейна и может быть представлена как:f(x,y)=1⊕x⊕0=1⊕x
А) Представим функцию в виде полинома по модулю два:f(x,y,z)=a0⊕a1x⊕a2y⊕a3zПодставляя значения функции и переменных из набора №0, получим:1=a0⊕a10⊕a20⊕a30откуда a0=1Используя аналогичным образом набор №1, получим (с учетом того, что a0=1):1=1⊕a10⊕a20⊕a31откуда a3=0Из набора №2:1=1⊕a10⊕a21⊕0*0откуда a2=0Из набора №4:1=1⊕a11⊕0*0⊕0*0откуда a1=0Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №3, получим:1=1⊕0*0⊕0*1⊕0*1что является истиной.Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №5, получим:0=1⊕0*1⊕0*0⊕0*1что является ложью.Следовательно, функция нелинейна.
Б) Представим функцию в виде полинома по модулю два:f(x,y,z)=a0⊕a1x⊕a2y⊕a3zПодставляя значения функции и переменных из набора №0, получим:1=a0⊕a10⊕a20⊕a30откуда a0=1Используя аналогичным образом набор №1, получим (с учетом того, что a0=1):1=1⊕a10⊕a20⊕a31откуда a3=0Из набора №2:1=1⊕a10⊕a21⊕0*0откуда a2=0Из набора №4:1=1⊕a11⊕0*0⊕0*0откуда a1=0Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №3, получим:1=1⊕0*0⊕0*1⊕0*1что является истиной.Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №5, получим:1=1⊕0*1⊕0*0⊕0*1что является истиной.Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №6, получим:1=1⊕0*1⊕0*1⊕0*0что является истиной.Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №7, получим:0=1⊕0*1⊕0*1⊕0*1что является ложью.Следовательно, функция нелинейна.
В) Представим функцию в виде полинома по модулю два:f(x,y,z)=a0⊕a1x⊕a2y⊕a3zПодставляя значения функции и переменных из набора №0, получим:0=a0⊕a10⊕a20⊕a30откуда a0=0Используя аналогичным образом набор №1, получим (с учетом того, что a0=0):1=0⊕a10⊕a20⊕a31откуда a3=1Из набора №2:1=0⊕a10⊕a21⊕1*0откуда a2=1Из набора №4:1=0⊕a11⊕1*0⊕1*0откуда a1=1Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №3, получим:0=0⊕1*0⊕1*1⊕1*1что является истиной.Подставляя полученные значения коэффициентов в выражение, где значения переменных и функции соответствуют набору №5, получим:1=0⊕1*1⊕1*0⊕1*1что является ложью.Следовательно, функция нелинейна.