AlgoVerse

جدول کارنو و صورت‌های DNF و CNF

از سطرهای درست جدول درستی، صورت متعارف فصلی (DNF) و عطفی (CNF) را می‌سازد و بعد مثل جدول کارنو، خانه‌های همسایه را ادغام می‌کند (روش کوین–مک‌کلاسکی) تا ساده‌ترین مجموع حاصل‌ضرب‌ها به دست آید.

هر تابع بولی را می‌شود از روی جدول درستی‌اش نوشت:

ادامه‌ی توضیح ↓
ورودی:
M 1×10 · n=4خروجی PDF

تابعی از چهار متغیر با مینترم‌های ۰، ۱، ۲، ۵، ۶، ۷، ۸، ۹، ۱۰، ۱۴؛ جدول کارنو آن را به سه جمله‌ی کوتاه می‌رساند.

  1. def karnaugh(M, n):
  2. # M: the minterms (rows of the truth table where f = 1) of a function of n variables a, b, c, d.
  3. ones = sorted(set(M[0]))
  4. for m in ones:
  5. if m >= 2 ** n:
  6. return None
  7. kmap = draw(ones, n)
  8. dnf = []
  9. cnf = []
  10. for m in range(2 ** n):
  11. if m in ones:
  12. dnf.append(term([m, 0], n, "∧"))
  13. else:
  14. cnf.append(clause(m, n))
  15. dnf_text = " ∨ ".join(dnf) if dnf else "0"
  16. cnf_text = " ∧ ".join(cnf) if cnf else "1"
  17. # Quine–McCluskey. An implicant is [value, mask]: the mask bits are the variables it no longer mentions.
  18. # Two implicants merge when they have the same mask and differ in one bit, as neighbouring K-map blocks do.
  19. current = [[m, 0] for m in ones]
  20. primes = []
  21. while current:
  22. merged = []
  23. used = []
  24. for i in range(len(current)):
  25. for j in range(i + 1, len(current)):
  26. a = current[i]
  27. b = current[j]
  28. x = a[0] ^ b[0]
  29. if a[1] != b[1] or x & (x - 1) != 0:
  30. continue
  31. used.append(a)
  32. used.append(b)
  33. both = [a[0] & ~x, a[1] | x]
  34. if both not in merged:
  35. merged.append(both)
  36. shown = term(both, n, "")
  37. for t in current:
  38. if t not in used and t not in primes:
  39. primes.append(t)
  40. shown = term(t, n, "")
  41. current = merged
  42. table = [] # for the picture: each prime implicant and the minterms it covers
  43. cover = []
  44. for p in primes:
  45. cover.append([m for m in ones if m & ~p[1] == p[0]])
  46. table.append([term(p, n, ""), cover[-1]])
  47. chosen = []
  48. for m in ones:
  49. holders = [k for k in range(len(primes)) if m in cover[k]]
  50. if len(holders) == 1 and holders[0] not in chosen:
  51. chosen.append(holders[0])
  52. shown = table[holders[0]][0]
  53. left = [m for m in ones if not any(m in cover[k] for k in chosen)]
  54. while left:
  55. best = 0
  56. for k in range(len(primes)):
  57. if len(set(cover[k]) & set(left)) > len(set(cover[best]) & set(left)):
  58. best = k
  59. chosen.append(best)
  60. left = [m for m in left if m not in cover[best]]
  61. shown = table[best][0]
  62. minimal = " ∨ ".join(table[k][0] for k in chosen) if chosen else "0"
  63. return minimal
  66. def term(p, n, op):
  67. parts = []
  68. for i in range(n):
  69. bit = 1 << (n - 1 - i)
  70. if p[1] & bit:
  71. continue
  72. parts.append("abcd"[i] if p[0] & bit else "¬" + "abcd"[i])
  73. if not parts:
  74. return "1"
  75. return op.join(parts)
  78. def clause(m, n):
  79. parts = []
  80. for i in range(n):
  81. bit = 1 << (n - 1 - i)
  82. parts.append("¬" + "abcd"[i] if m & bit else "abcd"[i])
  83. return "(" + " ∨ ".join(parts) + ")"
  86. def draw(ones, n):
  87. # Rows and columns in Gray-code order, so neighbouring cells differ in one variable (and the edges wrap around).
  88. gray = {1: ["0", "1"], 2: ["00", "01", "11", "10"]}
  89. rbits = n // 2
  90. cbits = n - rbits
  91. rows = [["·"] + gray[cbits]]
  92. for r in gray[rbits]:
  93. row = [r]
  94. for c in gray[cbits]:
  95. row.append("1" if int(r + c, 2) in ones else "0")
  96. rows.append(row)
  97. return rows

ناوردا: هر ایمپلیکنت فقط مینترم‌های تابع را می‌پوشاند؛ ادغام دو ایمپلیکنت همسایه یک ایمپلیکنت بزرگ‌تر با یک متغیر کمتر می‌دهد.

شروع اجرا

dnf_text—
cnf_text—
minimal—

kmap

جدول هنوز خالی است.

table

جدول هنوز خالی است.

متغیرهای محلی

n4

نارنجی = در همین گام عوض شد

M list

[0, 1, 2, 5, 6, 7, 8, 9, 10, 14]

Call stack

  1. karnaugh()خط 1
گام ۱ از ۲٬۰۸۸
خط سیاه = prime · خط نارنجی = گام کلیدیcanonical: 0/1 · merge: 0/16 · prime: 0/6 · essential: 0/2 · pick: 0/1 · minimal: 0/1
    توضیح

    صورت‌های متعارف

    هر تابع بولی را می‌شود از روی جدول درستی‌اش نوشت:

    • DNF متعارف (مجموع مینترم‌ها): برای هر سطری که تابع ۱ است، یک حاصل‌ضرب از همه‌ی متغیرها (یا نقیضشان).
    • CNF متعارف (حاصل‌ضرب ماکسترم‌ها): برای هر سطری که تابع ۰ است، یک بند «یا» که دقیقاً در آن سطر نادرست است.

    این صورت‌ها درست‌اند ولی طولانی.

    جدول کارنو

    جدول کارنو همان جدول درستی است که سطر و ستونش به ترتیب کد گری چیده شده‌اند، پس خانه‌های همسایه (حتی از لبه‌ها) در یک متغیر فرق دارند. هر بلوک مستطیلی از ۱ها با اندازه‌ی توانی از ۲ یک جمله با متغیرهای کمتر است. هدف: کمترین و بزرگ‌ترین بلوک‌ها برای پوشاندن همه‌ی ۱ها.

    کوین–مک‌کلاسکی

    همین کار به شکل الگوریتمی: ایمپلیکنت‌هایی را که در یک متغیر فرق دارند ادغام کن (0101 و 0111 → 01-1) تا دیگر چیزی ادغام نشود؛ آن‌هایی که ادغام نشدند ایمپلیکنت اولاند. بعد ایمپلیکنت‌های ضروری را بردار و بقیه را با انتخاب حریصانه بپوشان (پوشش بهینه در حالت کلی سخت است).

    ورودی

    M شماره‌ی سطرهایی است که تابع در آن‌ها ۱ است (a پرارزش‌ترین بیت)، و n تعداد متغیرها. جدول اول نقشه‌ی کارنو است (سطرها a یا ab، ستون‌ها بقیه) و جدول دوم ایمپلیکنت‌های اول با مینترم‌هایی که می‌پوشانند.