Методические указания к РГР "Синтез логической схемы"
учебно-методический материал на тему

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗАВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ГРАЖДАНСКОЙ  АВИАЦИИ

АВИАЦИОННО-ТРАНСПОРТНЫЙ КОЛЛЕДЖ

Н. А. Юновидова

М А Т Е М А Т И К А

Методические указания к выполнению

расчётно-графической работы по математической логике

для специальностей  100120 «Сервис на воздушном транспорте» и

190701 «Организация перевозок и управление на  воздушном транспорте»

Санкт-Петербург

2012 г.

Пояснительная записка

    Данные методические указания составлены на основе примерной программы дисциплины «Математика», утверждённой Министерством РФ для специальностей 100120 «Сервис на воздушном транспорте» и 190701 «Организация перевозок на воздушном транспорте». Согласно программе учащиеся должны ознакомиться с методами анализа и синтеза логических устройств. Усвоение этого материала отрабатывается и контролируется выполнением расчётно-графической работы.

    В методические указания включены основные теоретические сведения по математической логике, необходимые для выполнения расчётно-графической работы.  Даны методические рекомендации по выполнению задания и разобраны примеры решения задач, аналоги которых включены в расчётно-графическую работу. Приведено 60 вариантов заданий для расчётно-графической работы по синтезу логической схемы.

Введение

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

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

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

О С Н О В Ы   М А Т Е М А Т И Ч Е С К О Й  Л О Г И К И

1.  ВЫСКАЗЫВАНИЯ  И  ЛОГИЧЕСКИЕ  ПЕРЕМЕННЫЕ

   Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.

Пример 1.

 1)  «7  - простое число»;

2)  «Киев – столица России»;

3)  «x + y = 4 ».

    Первое и второе предложения являются высказываниями, причём первое из них истинно, а второе – ложно. Третье предложение высказыванием не является.

   На высказывание можно смотреть как на величину, которая принимает одно из двух значений: «истина», «ложь». Поэтому каждому высказыванию можно поставить в соответствие логическую переменную, которая принимает значение 1, если высказывание истинно и 0, если высказывание ложно.

   Первому высказыванию из рассмотренного выше примера можно сопоставить логическую переменную , а второму  –    и при этом   = 1, а   = 0.

   Будем высказывание называть простым (элементарным), если оно рассматривается как некоторое единое целое, и сложным (составным), если оно образовано из простых высказываний с помощью логических связок «не», «и», «или», «если …, то…», «тогда и только тогда»,…  

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

2.  ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД ВЫСКАЗЫВАНИЯМИ

   Отрицанием (инверсией) высказывания  называется новое высказывание   (читается «не »), которое истинно, когда  ложно и ложно, когда  истинно.

    Дизъюнкцией (логической суммой) двух высказываний  и    называется новое высказывание  ⋁  (читается « или »), которое истинно только тогда, когда хотя бы одно из данных высказываний истинно.

   Конъюнкцией (логическим произведением) двух высказываний   и    называется новое

высказывание,  обозначаемое   ⋀  или  &  (читается « и »), которое истинно только тогда, когда оба высказывания     и    истинны.

    Импликацией двух высказываний   и    называется новое высказывание       (читается «если , то  »), которое ложно тогда и только тогда, когда  истинно, а  ложно.

    Эквивалентностью  двух высказываний    и   называется новое высказывание       (  ,   ), которое истинно тогда и только тогда, когда   и    одновременно либо истинны либо одновременно ложны (читается « эквивалентно »).

   Введённые операции можно проиллюстрировать с помощью таблицы истинности, которая содержит количество строк равное , где  n – число участвующих в операциях

переменных.

Таблица № 1

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

3. ФОРМУЛЫ  И ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

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

   Если скобок нет, то операции выполняются в следующем порядке:  ⋀,⋁,,, .

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

    Функция  f(,,…,) от n переменных называется булевой, если она и каждая из её переменных могут принимать только одно  из двух значений  1 или 0.

     Число булевых функций от n переменных равно . Так    функций одной переменной будет  4 (таблица № 2), а двух переменных -  16.

Таблица № 2

  В таблице №3 приведём наиболее важные функции двух переменных (из 16 возможных в ней представлено 7).

таблицa № 3

 = ⋁ – дизъюнкция («  или »),

 =  ⋁  – дизъюнкция (« и »),

 =     – импликация («если , то  »),

 =    – эквивалентность (« эквивалентно »),

 =  =    – сложение по модулю два («или , или »),

=   =  | – штрих Шеффера (« не совместимо с »),

 =   =      – стрелка Пирса («ни , ни »).

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

Пример 2.   Рассмотрим две функции

 ( ) = ( ) ⋁ ⋀ (  )  и   ( ) =  ⋀ ( )⋀( ).

Построим для них таблицы истинности:

Таблица № 4

Таблица №5

Сравнивая таблицы истинности (последние столбцы), видим, что функции равны. Этот факт можно записать  ( ) = ( )  или  ( )  ( ).

4. НОРМАЛЬНЫЕ ФОРМЫ

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

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

