Булевы функции и их форма

 

     Из  таблицы видно, что данная функция  имеет две минимальные ДНФ: , . 

 

     Задание к лабораторной работе №3 

     I. Найти сокращенную ДНФ графическим  методом 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     II. Найти сокращенную ДНФ методом  Блейка 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     III. Найти сокращенную ДНФ методом  Нельсона  

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     IV. Найти сокращенную ДНФ методом  минимизирующих карт 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     VI. Найти все минимальные ДНФ 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     Контрольные вопросы 

     

1. Минимальная дизъюнктивная нормальная форма.
2. Область истинности булевой функции.
3. Интервал.
4. Покрытие области истинности.
5. Сокращенная ДНФ.
6. Алгоритмы построения сокращенной ДНФ (Блейка, Нельсона, минимизирующих карт).
7. Неприводимое покрытие.
8. Тупиковые ДНФ и алгоритм их построения.
9. Метод импликантных матриц (метод Квайна).

 

 

     Лабораторная  работа №4. Контактные и логические схемы 

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

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

       

     соответствует функция  . Схема  

       

     соответствует булева функция  .

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

     Например, контактная схема 

       

     реализуется булевой функцией .

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

     Рассмотрим  схему 

       

     Данная  схема реализуется следующей  формулой  

      .  

     Упростим  ее

 

       

       

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

     Составим  таблицу истинности для булевой  функции, соответствующей требуемой  контактной схеме 

 

     Найдем  для данной булевой функции СДНФ 

       

     Упростим  данную формулу 

       

 

     Данной  формуле соответствует схема 

       

     Контактные  схемы исторически были первыми  техническими средствами реализации булевых  функций. В дальнейшем появилось  много различных устройств, реализующих  булевы функции. Пусть имеется некоторое  устройство имеющее упорядоченных «входов» и один «выход», причем внутренняя структура этого устройства нас не интересует. На каждый из входов могут подаваться два сигнала, которые мы будем обозначать символами 0 и 1. При каждом наборе сигналов на входах и выходе возникает один из сигналов 0 или 1. Причем набор сигналов на входах однозначно определяет сигнал на выходе. Очевидно, что каждое такое устройство реализует булеву функцию.

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

 

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

     Например  схема 

       

     реализуется булевой функцией  

       

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

     Например:  

     

 

       

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

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

       

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