נניח שישנן שתי נוסחאות, X ו-Y. נוסחאות אלו יכוונו כאקוויוולנטיות אם X ↔ Y היא טאוטולוגיה. אם שתי נוסחאות X ↔ Y הן טאוטולוגיה, אז נוכל לכתוב אותה גם כ-X ⇔ Y, ונוכל לקרוא את הקשר הזה שכן X הוא שקילות ל-Y.

הערה: יש כמה נקודות שעלינו לזכור בזמן שקילות לינארית של נוסחה, המתוארות כדלקמן:

• ⇔ משמש לציון סמל בלבד, אך אינו מקשר.
• ערך האמת של X ו-Y תמיד יהיה שווה אם X ↔ Y הוא טאוטולוגיה.
• יחס השקילות מכיל שתי תכונות, כלומר, סימטרי וטרנזיטיבי.

שיטה 1: שיטת טבלת האמת:

בשיטה זו, נבנה את טבלאות האמת של כל נוסחת שתי הצהרות ולאחר מכן נבדוק האם ההצהרות הללו שוות ערך.

דוגמה 1: בדוגמה זו, עלינו להוכיח את X ∨ Y ⇔ ¬(¬X ∧ ¬Y).

פִּתָרוֹן: טבלת האמת של X ∨ Y ⇔ ¬(¬X ∧ ¬Y) מתוארת באופן הבא:

כפי שאנו יכולים לראות ש-X ∨ Y ו-¬(¬X ∧ ¬Y) היא טאוטולוגיה. מכאן X ∨ Y ⇔ ¬(¬X ∧ ¬Y).

דוגמה 2: בדוגמה זו, עלינו להוכיח (X → Y) ⇔ (¬X ∨ Y).

פִּתָרוֹן: טבלת האמת של (X → Y) ⇔ (¬X ∨ Y) מתוארת באופן הבא:

כפי שאנו יכולים לראות כי X → Y ו-(¬X ∨ Y) הם טאוטולוגיה. לפיכך (X → Y) ⇔ (¬X ∨ Y)

נוסחת שקילות:

ישנם חוקים שונים המשמשים להוכחת נוסחת השקילות, המתוארת כך:

חוק אדמומיות: אם יש נוסחת הצהרה אחת, היא תכיל את המאפיינים הבאים:

 X ∨ X ⇔ X X ∧ X ⇔ X 

חוק אסוציאטיבי: אם ישנן שלוש נוסחאות הצהרות, הוא יכיל את המאפיינים הבאים:

 (X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z) 

חוק חלופי: אם יש שתי נוסחאות הצהרות, הוא יכיל את המאפיינים הבאים:

 X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X 

חוק חלוקתי: אם ישנן שלוש נוסחאות הצהרות, הוא יכיל את המאפיינים הבאים:

תמונות סימון

 X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z) 

