logo

חוק השקילות הלוגית במתמטיקה בדידה

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

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

חוקי השקילות לוגית

בחוק זה, נשתמש בסמלים 'AND' ו'OR' כדי להסביר את חוק השקילות הלוגית. כאן, AND מסומן בעזרת סמל ∧ ו- OR מסומן בעזרת סמל ∨. ישנם חוקים שונים של שקילות לוגית, המתוארים כך:

חוק אימפוטנטיים:

בחוק האידמפוטנטי, אנו משתמשים רק באמירה אחת. לפי חוק זה, אם נשלב שני משפטים זהים עם הסמל ∧(ו) ו∨(או), אז ההצהרה המתקבלת תהיה ההצהרה עצמה. נניח שיש משפט מורכב P. הסימן הבא משמש לציון חוק האימפוטנטי:

 P ∨ P ? P P ∧ P ? P 

טבלת האמת של חוק זה מתוארת כך:

פ פ P ∨ P P ∧ P
ט ט ט ט
ו ו ו ו

טבלה זו מכילה את אותם ערכי אמת בעמודות P, P ∨ P ו- P ∧ P.

מכאן שאנו יכולים לומר ש- P ∨ P = P ו- P ∧ P = P.

חוקים קומוטטיביים:

שתי ההצהרות משמשות להצגה של החוק הקומוטטיבי. על פי חוק זה, אם נשלב שני משפטים עם הסמל ∧(ו) או ∨(או), אז ההצהרה המתקבלת תהיה זהה גם אם נשנה את מיקום ההיגדים. נניח שיש שתי הצהרות, P ו-Q. ההצעה של הצהרות אלו תהיה שקרית כאשר שתי ההצהרות P ו-Q שגויות. בכל שאר המקרים, זה יהיה נכון. הסימון הבא משמש לציון החוק הקומוטטיבי:

 P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ש P ∨ ש ש ∨ P
ט ט ט ט
ט ו ט ט
ו ט ט ט
ו ו ו ו

טבלה זו מכילה את אותם ערכי אמת בעמודות P ∨ Q ו-Q ∨ P.

מכאן נוכל לומר ש-P ∨ Q ? ש ∨ P.

בדיוק כפי שאנו יכולים להוכיח P ∧ Q ? ש ∧ P.

משפט אסוציאטיבי:

שלושת ההיגדים משמשים להצגה של החוק האסוציאטיבי. לפי חוק זה, אם נשלב שלוש משפטים בעזרת סוגריים על ידי הסמל ∧(ו) או ∨(או), אז ההצהרה המתקבלת תהיה זהה גם אם נשנה את סדר הסוגריים. זה אומר שהחוק הזה אינו תלוי בקיבוץ או בהתאגדות. נניח שיש שלוש הצהרות P, Q ו-R. ההצעה של הצהרות אלו תהיה שקרית כאשר P, Q ו-R שגויות. בכל שאר המקרים, זה יהיה נכון. הסימון הבא משמש לציון החוק האסוציאטיבי:

 P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ש ר P ∨ ש Q ∨ R (P ∨ Q) ∨ R P ∨ (Q ∨ R)
ט ט ט ט ט ט ט
ט ט ו ט ט ט ט
ט ו ט ט ט ט ט
ט ו ו ט ו ט ט
ו ט ט ט ט ט ט
ו ט ו ט ט ט ט
ו ו ט ו ט ט ט
ו ו ו ו ו ו ו

טבלה זו מכילה את אותם ערכי אמת בעמודות של P ∨ (Q ∨ R) ו- (P ∨ Q) ∨ R.

מכאן נוכל לומר ש-P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.

בדיוק כפי שאנו יכולים להוכיח P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R

חוק חלוקתי:

שלוש ההצהרות משמשות להצגה של החוק החלוקתי. על פי חוק זה, אם נשלב הצהרה על ידי סמל ∨(OR) עם שני ההיגדים האחרים המצורפים לסמל ∧(AND), אז ההצהרה המתקבלת תהיה זהה גם אם אנו משלבים את ההצהרות בנפרד עם הסמל ∨(OR) ושילוב ההצהרות המצורפות עם ∧(AND). נניח שיש שלוש הצהרות P, Q ו-R. הציון הבא משמש לציון החוק החלוקתי:

