Логические сети
Содержание
Введение
. Логические
сети
1.1 Определение
и реализация булевых функций
1.2 Схемы
функциональных элементов
.3 Мультиплексоры
.4 Программируемые
логические матрицы
. Практическая
часть
Заключение
Список
литературы
Введение
Логические сети - этот обобщенное название
технологий, реализующих кодовые преобразования. Например, мультиплексоры и
программируемые логические матрицы.
Мультиплексоры могут использоваться в делителях
частоты, триггерных устройствах, сдвигающих устройствах и др. Их часто используют
для преобразования параллельного двоичного кода в последовательный. Для такого
преобразования достаточно подать на информационные входы мультиплексора
параллельный двоичный код, а сигналы на адресные входы подавать в такой
последовательности, чтобы к выходу поочередно подключались входы, начиная с
первого и заканчивая последним.
В микропроцессорной технике программируемые
логические матрицы (ПЛМ) наиболее широко используются для реализации
микропрограммных устройств управления. По способу программирования различают
ПЛМ программируемые в процессе изготовления и программируемые пользователем.
В ПЛМ первого типа информация заносится в
матрицы путем подключения элементов к шинам благодаря металлизации нужных
участков схемы, что выполняется с помощью фотошаблона (маски). Никаких
изменений пользователь в этом случае в ходе эксплуатации ПЛМ сделать не может.
Подобным способом изготовляются ПЛМ, встраиваемые в МП БИС, а также автономные
ПЛМ стандартного микропрограммного обеспечения.
ПЛМ второго типа поставляются
незапрограммированными, и их функциональная ориентация производится
пользователем с помощью специального оборудования, причем существуют ПЛМ с
однократной записью информации и репрограммируемые ПЛМ, в которых записанная
информация может быть стерта ультрафиолетовым или рентгеновским лучом.
1. Логические сети
.1 Определение и реализация булевых функций
Мультиграф , в котором
выделено k вершин
(полюсов), называется k-полюсной сетью. Сеть G, задаваемая
неориентированным мультиграфом с k полюсами, в которой каждое ребро
помечено буквой из алфавита называется k-полюсной
контактной схемой.
На рисунке 1 приведен пример
контактной схемы с двумя полюсами а1 и а6.
Рисунок 1
(k+1) -
полюсная схема, в которой один полюс выделен (он называется входным), а
остальные полюса (выходные) равноправны, называется (1,k)-полюсником.
Таким образом, если в приведенной на рисунке 1 двухполюсной схеме
рассматривать, например, полюс а1 как входной, а полюс а6, как выходной, то
получаем (1, 1)-полюсник.
Ребра контактной схемы называются
контактами. Контакт, соответствующий логической переменной называется
замыкающим и обозначается через . Замыкающий контакт пропускает ток
при Контакт,
соответствующий литере называется
размыкающим и обозначается как . Через него ток проходит при Таким
образом, значение 1 интерпретируется как состояние переключателя “ток
проходит”, а 0 - “ток не проходит”. Функции соответствует последовательное
соединение контактов , а функции -
параллельное соединение контактов
Нетрудно заметить, что схеме,
показанной на рисунке 1, соответствует электрическая схема, приведенная на
рисунке 2, а также схема контактов, изображенная на рисунке 3. На последнем
рисунке показаны контакты, зависящие от значений переменных а также
схема соединений контактов.
Рисунок 2
Рисунок 3
Пусть a, b - полюса контактной схемы
, - некоторая
цепь из а в b, -
конъюнкция литер, приписанных ребрам цепи . Функция ,
определяемая формулой в которой
дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, называется
функцией проводимости между полюсами a и b схем Говорят,
что функция реализуется
(1, k)-полюсником,
если существует такой выходной полюс что где а - входной полюс.
(1,1)-полюсники называются эквивалентными, если они реализуют одну и ту же
булеву функцию. Сложностью (1,1)-полюсника называется число контактов.
(1,1)-полюсник, имеющий наименьшую сложность среди эквивалентных ему схем,
называется минимальным. Сложность минимального (1,1)-полюсника, реализующего
функцию называется
сложностью функции в классе
(1,1)-полюсников и обозначается через .
Заметим, что задача нахождения
минимального (1,1)-полюсника среди эквивалентных данному (1,1)-полюснику равносильна
нахождению среди функций, реализуемых схемой функции, имеющей наименьшее число
вхождений переменных. Действительно, функцию, реализуемую (1,1)-полюсником,
нетрудно представить в виде формулы, которая строится из литер в соответствии с
контактной схемой и имеет ровно столько вхождений переменных, сколько контактов
имеет схема. Например, изображенной на рисунке 3 схеме соответствует булева
функция:
(1)
математический метод
логический матрица задача
Таким образом, задача нахождения
минимального (1,1)-полюсника сводится к минимизации соответствующей булевой
функции.
Эффективное уменьшение числа
контактов достигается с помощью нахождения минимальной ДНФ булевой функции.
Найдем минимальную ДНФ функции (1),
реализуемой схемой на рисунке 2. Придавая логическим переменным все
возможные значения, но схеме или формуле (1) получаем таблицу истинности:
00001111
|
|
|
|
|
|
|
|
|
00110011
|
|
|
|
|
|
|
|
|
01010101
|
|
|
|
|
|
|
|
|
10101001
|
|
|
|
|
|
|
|
|
С помощью таблицы истинности
определим совершенную ДНФ:
Используя один из методов нахождения
минимальной ДНФ, получаем формулу эквивалентную формуле (1) и
соответствующую схеме, состоящей из семи контактов (рисунок 4а).
Рисунок 4
Отметим, что схема, изображенная на
рисунке 4а, допускает упрощение, соответствующее формуле которое
приведено на рисунке 4б и является минимальной схемой. Сложность минимальной
схемы равна 6: .
.2 Схемы из функциональных элементов
Ориентированная бесконтурная сеть, в
которой полюса делятся на входные (входы) и выходные (выходы), называется
схемой из функциональных элементов. Входные полюса помечаются символами
переменных, а каждая вершина, отличная от входного полюса, некоторым
функциональным символом. При этом должны выполняться следующие условия:
) если а входной полюс, то
полустепень захода вершины а равна нулю: ;
) если вершина а не является
полюсом и помечена n-местным функциональным символом то и дуги,
входящие в а, перенумерованы от 1 до n.
Функциональным элементом называется
всякий подмультиграф схемы, состоящий из невходного полюса а, помеченного
соответствующим символом , и вершины,
из которых исходят дуги в вершину а.
Пример 1. На рисунке 5а представлена
схема из функциональных элементов. Здесь входные символы помечены символами
переменных -
одноместный функциональный символ, соответствующий операции отрицания; & -
двухместный символ, соответствующий операции конъюнкции. - некоторый
двухместный символ, - некоторые
трехместные символы. Вершины, помеченные символами , являются
выходными полюсами. Им соответствуют термы:
На рисунке 5б изображен
функциональный элемент, определяемый вершиной, помеченной символом Ему
соответствует устройство, показанное на рисунке 5в.
Рисунок 5
В примере 1 продемонстрировано, что каждый вывод
схемы порождает некоторый терм.
Говорят, что функция реализуется
схемой, если
существует такой выход а схемы , что функция соответствующая
терму выхода а, эквивалента функции .
Схемы из функциональных элементов с
одним выходом, у которых входные полюса помечены символами а вершины,
отличные от входных полюсов, - символами называются -функциональными
схемами. Сложностью схемы из функциональных элементов называется число ее
вершин, отличных от входных полюсов, -функциональная схема ,
реализующая функцию называется
минимальной, если всякая другая -функциональная схема, реализующая имеет
сложность, не меньшую, чем сложность схемы . Сложность минимальной схемы,
реализующей функцию называется
сложностью функции в классе
схем из функциональных элементов и обозначается через
Пример 2. Сложность функции совпадает
со сложностью -функциональной
схемы, изображенной на рисунке 6, и равна 8: .
Рисунок 6
.3 Мультиплексоры
Мультиплексором каналов называется
схема с входами и одним
выходом в которой
при выход принимает
значение где:
На рисунке 7 показан мультиплексор.
Рисунок 7
Пример 3. Если то
С помощью мультиплексора , придавая
переменным постоянные
значения, можно реализовать любую булеву функцию
.4 Программируемые логические
матрицы
Рассмотрим схему, состоящую из входов , и выходов (рисунок
8), в которой значения выходов определяются матрицей соединений по
следующим правилам:
Рисунок 8
Таким образом, где а остальные
равны 0.
Полученная схема называется решеткой с входами и выходами
элементов &, которая определяется матрицей соединений .
Программируемой логической матрицей
(ПЛМ) называется изображенная на рисунке 9 схема, получающаяся соединением
решетки А с 2n входами и k выходами,
определяемой матрицей соединений , и решетки В с k входами и m выходами,
определяемой матрицей соединений .
Опишем преобразования, которые
происходят при прохождении через ПЛМ значений переменных Поскольку к
каждому входу присоединен
инвертор , на 2п
входов решетки А подаются значения переменных После прохождения решетки A h-й
выход принимает значение функции а последующей операции
инвертирования соответствует функция:
Полученные k значений подаются на
входы решетки В, после прохождения которой на выходе j образуется значение
функции
В заключение после инвертирования по
законам де Моргана на выходе j получаем значение функции:
Функции соответствует
дизъюнкция конъюнктов (определяемых формулами
) таких, что
Рисунок 9
Таким образом, при соответствующем
выборе матриц и можно
одновременно реализовать m произвольных ДНФ, содержащих не
более k различных
конъюнктов переменных от
2. Практическая часть
I. Исследовать систему булевых
функций на полноту. Является ли она базисом. .
|
k0
|
k1
|
kм
|
kл
|
kс
|
+--+-
|
|
|
|
|
|
+++--
|
|
|
|
|
|
-+++-
|
|
|
|
|
|
X
|
Y
|
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
Монотонность:
a. .
Линейность:
. - по
определению.
Самодвойственность:.
.
.
Система функций является полной.
Система функций называется базисом, если она полная, а удаление любой функции
из этой системы делает её неполной. Если удалить одну из имеющихся функций, то
система функций станет неполной. Таким образом, данная система функций является
базисом.
II. С помощью эквивалентных преобразований
привести формулу к ДНФ, КНФ; привести к СДНФ, СКНФ с помощью аналитического и
табличного способа. Проверить линейность булевой функции, заданной этой
формулой, с помощью полинома Жегалкина и методом неопределенных коэффициентов:
.
Приведение формулы к ДНФ, КНФ, СДНФ,
СКНФ аналитическим способом:
- КНФ.
- СКНФ.
- ДНФ.
- СДНФ.
Приведение формулы к ДНФ, КНФ, СДНФ,
СКНФ табличным способом:
X Y Z Элемент.
конъюнкцииЭлемент.
дизъюнкции
|
|
|
|
|
|
|
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
|
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
|
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
|
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
|
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
|
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
|
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
|
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
|
|
Пусть и .
СДНФ:
СКНФ:
Проверка линейности булевой функции, заданной
этой формулой, с помощью полинома Жегалкина:
Полученный полином Жегалкина
является нелинейным, и, следовательно, функция f(X,Y,Z) также
нелинейная.
Проверка линейности булевой функции,
заданной этой формулой, с помощью метода неопределенных коэффициентов:
III. Минимизировать двумя способами:
a. Методом Квайна;
b. Геометрическим методом.
Методом Квайна:
1) Привести функцию к СДНФ;
2) В СДНФ произвести всевозможные
склеивания, а затем поглощения;
) Перейти от сокращенной СДНФ к
минимальной, используя импликантную матрицу.
СДНФ:
- сокращенная СДНФ
Необходимо оставить такие простые
импликанты, чтобы в каждом столбце был хотя бы один “+”, следовательно, -
минимальная СДНФ.
Геометрический метод:
- геометрическое представление.
Получаем, что -
минимальная СДНФ.. Доопределить функции так, чтобы - была
монотонной; - была
линейной; - была
самодвойственной.
X
|
Y
|
Z
|
f
|
g
|
h
|
0
|
0
|
0
|
-
|
-
|
0
|
0
|
0
|
1
|
0
|
-
|
1
|
0
|
1
|
0
|
1
|
-
|
-
|
0
|
1
|
1
|
-
|
0
|
-
|
1
|
0
|
0
|
-
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
-
|
-
|
-
|
1
|
1
|
1
|
-
|
0
|
-
|
Функция называется
монотонной, если для любых наборов нулей и единиц А=(а1,…,аn), В=(b1,…,bn) таких, что
,
выполняется условие
Функция называется линейной , где .
Функция называется
самодвойственной, если она совпадает с двойственной к ней.
Пользуясь определениями монотонной,
линейной и самодвойственной функций, получим следующую таблицу истинности:
XYZfgh
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
V. Составить таблицу истинности. Доказать
истинность заключения дедуктивным методом. Нарисовать граф вывода заключения
дедуктивным методом. Доказать истинность заключения по методу резолюции и
нарисовать граф вывода пустой резольвенты.
├
Используя дедуктивный метод, докажем
истинность заключения:
├
Согласно правилу цепного заключения:
├
├
Граф вывода заключения:
Таблица истинности для данного заключения
выглядит следующим образом:
A
|
B
|
C
|
D
|
F
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
Пусть , и
Докажем истинность заключения по
методу резолюции:
) - КНФ
)
)
)
Граф вывода пустой резольвенты:
VI. Найти формулы ПНФ и ССФ, выполнить
унификацию атомов дизъюнктов.
Пусть , тогда:
Пусть y=w, тогда:
- ПНФ.
Приведём к ССФ:
Пусть , тогда:
- ССФ.
VII. Доказать, что функция примитивно
рекурсивна:
является простейшей одношаговой
рекурсивной функцией - функция константа.
. Найти функции, получаемые
из данной числовой функции с помощью операции минимизации по
каждой её переменной:
)
· y=0 при
· в остальных случаях не определена.
)
· y=0 при
· y=1 при
· в остальных случаях не определена.
)
Если набор переменных таков, что левая часть
уравнения имеет смысл и уравнение выполнимо, то можно считать, что оно
выполнимо при подстановке y=0 на самом первом шаге.
IX. Построить машину Тьюринга, которая
правильно вычисляет функцию:
Заключение
Математическая логика изучает вопросы применения
математических методов для решения логических задач и построения логических
схем, которые лежат в основе работы любого компьютера.
Математическая логика является современной
формой, так называемой формальной логики, применяющей математические методы для
исследования своего предмета. В формальной логике и, соответственно, в
математической логике, собраны результаты законов структуры правильных выводов.
Вывод - это мыслительный процесс, в результате которого появляются новые
открытия на основании уже имеющихся без практических исследований. В
действительности, новое открытие, полученное в результате вывода, в скрытой
форме находится в предварительно имеющихся знаниях.