View on GitHub

ITMO-PE

My study notes about Program Engineering at University ITMO

MainPage/Discrete Mathematics/Test1

Variant 1

  1. В каких пределах может находиться задержка схемы с однофазиыми входами, построенной на элементах базиса (И, НЕ) по минимальной КНФ и при каких условиях?(3 балла)

  2. Построить схему с однофазными входами, реализующую функцию на элементах базиса (ИЛИ, НЕ) и обладающую мини- мальной цсной по Кнайну. (5 баллов) Определить цену и задеряжку схемы.

  3. Опенить эффект факторизации при вынесснии одной буквы из двух термов. (4 балла)

  4. Сформулировать услония, при которых вынесение двух букв за скобки принодит к умепьшении цены схемы, (4 балла) и проиллюстрировать их примерами. (2 балла за каяждый пример)

  5. Построить схему, реализующую дизтьюнкцию семи переменных на двухвходовых элементах (И-НE). Проверить правильноеть функционирова- ния схемы дшя у=0.(6 баллов)

  6. Построить схему с парафазными входами, реализующую систему булевых функций от прех переменных: $у_{1}=$ & $(0, 2, 4, 5)$, $у_{2}=$ & $(2, 3, 4, 6)$. $У_{3}=$ & $(2, 3, 4, 5)$ на элементах булева базиса, обладающую минимальной це- ной. (14 баллон). Определитть цену и задержку схемы. (2 балла)

  8. Булевы функиии $у_{1}=f_{1}^3(x)$ и $у_{2}=f_{2}^3(x)$ совпадают на всех наборах аргументов, кроме (011) и (010), причем функция у на первом из них равна 1, а на нтором 0. Решить задачу декомпозиции примснительно к систсме $(у_{1}, у_{2})$, выразив функцию у, через $у_{1}$, (3 балла) а также у через $у_{2}$(З балла)

  9. Определить функцию, рсализусмую схемой.(3 балла) Привести функцию к нормальной форме. (3 балла) Определить реакцию схемы на входной набор (11010). (2 балла)

  10. Булева функция y=f4(x) принимает значение, равное 1, на наборах (2, 4, 10, 13, 15) и безразличное значение – на наборах (3, 5,9, 12). Построить схему с парафазными входами, реализующую данную функцию на элементах базиса (ИЛИ-НЕ) и обладающую минимальной ценой. (18 баллов) Опреде- лить реакцию схемы на безразличных наборах и пояснить ее. (2 балла за каждый набор)

Variant 2

  1. В чем состоит отличие между комбинационной и последоватьностной логическими схемами? (2 балла)
  2. Дать оценку нижней и верхних границ цены схемы по Квайяу для схемы с однофазными входами, построенной на элементах булева базиса по минимальной нормальной форме. Оценка должна содержать цены минимального покрытия $S^a$ и $S^b$. (4 балла)
  3. Оценить эффект факторизации при вынесении трех букв из двух термо (4 балла)
  4. Построить схему, реализующую функцию $у =(x_{1} \lor x_{2})(\bar{x_{1}}\lor \bar{x_{2+}})$ на элементах базиса (И - НЕ) и обладающую минимальной ценой. (3 балла)
  5. Построить схему с парафазными входами, реализующую функцию $у =(\bar{x_{1}} \lor x_{2} \lor \bar{x_{3}})(\bar{x_{2}} \lor \bar{x_{2}} \lor x_{3})\bar{x_{5}}$ на двухвходовых элементах базиса ИЛИ,НЕ), и содержащую минимальное количество элементов. (5 баллов)
  6. 6.Построить схему с парафазными входами, реалгоующую систему булевых функций от трех переменных: $у_{2}=$ & $(1, 2, 4, 5, 7)$, $у_{2}=$ & $ (0, 2, 5，6，7）$ , $y_{3}=$&$(0,2. 3, 6)$ на элементах булева базиса и обладающую минимальной леней. (18 баллов). Определить цену и задержку схемы. (2 балла)
  7. Булевы функции $y_{1}=f_{1}^3(x)$ и $y_ {2}=f_{2}^3(x)$ принимают противоположные значения на всех наборах аргументов, кроме (100) и (110), на которых значения функций совпадают и равны нулю и единице, соответственно. Решить- задачу декомпозиции применительно к системе $(у_{1},у_{2})$. выразив функцию $у_{2}$ через $у_{2}$. (3 балла)
  8. Определить функцию, реализуемую схемой, (3 балла) Привести функцию к нормальной форме. (4 балла) Определить реакции* схемы на входной набор (01010). (2 балла) 0
  9. Булева функция $у=f_{4}(х)$ принимает значение, равное нулю на наборах (0, 5, 7, 8, 14) и безразличное значение - на наборах (3, 6, 9,15) Построить схему с парафазными входами, реализующую данную функцию да элементах базиса (И-НЕ) и обладающую минимальной ценой. (18 баллов) Определить реакцию схемы на безразличных наборах и пояснить ее. 2 балла за каждый набор)

