Мінтерм Індексація мінтермів | Функціональна еквівалентність | Див. також | Навігаційне меню
Multi tool use
Математична логіка
булевої функціїїкон'юнкціязміннихкортежівіндексдвійковому кодуваннюістиннимфункціїсумибітів
Для булевої функціїї з ndisplaystyle n змінних (x1,…,xndisplaystyle x_1,dots ,x_n), елементарна кон'юнкція, в якій кожна з ndisplaystyle n змінних набуває значення одиниці лише на одному з кортежів своїх змінних називається
мінтермом (конституентою одиниці). Отже, мінтерм це логічний вираз, який використовує лише операцію доповнення та операцію кон'юнкції. Кількість різних мінтермів дорівнює кількості кортежів змінних, тобто 2n для n змінних.
Наприклад, abcdisplaystyle abc, ab′cdisplaystyle ab'c і abc′displaystyle abc' — три з восьми мінтермів для булевої функції з восьми змінних(a,b i c). Читаються ці вирази як «a і b і c», «a і не b і c „ a і b і не c“ відповідно.
Індексація мінтермів |
Кожний мінтерм має свій індекс, заснований на двійковому кодуванню(індекс показує скільки бітів (одиниць) було додано до мінтерму). Значення 1 присвоюється змінній (xidisplaystyle x_i), відповідно 0 присвоюється змінній(xi′displaystyle x'_i). Щоб краще це зрозуміти розглянемо кілька прикладів. Мінтерму abc′displaystyle abc' (110) присвоюють індекс 6 m6displaystyle m_6 (до нього було додано шість одиниць), m0displaystyle m_0 з тих самих трьох змінних означає a′b′c′displaystyle a'b'c' (000), а m7displaystyle m_7 — abcdisplaystyle abc (111).
Функціональна еквівалентність |
Очевидно, що мінтерм n дає істинне значення (наприклад,1) тільки для однієї комбінації вхідних змінних. Наприклад,m5displaystyle m_5 (ab′cdisplaystyle ab'c) є істинним лише коли adisplaystyle a і cdisplaystyle c є істинним, а b′displaystyle b' — хибним, тобто adisplaystyle a і cdisplaystyle c дорівнюють 1, а bdisplaystyle b=0.
Побудуємо таблицю істинності для деяких трьох змінних та функції суми бітів(sum), вона буде виглядати так:
| a | b | c | sum(a, b,c) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Тепер запишемо мінтерми цієї функції(ті кортежі змінних, де функція набуває істинного значення). Такими будуть m1,m2,m4,displaystyle m_1,m_2,m_4, та m7displaystyle m_7. Тоді функцію sum(a,b,c)displaystyle sum(a,b,c) ми можемо представити у вигляді чотирьох мінтермів: sum(a,b,c)=m1+m2+m4+m7=(a′b′c)+(a′bc′)+(ab′c′)+(abc)displaystyle sum(a,b,c)=m_1+m_2+m_4+m_7=(a'b'c)+(a'bc')+(ab'c')+(abc).
Див. також |
- булева алгебра
- булева функція
- біт
- логічні операції
- функція
- таблиця істинності
- кортеж
- двійкова система числення
am0ZV7XlNJA
