Карта Карно — различия между версиями
| Строка 1: | Строка 1: | ||
'''Карта Карно''' — это [[таблица истинности]] определённого вида для логической функции — была предложена в 1952 г. американским учёным Эдвардом В. Вейчем и усовершенствована в 1953 г. американским физиком Морисом Карно. | '''Карта Карно''' — это [[таблица истинности]] определённого вида для логической функции — была предложена в 1952 г. американским учёным Эдвардом В. Вейчем и усовершенствована в 1953 г. американским физиком Морисом Карно. | ||
[[Трёхмерная карта Карно|Карты Карно]] используются для минимизации нормальной формы булевых функций, т.е. для построения [[МДНФ]] и [[МКНФ]]. | [[Трёхмерная карта Карно|Карты Карно]] используются для минимизации нормальной формы булевых функций, т.е. для построения [[МДНФ]] и [[МКНФ]]. | ||
| − | |||
== Виды карт Карно: == | == Виды карт Карно: == | ||
=== Для функции двух переменных === | === Для функции двух переменных === | ||
[[файл:КК02.JPG]] | [[файл:КК02.JPG]] | ||
| − | |||
=== Для функции трёх переменных === | === Для функции трёх переменных === | ||
[[файл:КК03.JPG]] | [[файл:КК03.JPG]] | ||
| − | |||
=== Для функции четырёх переменных === | === Для функции четырёх переменных === | ||
[[файл:КК04.JPG]] | [[файл:КК04.JPG]] | ||
| − | |||
* Заметим, что в картах Карно наборы аргументов в соседних строках и столбцах (включая первые и последние) отличаются значением одного аргумента. | * Заметим, что в картах Карно наборы аргументов в соседних строках и столбцах (включая первые и последние) отличаются значением одного аргумента. | ||
* Для функций пяти и шести аргументов можно применять [[Трёхмерная карта Карно|трёхмерную карту Карно]]. | * Для функций пяти и шести аргументов можно применять [[Трёхмерная карта Карно|трёхмерную карту Карно]]. | ||
| − | |||
== Примеры использования карт Карно: == | == Примеры использования карт Карно: == | ||
| − | === Построение МДНФ === | + | === Функция двух переменных === |
| − | Строим карту Карно для функции четырёх переменных | + | [[файл:ЛФ21.JPG]] |
| + | |||
| + | Строим карту Карно для функции двух переменных | ||
| + | |||
| + | [[файл:КК22.JPG]] | ||
| + | ==== Построение МДНФ ==== | ||
| + | Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной | ||
| + | '''2<sup>n</sup>'''. | ||
| + | |||
| + | [[файл:МДНФ20.JPG]] | ||
| + | |||
| + | Единицы карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным конъюнкциям двух аргументов. | ||
| + | |||
| + | [[файл:МДНФ10.JPG]] | ||
| + | ==== Построение МКНФ ==== | ||
| + | Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной | ||
| + | '''2<sup>n</sup>'''. | ||
| + | |||
| + | [[файл:МКНФ20.JPG]] | ||
| + | |||
| + | Нули карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным дизъюнкциям двух аргументов. | ||
| + | |||
| + | [[файл:МКНФ10.JPG]] | ||
| + | === Функция трёх переменных === | ||
| + | [[файл:ЛФ31.JPG]] | ||
| + | |||
| + | Строим карту Карно для функции трёх переменных | ||
| + | |||
| + | [[файл:КК23.JPG]] | ||
| + | ==== Построение МДНФ ==== | ||
| + | Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной | ||
| + | '''2<sup>n</sup>'''. | ||
| + | |||
| + | [[файл:МДНФ21.JPG]] | ||
| + | |||
| + | Единицы карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что два неполных прямоугольника вида 2х1 соответствуют одному полному прямоугольнику покрытия. | ||
| + | |||
| + | [[файл:МДНФ11.JPG]] | ||
| + | ==== Построение МКНФ ==== | ||
| + | Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной | ||
| + | '''2<sup>n</sup>'''. | ||
| + | |||
| + | [[файл:МКНФ21.JPG]] | ||
| + | |||
| + | Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов. | ||
| + | |||
| + | [[файл:МКНФ11.JPG]] | ||
| + | === Функция четырёх переменных === | ||
[[файл:ЛФ41.JPG]] | [[файл:ЛФ41.JPG]] | ||
| + | Строим карту Карно для функции четырёх переменных | ||
| + | |||
| + | [[файл:КК24.JPG]] | ||
| + | ==== Построение МДНФ ==== | ||
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной | Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной | ||
'''2<sup>n</sup>'''. | '''2<sup>n</sup>'''. | ||
| Строка 28: | Строка 74: | ||
[[файл:МДНФ12.JPG]] | [[файл:МДНФ12.JPG]] | ||
| − | + | ==== Построение МКНФ ==== | |
| − | === Построение МКНФ === | + | |
| − | + | ||
| − | + | ||
| − | + | ||
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной | Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной | ||
'''2<sup>n</sup>'''. | '''2<sup>n</sup>'''. | ||
| Строка 41: | Строка 83: | ||
[[файл:МКНФ12.JPG]] | [[файл:МКНФ12.JPG]] | ||
| − | |||
== Другие понятия: == | == Другие понятия: == | ||
* [[логическая функция]]; | * [[логическая функция]]; | ||
| Строка 48: | Строка 89: | ||
* [[таблица истинности]]; | * [[таблица истинности]]; | ||
* [[трёхмерная карта Карно]]. | * [[трёхмерная карта Карно]]. | ||
| − | |||
== Ссылки == | == Ссылки == | ||
* Википедия | * Википедия | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Дискретная математика]][[Категория:Логика]] | [[Категория:Дискретная математика]][[Категория:Логика]] | ||
Версия 15:59, 15 января 2016
Карта Карно — это таблица истинности определённого вида для логической функции — была предложена в 1952 г. американским учёным Эдвардом В. Вейчем и усовершенствована в 1953 г. американским физиком Морисом Карно. Карты Карно используются для минимизации нормальной формы булевых функций, т.е. для построения МДНФ и МКНФ.
Виды карт Карно:
Для функции двух переменных
Для функции трёх переменных
Для функции четырёх переменных
- Заметим, что в картах Карно наборы аргументов в соседних строках и столбцах (включая первые и последние) отличаются значением одного аргумента.
- Для функций пяти и шести аргументов можно применять трёхмерную карту Карно.
Примеры использования карт Карно:
Функция двух переменных
Строим карту Карно для функции двух переменных
Построение МДНФ
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Единицы карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным конъюнкциям двух аргументов.
Построение МКНФ
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Нули карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным дизъюнкциям двух аргументов.
Функция трёх переменных
Строим карту Карно для функции трёх переменных
Построение МДНФ
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Единицы карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что два неполных прямоугольника вида 2х1 соответствуют одному полному прямоугольнику покрытия.
Построение МКНФ
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
Функция четырёх переменных
Строим карту Карно для функции четырёх переменных
Построение МДНФ
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Единицы карты Карно минимально покрываются тремя квадратами вида 2х2, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что четыре угловых неполных квадрата соответствуют одному полному квадрату покрытия.
Построение МКНФ
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
Другие понятия:
Ссылки
- Википедия
- Участник:Logic-samara
