Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Карты Карно

ВВЕДЕНИЕ | Основные логические функции | Аксиомы (тождества) алгебры логики | ПОЗИЦИОННАЯ СИСТЕМА СЧИСЛЕНИЯ И КОДИРОВАНИЕ ЧИСЕЛ | ЛОГИЧЕСКИЕ ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ | АЛГЕБРАИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ | Метод Квайна | Метод карт Карно | Приведение логической функции к базису И-НЕ. | Преобразование ЛФ к базису ИЛИ-НЕ |


Читайте также:
  1. Бесплатные карты и важность позиции
  2. Ваши карты
  3. Воспитание рабов системы. 11 лет под контролем: в школах появились электронные карты
  4. Все полученные данные записать в соответствующие графы индивидуальной карты беременной.
  5. Генетические (кроссоверные) карты
  6. Игра в карты
  7. Исследование карты

При небольшом числе переменных удобным и наглядным является графическое представление логической функции в виде карт минтермов или в виде карт Карно.

Карта Карно состоит из q=2n клеток, причем каждой из клеток соответствует один из q минтермов. Карта представляется в виде квадрата или прямоугольника. Переменные разбиваются на две группы. Переменным одной группы ставят в соответствие столбцы, другой - строки. Переменные первой группы остаются постоянными в пределах каждого столбца, второй - постоянными в пределах строки. Каждой клетке ставится в соответствие определенный набор переменных.

Например, для двух переменных (n=2) имеем q= 22=4 клетки. На рисунках последовательно представлена карта Карно для двух переменных, клетам которой поставлены в соответствие алгебраическое выражение минтерма (рис.12), наборы значений переменных, при которых минтерм равен 1 (рис.13), и числовое (десятичное) представление набора переменных (рис.14).

Х1 0       Х1 0       Х1 0  
Х2   Х1Х2   Х1Х2   Х2       Х2    
    Х1Х2   Х1Х2                

Рис. 12. Рис.13. Рис.14

 

Значение переменной обычно задается в виде

черты по периметру карты:

черта есть – переменная в пределах строки или

столбца равна 1,

черты нет – переменная равна 0.

Рис.15.

Для трех переменных имеем карту Карно из 23=8 клеток, которым соответствуют следующие наборы переменных в двоичном и десятичном представлении. Здесь расположение переменных по битам принято Х1Х2Х3.

 

Рис.16. Рис.17.

__ __ __ __ X1 X2 X3 X4 __ __ __ X1 X2 X3 X4 __ __ X1 X2 X3 X4 __ __ __ X1 X2 X3 X4
__ __ __ X1 X2 X3 X4 __ __ X1 X2 X3 X4 __ X1 X2 X3 X4 __ __ X1 X2 X3 X4
__ __ X1 X2 X3 X4 __ X1 X2 X3 X4   X1 X2 X3 X4 __ X1 X2 X3 X4
__ __ __ X1 X2 X3 X4 __ __ X1 X2 X3 X4 __ X1 X2 X3 X4 __ __ X1 X2 X3 X4

Для четырех переменных имеем карту Карно из 24=16 клеток.


Рис.19. Рис.20.

Здесь каждой клетке карты поставлены в соответствие выражение минтерма (рис.18), двоичное (рис.19) и десятичное (рис.20) представления набора переменных при расположении переменных по битам Х1Х2Х3Х4. При изменении порядка расположения битов изменится десятичное представление.

Аналогично, при n=5 имеем 32 клетки, при n=6 - 64 клетки.

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

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

 

Логическая функция “И”:

Y = X1 Ù X2.

 

 

Рис.21.


Логическая функция “ИЛИ”:

Y = X1 Ú X2 =

= X1 Ù X2 Ú X1 Ù X2 Ú X1 Ù X2.

Рис.22.

 

Логическая функция “Исключающее ИЛИ”:

 

   
   

Рис.23.


Для произвольной логической функции карта Карно представляет собой совокупность клеток, заполненных “1”, каждой из которых соответствует минтерм в СДНФ логических функций.

Например: Х1

       
       
       
       

__ __ __ __

F (X1,X2,X3,X4) = X1 X2 X3 X4 +

__ __ __ __ __ X3

+X1X2X3X4 + X1X2X3X4 + X1X2X3X4 .

 
 


Рис. 24. Функция и ее карта Карно.Х2

Клетки, содержащие 1, называются “1-клетками”, а клетки, содержащие 0, - “0-клетками”. Логические функции, имеющие определенные значения (0 или 1) при всех возможных наборах переменных, называются полностью определенными. Имеются функции, значения которых определены только для части наборов переменных. Такие логические функции называются частично определенными. Те наборы значений аргументов, для которых значение функции не определено, будем называть безразличными, на карте Карно эти клетки будем указывать знаком “ х ”. Этим наборам соответствуют ситуации, которые на практике никогда не реализуются. Частично определенную функцию можно доопределить, приписав безразличным значениям произвольно 0 или 1. Обычно доопределение проводят таким образом, чтобы, используя законы алгебры логики, упростить выражение.


Дата добавления: 2015-07-11; просмотров: 234 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Теорема разложения логических функций.| МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

mybiblioteka.su - 2015-2024 год. (0.009 сек.)