Елементарні кон'юнкції (відповідно елементарні диз'юнкції) називаються констітуентамі одиниці (відповідно нуля), якщо вони містять всі змінні функції.
Елементарна кон'юнкція (хв терм) утворюється кон'юнкція кінцевого безлічі логічних змінних і їх заперечень.
Елементарна кон'юнкція (минтерм) утворюється кон'юнкція кінцевого безлічі логічних змінних і їх заперечень, наприклад Р (X, Y, Z) X л Y л Z. Елементарна диз'юнкція (макстерм) утворюється диз'юнкція кінцевого безлічі логічних змінних і їх заперечень, наприклад Q (X, Y, Z) X v У v Z. елементарна кон'юнкція (минтерм) приймає одиничне значення при одному з усіх можливих наборів вхідних аргументів, а елементарна диз'юнкція (макстерм), навпаки, приймає нульове значення при одному з можливих наборів аргументів і середнє арифметичне значення - при всіх інших.
Елементарна кон'юнкція називається монотонної, якщо вона не містить заперечень змінних.
Елементарні кон'юнкції (диз'юнкції) - це кон'юнкція (диз'юнкція), в якій кон'юнктивний (диз'юнктивно) зв'язуються тільки окремі змінні.
Елементарна кон'юнкція називається монотонної, якщо вона не містить заперечень змінних.
Елементарна кон'юнкція До називається простим Импли-кантом, якщо До V / / і К V / ф f для кожної кон'юнкції К, отриманої з До викреслюванням букв. Довести, що ніякої простий импликант монотонної функції не містить заперечень змінних.
Елементарна кон'юнкція називається монотонної, якщо вона не містить заперечень змінних.
Елементарної кон'юнкція або Кон'юнктів називається кон'юнкція літер. Елементарної диз'юнкція або диз'юнкт називається диз'юнкція літер.
Елементарної кон'юнкція називається вираз, що представляє собою кон'юнкції будь-якого кінцевого безлічі попарно помітних букв або що складається з однієї літери. Вирази 1, xit у, ху, Х1х2х3х5 є елементарних кон'юнкція. Елементарної диз'юнкція називається вираз, що представляє собою диз'юнкцію будь-якого кінцевого безлічі попарно помітних букв або що складається з однієї літери. Вирази 0, х, x jy, Xj / xz / xt є елементарними диз'юнкції.
В елементарні кон'юнкції записати неінвертірованнимі змінні, задані одиницею в таблиці істинності, а інвертованими - ті змінні, які в таблиці істинності задані нулем.
В елементарні кон'юнкції записати неінвертірованнимі змінні, задані одиницею в табличному вигляді функції, а інвертованими - ті змінні, які в цій таблиці задані нулем.
Якщо елементарні кон'юнкції, що входять в діз'юнктівную нормальну форму, містять все я змінних, то остання називається досконалою диз'юнктивній нормальною формою.
Елемент затримки, який реалізує операцію якщо тільки p (t істинно, то. (. Теж істинно. Можна вважати, що fl (O помилково. | Схема, яка використовує елемент затримки. Умови функціонування. | Елемент зі зворотним зв'язком. Якщо елементарна кон'юнкція вихідної формули ні разу не задовольняла перевірці (в нашому прикладі такого випадку не було), то вона повинна з'явитися в остаточній формулі. Якщо ж елементарна кон'юнкція задовольняє перевірці, то в остаточну форму входить деяка інша кон'юнкція, отримана з вихідної.
Розподіл елементарних кон'юнкція системи 0 для їх реалізації на проміжних шинах різних ПЛМ здійснюється довільним чином.
Сукупність отриманих елементарних кон'юнкція описує всю область заборони Про: будь-який її елемент належить хоча б одному з інтервалів, що задаються цими кон'юнкції. Про - такий булевої функції, яка приймає значення 1 на безлічі U і значення 0 на додатковому безлічі U. Кожен її член представляє собою просту импликантами - елементарну кон'юнкцію з наступними двома властивостями: по-перше, вона имплицирует функцію ф (якщо кон'юнкція приймає значення 1 , то і функція теж), по-друге, вона не имплицирует ніякий інший кон'юнкції, що володіє першим властивістю. Якщо в ДНФ входять всі прості імпліканти (як в даному випадку), вона називається скороченою.
Для реалізації елементарної кон'юнкції потрібно п контактів.
Диз'юнкцію D елементарних кон'юнкція назвемо тупикової щодо елементарної кон'юнкції К, якщо D поглинає К (див. Розділ 2), а диз'юнкція, що виходить з D при видаленні будь-кон'юнкції, вже не поглинає К.
В цьому випадку елементарні кон'юнкції, відповідні гранях розмірності 2, містять три змінні.
Очевидно, що повні елементарні кон'юнкції є елементарних кон'юнкція.
Така диз'юнкція всіх елементарних кон'юнкція, для яких розглянута формула істинна, називається досконалою диз'юнктивній нормальною формою.
Конституентов одиниці називаємо елементарну кон'юнкцію, що містить всі змінні алгебри кінцевих предикатів.
У стовпці 1 записані елементарні кон'юнкції з шпальти X (am, as) табл. 8.8. У стовпці 2 з цих кон'юнкція видалена змінна х, а в стовпці 3 - змінні х, х з, хи.
Над частиною аргументів, елементарних кон'юнкція, творів кон'юнкція і вище виявляться знаки інверсії.
Число г називається рангом елементарної кон'юнкції.
Після цього переходять до наступної елементарної кон'юнкції.
Число аргументів, що утворюють елементарну кон'юнкцію або диз'юнкцію, є її рангом.
Як приватного тут використовуються елементарні кон'юнкції.
Елементам куба поставимо у відповідність елементарні кон'юнкції різного рангу. На рис. 1.2 вершин куба зіставлені кон'юнкції третього рангу, ребрах - другого рангу, гранях - першого рангу. При цьому кожен геометричний еквівалент меншою розмірності покривається відповідними геометричними еквівалентами більшої розмірності.
Надалі, кажучи про елементарну кон'юнкції, будемо називати її просто кон'юнкція.
СДНФ містить не більше Ds елементарних кон'юнкція, кожна з яких складається з O (log2 D) сомножителей.
Якщо в ДНФ є кілька однакових елементарних кон'юнкція, то ми залишаємо тільки одну.
На кожному кроці кільцевої алгоритм використовує елементарні кон'юнкції, що входять до округу k - ro порядку деякої кон'юнкції і інформаційні позначки цих кон'юнкція.
Конституента (повна сполучення) - елементарна кон'юнкція, в яку по одному разу входить кожна змінна, яка визначає стан середовища.
Ці форми являють собою лише диз'юнкції елементарних кон'юнкція або кон'юнкції елементарних диз'юнкцій.
Диз'юнкцію D елементарних кон'юнкція назвемо тупикової щодо елементарної кон'юнкції К, якщо D поглинає К (див. Розділ 2), а диз'юнкція, що виходить з D при видаленні будь-кон'юнкції, вже не поглинає К.
Якщо ж xi не входить в елементарну кон'юнкцію, в / - м компоненті ставиться прочерк. У цьому випадку на кожному етапі порівняння може проводитися лише між елементарних кон'юнкція, відповідними потрійним наборам з сусідніх по номеру груп.
Такі кон'юнкції всіх змінних формули називаються елементарними кон'юнкції.
Функція, в СДНФ якій додана одна елементарна кон'юнкція, приймає значення 1 ще тільки на одному наборі. Нехай R - вихідне відношення, a R1 - відношення, якому відповідав би ЛФО (У. Ана логічне міркування в разі видалення однієї кон'юнкції завершує доказ.
Для мінімізації БФ за методом Квайна все елементарні кон'юнкції в запису її досконалої ДНФ порівнюються попарно. Якщо дві кон'юнкції такі, що мають вид axi і axi, то замість них виписується єдина кон'юнкція a (L - 1) - го рангу.
Число змінних (аргументів), що складають елементарну кон'юнкцію або диз'юнкцію, називається її р а н тому. xs, xj XiXzXaXi є елементарною кон'юнкція летвертфго рангу; функція М (х, у, г) i хуг - елементарної коню'нкціей третього рангу.
Очевидно, що повні елементарні кон'юнкції є елементарних кон'юнкція.
G s - різні; Ki називаються повними елементарних кон'юнкція.
Кожній грані, що міститься в Nf, відповідає елементарна кон'юнкція, що має не менше двох множників з запереченнями і не менше одного множника без заперечень.
Послідовним застосуванням перетворення (29) до кожної елементарної кон'юнкції і до всіх змінним, що не входять в кон'юнкції, утворюється ДКФ функції, заданої своєї ДНФ.
ДНФ називається правильної, якщо для кожної її елементарної кон'юнкції виконана така умова: всі букви змінних, що зустрічаються в цій елементарній кон'юнкції, різні.
Формули, тотожне рівні одиниці. Диз'юнктивна нормальна форма вираження А являє собою диз'юнкцію елементарних кон'юнкція, для яких значення Л помилково.
Нагадаємо, що диз'юнкція piVp2V - / Рь елементарних кон'юнкція Pi поглинає елементарну кон'юнкцію р, якщо формула p - piVpaV VP є функція, тотожно рівна одиниці.
Отже, функція в СДНФ складається з чотирьох елементарних кон'юнкція третього рангу.
Таким чином, кожному інтервалу булева простору М відповідає своя елементарна кон'юнкція, що виявляється характеристичної функцією інтервалу. Вона приймає значення 1 на елементах інтервалу і Про за його межами.