Условие задачи

Реализовать функцию в базисе «И,ИЛИ,НЕ»

f₁=V( 0,3,5,6,9,13,14(2,4,8,10,12,15))_abcd

Реализовать функцию в базисе «2 ИЛИ-НЕ»

f₂=V( 0,2,3,6,8,14,15(1,4,5,7,9,10,13))_abcd

Реализовать функцию в базисе «4 И-НЕ»

f₃=V( 0,3,5,6,8,10,13(1,2,4,11,12,14,15))_abcd

Решение

Ниже приводится подробное решение задачи из дискретной математики (синтеза логических схем), в которой для функции четырёх переменных (a, b, c, d) заданы её единичные комбинации и «don’t care»‑состояния. Необходимо получить минимальные выражения и затем записать схему в трёх различных логических базисах:

• базис «И, ИЛИ, НЕ» (то есть стандартный базис с операциями ∧, ∨, ¬),
• базис, содержащий только двухвходовые элементы «ИЛИ‑НЕ» (то есть NOR–элементы),
• базис, содержащий только четырёхвходовые элементы «И‑НЕ» (то есть NAND–элементы с четырьмя входами).

Ниже приведён весь процесс синтеза для каждой из функций f₁, f₂, f₃.

─────────────────────────────

1. Общее условие и разметка минтермов

Во всех трёх задачах функция задана от переменных a, b, c, d. Записывая число в двоичном виде (старший бит – a, затем b, затем c, затем d), принято, что индекс 0 соответствует комбинации 0000, 1 → 0001 и т.д.

При записи вида

  f = V( m₁, m₂, … ( d₁, d₂, … ) )₍ₐᵦ ₎

под первой группой (без скобок) понимается множество минтермов, на которых функция равна единице, а внутрь скобок записаны те индексы, где её значение неважно («don’t care»). Остальные комбинации получают значение 0.

Ниже для каждой функции восстанавливается таблица значений (при 16 комбинациях). Например, если сумма «единиц» плюс «don’t care» не равна 16, то оставшиеся комбинации – нули.

─────────────────────────────

2. Функция f₁ в базисе «И, ИЛИ, НЕ»

Задано:
  f₁ = V(0, 3, 5, 6, 9, 13, 14 (2, 4, 8, 10, 12, 15))₍ₐᵦ ₎

«Единицы» имеют индексы:
  0 → 0000,
  3 → 0011,
  5 → 0101,
  6 → 0110,
  9 → 1001,
  13 → 1101,
  14 → 1110.
«Don’t care» (Х) имеют индексы:
  2 → 0010,
  4 → 0100,
  8 → 1000,
  10 → 1010,
  12 → 1100,
  15 → 1111.
Остальные (1, 7, 11) – нули.

Для минимизации удобно расположить значения на карте Карно (представляем строки по ab по порядку 00, 01, 11, 10 и столбцы по cd в порядке 00, 01, 11, 10). Полученная таблица (значения 1, 0 и X) позволяет выделить большие группы с использованием don’t care.

После анализа можно получить минимальное СДНФ (сумму произведений) в стандартном виде. Одно из возможных минимальных решений выглядит так:

  f₁ = (c ∧ ¬d) ∨ (b ∧ ¬c ∧ d) ∨ (¬a ∧ ¬c ∧ ¬d) ∨ (¬a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ ¬c)

Пояснения по группированию:
– Группа по столбцу, соответствующему cd = 10 (то есть c = 1 и d = 0), покрывает ячейки с f₁ = 1 (например, для индексов 6 и 14), даётся импликанта (c ∧ ¬d).
– Другие группы получены объединением единиц с использованием соседних don’t care:
 • (b ∧ ¬c ∧ d)
 • (¬a ∧ ¬c ∧ ¬d)
 • (¬a ∧ ¬b ∧ c)
 • (a ∧ ¬b ∧ ¬c).

Таким образом, в стандартном базисе ответ можно реализовать с помощью вентилей И, ИЛИ и НЕ согласно формуле, записанной выше.

─────────────────────────────

3. Функция f₂ в базисе «2 ИЛИ‑НЕ»

Задано:
  f₂ = V(0, 2, 3, 6, 8, 14, 15 (1, 4, 5, 7, 9, 10, 13))₍ₐᵦ ₎

Единицы:
  0 → 0000,
  2 → 0010,
  3 → 0011,
  6 → 0110,
  8 → 1000,
  14 → 1110,
  15 → 1111.
