Normálformák

A logikai kifejezéseket átírhatjuk szabványos alakokra. Ezeket nevezzük normálformáknak. Két legfontosabb típusuk: konjunktív normálforma (KNF) és diszjunktív normálforma (DNF).

Diszjunktív normálforma (DNF)

A DNF olyan alak, ahol a kifejezés több ÉS-tagból álló részek VAGY-kapcsolata. Másképp: minden részben ∧ kapcsolatok vannak, a részeket pedig ∨ köti össze.

Ez DNF alak: az első rész (p ∧ q), a második rész (¬p ∧ r), és a kettőt ∨ köti össze.

Konjunktív normálforma (KNF)

A KNF olyan alak, ahol a kifejezés több VAGY-tagból álló részek ÉS-kapcsolata. Másképp: minden részben ∨ kapcsolatok vannak, a részeket pedig ∧ köti össze.

Ez KNF alak: az első rész (p ∨ q), a második rész (¬p ∨ r), és a kettőt ∧ köti össze.

Miért hasznosak?

• Segítik a logikai kifejezések egyszerűsítését.
• Automatikus bizonyítási rendszerekben alapformák.
• Számítógépes algoritmusok könnyebben tudnak velük dolgozni.

Példa átalakításra

Vegyük a kifejezést: (p → q). Ez átalakítható: (¬p ∨ q). Ez már egy KNF és DNF alak is egyben, mert csak egy ∨ kapcsolat van.

Összefoglalás

A DNF: ÉS-tagok VAGY-kapcsolata. A KNF: VAGY-tagok ÉS-kapcsolata. Minden logikai kifejezés átírható valamelyik normálformába.

Gyakorló feladat