Variant 3

  1. В чем состоит отличие между позитивным и негативным кодированием? (3 балла)
  2. Применительно к минимальной КНФ сформулировать условия, прикоторых схема с однофазными входами, построенная на элементах булева базиса по этой форме, будет иметь задержку $T=2t$, где $t$ - задержка на одном логическом элементе. (4 балла)
  3. Построить схему, реализующую дизъюнкцию шести переменных надвухвходовых элементах (И-НЕ). (4 балла)
  4. Построить схему с однофазными входами, реализующую функцию $у = (x_2\lor x_3)(\overline{x}_1\lor \overline{x}_2)(\overline{x}\lor x_4)$ на элементах базиса (И, НЕ) и обладающуюминимальной ценой. (5 балла) Определить цену и задержку схемы. (1 балл)
  5. Сформулировать условия, при которых вынесение одной буквы заскобки нс приводит к уменьшении цены схемы, (4 балла) и проиллюстриро¬вать их примерами. (2 балла за каждый пример)
  6. Построить схему с парафазными входами, реализующую систему булевых функций от трех переменных: $y_1=\lor(1, 2, 5, 7), y_2=\lor(0, 2, 5, 6, 7), y_3=\lor(0, 2, 3, 6)$ на элементах булева базиса, обладающую минимальной ценой.(16 баллов). Определить цену и задержку схемы. (2 балла)
  7. Булевы функции $y_1=f_1^3(x)$ принимают противоположныезначения на всех наборах аргументов, кроме (101) и (111), на которых значе¬ния функций совпадают и равны единице и нулю, соответственно. Решитьзадачу декомпозиции применительно к системе (у>, у-), выразив функцию г.через у?. (3 балла)
  8. Определить функцию, реализуемую схемой. (3 балла) Привести функцию к нормальной форме (4 балла)Определить реакцию схемы на входной набор (0101).(2 балла)
  9. Булева функция $y=f_{4}(x)$принимает значение,равное нулю,на наборах (0,3,5,8,10,12,15)и безразличное значение-на наборах (2,14).Построить схему с парафазными входами,реализующую данную функцию на элементах базиса (И-НЕ)и обладающую минимальной ценой (18 баллов)Определить реакцию схемы на безразличных наборах и пояснить ее (2 балла за каждый набор)

Variant 4

  1. Сформулировать условия, при которых цена схемы с однофазными входами, построенной на элементах булева базиса по минимальной нормальной форме, в точности совпадает с ценой покрытия Sb. (3 балла)
  2. Сформулировать условия, при которых схема с парафазными входа­ ми, построенная на элементах универсального базиса (ИЛИ-HE), будет иметь ту же цену по Квайну, что и схема, построенная на элементах булева базиса и реализующая ту же самую булеву функцию. (4 балла)
  3. Построить схему, реализующую функцию эквивалентности на эле­ ментах базиса (ИЛИ - НЕ) и обладающую минимальной ценой. (3 балла)
  4. Построить схему с парафазными входамй, реализующую функцию у - XiXzХ4Xzvx2х2vx2Х4vx2^5 на элементах булева базиса (ИЛИ, НЕ) и обла­ дающую минимальной ценой. (5 баллов) Определить цену и задержку схемы. (1 балл)
  5. Построить схему с однофазными входами, реализующую функцию из вопроса 4 на элементах булева базиса и обладающую минимальной задержкой. (4 балла) Определить цену и задержку схемы. (1 балл)
  6. Построить схему с парафазными входами, реализующую систему бу­ левых функций от трех переменных: yi=v(0, 2, 4, 5, 7), y2=v(0, 2, 5, 6, 7), yz–v(0, 2, 3, 6) на элементах булева базиса и обладающую минимальной ценой. (18 баллов). Определить цену и задержку схемы. (2 балла)
  7. Булевы функции yf=fi(x) и у2=/г(.х) совпадают на всех наборах аргу­ ментов, кроме (100) и (110), причем функция у, на этих равна единице. Решить задачу декомпозиции применительно к системе (уь у2), выразив функцию у, че­ резу2, ау2черезу. (4 балла)
  8. Определить функцию, реализуемую схемой. (3 балла)
  9. Привести функцию к нормальной форме. (4 балла) Определить реакцию схемы на входной набор (0101K). (2 балла)
  10. Булева функция y=f4 (х) принимает значение, равное нулю, на набо­ рах (0, 2, 7, 9, 15) и безразличное значение - на наборах (4, 11, 13, 14). Постро­ ить схему с парафазными входами, реализующую данную функцию на элемен­ тах базиса (ИЛИ-HE) и обладающую минимальной ценой. (18 баллов) Опреде­ лить реакцию схемы на безразличных наборах и пояснить ее. (2 балла за каж­ дый набор)