Don’t care:
  1, 4, 5, 7, 9, 10, 13.
Нули определяются оставшимися (11 и 12).

Снова располагаем значения на карте Карno с той же разметкой:
 Строки: 00, 01, 11, 10; Столбцы: 00, 01, 11, 10.

После группировки с использованием «don’t care» можно получить следующее минимальное СДНФ:
  f₂ = (c ∧ ¬d) ∨ (a ∧ b ∧ c) ∨ (b̅ ∧ c̅ ∧ d̅) ∨ (a̅ ∧ c ∧ d)

Пояснения:
– Большая группа по столбцу, соответствующему cd = 10 (то есть c = 1 и d = 0), покрывает минтермы 2, 6 и (с don’t care в других строках) – даёт импликанту (c ∧ ¬d).
– Группа, объединяющая два соседних единичных элемента в строке 11 (индексы 14 и 15), даёт импликанту (a ∧ b ∧ c).
– Ещё одна группа по «обёртыванию» (при использовании don’t care) даёт импликанту (b̅ ∧ c̅ ∧ d̅).
– Отдельно выделяется пара, покрывающая индекс 3, что приводит к импликанте (a̅ ∧ c ∧ d).

Так как базис должен состоять только из двухвходовых элементов «ИЛИ‑НЕ» (то есть NOR–элементов), необходимо реализовать функцию, используя только NOR–элементы. Известно, что NOR – это функционально полный базис; стандартная схема преобразования СДНФ к схеме, состоящей лишь из NOR–элементов, выглядит так:
 – Представляют каждое литеральное отрицание (например, a̅) через отдельный NOR–элемент (подавая один сигнал на все входы вентиля‑инвертора);
 – Строят схему суммирования (операция ∨) и умножения (операция ∧) с помощью законов де Моргана.

Итоговую схему можно представить в виде двух уровней, где сначала получают инверсии произведений (каждое произведение Pᵢ реализуют как 2‑или 3‑входовый блок, «дополняя» до 2‑входовых NOR, подставляя на недостающие входы логическую 1), а затем объединяют их посредством NOR–элемента по схеме:
  f₂ = ¬( (¬P₁) ∧ (¬P₂) ∧ (¬P₃) ∧ (¬P₄) ).

Таким образом, окончательное выражение для f₂, записанное СОП, выглядит так:

  f₂ = (c ∧ ¬d) ∨ (a ∧ b ∧ c) ∨ (b̅ ∧ c̅ ∧ d̅) ∨ (a̅ ∧ c ∧ d)

и его можно «перерисовать» в схеме, использующей только NOR–элементы (эту процедуру можно выполнить по стандартной схеме синтеза по методу двойного отрицания).

─────────────────────────────

4. Функция f₃ в базисе «4 И‑НЕ»

Задано:
  f₃ = V(0, 3, 5, 6, 8, 10, 13 (1, 2, 4, 11, 12, 14, 15))₍ₐᵦ ₎

Единицы:
  0 → 0000,
  3 → 0011,
  5 → 0101,
  6 → 0110,
  8 → 1000,
  10 → 1010,
  13 → 1101.
Don’t care:
  1, 2, 4, 11, 12, 14, 15.
Нули – те, что не покрыты (получаются: 7 и 9).

После размещения на карте Карно (строки: 00, 01, 11, 10; столбцы: 00, 01, 11, 10) и с использованием don’t care для расширения групп получаем минимальное СДНФ:

  f₃ = (b̅ ∧ c̅ ∧ d̅) ∨ (b ∧ c̅ ∧ d) ∨ (c ∧ ¬d) ∨ (a̅ ∧ b̅ ∧ c)

Пояснения по группам:
1. Группа по столбцу с cd = 00 (c = 0, d = 0) объединяет ячейки с индексами 0 и 8 (при использовании don’t care для «обёртывания») – даёт (b̅ ∧ c̅ ∧ d̅) (так как в этих ячейках b имеет значения 0 и 1, общее условие – b̅, если объединять по вертикальному wrap‑around, можно добиться invariance по b; в приведённом решении принято, что общим остаётся литерал b̅).
2. Группа для ячеек в столбце с cd = 01 (c = 0, d = 1) в строках 01 и 11 даёт (b ∧ c̅ ∧ d).
3. Группа по столбцу с cd = 10 (c = 1, d = 0) объединяет ячейки (индексы 6 и 10) – даёт (c ∧ ¬d).
4. Отдельная группа для ячейки с индексом 3 (00011) в строке 00, использующая don’t care в соседней ячейке, даёт (a̅ ∧ b̅ ∧ c).

