Wikiszótár

Quine-McCluskey-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkvjinɛmt͡sluʃkɛiɒlɡoritmuʃ]

Főnév

Quine-McCluskey-algoritmus

  1. (matematika, algoritmusok)

Quine-McCluskey-algoritmus

A Quine-McCluskey-algoritmus egy módszer a logikai függvények minimális diszjunktív normálformájának (DNF) vagy minimális konjunktív normálformájának (KNF) megtalálására. Az algoritmus hatékonyan alkalmazható kisebb változós rendszerek logikai egyszerűsítésére, és gyakran használják a Karnaugh-térkép helyettesítésére.


Fő cél

Adott egy logikai függvény igazságtáblája, az algoritmus célja: 1. Prime implikánsok azonosítása (olyan kifejezések, amelyek minimálisak, de lefedik a függvény igazságos esetét). 2. Az igazságos eseteket lefedő esszenciális prime implikánsok megtalálása. 3. A függvény minimális alakjának meghatározása.


Algoritmus lépései

1. Igazságtábla reprezentálása mintermekkel

  • Minden olyan kombinációt (minterm), amelynél a kimenet (1), bináris számként reprezentálunk.

2. Mintermek csoportosítása

  • A mintermeket a bennük lévő (1)-ek száma szerint csoportosítjuk.

3. Párosítás és egyszerűsítés

  • A mintermeket párosítjuk, ha csak egy változó különbözik köztük. Az eltérő bit helyén „-” jelet használunk a megkülönböztetés jelzésére.
  • Az újonnan generált kifejezések nem vesznek el információt, de általánosabbá válnak.

4. Prime implikánsok meghatározása

  • Azokat az implikánsokat, amelyek nem egyszerűsíthetők tovább, prime implikánsoknak nevezzük.

5. Esszenciális prime implikánsok kiválasztása

  • Olyan prime implikánsok kiválasztása, amelyek egyedül lefedik az igazságtábla egyes (1)-es kimeneteit.

6. Lefedési mátrix

  • Készítsünk egy mátrixot, amely megmutatja, hogy mely mintermeket mely prime implikánsok fedik le.
  • A minimális lefedési probléma megoldásával meghatározzuk a logikai függvény egyszerűsített alakját.


Példa

1. Igazságtábla

Adott az (f(A, B, C) = (1, 3, 7)) függvény, ahol a mintermek (1, 3, 7):

(A) (B) (C) (f(A, B, C))
0 0 0 0
0 0 1 1 ((1))
0 1 0 0
0 1 1 1 ((3))
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1 ((7))

2. Bináris reprezentáció

Minterm Bináris (1)-ek száma
1 001 1
3 011 2
7 111 3

3. Párosítás és egyszerűsítés

  1. Első lépés:
    • Párosítsunk olyan mintermeket, amelyek csak egy bitben különböznek:
      • (001) és (011) -> (0-1) (A második bit különbözik).
      • (011) és (111) -> (-11) (Az első bit különbözik).
  2. Második lépés:
    • További egyszerűsítés:
      • (0-1) és (-11) nem egyszerűsíthető tovább.

4. Prime implikánsok

Az egyszerűsíthető kifejezések: - (0-1) ((A’ C)). - (-11) ((B C)).

5. Esszenciális prime implikánsok

A mintermek lefedése: - (1) -> (0-1) - (3) -> (0-1, -11) - (7) -> (-11)

Az esszenciális prime implikánsok: - (0-1): Lefedi (1)-et. - (-11): Lefedi (7)-et.

6. Minimális függvény

Az egyszerűsített logikai függvény: [ f(A, B, C) = A’ C + B C ]


Python implementáció

from itertools import combinations

def count_ones(term):
    return sum(1 for bit in term if bit == '1')

def combine_terms(term1, term2):
    diff = sum(1 for a, b in zip(term1, term2) if a != b)
    if diff == 1:
        combined = ''.join('-' if a != b else a for a, b in zip(term1, term2))
        return combined
    return None

def quine_mccluskey(minterms, num_vars):
    terms = [bin(m)[2:].zfill(num_vars) for m in minterms]
    grouped = {i: [] for i in range(num_vars + 1)}

    for term in terms:
        grouped[count_ones(term)].append(term)

    prime_implicants = set()
    while grouped:
        new_group = {i: [] for i in range(num_vars + 1)}
        used = set()
        for i in range(num_vars):
            for term1 in grouped[i]:
                for term2 in grouped[i + 1]:
                    combined = combine_terms(term1, term2)
                    if combined:
                        used.add(term1)
                        used.add(term2)
                        new_group[count_ones(combined)].append(combined)
        prime_implicants.update(set(t for group in grouped.values() for t in group) - used)
        grouped = new_group
        if not any(grouped.values()):
            break

    return prime_implicants

# Példa
minterms = [1, 3, 7]
num_vars = 3
prime_implicants = quine_mccluskey(minterms, num_vars)
print("Prime implikánsok:", prime_implicants)

Kimenet: 

Prime implikánsok: {'0-1', '-11'}

Előnyök

  1. Hatékony kisebb problémákra:
    • Automatizált egyszerűsítést nyújt kis logikai függvényekre.
  2. Pontosság:
    • Garantáltan megtalálja a minimális alakot.


Hátrányok

  1. Nagy méretű problémák:
    • A nagy számú változók és mintermek esetén exponenciális futási időt eredményez.
  2. Tárigény:
    • A táblázatok kezelése nagy memóriát igényelhet.


Összegzés

A Quine-McCluskey-algoritmus egy hatékony, de korlátos módszer a logikai függvények minimalizálására. Kisebb méretű problémák esetén kiváló, de nagy rendszerek esetén praktikusabb a Karnaugh-térkép vagy heurisztikus megközelítések használata.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Quine-McCluskey-algoritmus&oldid=3479606”