Построение дискретного преобразователя, на основе дизъюнктора, конъюнктора и инвертора, реализуемого проводимость z=f(x1, x2, x3, x4)

 

Министерство  образования Российской Федерации

 

ЗАДАНИЕ

по курсовой работе

 

студенту группы

 

1. Тема: Построение дискретного  преобразователя, на основе дизъюнктора,  конъюнктора и инвертора, реализуемого проводимость z=f(x₁, x₂, x₃, x₄).

2. Срок сдачи работы 20 декабря 2007 года

3. Техническое задание:

     1. Вычислить число N=n₁n₂n₃ + n₁ + n₂ + n₃ + n, где

        n₁ - число букв в фамилии

         n₂ – число букв в имени

         n₃ – число букв в отчестве

         n – номер варианта

    2. Записать N в двоичной системе исчисления

    3. Полученную двоичную запись представить как столбец значений для функции g(x₁, x₂, x₃, x₄) (разряды возрастают сверху вниз), при недостатке заполнить нулями, при избытке убрать лишнее.

   4. Записать функцию f(x₁, x₂, x₃, x₄)=(g(x₁, x₂, x₃, x₄))*

   5. Записать функцию f в СДНФ, СКНФ, в виде полинома Жегалкина

  Выяснить класс принадлежности (T₀, T₁, S, M, L) . Дать ответ является ли система из f полной?

   6. Для f найти сокращенную ДНФ, ДНФ Квайна, ДНФ типа ∑Т, минимальную ДНФ и минимальную КНФ.

   7. Используя минимальную ДНФ и минимальную КНФ, построить дискретный преобразователь на основе конъюнктора, дизъюнктора и инвертора, реализуемого проводимость z=f(x₁, x₂, x₃, x₄)  

 

 

 

 Задание принял к исполнению: 27 сентября   2007 года               

                                                         Руководитель работы_        _ 

АННОТАЦИЯ.

Данная курсовая работа заключается в проектировании дискретного  преобразователя на основе конъюнктора, дизъюнктора и инвертора, реализующего проводимость z=f(x₁, x₂, x₃, x₄) по заданным условиям, при которых необходимо минимизировать функцию f(x₁, x₂, x₃, x₄).При проектировании использовалась учебная, методическая и справочная литература.

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

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

 

СОДЕРЖАНИЕ:

1. Аннотация……………………………………………………………………3

2. Введение……………………………………………………………………..5

3. Расчет числа N………………………………………………………………6

4. Запись в двоичную систему числа  N……………………………………...6

5. Запись таблицы значений  для функции g…………………………………6

6. Запись функции f(x₁, x₂, x₃, x₄) в виде таблицы…………………………...7

7. Запись функции f(x₁, x₂, x₃, x₄) в виде СДНФ, СКНФ,

полинома Жегалкина……………………………………….………………….8

8. Принадлежность к  классам T₀, T₁, S, M, L………………………………..10

9. Запись в виде:

        Сокращенной ДНФ………………………………………………………12

        ДНФ Квайна………………………………………………………………15

        ДНФ типа ∑Т……………………………………………………………..16

        Минимальной ДНФ………………………………………………………18

        Минимальной КНФ………………………………………………………18

10. Построение дискретного преобразователя на основе конъюнктора, дизъюнктора и инвертора, реализующего проводимость z=f(x₁, x₂, x₃, x₄):

Схема 1………………………………………………………………………23

Схема 2………………………………………………………………………24

11. Список литературы………………………………….……………………..25

 

 

 

 

 

ВВЕДЕНИЕ:

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

Обычно входам дискретного  преобразователя ставят в соответствие независимые переменные  x₁,……, x_n ; а выходам - z₁,……, z_n

Работа данного преобразователя  описывается системой функций:

    (1)

Наиболее часто приходится сталкиваться с преобразователями, у которых  входная информация – это набор  нулей и единиц;  и  выходящая  информация также представляется в  таком же виде. Поэтому особый интерес  представляет изучение  функций вида:

,      (2)

которая описывает работу преобразователя.

Над z₂ определены операции сложения, умножения. Эти операции выполнены по модулю 2: сначала идет умножение или сложение, а затем делим на остаток.

Булевой функцией, зависящей от п-переменных будем называть отображение вида (2).

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

