Карты Карно
Карта Карно для функции трех переменных состоит из 8 клеток и имеет обычно 2 строки и четыре столбца. На верхней стороне прямоугольника каждому столбцу ставится в соответствие одна комбинация входных переменных х1 и х2. Причем, при переходе от каждого столбца к соседнему имеет право измениться только одна переменная, а первый и последний столбцы карты также считаются соседними. В карте трех переменных каждая клетка имеет три соседние.
Или
|
х1х2 |
00 |
01 |
11 |
10 |
|
|
х3 |
0 |
|
|
|
|
|
1 |
|
|
|
|
|
Пример
6:
Построить карту Карно для функции
Для начала построим таблицу истинности. Для этого будем подставлять всевозможные комбинации входных значений в функцию и вычислять значение F по правилам булевой алгебры
Всего в таблице будет 2n строк, где n – число переменных
1
строка:
Находим значение для F во всех остальных строках и формируем таблицу
|
x |
y |
z |
F |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Теперь заполняем карту Карно:
|
x y |
00 |
01 |
11 |
10 |
|
|
z |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
|
Минимизация логических функций
Законы и теоремы булевой алгебры позволяют минимизировать (упростить) логическое выражение. При небольшом количестве переменных минимизацию удобно осуществлять непосредственно по карте Карно. Если в карте Карно встречаются группы из 2-х, 4-х, 8-ми и т.д. соседних ячеек, содержащих единицы, которые можно выделить контуром в виде квадрата или прямоугольника, то такая группа может быть описана одним логическим произведением. В это произведение входят только неизменные для всех ячеек данной группы переменные.
Пример 7: Минимизируем функцию из примера 6 при помощи карты Карно
Карту Карно мы уже построили, теперь объединим ячейки, содержащие 1
|
x y |
00 |
01 |
11 |
10 |
|
|
z |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
|
Так в произведение входят неизменные переменные, то получим F=f1+f2:
f1 (две 1): переменная x в обоих ячейках – неизменный 0, переменная z в обоих ячейках – неизменная 1, а переменная y меняет свое значение с 0 на 1, то есть в конечную функцию войдут только переменные x и z. Теперь определим, как именно запишем эти переменные. Так как z в ячейках имела 1, то так ее и запишем, а у x было значение 0, значит, мы запишем ее инверсию. f1=xz
f2: Так как ячейка всего одна, то мы записываем все переменные, используя тот же принцип. f2=xyz
Итого минимизированная функция выглядит так:
