Съединителната нормална форма -
CNF формула не е:
Но тези 3 формули не са в CNF еквивалентни на следните формули в CNF:
Изграждане на CNF
Алгоритъм за изграждане CNF
1) Отърви се от всички логически операции, съдържащи се във формулата, заменяйки ги с основно: връзка, дизюнкция, отрицание. Това може да бъде направено чрез формула са еквивалентни:
2) Поставете знак отрицание, свързана с целия израз, отрицание признаци, свързани с отделни променливи въз основа на изказвания на формулите:
3) Отърви се от двойни негативни знаци.
4) Прилага се, ако е необходимо, с операции за съгласуване и дизюнкция Distributivity и абсорбционните свойства на формулата.
Пример конструиране CNF
За да се даде CNF формула
F трансформира формула формула не съдържащ →:
Полученият формула прехвърля отрицание на променливите и ще намали двойно отрицание:
к -konyunktivnaya нормална форма
к -konyunktivnoy нарича нормална форма конюнктива нормална форма, в която всеки дизюнкция съдържа точно к литерали.
Например, формулата се записва в 2 CNF:
Преходът от CNF да SKNF
Ако просто дизюнкция липсва някоя променлива (например, на Z), а след това добавете към него изразът (това не променя много дизюнкцията), а след това се разкрие скобите, използвайки разпределителни закона:
По този начин, от полученото CNF SKNF.
Официално граматика, описваща CNF
Следваща Официално граматика описва всички формули, дадени в CNF:
<КНФ> → <дизъюнкт> <КНФ> → <КНФ> ∧ <дизъюнкт> <дизъюнкт> → <литерал> <дизъюнкт> → (<дизъюнкт> ∨ <литерал>) <литерал> → <терм> <литерал> → ¬<терм>
където <терм> означава произволно булева променлива.
Формулата за задача приложимост CNF
В теория на изчислителната сложност играе важна роля Булева проблем satisfiability в съединителната нормална форма. Според теоремата на Кук. този проблем е NP-пълна. и то се свежда до проблема с realizability на формули в 3-CNF, която се намалява, и които, от своя страна, намалява другите NP-пълни проблеми.
Проблемът на satisfiability 2-CNF формули могат да бъдат решени в линейно време.
бележки
литература
Вижте това, което "съюзен нормална форма" в други речници:
Съединителната нормална форма - Пропозиционални формула като формата (*), където всеки С у, I = 1. п; J = 1. ми, е или променлива или отрицание на променливата. К. п. е. (*) Е тавтология, ако и само ако по някаква isredi С i1. CIMI. ... ... енциклопедия по математика
K-съединителната нормална форма - (к CNF) в булева логика нормална форма, в която булева формула е съчетание на няколко точки, всяка от които съдържа точно к литерали. Например, формулата се записва в 2 CNF ... Wikipedia
Нормално Форма (пояснение) - Normal Form Нормално форма в отношенията бази имоти в модела на релационни данни. Нормалната форма на математиката в някакъв смисъл или друг прост или канонична форма, на които обектът е трансформация ... ... Уикипедия
Разделителен нормална форма - (DNF) в булева логика нормална форма, в която булева формула е дизюнкция на съюзи на литерали. Всяко булева формула може да бъде намалена до DNP [1]. Можете да използвате правото на двойно отрицание, правото на закона де Морган ... ... Wikipedia
Перфектно нормални форми - перфектно перфектно дизюнктивен или конюнктива нормална форма (. Виж булеви функции, нормални форми) ... енциклопедия по математика
Булева функция - Тази статия или раздел е даден списък на източници или външни връзки, но индивидуалните отчети източници остават неясни поради липсата на бележки под линия ... Wikipedia
Булеви изрази - Теорията на дискретни функционални системи на функцията на булевата се нарича функция на тип. където булева набор, и п неотрицателно цяло число, което се нарича arity на функцията или терена. Елементи 1 (един) и 0 (нула) се тълкува като стандарт ... ... Wikipedia
- Дискретна математика и математическа логика част I. Евгения Filenko. Тази работа включва необходимите информационни фон и модел примерите в следните раздели, някои от които не са достатъчно добре уредени в съществуващата научна литература: 1. Комплектите и ... Прочети повече Купи (Украина) за 4887 UAH