Postać normalna (matematyka)
Postać normalna (ang. normal form) – pewna szczególna postać wyrażenia, która jest w pewnym sensie "równoważna" każdemu wyrażeniu z pewnego zbioru wyrażeń. Od postaci systemu zależy, jaki to zbiór i jaki jest sens tej "równoważności". Wyrażenie może mieć jedną postać normalną lub nie mieć jej wcale.
Systemy redukcji[edytuj | edytuj kod]
W systemach redukcji postać normalna to wyrażenie, którego nie można zredukować.
Na przykład w systemie złożonym z liczb, znaku + oraz reguły redukcji pozwalającej zastąpić parę liczb po obu stronach znaku + ich sumą, postacią normalną jest pojedyncza liczba. Postacią normalną wyrażenia "1 + 2 + 3 + 4" jest "10". "10" jest też postacią normalną dla "7 + 3", "1 + 4 + 5" i wielu innych wyrażeń. Wszystkie wyrażenia, których postać normalna to "10", są w pewnym sensie równoważne. W rachunku lambda postać normalna to lambda-wyrażenie, w którym niczego nie można β-zredukować. Żeby uznać to za postać normalną, musimy założyć, że α-konwersja nie tworzy innej formuły.
Wyrażenia logiczne[edytuj | edytuj kod]
Dwie ważne postacie normalne występujące w logice matematycznej to koniunkcyjna postać normalna (CNF) oraz dysjunkcyjna postać normalna (DNF).