Карти на Карно

Опростяването на логическите изрази може да бъде досадна работа, особено ако трябва да запомняме всичките тези правила. За тези, които имат пространствено-образно мислене може да се окаже по-удобно да се използват така наречените карти на Карно.

Измислени през 1952 от Едуард В. Вейч и усъвършенствани малко по-късно от Морис Карно, физик от Bell Lab, с цел да се опростят цифровите електронни схеми.

Представляват координатна карта на състоянията, която е преустроена по определен начин таблица на истинности. Картите Карно може да се разглежда като плоска разгъвка на n-мерен булев куб.

Известно е, че булевите функции от N променливи имат 2^N различни отношения. Всички тези членове представляват някаква структура, топологично еквивалентна на N-мерен куб, при който всеки две стойности, свързани с ребро, са подходящи за слепване и поглъщане.В клетката на картата на Карно се поставя стойността на функцията за дадения набор. Променливите в редовете и колоните се разполагат така, че съседните клетки на картата да се различават само с един разряд на променливите, т.е. да са съседни

Как ще изглежда една карта на Карно зависи от броя на променливите във формулата.

За две променливи е просто квадрат от 2×2

Илюстрация: psi-logic

Илюстрация: psi-logic

За три променливи е правоъгълник 2×4, със залепени краища във форма на цилиндър.

Илюстрация: psi-logic

За четири променливи е квадрат 4×4, който трябва да се залепи и от двете посоки като се получи тор. Повърхностите, боядисани в сиво, показват, фигурата, която трябва да се получи след залепването. За 5 или 6 променливи вече ще са необходими не повърхности, а обемни фигури, например, за шест променливи е куб със страни от по 4 клетки. Между другото, триизмерни форми могат да се използват и за по-малък брой променливи, за три – 2x2x2 куб, за четири – блок 2x2x4. Но принципът е един и същ навсякъде.

Илюстрация: psi-logic

В картите на Карно трябва да бъдат 2N клетки, където N е броят на променливите. В дадения случай променливите са 4 и клетките 16.

Илюстрация: psi-logic

По ръбовете на картата се пишат променливите, участващи във формулата или на техния номер (1, 2, 3, 4). Да речем,е нашата формула съдържа променливите X, Y, Z, T. За други променливи, принципът е един и същ. До променливите са нарисувани [-образни фигури, показващи областта на картата, към която се отнася променливата. Всяка променлива заема точно половината от картата. На фигурата вляво съответните области за всяка променлива са оцветените с оранжево. Районът, в оцветен в синьо се отнася до същата променлива, но с отрицание:

На константата true съответства напълно оцветена карта, а на константата false – напълно неоцветена.

Илюстрация: psi-logic

Сега, когато знаем как се попълва картата за отделните променливи и константи, ще обясним какво се случва с отделните събираеми, които може да се състоят от няколко променливи и константи, свързани с "&", т.е. от серия множители. За да се запълни част от картата, която се отнася до такава серия, трябва да се намери тази част от картата, която е боядисана за всеки един от множителите. Например, така изглежда множителя: X & Y & ¬ Z. На схемата всеки от трите множителя е показан като полупрозрачно "стъкло". Над две клетки се оказват три "стъкла" и те ще бъдат най-тъмни. Този 2×1 правоъгълник точно съответства на формулата X & Y & ¬ Z.

От този нагледен метод следва правилото за поглъщане за множители. Например x&x – като две еднакви "стъкла", разположени точно едно над друго, нямат ефект.

Такава конструкция нищо няма да промени: едни и същи клетки ще бъдат едновременно под всички стъкла, тоест, x&x = x. На формулата x&¬x съответстват на двете "стъкла", които не се пресичат помежду си. Това означава, че ни една клетка няма да се окаже едновременно под двете стъкла и ще се получи небоядисана карта на Карно, тоест, x&¬x = false.

За формулата X & FALSE може да вземе такава аналогия: стъклото за Х и едно невидимо стъкло колкото прашинка FALSE, неспособно да покрие ни една клетка от картата. В резултат ни една клетка няма да се окаже покрита от две стъкла: x&false = false. На формулата true&x съответства до голямо стъкло, което покрива цялата карта и стъклото покриващо частта на Х. Двете стъкла едновременно ще бъдат само над клетките, покривани от Х, тоест, x&true = x.

Веднъж като са определени оцветените области за всяко събираемо, остава само да ги "съберем" с операцията "". За да направим това, просто боядисваме всички области, на които съответства поне едно събираемо.

Ако се обединят в една дизюнктивна форма всички събираеми, в примера: ¬y ¬y&¬x&¬z&¬t y&x&z&z&t x&¬t,    (1) то ще се получи такава карта:

Илюстрация: psi-logic

:Какви са стъпките:

1. Премахване на излишните знаци за отрицание по формулата ¬¬X = X.
2. Определяне на областта за всеки множител.
3. За всеко събираемо, състоящо се от няколко множителя да се боядиса областта, която се покрива едновременно от всички тези множители.
4. За цялата формула да се оцвети областта, която се покрива поне от едно от събираемите.

През втория етап на се извършват обратните действия. Трябва да се опитаме да си представим колко и какви правоъгълни "стъкла" със страни 1, 2 или 4 клетки са необходими за да се покрие оцветената област и само нея. Точно сега ще ни потрябва добро пространствено въображение (особено ако добавим, че краищата на картите са съединени). След като бъдат определени нужните "стъкла", ни остава само изпълним обратните действия и да напишем получената формула. В нашия пример са достатъчни две "стъкла" (забележка: "стъклото" за Y е съединено отзад на квадрата

Илюстрация: psi-logic

На тези две стъкла съответстват събираемите ¬y и x&¬t. Следователно, след опростяването, формула та(1) приема вида:

¬y x&¬t

Този метод с цветните стъкла изисква може би повече въображение

Следва червърта част