Введение в схемы, автоматы и алгоритмы - тест 2

Упражнение 1:

---

Номер 1

Какую булеву функцию реализует эта логическая схема в вершине a ?

Ответ:

---

Номер 2

Какую булеву функцию реализует эта логическая схема в вершине a?

Ответ:

---

Номер 3

Какую булеву функцию реализует эта логическая схема в вершине a ?

Ответ:

---

Упражнение 2:

---

Номер 1

 Какие из следующих схем  реализуют в вершине a функцию, заданную формулой
A = ¬ (a ∧ ¬b) ∨ ((b∨ c) ∧ (a ∧ ¬b)) ?

Ответ:

---

Номер 2

 Какие из следующих схем  реализуют в вершине a функцию, заданную формулой
A =  ((a ∧ ¬b) ∨ ¬b) ∨  ¬ (b∨ c) ?

Ответ:

---

Номер 3

 Какие из следующих схем  реализуют в вершине a функцию, заданную формулой
A =  (a ∧ b ∧ с) ∨ (¬b ∧ (b∨ c)) ?

Ответ:

---

Упражнение 3:

---

Номер 1

 Пусть задана логическая схема S=(V, E) :
V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∧),g(∧),h(∧), i(∨), k(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, d), (a, g), (b, e), (b, f), (c, f), (c, h), (d, h), (e, g), (f,k), (g, i), (i, k) }.
Какую булеву функцию реализует схема  S=(V, E) в вершине  k?
(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

Ответ:

---

Номер 2

 Пусть задана логическая схема S=(V, E) :
V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(¬),g(∧),h(∨), i(∧), k(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, d), (a, g), (b, e), (c, f), (c, g), (d, i), (e, h), (f,h), (g,k), (i, k) }.
Какую булеву функцию реализует схема  S=(V, E) в вершине  k?
(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

Ответ:

---

Номер 3

 Пусть задана логическая схема S=(V, E) :
V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∨),g(∨),h(∨), i(∧), k(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, d), (a, g), (b, e), (b, f), (b, g), (c, f), (d, h), (e, h), (f,k), (g,i), (h, i), (i, k) }.
Какую булеву функцию реализует схема  S=(V, E) в вершине  k?
(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

Ответ:

---

Упражнение 4:

---

Номер 1

 Пусть задана логическая схема S=(V, E) :
V= {a (X), b(Y), c(Z), d(V), e(¬), f(∨),g(∨),h(¬), i(¬), k(∨), m(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, i), (b, f), (b, k), (c, g), (d, e), (e, g), (f, h), (g, k), (h, m), (i, f), (k, m) }.
Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                       P2:                        P3:
X = ¬X;                   i = ¬X;                    X = ¬X;
V = ¬V;                   e = ¬V;                    X = X ∨ Y;
X = X ∨ Y;                f = i ∨ Y;                 X = ¬X;  
Z = Z ∨ V;                h = ¬i;                    V = ¬V;
X = ¬X;                   g = Z ∨ e;                 V = Z ∨ V;
Y = Y ∨ Z;                k = Y ∨ g;                 V = Y ∨ V;
Z = X ∧ Y.                Z = h ∧ k.                 Z = X ∧ V.

Ответ:

---

Номер 2

 Пусть задана логическая схема S=(V, E) :
V= {a (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }.
Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                        P2:                             P3:
V = X ∧ V;                 f = ¬Y;                         Y = ¬Y;
V = ¬V;                    g = ¬Z;                         Z = ¬Z;
Y = ¬Y;                    e = X ∧ V;                      Z = Y ∧Z;
Z = ¬Z;                    k = ¬e;                         Z = Z ∧V;
Y = Y ∧ Z;                 h = f ∧ g;                      V = X ∧ V;
Z = Y ∧ V;                 i = h ∧ V;                      V = ¬V;
Z = V ∨ Z .                Z = h ∨ k.                      Z = Z ∧ V.

Ответ:

---

Номер 3

 Пусть задана логическая схема S=(V, E) :
V= {a (X), b(Y), c(Z), d(V), e(∧), f(∧),g(¬),h(¬), i(∧), k(∧), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, h), (b, f), (c, e), (c, g), (d, f),  (e, i), (f ,i), (f ,k), (g,, k), (h,e),(i, m), (k, m) }.
Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                         P2:                        P3:
X = ¬X;                     h = ¬X;                    X = ¬X; 
Z = ¬Z;                     g = ¬Z;                    X = X ∧ Z;  
X = X ∧ Z;                  e = h ∧ Z;                 Z = ¬Z;      
Y = Y ∧ V;                  f = Y ∧ V;                 V = Y ∧ V;
Y = Y ∧ X;                  k = f ∧ g;                 V = X ∧ V;
Z = Y ∧ Z;                  i = e ∧ f;                 Y = V ∧ Z;
Z = Y ∨ Z.                  Z = i ∨ k.                 Z = Y ∨ V.

Ответ:

---

Упражнение 5:

---

Номер 1

  Пусть задана линейная программа P со входными переменными X1, X2, X3:
Y = ¬X1;
Z = ¬X2;
U = ¬X3;
V = X1 ∧ X2;
Z = Y ∧ Z;
W= Y ∧ X2;
Z = Z ∧ W ;
V = V ∧ U ;
Z = Z ∨ V.
Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Ответ:

---

Номер 2

  Пусть задана линейная программа P со входными переменными X1, X2, X3:
Y = ¬X1; 
Z = ¬X2;	
U = ¬X3;
Y = Y ∧ X2; 
W = X2 ∧ X3;
Y = Y ∧ U; 
Y = W ∨ Y ; 
Z = Z ∨ Y.
Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Ответ:

---

Номер 3

  Пусть задана линейная программа P со входными переменными X1, X2, X3:
Y = X1 ∨ X2; 
Z = X1 ∨ X3; 
U = ¬X3;
Y = Y ∧ Z;
W = X2 ∨ X3; 
U = X2 ∨  U; 
Z = W ∨ Y ; 
Z = U ∧ Y.
Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Ответ:

---

Упражнение 6:

---

Номер 1

  Чему равна глубина схемы Sodd  , реализующей функцию 
odd(X1, X2, …,Xn) = X1 + X2 + … Xn ?

Ответ:

---

Номер 2

  Чему равна глубина схемы S1, реализующей функцию сложения однобитовых чисел?

Ответ:

---

Номер 3

  Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?

Ответ:

---