Карта Карно

Материал из Циклопедии
Перейти к: навигация, поиск
Лекция 80. Карта Карно // Электротехника и электроника для программистов [9:41]

Карта Карно — это таблица истинности определённого вида для логической функции — была предложена в 1952 г. американским учёным Эдвардом В. Вейчем и усовершенствована в 1953 году американским физиком Морисом Карно.

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

Содержание

[править] Виды карт Карно:

[править] Для функции двух переменных

КК02.JPG

[править] Для функции трёх переменных

КК03.JPG

[править] Для функции четырёх переменных

КК04.JPG

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

[править] Примеры использования карт Карно:

[править] Функция двух переменных

[math]f(x_1,x_2)=(0110)[/math]

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

КК22.JPG

[править] Построение МДНФ

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

МДНФ20.JPG

Единицы карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным конъюнкциям двух аргументов.

[math]P_1(x_1,x_2)=\{(1,2)\}[/math]
[math]P_2(x_1,x_2)=\{(2,1)\}[/math]
[math]f_{\text{МДНФ}}(x_1,x_2)=\left(\bar{x}_1 \land x_2\right)\lor\left(x_1 \land \bar{x}_2\right)[/math]

[править] Построение МКНФ

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

МКНФ20.JPG

Нули карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным дизъюнкциям двух аргументов.

[math]P_1(x_1,x_2)=\{(1,1)\}[/math]
[math]P_2(x_1,x_2)=\{(2,2)\}[/math]
[math]f_{\text{КДНФ}}(x_1,x_2)=\left(x_1 \lor x_2\right)\land\left(\bar{x}_1 \lor \bar{x}_2\right)[/math]

[править] Функция трёх переменных

[math]f(x_1,x_2,x_3)=(01001101)[/math]

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

КК23.JPG

[править] Построение МДНФ

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

МДНФ21.JPG

Единицы карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что два неполных прямоугольника вида 2х1 соответствуют одному полному прямоугольнику покрытия.

МДНФ11.JPG

[править] Построение МКНФ

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

МКНФ21.JPG

Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.

МКНФ11.JPG

[править] Функция четырёх переменных

ЛФ41.JPG

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

КК24.JPG

[править] Построение МДНФ

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

МДНФ22.JPG

Единицы карты Карно минимально покрываются тремя квадратами вида 2х2, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что четыре угловых неполных квадрата соответствуют одному полному квадрату покрытия.

МДНФ12.JPG

[править] Построение МКНФ

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

МКНФ22.JPG

Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.

МКНФ12.JPG

[править] Другие понятия:

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты