הצגת המקור של הדף "מתמטיקה דיסקרטית/מציאת CNF ו-DNF"

'''הצורה הנורמלית הקוניוקטיבית''' (Conjunctive Normal Form) הוא ביטוי המורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות וגם שצורתה הכללית: 
<math>(x_1\lor \overline{x_3})\land(x_2)\land(x_2\lor x_5 \lor \overline{x_6} \lor x_n)</math>

'''הצורה הנורמלית הדיסיונקטיבית''' (Disjunctive Normal Form) ביטוי המורכב מאוסף פרדיקטים לוגיים המחוברים ביניהם על ידי ביטויי "או" כאשר כל פרידיקט הוא אוסף של ביטויים המחוברים ביניהם על ידי ביטויי "וגם" שצורתו הכללית: <math>(x_1 \land x_2 \land x_3) \lor (x_4 \land x_5 \land x_6)</math>

===מציאת CNF ===
{| class="wikitable"
|-
!f !!Q !! P
|-
|0 || 0 ||0
|-
| 1 || 1 || 0
|-
| 0 || 0|| 1
|-
| 0 || 1 || 1
|}
* כאשר אנו מתבקשים למצוא CNF ל-f נעקוב אחר '''האפסים'''. נזכור כי כל ביטוי בקשר זה בעל קשר "וגם".
* כל שורה מהווה <math>(x_1\lor \overline{x_3})</math>
* ה-f הראשון שלנו עם אפס הוא ה-f הראשון ולכן נרצה לייצר משני ביטוי שקר שקר - קיימים 3 אפשרויות לשם כך ולכן נמתין עם f זה.
* ה-f השני שלנו עם אפס הוא ה-f השלישי ולכן נרצה לייצר מביטוי אמת ושקר שקר - אין לנו בעיה עם P ו-Q ולכן נמשיך הלאה.
*ה-f השלישי שלנו עם אפס הוא ה-f הרביעי ולכן נרצה לייצר מביטוי אמת ואמת שקר - יש לנו בעיה ולכן בכדי שיווצר ביטוי כזה נצטרך לשלול את P כלומר (''¬p''). נבדוק ששינוי זה לא השפיע על ה-f במקום השלישי והראשון: 
** ה-f השני שלנו עם אפס הוא ה-f השלישי ולכן נרצה לייצר מביטוי שקר ושקר שקר - אין לנו בעיה עם P ו-Q ולכן נמשיך הלאה.
** ה-f הראשון שלנו עם אפס הוא ה-f הראשון ולכן נרצה לייצר מביטוי אמת ושקר שקר - אין בעיה 
על כן ה-f שנקבל הינה <math>\lnot p  \land Q</math>

{| class="wikitable"
|-
! <math>\lnot p  \land Q</math> !!Q !! P
|-
|0 || 0 ||0
|-
| 1 || 1 || 0
|-
| 0 || 0|| 1
|-
| 0 || 1 || 1
|}

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