Нормал және жетілдірілген формалар туралы қазақша реферат

Нормал және жетілдірілген формалар

А(а₁, а₂, …, а_n) тұжырымның формуласын қарастырайық. Тұжырымдар алгебрасында кез келген формуланы тепе-тең түрлендірулер арқылы нормал формаларға келтіруге болады. Бұл бөлімде қарапайым конъюнкция мен дизъюнкция ұғымдары, сондай-ақ КНФ, ДНФ және олардың жетілдірілген түрлері беріледі.

Анықтама 1. Қарапайым конъюнкция және қарапайым дизъюнкция

n тұжырымның қарапайым конъюнкциясы (немесе қарапайым дизъюнкциясы) деп тұжырымдардың немесе олардың терістеулерінің конъюнкциясын (тиісінше дизъюнкциясын) айтады.

Мысал 1

Қарапайым конъюнкция: xyz, ¬x y ¬z
Қарапайым дизъюнкция: ¬x ∨ y ∨ z, y ∨ z, x ∨ ¬z

Анықтама 2–3. КНФ және ДНФ

Анықтама 2. Егер A формуласындағы қарапайым дизъюнкциялар бір-бірімен конъюнкция арқылы байланысса, онда формула конъюнктивті нормал форма (КНФ) деп аталады.

Анықтама 3. Егер A формуласындағы қарапайым конъюнкциялар бір-бірімен дизъюнкция арқылы байланысса, онда формула дизъюнктивті нормал форма (ДНФ) деп аталады.

Тұжырымдар алгебрасының кез келген формуласы үшін тепе-тең түрлендірулер көмегімен оның ДНФ немесе КНФ табуға болады. Алайда бұл нормал формалар, жалпы жағдайда, бірмәнді болмайды.

Жетілдірілген нормал формалар

Нормал формалардың «жетілдірілген» нұсқалары әрбір қарапайым тұжырымның формула ішінде міндетті түрде қамтылуын талап етеді. Бұл талап ЖДНФ пен ЖКНФ-тың бірмәнді сипаттамаларына негіз болады.

Анықтама 4. Жетілдірілген дизъюнктивті нормал форма (ЖДНФ)

Егер дизъюнктивті нормал формадағы әрбір қарапайым конъюнкцияның құрамына әрбір қарапайым тұжырымның өзі немесе оның терістеуі міндетті түрде кірсе, онда формула жетілдірілген дизъюнктивті нормал форма (ЖДНФ) деп аталады.

Анықтама 5. Жетілдірілген конъюнктивті нормал форма (ЖКНФ)

Егер конъюнктивті нормал формадағы әрбір қарапайым дизъюнкцияның құрамына әрбір қарапайым тұжырымның өзі немесе оның терістеуі міндетті түрде кірсе, онда формула жетілдірілген конъюнктивті нормал форма (ЖКНФ) деп аталады.

Мысал 2. Формалардың үлгілері

ДНФ

A(x, y, z) = xyz ∨ (¬x y ¬z)

КНФ

B(x, y, z) = (¬x ∨ y ∨ z)(y ∨ z)(x ∨ ¬z)

ЖДНФ

C(x, y, z) = xyz ∨ (¬x y z)

ЖКНФ

D(x, y, z) = (¬x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ ¬z)

Негізгі теоремалар

Теорема 1

Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және КНФ бар.

Теорема 2

Тұжырымдар алгебрасының кез келген тепе-тең жалған емес формуласы бірмәнді ЖДНФ түрінде өрнектеледі.

Теорема 3

Тұжырымдар алгебрасының кез келген тепе-тең ақиқат емес формуласы бірмәнді ЖКНФ түрінде өрнектеледі.