Логические сети

Содержание Введение

1. Логические сети

1.1 Определение и реализация булевых функций

1.2 Схемы функциональных элементов

1.3 Мультиплексоры

1.4 Программируемые логические матрицы

2. Практическая часть Заключение Список литературы Введение Логические сети — этот обобщенное название технологий, реализующих кодовые преобразования. Например, мультиплексоры и программируемые логические матрицы.

Мультиплексоры могут использоваться в делителях частоты, триггерных устройствах, сдвигающих устройствах и др. Их часто используют для преобразования параллельного двоичного кода в последовательный. Для такого преобразования достаточно подать на информационные входы мультиплексора параллельный двоичный код, а сигналы на адресные входы подавать в такой последовательности, чтобы к выходу поочередно подключались входы, начиная с первого и заканчивая последним.

В микропроцессорной технике программируемые логические матрицы (ПЛМ) наиболее широко используются для реализации микропрограммных устройств управления. По способу программирования различают ПЛМ программируемые в процессе изготовления и программируемые пользователем.

В ПЛМ первого типа информация заносится в матрицы путем подключения элементов к шинам благодаря металлизации нужных участков схемы, что выполняется с помощью фотошаблона (маски). Никаких изменений пользователь в этом случае в ходе эксплуатации ПЛМ сделать не может. Подобным способом изготовляются ПЛМ, встраиваемые в МП БИС, а также автономные ПЛМ стандартного микропрограммного обеспечения.

ПЛМ второго типа поставляются незапрограммированными, и их функциональная ориентация производится пользователем с помощью специального оборудования, причем существуют ПЛМ с однократной записью информации и репрограммируемые ПЛМ, в которых записанная информация может быть стерта ультрафиолетовым или рентгеновским лучом.

1. Логические сети

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) получаем таблицу истинности:

С помощью таблицы истинности определим совершенную ДНФ:

Используя один из методов нахождения минимальной ДНФ, получаем формулу эквивалентную формуле (1) и соответствующую схеме, состоящей из семи контактов (рисунок 4а).

Рисунок 4

Отметим, что схема, изображенная на рисунке 4а, допускает упрощение, соответствующее формуле которое приведено на рисунке 4б и является минимальной схемой. Сложность минимальной схемы равна 6: .

1.2 Схемы из функциональных элементов Ориентированная бесконтурная сеть, в которой полюса делятся на входные (входы) и выходные (выходы), называется схемой из функциональных элементов. Входные полюса помечаются символами переменных, а каждая вершина, отличная от входного полюса, некоторым функциональным символом. При этом должны выполняться следующие условия:

1) если, а входной полюс, то полустепень захода вершины, а равна нулю: ;

2) если вершина, а не является полюсом и помечена n-местным функциональным символом то и дуги, входящие в а, перенумерованы от 1 до n.

Функциональным элементом называется всякий подмультиграф схемы, состоящий из невходного полюса а, помеченного соответствующим символом, и вершины, из которых исходят дуги в вершину а.

Пример 1. На рисунке 5а представлена схема из функциональных элементов. Здесь входные символы помечены символами переменных — одноместный функциональный символ, соответствующий операции отрицания; & — двухместный символ, соответствующий операции конъюнкции. — некоторый двухместный символ, — некоторые трехместные символы. Вершины, помеченные символами, являются выходными полюсами. Им соответствуют термы:

На рисунке 5б изображен функциональный элемент, определяемый вершиной, помеченной символом Ему соответствует устройство, показанное на рисунке 5 В.

Рисунок 5

В примере 1 продемонстрировано, что каждый вывод схемы порождает некоторый терм.

Говорят, что функция реализуется схемой, если существует такой выход, а схемы, что функция соответствующая терму выхода а, эквивалента функции .

Схемы из функциональных элементов с одним выходом, у которых входные полюса помечены символами, а вершины, отличные от входных полюсов, — символами называютсяфункциональными схемами. Сложностью схемы из функциональных элементов называется число ее вершин, отличных от входных полюсов, -функциональная схема, реализующая функцию называется минимальной, если всякая другаяфункциональная схема, реализующая имеет сложность, не меньшую, чем сложность схемы. Сложность минимальной схемы, реализующей функцию называется сложностью функции в классе схем из функциональных элементов и обозначается через

Пример 2. Сложность функции совпадает со сложностьюфункциональной схемы, изображенной на рисунке 6, и равна 8: .

Рисунок 6

1.3 Мультиплексоры Мультиплексором каналов называется схема с входами и одним выходом в которой при выход принимает значение где:

На рисунке 7 показан мультиплексор.

Рисунок 7

Пример 3. Если то

С помощью мультиплексора, придавая переменным постоянные значения, можно реализовать любую булеву функцию

1.4 Программируемые логические матрицы Рассмотрим схему, состоящую из входов, и выходов (рисунок 8), в которой значения выходов определяются матрицей соединений по следующим правилам:

Рисунок 8

Таким образом, где, а остальные равны 0. Полученная схема называется решеткой с входами и выходами элементов &, которая определяется матрицей соединений .

