מתמטיקה דיסקרטית/מציאת CNF ו-DNF

הצורה הנורמלית הקוניוקטיבית (Conjunctive Normal Form) הוא ביטוי המורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות וגם שצורתה הכללית: $(x_{1}\lor {\overline {x_{3}}})\land (x_{2})\land (x_{2}\lor x_{5}\lor {\overline {x_{6}}}\lor x_{n})$

הצורה הנורמלית הדיסיונקטיבית (Disjunctive Normal Form) ביטוי המורכב מאוסף פרדיקטים לוגיים המחוברים ביניהם על ידי ביטויי "או" כאשר כל פרידיקט הוא אוסף של ביטויים המחוברים ביניהם על ידי ביטויי "וגם" שצורתו הכללית: $(x_{1}\land x_{2}\land x_{3})\lor (x_{4}\land x_{5}\land x_{6})$

מציאת CNF

f	Q	P
0	0	0
1	1	0
0	0	1
0	1	1

• כאשר אנו מתבקשים למצוא CNF ל-f נעקוב אחר האפסים. נזכור כי כל ביטוי בקשר זה בעל קשר "וגם".
• כל שורה מהווה $(x_{1}\lor {\overline {x_{3}}})$
• ה-f הראשון שלנו עם אפס הוא ה-f הראשון ולכן נרצה לייצר משני ביטוי שקר שקר - קיימים 3 אפשרויות לשם כך ולכן נמתין עם f זה.
• ה-f השני שלנו עם אפס הוא ה-f השלישי ולכן נרצה לייצר מביטוי אמת ושקר שקר - אין לנו בעיה עם P ו-Q ולכן נמשיך הלאה.
• ה-f השלישי שלנו עם אפס הוא ה-f הרביעי ולכן נרצה לייצר מביטוי אמת ואמת שקר - יש לנו בעיה ולכן בכדי שיווצר ביטוי כזה נצטרך לשלול את P כלומר (¬p). נבדוק ששינוי זה לא השפיע על ה-f במקום השלישי והראשון:
  • ה-f השני שלנו עם אפס הוא ה-f השלישי ולכן נרצה לייצר מביטוי שקר ושקר שקר - אין לנו בעיה עם P ו-Q ולכן נמשיך הלאה.
  • ה-f הראשון שלנו עם אפס הוא ה-f הראשון ולכן נרצה לייצר מביטוי אמת ושקר שקר - אין בעיה

על כן ה-f שנקבל הינה $\lnot p\land Q$

$\lnot p\land Q$	Q	P
0	0	0
1	1	0
0	0	1
0	1	1

DNF

כאשר אנו מתבקשים למצוא DNF נעקוב אחר האחדים.