mustERkennung

mustERkennung … stuff about patterns and their recognition

karnaugh veitch

leave a comment »

Triggerd by Jörgs posting about the simple creation of decission tables for later test cases I remebered a part of my thesis back in 1997: Karnaugh Veitch Diagram. So, I re-LaTexed the specific part and try to describe it here.

Purposes

One uses Karnaugh Veitch Diagram (KVD) to create a formular representation of Boolean expression. A real detailed explanation could be found at Wikipedia. In the case of Jörg’s example, the description of test cases could lead to simple If-Then-Else-Clauses really representing customers needs.

The Example – Step by Step

This is the original example from source page:

Condition A | Y | Y | Y | Y | N | N | N | N |
Condition B | Y | Y | N | N | Y | Y | N | N |
Condition C | Y | N | Y | N | Y | N | Y | N |
---------------------------------------------
Decision 1  |   | X | X |   |   |   |   |   |

First of all you assign every true expression (The columns with ‘X’ in the Decission row) a new symbol. This will result in:

a = A and B and (not C)
b = A and (not B) and C

To have a working demonstration I’ll add a new Decision c:

c = A and B and C

Then you put all the symbols in a table or map. As this is a quite simple example the map does not look very outstanding:

   |   C   |
AB | 0 | 1 |
---+---+---|
00 |   |   |
01 |   |   |
10 |   | b |
11 | a | c |

Then you group symbols with only one difference. Lucky we are, this is a and c, and b and c. The result is:

(A and B and (not C)) or (A and B and C)
(A and (not B) and C) or (A and B and C)

Due to formal sentences in Boolean algebra this could be transformed into:

(A and B) and (C or (not C)), as C or not C = 1 we have: A and B
(A and C) and ((not B) or B), as B or not B = 1 we have: A and C

The combination of both is:

(A and B) or (A and C)

The final expression will be:

A and (B or C)

So, you may have a coding like

if A and (B + C > 0)
then ...
else ...

That could be the usage of Karnaugh Veitch Diagrams.

Written by Rayk Fenske

April 5, 2009 at 7:57 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: