- •Синтез комбинационного устройства для приёмной комиссии
- •Глава 1. Теоретическая часть 4
- •Глава 2 Практическая часть 16
- •Введение
- •Глава 1. Теоретическая часть
- •1.1Применение булевой алгебры в вычислительной технике.
- •1.2 Преобразование выражений, состоящих из булевых функций.
- •1.3 Комбинационные схемы. Уго основных логических элементов.
- •1.4 Синтез комбинационных схем на мультиплексорах
- •1.5 Совершенная дизъюнктивная нормальная форма (сднф)
- •Пример составления сднф.
- •Глава 2 Практическая часть
- •2.1 Построение сднф устройства для приёмной комиссии
- •2.2. Построение схемы устройства в базисе и-не
- •2.3 Построение схемы устройства на мультиплексоре
- •Заключение
- •Список используемой литературы
1.5 Совершенная дизъюнктивная нормальная форма (сднф)
Докажем, что всякую логическую функцию от N аргументов можно выразить через операции &, , ~ и константы 0 и 1. По ходу доказательства покажем, по какому именно алгоритму это делается. В принципе, вы можете пропустить этот параграф и сразу перейти к рассмотрению примера составления СДНФ. Вернитесь к доказательству, если захочется понять в деталях, каким образом работает СДНФ.
Пусть нам дана эта функция f(x1, x2, x3,...,xN) в виде таблицы истинности:
x1 |
x2 |
x3 |
... |
xN |
f(x1, x2, x3,...,xN) |
A1,1 |
A2,1 |
A3,1 |
... |
AN,1 |
F1 |
A1,2 |
A2,2 |
A3,2 |
... |
AN,2 |
F2 |
... |
... |
... |
... |
... |
... |
A1,j |
A2,j |
A3,j |
... |
AN,j |
Fj |
... |
... |
... |
... |
... |
... |
A1,M |
A2,M |
A3,M |
... |
AN,M |
FM |
Таблица 14
В таблице Ai,j - константы 0 или 1, определяющие значения аргументов; Fj - константы 0 или 1, определяющие значения функции для данной комбинации аргументов; M = 2N - количество всех возможных комбинаций.
Определим функции от 1 аргумента:
Si,j(xi) = xi, если Ai,j = 1; Si,j(xi) = ~xi, если Ai,j = 0;
Тогда исходная функция может быть представлена в виде:
(S1,1(x1) & S2,1(x2) & S3,1(x3) & ... & SN,1(xN) & F1) (S1,2(x1) & S2,2(x2) & S3,2(x3) & ... & SN,2(xN) & F2) (S1,3(x1) & S2,3(x2) & S3,3(x3) & ... & SN,3(xN) & F3) ... (*) (S1,M(x1) & S2,M(x2) & S3,M(x3) & ... & SN,M(xN) & FM) = = f(x1, x2, x3,...,xN)
Как видите, она выражена только через функции , ~ и &. Каждая строка в нашем правиле (*) соответствует строке таблицы.
Осталось доказать, что левая часть (*) действительно равна исходной функции. Возьмем произвольную n-ю строку таблицы. Убедимся, что значение функции Fn действительно равно значению левой части (*) когда значения аргументов равны значениям, указанным в этой строке: xi = Ai,n для i = 1, 2, 3,..., N.
Si,n(xi) = xi = Ai,n = 1, если Ai,n = 1; Si,n(xi) = ~xi = ~Ai,n = ~0 = 1, если Ai,n = 0.
То есть, для выбранного n и для любого i верно:
Si,n(xi) = 1 (1).
Берем в (*) n-ю строку, подставляем в нее (1) и применяем закон поглощения x & 1 = x:
S1,n(x1) & S2,n(x2) & S3,n(x3) & ... & SN,n(xN) & Fn = Fn & 1 & 1 & 1 ... & 1 = Fn
Теперь берем в (*) любую другую строку, кроме n-й. Пусть она имеет номер m. Поскольку все строки таблицы содержат разные наборы Ai,j, то хотя бы в одном столбце будет различие. Пусть различие содержится в k-м столбце:
Ak,n ≠ Ak,m
Отсюда:
Sk,m(xk) = xk = Ak,m = 0, если Ak,n = 1; Sk,m(xk) = ~xk = ~Ak,m = ~1 = 0, если Ak,n = 0.
То есть, для выбранных k и m верно:
Sk,m(xk) = 0 (2).
Берем в (*) m-ю строку, подставляем в нее (2) и применяем законы поглощения x & 0 = 0 и 0 & x = 0:
S1,m(x1) & S2,m(x2) & ... & Sk,m(xk) & ... & SN,m(xN) & Fm = = S1,m(x1) & S2,m(x2) & ... & 0 & ... & SN,m(xN) & Fm = = ... & 0 & ... & Fm = 0
Таким образом, значение всех строк СДНФ, кроме n-й равно 0 за счет нуля, который дает хотя бы одно различие в наборах аргументов. И лишь n-я строка равна Fn.
В результате получаем:
(0) (0) ... (0) (Fn) (0) ... (0) = = f(x1, x2, x3,...,xN)
И по законам поглощения x 0 = x и 0 x = x получаем:
0 0 ... 0 (Fn) 0 ... 0 = Fn = f(x1, x2, x3,...,xN)
Мы рассматривали произвольную n-ю строку таблицы и убедились, что для набора аргументов, записанного в этой строке, значение функции совпадает со значением левой части (*). Точно такое же рассуждение можно повторить для всех остальных строк, сколько бы их ни было. Таким образом, значение функции совпадает с левой частью (*) для всех возможных наборов аргументов. Что и требовалось доказать.
В формуле (*) строки, в которых Fj = 0 можно опустить, благодаря законам поглощения: x & 0 = 0, x 0 = x и 0 x = x. А в строках, в которых Fj = 1 можно опустить Fj, благодаря закону поглощения: x & 1 = x.
После этих сокращений получается запись, которая и называется совершенной дизъюнктивной нормальной формой (СДНФ).