Основи дискретної математики (теорія)

Метод Квайна – Маккласкі

У методі Квайна є істотна незручність , пов’язана з необхідністю повного попарного порівняння імплікант на етапі визначення простих імплікант. Із зростанням числа мін термів , що визначають ДДНФ заданої функції , збільшується кількість цих порівнянь. Це збільшення характеризується факторіальною функцією. Тому при досить великому числі мін термів застосування методу Квайна стає важким. У 1956 році Маккласкі запропонував модернізацію першого етапу методу Квайна, яка істотно зменшує кількість порівнянь мін термів. Якщо записати мін терми у вигляді їхніх двійкових номерів, то всі номери можна розбити за числом одиниць у цих номерах на непересічні групи. При цьому в і-ту групу ввійдуть усі номери, що мають у своєму двійковому запису і одиниць. Попарно порівнювати можна тільки сусідні за номером групи, оскільки саме вони різні для тих мін термів, що входять у них, в одному розряді. При створенні мін термів з рангом, вищим від нульового, в розряди, які відповідають вилученим змінним, записують знак „тире”. Така модифікація на практиці дуже зручна, оскільки дає змогу уникнути виписування громіздких мінтермів та імплікант , замінюючи виписування їхнім двійковим номером.

Приклад.

Функцію в ДДНФ задано мін термами з номерами 0,1,2,3,4,7,8,9,11,15. Записати ці мін терми по групах у двійковому коді:

Нульова група 0000

Перша _”_0001,0010,0100,1000

Друга_”_0011,0110,1001

Третя_”_0111,1011

Четверта_”_1111

Порівнюючи сусідні групи, визначаємо по групах мінтерми першого рангу :

Нульова група 000-,00-0,0-00,-000

Перша_”_00-1,-001,001-,0-10,01-0,100-

Друга_”_0-11,-011,011-,10-1

Третя_”_-111,1-11

Тепер знаходимо мінтерми другого рангу:

Нульова група 00-,-00-,0-0

Перша_”_ -0-1,0-1-

Друга_2_ -11

Складаємо таблицю міток: |

0000 | 0001 | 0010 | 0011 | 0100 | 0110 | 0111 | 1000 | 1001 | 1011 | 1111

00- | v | v | v | v

-00- | v | v | v | v

0-0 | v | v | v | v

-0-1 | v | v | v | v

0-1- | v | v | v | v

-11 | v | v | v | v

Подальша мінімізація функції за методом Маккласкі збігається з мінімізацією за методом Квайна. Для ДНФ, що розглядається , мінімальна форма має такий вигляд:

F(x1x2x3x4)=

Основне поняття і властивості відношень. Відношення еквівалентності

Відношення означає яки й не-будь зв'язок між предметами або поняттями. Відношення між парами об’єктів називається бінарними. Приклади бінарних відношень:

Відношення належності;

Включення множин;

Рівність дійсних чисел;

Нерівності;

Загалом відношення записується у вигляді співвідношень хАу, де А- відношення , яке встановлює зв'язок між елементом хХ і елементом уУ.

Бінарним відношенням А, що діє з множини Х у множину У, називається деяка підмножина Х У(АХУ).

Властивості відношень.

Нехай А-бінарне відношення у множині Х(АХХ). Тоді відношення А є:

Рефлексивним, Якщо ЕА, тобто іншими словами, воно завжди виконується між елементом і ним самим (.

Анти рефлексивним, якщо А, тобто якщо співвідношення хіАхj виконується, то хіхj.

Симетричним , якщо А=А-1, тобто при виконанні співвідношення хіАхj виконується співвідношення хjАхі .

Асиметричним , якщо АА-1=0, тобто із двох співвідношень хіАхj й хjАхі щонайменше одне не виконується.

Антисиметричним , якщо АА-1Е, тобто обидва співвідношення хіАхj й хjАхі одночасно виконуються тоді й тільки тоді , коли хі = хj.

Транзитивним , якщо AAA, тобто з виконанням співвідношень хіАхj й хjАхк випливає виконання співвідношення хіАхк .

Відношення еквівалентності є експлікацією таких слів як „подібність”, „нерозрізненість”, „взаємозвязаність”, „рівносильність”.

Бінарне відношення в множині Х називається відношенням еквівалентності якщо виконуються такі властивості:

Рефлективність(х~х);

Симетричність (х~уу~х);

Транзитивність (х~уу~zx~z).

Найважливіше значення відношення еквівалентності полягає в тому , що воно задає ознаку для розбиття множини Х на неперерізні підмножини. Приклади відношень еквівалентності:

„Проживати у одному будинку” у множині людей.

„Подібність трикутників” у множині всіх трикутників на площині.

„Паралельність прямих” у множині всіх прямих на площині.