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

Размещено на http://www.allbest.ru/

Содержание

Введение

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

	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1
	1	0	1	0	1	0	0	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. Исследовать систему булевых функций на полноту. Является ли она базисом. .

	k0	k1	kм	kл	kс
	+	-	-	+	-
	+	+	+	-	-
	-	+	+	+	-

X	Y
0	0	0	0
0	1	1	1
1	0	1	1
1	1	0	1

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

a.

b.

Линейность:

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

b.

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

a.

b.

c.

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

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) В СДНФ произвести всевозможные склеивания, а затем поглощения;

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

СДНФ:

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

	+	+	-	-
	-	-	+	+
	+	-	-	+

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

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

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



Размещено на http://www.allbest.ru/

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

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

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) таких, что , выполняется условие

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

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

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

X	Y	Z	f	g	h
0	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

Пусть , и

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

1) - КНФ

2)

3)

4)



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

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

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

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

- ПНФ.

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



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

- ССФ.

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

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

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

1)

· y=0 при

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

2)

· y=0 при

· y=1 при

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

3)

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

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



Заключение

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

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

Размещено на Allbest.ru