Perfect разделителния и съединителната нормални форми (PDNF и sknf)

Начало | За нас | обратна връзка

Определение. Елементарно връзка се нарича връзка на литерали (променливи или техните отрицания), взети не повече от веднъж.

Например, една връзка. , 1 са елементарни. Където първият елементарен съюзът има ранг (брой литерали) 2, а вторият - 3, а третият - 0.

Следващите съюзи :. , , , 0 не са елементарни.

Определение. Елементен връзка булева функция. съдържащ п литерали, наречен пълно (или mintermom).

Определение. Дизюнкция всеки ограничен набор от елементарни съюзи булева функция F се нарича разделителен нормална форма (DNF) на функция Е. Броят на елементарни съюзи (условия, условия), съставляваща DNP нарича дължина DNP.

Пример, DNP има дължина, равна на 3.

За произволно булева функция F съществува, най-общо казано, много различни изпълнението на DNF, различаващи се по дължина, на броя на случаи на литерали и т.н.

Определение. Две (или повече) DNF прилагане на същия булева функция F. наречен еквивалент (или да бъде еквивалент).

Например, за функцията. предварително зададена булева вектор w (F) = (00100111), следната еквивалент DNF:

Определение. DNP Булева функция F. състоящ се само от елементарни пълни съюзи, наречени sovershennoyDNF (PDNF).

Например, (1) - PDNF функция F.

Имайте предвид, че PDNF е уникално (до термини пермутация) за определен Булева функция F.

Всяко булева функция F. предварително определена формула чрез използване на основни equipollences превръща DNP, и след това да PDNF.

Пример. Навяваща PDNF булеви функции F =.

Решение. С основните стойности на еквивалент, за да се превърне DNF:

Прилагането на закона за свързване (в обратен ред), допълни връзка. да завърши елементарни съюзи:

Тъй като. след намаляване на същите съюзи получите PDNF: F =.

Форма маса истина за булева функция F = (функцията на предходния пример). Обърнете внимание на връзката между PDNF и истина маса.

Таблица PDNF истина