P ∨ (Q ∧ R) ? (P ∨ Q) ∧ (P ∨ R)

P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ש ר ש ∧ ר P∨(Q ∧R) P ∨ ש P ∨ R (P ∨ Q) ∧ (P ∨ R)
ט ט ט ט ט ט ט ט
ט ט ו ו ט ט ט ט
ט ו ט ו ט ט ט ט
ט ו ו ו ט ט ט ט
ו ט ט ט ט ט ט ט
ו ט ו ו ו ט ו ו
ו ו ט ו ו ו ט ו
ו ו ו ו ו ו ו ו

טבלה זו מכילה את אותם ערכי אמת בעמודות של P ∨ (Q ∧ R) ו- (P ∨ Q) ∧ (P ∨ R).

מכאן נוכל לומר ש-P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)

בדיוק כפי שאנו יכולים להוכיח P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)

חוק הזהות:

הצהרה אחת משמשת להצגת חוק הזהות. לפי חוק זה, אם נשלב משפט וערך True עם הסמל ∨(or), אז זה יפיק את הערך True. אם נשלב הצהרה וערך False עם הסמל ∧(and), אז זה יפיק את המשפט עצמו. באופן דומה, נעשה זאת עם הסמלים ההפוכים. כלומר אם נשלב משפט וערך True עם הסמל ∧(and), אז זה יפיק את ההצהרה עצמה, ואם נשלב משפט וערך False עם הסמל ∨(or), אז זה יפיק את ה- ערך כוזב. נניח שיש משפט מורכב P, ערך אמיתי T וערך שקרי F. הציון הבא משמש לציון חוק הזהות:

 P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ט ו P ∨ T P ∨ F
ט ט ו ט ט
ו ט ו ט ו

טבלה זו מכילה את אותם ערכי אמת בעמודות של P ∨ T ו- T. מכאן שניתן לומר ש- P ∨ T = T. באופן דומה, טבלה זו מכילה גם את אותם ערכי אמת בעמודות של P ∨ F ו- P. מכאן אנו יכולים לומר ש- P ∨ F = P.

בדיוק כפי שאנו יכולים להוכיח P ∧ T ? P ו-P ∧ F ? ו

חוק משלים:

בחוק המשלים נעשה שימוש במשפט יחיד. לפי חוק זה, אם נשלב הצהרה עם ההצהרה המשלימה שלה עם הסמל ∨(או), אז היא תיצור את הערך True, ואם נשלב את ההצהרות הללו עם הסמל ∧(and), אז היא תיצור את ה-False ערך. אם נשלול ערך אמיתי, אז הוא יפיק ערך שקר, ואם נשלול ערך שקר, אז זה יפיק את הערך האמיתי.

הסימון הבא משמש לציון חוק המשלים:

 P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ¬P ט ¬T ו ¬F P ∨ ¬P P ∧ ¬P
ט ו ט ו ו ט ט ו
ו ט ט ו ו ט ט ו

טבלה זו מכילה את אותם ערכי אמת בעמודות של P ∨ ¬P ו-T. מכאן שאנו יכולים לומר ש- P ∨ ¬P = T. באופן דומה, טבלה זו מכילה גם את אותם ערכי אמת בעמודות של P ∧ ¬P ו F. מכאן שאנו יכולים לומר ש-P ∧ ¬P = F.

טבלה זו מכילה את אותם ערכי אמת בעמודות ¬T ו-F. מכאן, אנו יכולים לומר ש- ¬T = F. באופן דומה, טבלה זו מכילה את אותם ערכי אמת בעמודות ¬F ו-T. מכאן שאנו יכולים לומר ש ¬F = T.

חוק שלילה כפולה או חוק אינבולוציה

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

 ¬(¬P) ? P 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ¬P ¬(¬P)
ט ו ט
ו ט ו

טבלה זו מכילה את אותם ערכי אמת בעמודות ¬(¬P) ו-P. מכאן שאנו יכולים לומר ש¬(¬P) = P.

מתוך חוק מורגן:

שתי ההצהרות משמשות כדי להראות את חוק דה מורגן. לפי חוק זה, אם נשלב שני משפטים עם הסמל ∧(AND) ואז נעשה את השלילה של ההצהרות המשולבות הללו, אז ההצהרה המתקבלת תהיה זהה גם אם נשלב את השלילה של שני ההיגדים בנפרד עם הסמל ∨( אוֹ). נניח שיש שתי הצהרות מורכבות, P ו-Q. הציון הבא משמש לציון חוק דה מורגן:

 ¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ש ¬P ¬ש P ∧ ש ¬(P ∧ ש) ¬ P ∨ ¬ש
