Карта Карно - графический способ представления логической функции, составляемый для формирования минимизированной функции в аналитическом виде.
Для логической функции от четырёх переменных f(a, b, c, d) карта составляется следующим образом:
ab
cd |
00 |
01 |
11 |
10 |
| 00 |
f(0,0,0,0) |
f(0,0,0,1) |
f(0,0,1,1) |
f(0,0,1,0) |
| 01 |
f(0,1,0,0) |
f(0,1,0,1) |
f(0,1,1,1) |
f(0,1,1,0) |
| 11 |
f(1,1,0,0) |
f(1,1,0,1) |
f(1,1,1,1) |
f(1,1,1,0) |
| 10 |
f(1,0,0,0) |
f(1,0,0,1) |
f(1,0,1,1) |
f(1,0,1,0) |
После составления карты в ней выделяют "склейки" - прямоугольные области, удовлетворяющие
двум условиям:
- все значения истинны;
- размер области равен 2n, где n - любое натуральное число.
При этом считают, что первый и последний столбец, а также первая и последняя строки расположены "рядом", то есть в них также можно формировать склейки.
Цель формирования склеек - выделить как можно меньшее их число, для этого склейки должны иметь наибольший размер и могут накладываться друг на друга.
Для логической функции от четырёх переменных требуется составить карту Карно, в которой указать разными цифрами формируемые склейки: самые большие для этой функции (по 8 элементов) - цифрой 4, следующие по размеру (по 4 элемента) - цифрой 3, и т.д.
Входные данные
16 строк, составляющие полную таблицу истинности функции. В каждой строке через пробел записаны значения переменных a, b, c, d и значение функции f в виде нулей и единиц (0 - значение ложно, 1 - значение истинно).
Выходные данные
матрица из 4 строк по 4 цифры, записанных через пробел и соответствующих искомым значениям. Цифры могут принимать значения от 0 до 4.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0 |
0 3 3 0
3 3 3 3
0 0 0 0
0 3 3 2 |
Для заданной функции выделяются склейки во 2-й строке и
в квадрате в первой и последней строках по 4 элемента
(обозначены цифрой 3), а также склейка из двух элементов
в конце 4-й строки. Поскольку она накладывается на
предыдущую склейку, то только второй элемент в ней
обозначен цифрой 2. |
| 2 |
0 0 0 0 1
0 0 0 1 1
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1 |
3 3 0 0
4 4 4 4
4 4 4 4
0 0 0 0 |
Для данной функции выделяется склейка во 2-й и 3-й
строках, она состоит из 8 элементов и обозначается
цифрой 4. Также выделяется квадрат из 4-х элементов
(первые 2 в 1-й и 2-й строках), он накладывается на
большую склейку, поэтому только его половина отмечена
цифрой 3. |