Примеры функционально полных систем:

,  ,   ,  ,   ,   ,  ,  ,…

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

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

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

1. Для любого набора значений переменных , , …,, на которых функция f(,, … ,) равна 1, выписываются конъюнкции всех переменных, над теми переменными, которые в этих наборах равны 0, ставится отрицание; все такие конъюнкции соединяются знаком дизъюнкции. Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции  f(,,… ,).

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

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

Пример 3.

Таблица  № 6

Для функции , заданной таблицей № 6, руководствуясь правилом 1,  запишем СДНФ:

(,,z) =   ⋁     ⋁  y ⋁   ⋁     ⋁   .

2.   Если для каждого набора значений переменных  , ,… ,,  на котором функция   f(,, … ,) равна 0, выписать дизъюнкции всех переменных и над теми переменными, которые в этих наборах равны 1, поставить отрицание, а затем все такие дизъюнкции соединить  знаком конъюнкции, то полученная таким образом формула называется совершенной конъюнктивной нормальной формой (СКНФ) логической функции  

f (,, … ,).

   Пользуясь вторым правилом, получаем СКНФ для функции   , заданной таблицей №6:

= ( ⋁  ⋁ ) (  ⋁  ⋁ z).

СКНФ также как и СДНФ единственна. Так как совершенные нормальные формы единственны, то используя их можно установить, являются ли рассматриваемые функции равными.

5.  МИНИМИЗАЦИЯ БУЛЕВЫХ ФОРМУЛ

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

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

 Карта Карно для функции двух переменных            Карта Карно для функции трёх переменных

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

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

  Пример  4.

1. Минимизация СДНФ.

    Заносим в клетки карты КАРНО значения функции  из таблицы № 6, затем  соседние клетки, которые подлежат склеиванию,  обводим.

Таблица № 7

В результате склеивания получаем минимальную дизъюнктивную нормальную форму (МДНФ):    =    ⋁ z ⋁  .

    Если склеивание единичных клеток проводить  согласно таблице № 6, то получим вторую МДНФ для рассматриваемой функции.

Таблица № 8

=   ⋁ y  ⋁  .

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

2. При отыскании МКНФ поступают аналогично, но склеиванию подлежат нулевые клетки.

Таблица № 9

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

МКНФ:

= ( ⋁  ⋁ ) (  ⋁ y ⋁ z).

Для функции провести минимизацию самостоятельно.

6. РЕАЛИЗАЦИЯ ОСНОВНЫХ ЛОГИЧЕСКИХ ОПЕРАЦИЙ

        Любая информация, представленная в двоичном коде, в цифровом дискретном устройстве представляется в виде набора 0 и 1. Пусть символу 0 соответствует, например, отсутствие тока в электрической цепи, а символу 1 – наличие тока. Такого рода сигнал легко формируется с помощью электрического последовательного ключа:

?

5в

                              Рис. 1.

    Когда переключатель А разомкнут, сигнал на выходе имеет значение 0, когда замкнут – значение 1.

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

   Согласно ГОСТу ЕСКД  логические схемы обозначаются следующим образом:

Дизъюнктoр                                         Конъюнктор                                    Инвертор

Это основные логические операции. Следует отметить, что дизъюнкторы  и  конъюнкторы  могут иметь более двух входов. В некоторых устройствах иногда используются:

    Стрелка  Пирса                                                        Штрих Шеффера

7. СИНТЕЗ  ЛОГИЧЕСКОЙ  СХЕМЫ

   Синтез – это соединение разрозненных частей в единое целое.

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

                                 Методика синтеза логических схем

1. Формализация словесного задания схемы (сводится к выявлению набора переменных, на которых функция равна 1 и 0, разумеется, если задача задана корректно).
2. Составление таблицы истинности.
3. Стандартное каноническое описание функционирования схемы с помощью логических функций, т.е. запись в СДНФ (СКНФ).
4. Выбор базиса.
5. Минимизация логической функции.
6. Построение ЛС, соответствующей логической функции (построение ЛС по минимизированной логической функции включает в себя выполнение всех логических операций, указанных в выражении функции).
7. Проверка правильности работы ЛС (возможна частичная  или полная проверка).

В зависимости от конкретной задачи некоторые этапы могут быть опущены.

Пример 5.

   Для функции  , заданной таблицей № 6 и рассмотренной ранее, уже были найдены минимальные нормальные формы:

МДНФ:

=   ⋁ z ⋁  .

МКНФ:

= ( ⋁  ⋁ ) (  ⋁ y ⋁ z).

                    Строим по ним соответствующие схемы.

Рис. 2.

Рис. 3.

При выполнении задания  необходимо:

1. Для заданной функции составить таблицу истинности.
2. Записать СДНФ и СКНФ.
3. С помощью карт Карно минимизировать нормальные формы.
4. Построить логические схемы.