ט ט ו ו ט ו ו
ט ו ו ט ו ט ט
ו ט ט ו ו ט ט
ו ו ט ט ו ט ט

טבלה זו מכילה את אותם ערכי אמת בעמודות ¬(P ∧ Q) ו-¬ P ∨ ¬Q. מכאן נוכל לומר ש¬(P ∧ Q) = ¬ P ∨ ¬Q.

בדיוק כפי שאנו יכולים להוכיח ¬(P ∨ Q) ? ¬P ∧ ¬ש

חוק הקליטה:

שתי האמירות משמשות להצגת חוק הקליטה. על פי חוק זה, אם נשלב משפט P על ידי סמל ∨(OR) עם אותו משפט P ומשפט אחד נוסף Q, המצורפים לסמל ∧(AND), אז ההצהרה המתקבלת תהיה ההצהרה הראשונה P. אותה תוצאה תיווצר אם נחליף את הסמלים. נניח שיש שני משפטים מורכבים, P ו-Q. הסימן הבא משמש לציון חוק הקליטה:

 P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P 

טבלת האמת לסימונים אלה מתוארת באופן הבא:

פ ש P ∧ ש P ∨ ש P ∨ (P ∧ Q) P ∧ (P ∨ Q)
ט ט ט ט ט ט
ט ו ו ט ט ט
ו ט ו ט ו ו
ו ו ו ו ו ו

טבלה זו מכילה את אותם ערכי אמת בעמודות P ∨ (P ∧ Q) ו-P. מכאן שאנו יכולים לומר ש- P ∨ (P ∧ Q) ? פ.

באופן דומה, טבלה זו מכילה גם את אותם ערכי אמת בעמודות P ∧ (P ∨ Q) ו-P. מכאן שאנו יכולים לומר ש- P ∧ (P ∨ Q) ? פ.

דוגמאות לשוויון לוגי

ישנן דוגמאות שונות של שקילות לוגית. כמה מהם מתוארים כך:

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

p → q ? ¬p ∨ ש

פִּתָרוֹן:

נוכיח זאת בעזרת טבלת אמת, המתוארת כך:

פ ש ¬עמ' p → ש ¬p ∨ ש
ט ט ו ט ט
ט ו ו ו ו
ו ט ט ט ט
ו ו ט ט ט

טבלה זו מכילה את אותם ערכי אמת בעמודות של p → q ו-¬p ∨ q. מכאן נוכל לומר ש-p → q ? ¬p ∨ ש.

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

P ↔ ש ? ( P → Q ) ∧ ( Q → P )

פִּתָרוֹן:

קלט java
פ ש P → ש ש → P P ↔ ש ( P → Q ) ∧ ( Q → P )
ט ט ט ט ט ט
ט ו ו ט ו ו
ו ט ט ו ו ו
ו ו ט ט ט ט

טבלה זו מכילה את אותם ערכי אמת בעמודות של P ↔ Q ו- (P → Q) ∧ (Q → P). מכאן נוכל לומר ש-P ↔ Q ? (P → Q) ∧ (Q → P).

דוגמה 3: בדוגמה זו, נשתמש במאפיין המקביל כדי להוכיח את המשפט הבא:

p ↔ q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q )

פִּתָרוֹן:

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

p ↔ q ? (¬p ∨ q) ∧ (¬q ∨ p) ...........(1)

כעת נשתמש בחוק הקומוטטיבי במשוואה שלעיל ונקבל את הדברים הבאים:

? (p ∨ q) ∧ (p ∨ ¬q)

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

? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))

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

? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)

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

? F ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F

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

? (¬ p ∧ ¬ ש) ∨ (ש ∧ p)

כעת נשתמש בחוק הקומוטטיבי במשוואה זו ונקבל את הדברים הבאים:

? (p ∧ q) ∨ (¬ p ¬q)

לבסוף, משוואה (1) הופכת להיות הבאה:

p ↔ q ? (p ∧ q) ∨ (¬ p ¬q)

לבסוף, ניתן לומר שהמשוואה (1) הופכת ל-p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)