К элементарным булевым функциям относятся: константы 0 и 1, дизъюнкция, конъюнкция, импликация, сложение, произведение, операция эквивалентности, штрих Шеффера, отрицание.

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

 

 

 

1.Расчет  числа N:

Вычислим число N по формуле: N=n₁n₂n₃ + n₁ + n₂ + n₃ + n,

где n₁=6, n₂ =4,  n₃ =8, n=6;

Получаем:

N=6*4*8 +6 + 4 + 8 + 6 = 216

 

2.Запись  в двоичную систему числа N:

216= 2⁸ + 2⁷ + 2⁵ + 2⁴

216₁₀ = 11011000₂

 

3.Запись  таблицы значений для функции  g:

Записываем число 0000000011011000₂ в столбец значений в порядке возрастания разрядов, остальные заполняем нулями.

Таблица 1: Задание функции g(x₁, x₂, x₃, x₄) :

X1	X2	X3	X4	g(x1, x2, x3, x4)
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	0

 

 

4. Запись  функции f(x₁, x₂, x₃, x₄) в виде таблицы:

Функция  f(x₁, x₂, x₃, x₄)   является двойственной функции g(x₁, x₂, x₃, x₄). Для нахождения двойственной функции, заданной таблицей упорядоченных значений аргументов, необходимо записать столбец значений исходной функции в обратном порядке, заменив при этом единицы на нули, а нули на единицы.

Получаем запись функции f(x₁, x₂, x₃, x₄) в виде таблицы:

 

Таблица 2: Задание функции f(x₁, x₂, x₃, x₄).

X1	X2	X3	X4	f(x1, x2, x3, x4)
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0
1	1	1	1	0

 

5. Запись функции f в СДНФ, СКНФ, в виде полинома Жегалкина:

Совершенной дизъюнктивной нормальной формой (СДНФ) называется представление функции в виде:

          f(x₁,……, x_n)=   V   x₁˄x₂˄…˄x_n

                              (σ₁,…,σ_n)ϵZ₂ⁿ

                                              f(σ₁,…,σ_n)=1

  

 

 

СДНФ:

 

Совершенной конъюнктивной нормальной формой (СКНФ) называется представление функции в виде:

          f(x₁,……, x_n)=   Ʌ   x₁˅x₂˅…˅x_n

                              (σ₁,…,σ_n)ϵZ₂ⁿ

                                              f(σ₁,…,σ_n)=0

 

СКНФ:

 

Теорема Жегалкина:

Пусть f(x₁,……, x_n)ϵP₂, тогда f представляется единственным образом в виде многочлена от x₁,……, x_n, в котором каждая переменная входит со степенью меньше единицы.

 

Полином Жегалкина:

В соответствии с теоремой запишем многочлен в общем виде:

f(x₁, x₂, x₃, x₄)= ax₁x₂x₃x₄ + bx₁x₂x₃ + cx₁x₃x₄ + dx₁x₂x₄ + ex₂x₃x₄ + fx₁x₂ +

+ gx₁x₃ + hx₁x₄ + ix₂x₃ + jx₂x₄ + kx₃x₄ + lx₁ + mx₂ + nx₃ + px₄ +q

Исходя из общего вида, необходимо посчитать коэффициенты. Для этого нужно подставить набор значений переменных x₁, x₂, x₃, x₄ в формулу многочлена общего вида и приравнять получившиеся уравнения к соответствующим значениям функции f(x₁, x₂, x₃, x₄), тогда получим следующую систему уравнений:

Решая эту систему, получаем значения коэффициентов:

Подставив получившиеся значения коэффициентов в многочлен  общего вида, получили полином Жегалкина  данной функции f(x₁, x₂, x₃, x₄ ) :

 

6. Принадлежность к классам (T₀, T₁, S, M, L):

 

1. Класс T₀ функций, сохраняющих нуль:

Функция f(x₁,……, x_n) принадлежит классу T₀ тогда только тогда, когда f(0,….,0)=0

 

2. Класс T₁ функций, сохраняющих единицу:

Функция f(x₁,……, x_n) принадлежит классу T₁ тогда только тогда, когда f(1,….,1)=1

 

3. Класс S самодвойственных функций:

Функция f(x₁,……, x_n) принадлежит классу S тогда только тогда, когда f(x₁,……, x_n)=( f(x₁,……, x_n))*

 

4. Класс М монотонных функций: