Perfect съединителната нормална форма - studopediya

По същата формула може да направи много равностоен CNF. Но сред тях има уникален CNF със свойствата на съвършенство.

Ние списък на свойствата на съвършенство за CNF:

1. Всяка логическа множител формула съдържа всички променливи са включени във функцията.

2. Всички логични фактори са различни.

3. Никой не фактор не съдържа както променлива и нейното отрицание.

4. Никой не фактор не съдържа една и съща променлива два пъти.

CNF за които свойствата на съвършенство екзекутиран се нарича перфектен CNF (SKNF).

Дали не идентично вярно формула има уникален SKNF.

Един от начините да се получи SKNF е да се използва за истина маси за:

1. Правят се PDNF.

2. За изграждането SKNFA PDNF отрицание, т.е.

Или групи от променливи, в която А е невярно, правят елементарни дизюнкция, в които променливите, които са влезли със стойността на истината се въвежда с отричането, а стойността се крие - без отрицание. От получените елементарни дизюнкции представлява връзка.

Друг метод се основава на еквивалентни трансформации

Тук са подходящ алгоритъм:

1. Чрез еквивалентни преобразувания, за да получите някои - или CNF.

2. Ако една елементарна дизюнкция в не съдържа променлива XI. след това да го представим с помощта на равностойността. И с помощта на разпределителни имота.

3. Ако CNF включва две идентични дизюнкция, след това излишъкът се отстранява с помощта idempotency собственост в B º Б.

4. Ако някоя дизюнкция съдържа XI заедно с отказ, а след това Б º 1. И в управлението на CNF.

5. Ако някоя дизюнкция съдържа променлива XI два пъти, един от тях се изхвърля с помощта на имот XI срещу XI в º XI.

1. Създайте SKNF формула за истина маса и чрез еквивалентни преобразувания.

Ние създаде таблица истина, която съдържа четири реда за

3. Чрез еквивалентни преобразувания се SKNFA.

Задачи за независим решение.

1. За следните формули и да намерят PDNF SKNF всеки два начина (от еквивалентни образуване и преобразуване с помощта на таблицата за истина):

2. Виж PDNF за всички еднакви цис-калния формула, съдържаща: 1) една променлива, 2) две променливи, 3) три променливи.

3.Find SKNF за всички еднакви-ложи солна формула, съдържаща: 1) една променлива, 2) две променливи, 3) три променливи.

4. Докажете, за еквивалентност формули и сравняването им перфектни нормални форми (съединителната или разделителен).

5. Намерете по-проста форма на формулите, които са напълно нормални следния вид:

1. Списък на свойствата на съвършенство за DNF.

2. Списък на свойствата на съвършенство за CNF.

3. Колко от формула може да направи PDNF и SKNF?

4. Що се отнася до масата за истината, за да направят PDNF?

5. Комуникацията между SDNFA и SKNFA.

6. Как да се промени, като еквивалентната PDNF и SKNF формула?