Таким образом, окончательное минимальное выражение:
  f₃ = (b̅ ∧ c̅ ∧ d̅) ∨ (b ∧ c̅ ∧ d) ∨ (c ∧ ¬d) ∨ (a̅ ∧ b̅ ∧ c)

Теперь необходимо реализовать эту функцию в базисе «4 И‑НЕ». Здесь на элементах доступны только четырёхвходовые вентили И‑НЕ (NAND‑элементы, функции которых задаются как
  NAND(x₁, x₂, x₃, x₄) = ¬(x₁ ∧ x₂ ∧ x₃ ∧ x₄) ).
При этом для вентилей с числом входов меньше требуемого обычно подставляют на недостающие входы постоянную единицу.

Чтобы получить схему на NAND–элементах, выражают функцию в виде двухслойной схемы по схеме «Нанд–Нанд»:
  f₃ = ¬( ¬P₁ ∧ ¬P₂ ∧ ¬P₃ ∧ ¬P₄ ),
где P₁, P₂, P₃, P₄ – произведения литералов из каждого слагаемого.
Например, пусть:
  P₁ = a̅ ∧ b̅ ∧ c, 
  P₂ = b ∧ c̅ ∧ d, 
  P₃ = c ∧ ¬d, 
  P₄ = b̅ ∧ c̅ ∧ d̅.
Каждое из них можно реализовать с помощью четырёхвходового NAND–элемента, если на четвёртый вход подавать 1 (логическую единицу), а инверсии реализовывать также через NAND–элемент (подведение одного сигнала ко всем четырём входам). Затем объединяющая схема – четырёхвходовый NAND–элемент – выдаёт отрицание произведения инверсий, что по схеме де Морган дает нужное значение f₃.

Таким образом, окончательное решение для f₃ записывается в виде:

  f₃ = (b̅ ∧ c̅ ∧ d̅) ∨ (b ∧ c̅ ∧ d) ∨ (c ∧ ¬d) ∨ (a̅ ∧ b̅ ∧ c)

и эта формула затем преобразуется в схему с четырёхвходовыми вентилями И‑НЕ согласно методу реализации «NAND–NAND».

─────────────────────────────

5. Итоговый ответ

Ответ по дисциплине «синтез логических схем (дискретная математика)»:

1) Реализация f₁ в базисе «И, ИЛИ, НЕ»:

  f₁ = (c ∧ ¬d) ∨ (b ∧ ¬c ∧ d) ∨ (¬a ∧ ¬c ∧ ¬d) ∨ (¬a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ ¬c).

2) Реализация f₂ в базисе «2 ИЛИ‑НЕ» (при реализации с использованием двухвходовых NOR–элементов):

  f₂ = (c ∧ ¬d) ∨ (a ∧ b ∧ c) ∨ (¬b ∧ ¬c ∧ ¬d) ∨ (¬a ∧ c ∧ d).

При этом всю схему можно синтезировать, представив инверсии и логические операции через двухвходовые NOR–элементы по стандартной схеме (используя формулу: f₂ = ¬( (¬P₁) ∧ (¬P₂) ∧ (¬P₃) ∧ (¬P₄) )).

3) Реализация f₃ в базисе «4 И‑НЕ» (с четырёхвходовыми NAND–элементами):

  f₃ = (¬b ∧ ¬c ∧ ¬d) ∨ (b ∧ ¬c ∧ d) ∨ (c ∧ ¬d) ∨ (¬a ∧ ¬b ∧ c).

Далее данное выражение преобразуется в эквивалентную схему «NAND–NAND»: сначала каждый конъюнктивный член (слагаемое) реализуется с помощью четырёхвходового NAND–элемента (на недостающие входы подаётся 1), а затем их объединяют также четырёхвходовым NAND–элементом, реализующим операцию отрицания произведения инверсий.

─────────────────────────────

Замечание. Возможны и иные минимизации (с частичным перекрытием групп на карте Карно) – приведённые решения являются одними из вариантов.

Таким образом, приведённое подробное решение следует правилам логического синтеза в дискретной математике с использованием базисов И, ИЛИ, НЕ; двухвходовых NOR–элементов; и четырёхвходовых NAND–элементов.