==צורות נורמליות: CNF ,DNF==
ישנן 2 שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.
===DNF===
ביטוי מצורת DNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "או". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "וגם". כל אטום הוא משתנה או שלילת משתנה.
ביטוי בצורת DNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "או". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "וגם". כל אטום הוא משתנה או שלילת משתנה. בצורה סכמטית : <math>D_1 \lor D_2 \lor \dots \lor D_n</math> כאשר כל <math>D_i</math> מהצורה <math>p_1\land p_2 \land \dots \land p_m</math> וכל <math>p_i</math> שווה למשתנה <math>x</math> או לשלילותו לשלילתו <math>\lnot x</math>.
דוגמא: נמצא את צורת DNF של טבלת האמת הבאה:
|}
נתמקד בשורות שערך האמת שלהן הוא 1 (שורות 3, 4, 6).
לשורה 3 נתאים את הפסוקית <math>p_1=\lnot x_1 \land x_2 \land \lnot x_3</math>
<math>p_1=\lnot x_1 \land x_2 \land \lnot x_3</math>מה עשינו? החלפנו כל משתנה שערכו 0 בשלילה שלו, וכל משתנה שערכו 1 השארנו בלי לגעת.
מה עשינויצא לנו מזה? התאמנו שימו לב שרק הצבה של ערכי האמת של <math>x_1,x_2,x_3</math> שמופיעים בשורה 3 תתן ערך אמת 1 ב <math>p_1</math>. כל משתנה שערכו הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 0 לשלילה שלו וכל משתנה שערכו 1 השארנו בלי לגעתב <math>p_1</math>.
מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של באופן דומה נייצר <math>x_1,x_2,x_3p_2</math> שמופיעים בשורה 3 תתן ערך אמת 1 ב עבור שורה 4 ו <math>p_1p_3</math>. כל הצבה אחרת (כלומרעבור שורה 6: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 0 ב <math>p_1</math>
באופן דומה נייצר <math>p_2</math> עבור שורה 4 ו <math>p_3</math> עבור שורה 6 <math>p_2=\lnot x_1 \land\lnot x_2 \land x_3, \quad p_3=x_1\land \lnot x_2 \land x_3</math>
כעת ה DNF של טבלת האמת היא פשוט
<math>p_1\or p_2 \or p_3=[(\lnot x_1 \land x_2 \land \lnot x_3]) \or [(\lnot x_1 \land\lnot x_2 \land x_3] ) \or [(x_1\land \lnot x_2 \land x_3])</math>.
===CNF===
ביטוי מצורת CNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "וגם". כל פסוקית בעצמה מורכבת ממחוברים המחוברים ביניהם על ידי פעולות "או". כל מחובר הוא משתנה או שלילת משתנה.
ביטוי בצורת CNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "וגם". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "או". כל אטום הוא משתנה או שלילת משתנה. בצורה סכמטית : <math>C_1 \land C_2 \land \dots \land C_n</math> כאשר כל <math>C_i</math> מהצורה
<math>q_1\lor q_2 \lor \dots \lor q_m</math> וכל <math>q_i</math> שווה למשתנה <math>x</math>
או לשלילותו לשלילתו <math>\lnot x</math>.
נדגים על הדוגמא לעיל.
נתמקד בשורות שערך האמת שלהן הוא 0 (שורות 1,2,5,7,8) שורה 1: נתאים ל- <math>q_1</math>
לשורה 1 נתאים את הפסוקית <math>q_1= x_1 \lor x_2 \lor x_3</math>
מה עשינו? התאמנו כל משתנה שערכו 0 השארנו בלי לגעת , וכל משתנה שערכו 1 התאמנו לשלילתוהחלפנו בשלילתו.
מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של <math>x_1,x_2,x_3</math> שמופיעים בשורה 1 יתנו תתן ערך אמת 0 ב <math>q_1</math>. כל הצבה אחרת (כלומר כל : הצבה של ערכי אמת של המשתנים בשורה אחרת) יתנו תתן 1 ב <math>q_1</math>.
באופן דומה ניצר נייצר <math>q_2,q_3,q_4,q_5</math> עבור שורה שורות 2 , 5 , 7 ו-8:
<math>q_2= x_1 \lor \lnot x_2 \lor \lnot x_3, q_3=\lnot x_1\lor \lnot x_2 \lor x_3</math>
<math>q_1 \land q_2 \land q_3 \land q_4 \land q_5 </math>
הרחבה על ענינים עניינים אלו ניתן למצוא פה [[88-101 חשיבה מתמטית]]