Программируемой логической матрицей (ПЛМ) называется изображенная на рисунке 9 схема, получающаяся соединением решетки, А с 2n входами и k выходами, определяемой матрицей соединений, и решетки В с k входами и m выходами, определяемой матрицей соединений .

Опишем преобразования, которые происходят при прохождении через ПЛМ значений переменных Поскольку к каждому входу присоединен инвертор, на 2п входов решетки, А подаются значения переменных После прохождения решетки A h-й выход принимает значение функции, а последующей операции инвертирования соответствует функция:

Полученные k значений подаются на входы решетки В, после прохождения которой на выходе j образуется значение функции В заключение после инвертирования по законам де Моргана на выходе j получаем значение функции:

Функции соответствует дизъюнкция конъюнктов (определяемых формулами

) таких, что

Рисунок 9

Таким образом, при соответствующем выборе матриц и можно одновременно реализовать m произвольных ДНФ, содержащих не более k различных конъюнктов переменных от

2. Практическая часть

I. Исследовать систему булевых функций на полноту. Является ли она базисом. .

Монотонность:

a.

b.

Линейность:

a. — по определению

b.

Самодвойственность:

a.

b.

c.

Система функций является полной. Система функций называется базисом, если она полная, а удаление любой функции из этой системы делает её неполной. Если удалить одну из имеющихся функций, то система функций станет неполной. Таким образом, данная система функций является базисом.

II. С помощью эквивалентных преобразований привести формулу к ДНФ, КНФ; привести к СДНФ, СКНФ с помощью аналитического и табличного способа. Проверить линейность булевой функции, заданной этой формулой, с помощью полинома Жегалкина и методом неопределенных коэффициентов:

.

Приведение формулы к ДНФ, КНФ, СДНФ, СКНФ аналитическим способом:

— КНФ.

— СКНФ.

— ДНФ.

— СДНФ.

Приведение формулы к ДНФ, КНФ, СДНФ, СКНФ табличным способом:

Пусть и .

СДНФ:

СКНФ:

Проверка линейности булевой функции, заданной этой формулой, с помощью полинома Жегалкина:

Полученный полином Жегалкина является нелинейным, и, следовательно, функция f (X, Y, Z) также нелинейная.

Проверка линейности булевой функции, заданной этой формулой, с помощью метода неопределенных коэффициентов:

III. Минимизировать двумя способами:

a. Методом Квайна;

b. Геометрическим методом.

Методом Квайна:

1) Привести функцию к СДНФ;

2) В СДНФ произвести всевозможные склеивания, а затем поглощения;

3) Перейти от сокращенной СДНФ к минимальной, используя импликантную матрицу.

СДНФ:

— сокращенная СДНФ

Необходимо оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один «+», следовательно, — минимальная СДНФ.

Геометрический метод:

— геометрическое представление.

Получаем, что — минимальная СДНФ.

IV. Доопределить функции так, чтобы — была монотонной; - была линейной; - была самодвойственной.

Функция называется монотонной, если для любых наборов нулей и единиц А=(а1,…, аn), В=(b1,…, bn) таких, что, выполняется условие

Функция называется линейной, где .

Функция называется самодвойственной, если она совпадает с двойственной к ней.

Пользуясь определениями монотонной, линейной и самодвойственной функций, получим следующую таблицу истинности:

V. Составить таблицу истинности. Доказать истинность заключения дедуктивным методом. Нарисовать граф вывода заключения дедуктивным методом. Доказать истинность заключения по методу резолюции и нарисовать граф вывода пустой резольвенты.

Используя дедуктивный метод, докажем истинность заключения:

Согласно правилу цепного заключения:

Граф вывода заключения:

Таблица истинности для данного заключения выглядит следующим образом:

Пусть, и

Докажем истинность заключения по методу резолюции:

1) — КНФ

2)

3)

4)

Граф вывода пустой резольвенты:

VI. Найти формулы ПНФ и ССФ, выполнить унификацию атомов дизъюнктов.

Пусть, тогда:

Пусть y=w, тогда:

— ПНФ.

Приведём к ССФ:

Пусть, тогда:

— ССФ.

VII. Доказать, что функция примитивно рекурсивна:

является простейшей одношаговой рекурсивной функцией — функция константа.

VIII. Найти функции, получаемые из данной числовой функции с помощью операции минимизации по каждой её переменной:

1)

· y=0 при

· в остальных случаях не определена.

2)

· y=0 при

· y=1 при

· в остальных случаях не определена.

3)

Если набор переменных таков, что левая часть уравнения имеет смысл и уравнение выполнимо, то можно считать, что оно выполнимо при подстановке y=0 на самом первом шаге.

IX. Построить машину Тьюринга, которая правильно вычисляет функцию:

Заключение

Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера.

Математическая логика является современной формой, так называемой формальной логики, применяющей математические методы для исследования своего предмета. В формальной логике и, соответственно, в математической логике, собраны результаты законов структуры правильных выводов. Вывод — это мыслительный процесс, в результате которого появляются новые открытия на основании уже имеющихся без практических исследований. В действительности, новое открытие, полученное в результате вывода, в скрытой форме находится в предварительно имеющихся знаниях.