Федеральное агентство по образованию

 

Тульский  государственный университет 

Кафедра «Автоматизированные станочные системы» 
 
 
 
 
 
 
 
 

Контрольно-курсовая работа

по курсу  «Дискретная математика» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил: студ. гр. 620281 Ю. И. Кураева

      ____________

      Проверил: докт. техн. наук, доцент А.Б.Орлов

____________ 
 
 
 
 

Тула 2010 г. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание: 
 

1.Сложение  в шестнадцатеричной, двоичной, восьмеричной  и десятичной системах счисления…………………………………………………………………3стр. 

2.Минимизация  логических функций методами  тождественных преобразований и  S-кубов…………………………………………………………………………6стр.

3.Минимизация  логических функций методом карт  Карно. Построение логических схем………………………………………………………………………..10стр.

4.Построение  графа конченого автомата по общей таблице выходов и переходов. Моделирование работы конечного автомата…………………………...12стр.   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.Сложение  в шестнадцатеричной,  двоичной, восьмеричной  и десятичной системах счисления.   

1)Вычисления целесообразно начать с шестнадцатеричной системы: 

7С₁₆ + B9₁₆ 

Вычисление: 

      C+ 9 = 12₁₀ + 9= 21₁₀, поскольку 21>15, требуется перенос в

      старший разряд      

      21 = 16₁₀ + 5₁₀  

С учетом переноса получаем: 

      7+ B + 1 = 19₁₀ , поскольку 19>15, требуется перенос в старший раз

            ряд. 

      19₁₀ = 16₁₀ + 3 

      Получаем  в старшем разряде 1. 

7С₁₆+В9₁₆=7×16¹ + 11*16¹ + 9×16⁰ + 12×16⁰ = 135₁₆=309₁₀ 

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

      7= 0111₂

      С = 1100₂

      В = 1011₂

      9=1001₂ 

      7С= 0111 1100₂

      В9₁₆=1011 1001₂ 

      Выполним  сложение, учитывая, что 

      0+0= 0

      1+0= 1

      1+1 =10₂

      1+1+1 =11₂ 

      В результате с учетом переносов в старшие разряды получим: 
 

 

      Выполнив  обратный перевод результата в шестнадцатеричную  систему счисления (по тетрадам) можно убедиться в его правильности:

       

      0101₂ = 5

      0011₂ = 3

      0001₂ = 1

      0001 0011 0101₂ = 135₁₆

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

 

      7С= 0111 1100₂ = 01  111  100₂  

      Из  таблицы получаем: 

      01₂ = 1

      111₂ = 7

      100₂=4 

      7С₁₆ = 174₈ 

      Аналогично  получим: 

      В9₁₆=1011 1001₂ = 10    111    001₂   

      10₂ = 2

      111₂ = 7

      001₂ = 1 

      В9₁₆ = 271₈ 
 

      Осуществим  поразрядное сложение 174₈ + 271₈  
 

      В результате получим:

 

      Вычисления  выполняются аналогично шестнадцатеричной  системе 

      4 + 1 = 5₁₀ ,

      7 + 7 = 14₁₀ , поскольку 14>7 требуется перенос в старший

        разряд    

       

      14₁₀ = 8₁₀ + 6  

      1 + 2+1 = 4₈ 

      Таким образом:  

      174₈ + 271₈ = 465₈ 

      Выполним проверку путем перевода результата в двоичную и шестнадцатеричную системы счисления 

       

      5₈ = 101₂

      6₈ = 110₂ 

      4₈ = 100₂   

      Отсюда  получим 

      465₈ = 100  110   101₂ = 0001 0011 0101₂ = 135₁₆    

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

      7C= 7× 16¹+12× 16⁰=112₁₀+16₁₀=124₁₀

      B9₁₆= 11× 16¹+9× 16⁰=185₁₀ 

      124₁₀+185₁₀=309₁₀ 

      135₁₆=1₁₀×16²+3×16+5×16⁰ =256+48=309₁₀ 

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

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

      Логическая функция задана следующей таблицей соответствия: 

 

      Здесь   аргументы функции, а входные слова – наборы значений аргументов.

      На  основе данной таблицы можно получить аналитическое выражение для логической функции в совершенной дизъюнктивной или конъюнктивной нормальной формах (СДНФ или СКНФ). Элементы СДНФ называют минитермами, а СКНФ – макстермами. СДНФ представляет собой дизъюнкцию минитермов, а СКНФ – конъюнкцию макстермов . Легко обнаружить, что минитерм равен 1 только при одном единственном входном слове, а макстерм равен 0 также только при одном единственном входном слове. Аналитическое выражение функции в форме СДНФ будет содержать конституенты единиц (и только их) для входных слов, при которых функция =1, а в форме СКНФ будет содержать конституенты нулей (и только их) для входных слов, при которых функция =0. При этом, если аргумент во входном слове =1, он входит в конституенту единицы в прямой форме, а в конституенту нуля – в инверсной. И наоборот, если аргумент во входном слове =0, он входит в конституенту нуля в прямой форме, а в конституенту единицы – в инверсной.      

      В результате для заданной функции  можно получить следующие аналитические выражения в форме СДНФ:  

        
 

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

     Каноническая  задача синтеза логических схем сводится к минимизации булевых функций, т. е. к представлению их в дизъюнктивной  нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением закона склеивания и закона поглощения . Здесь под a и b можно понимать любую формулу алгебры логики.  

     Минимизируем  булевы функции: 