Пример 6.

     Для булевой функции      f(, , , u) =(( ) ⋀ (  ( ⋁u))   в наборе    синтезировать логическую схему.

Решение

1. Ради удобства записи в таблице истинности обозначим

 =  ,

 =   =  ,

 =   =  ,

 = (  ) =  ,

 =  ⋁ u,

 =    ⋁u  =  ,

 =  ⋀ .

Составляем таблицу истинности для функции  f(, , , u):

Таблица № 10

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

СДНФ:

  f =     ⋁     ⋁     ⋁     ⋁    ⋁     ⋁     ⋁    ⋁    ⋁ ⋁    ⋁     ⋁ ;

СКНФ:

f = ( ⋁  ⋁ ⋁ ) ( ⋁  ⋁ z ⋁  ) ( ⋁  ⋁  ⋁  ) (  ⋁   ⋁ z ⋁ ).

3. Минимизируем полученные совершенные нормальные формы  с помощью карты Карно.

Таблица № 11

Склеивая единичные соседние клетки, как это показано в таблице № 11, получаем минимальную дизъюнктивную нормальную форму (МДНФ) функции:

f =  ⋁  ⋁.

Таблица № 12

Минимальная конъюктивная нормальная форма получается склеиванием (см. таб. № 11) соседних нулевых клеток:

f = (x ⋁  ⋁   ) (  ⋁ z ⋁ u).

   Видим, что нормальные  формы данной функции  при минимизации существенно упростились.

4. Строим схему для МДНФ (рис. 9) схему для МКНФ (рис. 10).

Рис. 9.

Рис. 10.

Расчётно-графическая работа

   Синтезировать логическую схему для заданной булевой функции  f = f (,,)  в системе функций .

1.    f (,,) =
2.   f (,,) = ( ⋀  );
3.    f (,,) = ;
4.    f (,,) =  ⋀ ⋁( );
5.    f (,,) =   (⋁ ( ⋀ ()));
6.    f (,,) = ( ⋁  )  z;
7.    f (,,) = ;
8.    f (,,) = (⋀  z) ;
9.     f (, , z) = ;
10. f (,,) = ()  ;
11. f (,,) =  ⋀ z ⋁ ;
12. f (,,) = (  )⋀;
13. f (,,) = z ⋀ (  y) ⋁ ;
14. f (,,) = (  z) ⋀ ;
15. f (,,) =    );
16. f (,,) = );
17. f (,,) = (  )  ( ⋁ );
18. f (,,) = ;
19. f (,,) = ( ⋁ y) ( y);
20. f (,,) =   |  ;  
21. f (,,) =   ( ⋀ );
22. f (,,) = (  ⋁ )  (z ⋀ y);
23. f (,,) = ;
24. f (,,) = ( ⋁)  ;
25. f (,,) = ;
26. f (,,) = (;
27. f (,,) = (  ) | ;    
28. f (,,) =   ( ⋁ ( ⋀ ));
29. f (,,) =(|( ⋀ )) ⋀ (  (  )) ⋀ (  |();
30. f (,,) = ( ;
31. f (,,) = ;
32. f (,,) = (  )   ;
33. f (,,) =((  ) ) ;
34. f (,,) = (( )  ) ;
35. f (,,) = ( ) ⋀ ( 
36. f (,,) = (  (  ))  ;
37. f (,,) = ( )  (  );
38. f (,,) =     ( ⋁ ( ⋀ ));
39. f (,,) =  ⋁   ;
40. f (,,) = ( )    ( ⋁);
41.  f (,,) = ( )  (  );
42. f (,,) = ( ⋁ )   ;
43. f (,,) = ( )  ⋀);
44. f (,,) = (  ) ⋁ ;
45. f (,,) = (  ) ( );
46. f (,,) = (⋁)  ( );
47. f (,,) =   (  );
48. f (,,) = (( ⋁)  ;
49. f (,,) = (  ) ⋁ (  );
50. f (,,) =(    ) ⋁ ;
51. f (,,) =  ⋀ ( | ) ⋁ (  );
52. f (,,) =  ⋁ (  );
53. f (,,) = ( ) ⋁ ( );
54. f (,,) = ( ⋁)  (  );
55. f (,,) = ⋀ ( ) ⋁  ⋀ ( );
56. f (,,) = ⋁ (   ⋀);
57. f (,,) = ( ⋀   ) ⋀ ( ⋀  ) ⋀  (  );
58. f (,,) = (| )  (  ⋀ y  );
59. f (,,) = (⋁ (  )) ;
60. f (,,) =  ⋁ (  ).

 Литература

1. Осипова В.А.

 Основы дискретной математики. М.: ФОРУМ -  ИНФРА-М, 2006.

2. Москинова Г.И.

 Дискретная математика.  М.:  Логос, 2004.

3. Макоха А.Н., Сахнюк П.А., Червяков Н.И.

 Дискретная математика.  М.:ФИЗМАТЛИТ, 2005.

Оглавление

1.   Введение
2. Высказывания и логические переменные.
3. Основные логические операции над высказываниями
4. Формулы и функции алгебры логики
5. Нормальные формы
6. Минимизация булевых формул
7. Реализация основных логических операций
8. Синтез логической схемы
9. Варианты задания для расчётно-графической работы

Список литературы