חוק זהות: אם יש נוסחת הצהרה אחת, היא תכיל את המאפיינים הבאים:

 (a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F 

חוק משלים: אם יש נוסחת הצהרה אחת, היא תכיל את המאפיינים הבאים:

 (a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T 

חוק הקליטה: אם יש שתי נוסחאות הצהרות, הוא יכיל את המאפיינים הבאים:

 X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X 

מתוך חוק מורגן: אם יש שתי נוסחאות הצהרות, הוא יכיל את המאפיינים הבאים:

 ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y 

שיטה 2: תהליך החלפה

בשיטה זו, נניח נוסחה A : X → (Y → Z). הנוסחה Y → Z יכולה להיות ידועה כחלק של הנוסחה. אם נחליף חלק זה של הנוסחה, כלומר Y → Z, בעזרת נוסחת השקילות ¬Y ∨ Z ב-A, אז נקבל נוסחה נוספת, כלומר, B : X → (¬Y ∨ Z). זהו תהליך קל לוודא אם הנוסחאות הנתונות A ו-B שוות זו לזו או לא. בעזרת תהליך החלפה נוכל לקבל את ב' מא'.

דוגמה 1: בדוגמה זו, עלינו להוכיח כי {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.

פִּתָרוֹן: כאן, ניקח את חלק הצד השמאלי וננסה להשיג את החלק הימני.

 X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y] 

כעת נשתמש בחוק האסוציאטיבי כך:

 ⇔ (¬X ∨ ¬Y) ∨ Z 

כעת נשתמש בחוק של דה מורגן כך:

 ⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y] 

מכאן הוכח

 {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z 

דוגמה 2: בדוגמה זו, עלינו להוכיח ש-{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) ​​→ Y.

פִּתָרוֹן: כאן, ניקח את חלק הצד השמאלי וננסה להשיג את החלק הימני.

 (X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y 

מכאן הוכח

{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) ​​→ Y

דוגמה 3: בדוגמה זו, עלינו להוכיח ש-X → (Y → X) ⇔ ¬X → (X → Y).

פִּתָרוֹן: כאן, ניקח את חלק הצד השמאלי וננסה להשיג את החלק הימני.

 X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T 

מכאן הוכח

 X → (Y → X) ⇔ ¬X → (X → Y) 

דוגמה 4: בדוגמה זו, עלינו להוכיח כי (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.

פִּתָרוֹן: כאן, ניקח את חלק הצד השמאלי וננסה להשיג את החלק הימני.

הערות java

 (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) 

כעת נשתמש בחוקים האסוציאטיביים וההפצתיים כך:

 ⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z) 

כעת נשתמש בחוק דה מורגן כך:

 ⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z) 

כעת נשתמש בחוק ההפצה כך:

 ⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R 

מכאן הוכח

 (¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R 

דוגמה 5: בדוגמה זו, עלינו להראות ש-((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) היא טאוטולוגיה.

פִּתָרוֹן: כאן, ניקח חלקים קטנים ונפתור אותם.

ראשית, נשתמש בחוק דה מורגן ונקבל את הדברים הבאים:

 ¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z) 

לָכֵן,

 (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z)) 

גַם

 ¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) 

לָכֵן

 ((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) 

לכן

 ((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T 

מכאן שאנו יכולים לומר שהנוסחה הנתונה היא טאוטולוגיה.

דוגמה 6: בדוגמה זו, עלינו להראות ש-(X ∧ Y) → (X ∨ Y) היא טאוטולוגיה.

פִּתָרוֹן: (X ∧ Y) → (X ∨ Y)

 ⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y] 

כעת נשתמש בחוק של דה מורגן כך:

 ⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y) 

כעת נשתמש בחוק האסוציאטיבי ובחוק הקומוטטיבי כך:

 ⇔ (¬X ∨ X) ∨ (¬Y ∨ Y) 

כעת נשתמש בחוק השלילה כך:

 ⇔ (T ∨ T) ⇔ T 

מכאן שאנו יכולים לומר שהנוסחה הנתונה היא טאוטולוגיה.

דוגמה 7: בדוגמה זו, עלינו לכתוב את השלילה של כמה הצהרות, המתוארות כך:

1. נישואי תסיים את לימודיה או תקבל את מכתב ההצטרפות של חברת XYZ.
2. הארי ייצא מחר לסיבוב או ירוץ.
3. אם אקבל ציונים טובים, בן דוד שלי יקנא.

פִּתָרוֹן: ראשית, נפתור את ההצהרה הראשונה כך:

1. נניח X: תתחתן תשלים את השכלתה.

Y: קבל את מכתב ההצטרפות של חברת XYZ.

אנו יכולים להשתמש בצורה הסמלית הבאה כדי לבטא את ההצהרה הזו:

 X ∨ Y 

השלילה של X ∨ Y מתוארת באופן הבא:

 ¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y 

לסיכום, שלילת ההצהרה הנתונה תהיה:

 ¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company. 

2. נניח X: הארי ייצא לסיבוב

Y: הארי ירוץ מחר

אנו יכולים להשתמש בצורה הסמלית הבאה כדי לבטא את ההצהרה הזו:

 X ∨ Y 

השלילה של X ∨ Y מתוארת באופן הבא:

 ¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y 

לסיכום, שלילת ההצהרה הנתונה תהיה:

 ¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow 

3. נניח X: אם אקבל ציונים טובים.

Y: בן דוד שלי יקנא.

אנו יכולים להשתמש בצורה הסמלית הבאה כדי לבטא את ההצהרה הזו:

 X → Y 

השלילה של X → Y מתוארת באופן הבא:

 ¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y. 

לסיכום, שלילת ההצהרה הנתונה תהיה:

 X ∧ ¬Y: I get good marks, and my cousin will not be jealous. 

דוגמה 8: בדוגמה זו, עלינו לכתוב את השלילה של כמה אמירות בעזרת חוק דה מורגן. הצהרות אלו מתוארות כדלקמן:

1. אני צריך משובץ יהלומים ושווה טבעת זהב.
2. תשיג עבודה טובה או שלא תקבל שותף טוב.
3. אני לוקח הרבה עבודה ואני לא יכול להתמודד עם זה.
4. הכלב שלי יוצא לטיול או שהוא עושה בלגן בבית.

פִּתָרוֹן: שלילת כל ההצהרות בעזרת חוק דה מורגן מתוארת אחת אחת כך:

1. אני לא צריך משובץ יהלומים או לא שווה טבעת זהב.
2. אתה לא יכול להשיג עבודה טובה ותקבל שותף טוב.
3. אני לא לוקח הרבה עבודה או שאני יכול להתמודד עם זה.
4. הכלב שלי לא יוצא לטיול והוא לא עושה בלגן בבית.

דוגמה 9: בדוגמה זו, יש לנו כמה הצהרות, ועלינו לכתוב את השלילה של הצהרות אלו. ההצהרות מתוארות כך:

1. אם יורד גשם, אז התוכנית ללכת לים מבוטלת.
2. אם אלמד קשה, אז אקבל ציונים טובים בבחינה.
3. אם אלך למסיבה מאוחרת בלילה, אז אקבל עונש מאבי.
4. אם אתה לא רוצה לדבר איתי, אז אתה צריך לחסום את המספר שלי.

פִּתָרוֹן: השלילה של כל ההצהרות מתוארת אחת אחת כך:

1. אם התוכנית ללכת לים תבוטל, אז יורד גשם.
2. אם אני מקבל ציונים טובים בבחינה, אז אני לומד קשה.
3. אם אקבל עונש מאבי, אז אני הולך למסיבה מאוחרת בלילה.
4. אם אתה צריך לחסום את המספר שלי, אז אתה לא רוצה לדבר איתי.

דוגמה 10: בדוגמה זו, עלינו לבדוק אם (X → Y) → Z ו-X → (Y → Z) שווים מבחינה לוגית או לא. עלינו לנמק את תשובתנו בעזרת טבלאות אמת ובעזרת כללי היגיון כדי לפשט את שני הביטויים.

פִּתָרוֹן: ראשית, נשתמש בשיטה 1 כדי לבדוק האם (X → Y) → Z ו-X → (Y → Z) שוות ערך מבחינה לוגית, המתוארת כך:

hashing במבנה הנתונים

שיטה 1: כאן, נניח את הדברים הבאים:

 (X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z) 

ו

 X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z) 

שיטה 2: כעת, נשתמש בשיטה השנייה. בשיטה זו נשתמש בטבלת האמת.

בטבלת אמת זו, אנו יכולים לראות שהעמודות של (X → Y) → Z ו-X → (Y → Z) אינן מכילות ערכים זהים.