Начинаем  склеивание входных слов в форме СДНФ: 

       

     Путем склеивания мы получили минмальную форму . 

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

      Отобразим логическую функцию в логическом пространстве. Легко обнаружить, что данная логическая функция будут задана только в вершинах куба с длиной ребра, равной 1. Отметим (зачерним) все вершины (точки в логическом пространстве), в которых функция равна 1.     

      Для каждой вершины можно записать соответствующую  ей конституенту единицы. Легко обнаружить, что к конституентам единиц для точек, принадлежащих одному ребру можно применить закон склеивания. Тогда для ребер появятся новые конституенты, содержащие уже только две переменные. Аналогично к подобным конституентам для двух параллельных ребер, принадлежащих одной грани, также можно применить закон склеивания и получить значения переменных или их инверсий, выступающие в качестве конституент, соответствующих граням. Тогда конституенты, соответствующие ребрам могут быть получены как конъюнкции конституент граней, на пересечении которых данное ребро находится.      

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

      Рисунок 1 

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

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

        

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

         
 
 
 
 
 
 
 
 
 
 

В итоге  получаем минимальную функцию .  

      Таким образом, результат минимизации  методом S-кубов проверен тождественными преобразованиями.

3.Минимизация  логических функций  методом карт Карно. Построение логических схем. 

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

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

 

      Отобразим данную функцию на карте Карно, проставив 1 в ячейки карты, соответствующие  входным словам, при  которых функция =1. Ребрам, граням и кубам на карте Карно соответствуют ортогональные области (блоки  – строки, столбцы, квадраты, прямоугольники) заполненные 2, 4 и 8 единицами.

          
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

        В результате минимальная форма будет иметь вид: 

        

      Для полученной минимальной формы логическая схема будет иметь вид: 
 
 
 
 
 
 
 
 
 
 
 
 
 

  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.Построение  графа конченого  автомата по общей  таблице выходов  и переходов. Моделирование работы конечного автомата.   

      Таблицa состояний и переходов конечного автомата: 
 

 
 

      В данной таблице указано, какие слова обозначают те или иные элементы таблицы. Построение графа начинается с построения четырех вершин, соответствующих четырем состояниям автомата. Затем построение ведется по строкам таблицы. Из соответствующей вершины для каждого входного слова X в графе проводится соответствующая дуга. Концом дуги будет вершина, соответствующая состоянию, в которое перейдет автомат в следующем такте, если на его вход подано слово X. Около каждой дуги указывается ее вес – в числителе входное слово, при котором произойдет данный переход, а в знаменателе – выходное слово, которое при этом установится.

      Подобное  построение осуществляется для каждого  исходного состояния конечного  автомата (каждой строки).  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

      По  графу осуществляем моделирование работы автомата при подаче на него некоторой последовательности входных слов. Для каждого входного слова и данного состояния по графу определяется выходное слово и состояние в следующем такте S(n+1). Затем процедура повторяется для этого нового состояния и т.д. Таблица моделирования работы автомата приведена ниже: