Кафедра интеллектуальных систем и защиты информации

ЗАДАНИЕ

На курсовую работу

Студенту

Института Информационных технологий и автоматизации

Курс: 1  Группа: МДА-9 (очная форма обучения)

Направление подготовки: 10.03.01 Информационная безопасность

Профиль: Безопасность компьютерных систем (в коммерческих структурах)

Дисциплина: Математическая логика

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

2. Срок сдачи курсовой работы:

3. Исходные данные по курсовой работе: Электронные ресурсы

4. Перечень вопросов, подлежащих разработке в курсовой работе:

Найти МДНФ и МКНФ с применением различных методов. Построить комбинационные схемы в булевом базисе и в базисе Жегалкина, реализующие не полностью определенную булеву функцию f(x) = f(X₁,X₂,X₃,X₄,X₅),

которая принимает значение 1 при условии:  2 < |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| <= 5

неопределенное значение при условии:  |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| = 1

(Вариант № 5)

5. Комбинационные схемы имеют следующие наложенные условия: коэффициент объединения по входам - 2, коэффициент разветвления по выходу – 1.

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

Дата выдачи задания: 13.02.2020

Задание выдала: ст. преподаватель._____________________

Задание принял к исполнению:  

Оглавление

ЗАДАНИЕ. 2

1. ВВЕДЕНИЕ. 4

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 5

3. ПРАКТИЧЕСКАЯ ЧАСТЬ. 10

3.1. СОСТАВЛЕНИЕ ТАБЛИЦЫ ИСТИННОСТИ.. 10

3.1.1 ПРЕДСТАВЛЕНИЕ БУЛЕВОЙ ФУНКЦИИ В АНАЛИТИЧЕСКОМ ВИДЕ С ПОМОЩЬЮ КДНФ И ККНФ.. 11

3.2 МИНИМИЗАЦИЯ БУЛЕВОЙ ФУНКЦИИ.. 12

3.2.1 МЕТОД КВАЙНА – МАК-КЛАСКИ.. 12

3.2.2. МЕТОД ПЕТРИКА.. 16

3.2.3. МЕТОД КАРТ КАРНО.. 18

3.2.3.1. ДЛЯ МДНФ.. 18

3.2.3.2. ДЛЯ МКНФ.. 18

3.3 ФАКТОРИЗАЦИЯ И ДЕКОМПОЗИЦИЯ БУЛЕВОЙ ФУНКЦИИ.. 21

3.4 ПОСТРОЕНИЕ КОМБИНАЦИОННЫХ СХЕМ.. 23

3.4.1. КОМБИНАЦИОННАЯ СХЕМА (НЕФАКТОРИЗОВАННОЙ МДНФ) 23

3.4.2. КОМБИНАЦИОННАЯ СХЕМА (КАРТЫ КАРНО) 24

3.4.3. КОМБИНАЦИОННАЯ СХЕМА (ФАКТОРИЗОВАННОЙ МДНФ) 25

3.4.4 КОМБИНАЦИОННАЯ СХЕМА (В БАЗИСЕ ЖЕГАЛКИНА) 26

3.5 УСЛОВНЫЕ ОБОЗНАЧЕНИЯ.. 30

4. ЗАКЛЮЧЕНИЕ. 31

5. СПИСОК ЛИТЕРАТУРЫ.. 33

ВВЕДЕНИЕ

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

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

Булева функция от 5ти переменных 2 < |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| <= 5 задана в качестве исходной. Данная функция является неопределенной при условии |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| = 1. В итоге будут построены комбинационные схемы, реализующие данную функцию, с учетом наименьшей цены.

 

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Булевой функцией называется функция, аргументами которой являются булевы переменные, а сама функция принимает значение из множества {0,1}.

Ранг терма  - количество букв входящих в терм.

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

Простая дизъюнкция:

· полная, если в неё каждая переменная (или её отрицание) входит ровно один раз;

· монотонная, если она не содержит отрицаний переменных.

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

Простая конъюнкция:

· полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;

· монотонная, если она не содержит отрицаний переменных.

Конъюнктивная нормальная форма, КНФ — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.

Дизъюнктивная нормальная форма, ДНФ — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов.

Совершенная (каноническая) конъюнктивная нормальная форма, СКНФ — это такая КНФ, которая удовлетворяет условиям:

· в ней нет одинаковых простых дизъюнкций

· каждая простая дизъюнкция полная

Совершенная (каноническая) дизъюнктивная нормальная форма, СДНФ — ДНФ, удовлетворяющая условиям:

· в ней нет одинаковых простых конъюнкций,

· каждая простая конъюнкция полная.

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

В кубическом представлении булевой функции от n переменных все множество из 2ⁿ наборов ее аргументов рассматривается как множество координат вершин n-мерного куба с длиной ребра равной 1.

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

Покрытием булевой функции f называется такое подмножество кубов из кубического комплекса K(f), которое покрывает все существенные вершины функции.

Покрытие булевой функции, которое соответствует минимальной ДНФ, называется минимальным покрытием.

ДНФ, соответствующая множеству максимальных кубов, называется сокращенной (СДНФ).

Множество максимальных кубов, без которых не может быть образовано покрытие булевой функции, называется ядром покрытия и обозначается T(f) (например, T(f) = {0110-, 11-01}.

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

Минимальным покрытием называется покрытие, обладающее минимальной ценой S^a по сравнению с любым другим покрытием этой функции.

Булева функция g(X) называется импликантой булевой функции f(X), если для любого набора аргументов, на которых g(X)=1, f(X) также равна единице.

Простой (первичной) импликантой булевой функции называется конъюнктивный терм, который сам является импликантой этой функции, но никакая его собственная часть уже не является импликантой этой функции.

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

Дизъюнкция всех простых импликант булевой функции представляет собой ДНФ этой функции, которая называется сокращенной - СДНФ.

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

Нахождение минимальных форм булевой функции методом Квайна-Мак-Класки базируется на ее кубическом представлении. При этом куб минимальной размерности (0-куб) отождествляется с набором аргументов булевой функции, на котором он принимает значение, равное единице. Над кубами одинаковой размерности определена операция склеивания, соответствующая правилу склеивания конъюнктивных термов. Склеивание двух k-кубов (размерность k куба определяется числом независимых координат, отмечаемых в записи куба символом -) в результате дает один (k+1)-куб. Проводя всевозможные операции склеивания между кубами можно получить множество кубов различных размерностей, образующих кубический комплекс K(f) заданной функции f(x). С использованием кубического представления булевой функции решение задачи минимизации сводится к получению так называемого минимального покрытия, т.е. покрытия, обладающего минимальной ценой. При этом для получения МДНФ используется единичное покрытие.

Таблица Карно (ТК) это видоизмененная запись таблицы истинности.

Правила построения ТК следующие:

1) Количество клеток ТК равно количеству строк таблицы истинности.

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

3) В клетки заносятся соответствующие значения логической функции (ЛФ).

4) Единичные клетки объединяются в прямоугольники (импликанты) по 2ⁿ клеток.

5) Для каждого прямоугольника записывается конъюнкция тех аргументов, которые в соседних клетках не изменяют своего значения.

6) Переменные входят в конъюнкцию в прямом виде, если их значение в соседних клетках равно 1, в противном случае в обратном.

7) Полученные конъюнкции литералов объединяются через дизъюнкции.

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

 

ПРАКТИЧЕСКАЯ ЧАСТЬ