logo

Закон за логическата еквивалентност в дискретната математика

Да предположим, че има две съставни изявления, X и Y, които ще бъдат известни като логическа еквивалентност, ако и само ако таблицата на истинност и на двете съдържа еднакви стойности на истинност в техните колони. С помощта на символа = или ⇔ можем да представим логическата еквивалентност. Така че X = Y или X ⇔ Y ще бъде логическата еквивалентност на тези твърдения.

С помощта на дефиницията за логическа еквивалентност изяснихме, че ако съставните изрази X и Y са логическа еквивалентност, в този случай X ⇔ Y трябва да е тавтология.

Закони на логическата еквивалентност

В този закон ще използваме символите „И“ и „ИЛИ“, за да обясним закона за логическата еквивалентност. Тук И е посочено с помощта на символа ∧, а ИЛИ е посочено с помощта на символа ∨. Има различни закони за логическа еквивалентност, които са описани по следния начин:

Идемпотентен закон:

В идемпотентния закон ние използваме само едно твърдение. Съгласно този закон, ако комбинираме две еднакви изявления със символа ∧(и) и ∨(или), тогава полученото изявление ще бъде самото изявление. Да предположим, че има съставно твърдение P. Следната нотация се използва за обозначаване на идемпотентния закон:

 P ∨ P ? P P ∧ P ? P 

Таблицата на истината за този закон е описана по следния начин:

П П P ∨ P P ∧ P
T T T T
Е Е Е Е

Тази таблица съдържа еднакви стойности на истината в колоните на P, P ∨ P и P ∧ P.

Следователно можем да кажем, че P ∨ P = P и P ∧ P = P.

Комутативни закони:

Двете твърдения се използват за показване на комутативния закон. Съгласно този закон, ако комбинираме две твърдения със символа ∧(и) или ∨(или), тогава полученото твърдение ще бъде същото, дори ако променим позицията на изявленията. Да предположим, че има две твърдения, P и Q. Предложението на тези твърдения ще бъде невярно, когато и двете твърдения P и Q са неверни. Във всички останали случаи ще е вярно. Следната нотация се използва за обозначаване на комутативния закон:

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

Таблицата на истината за тези обозначения е описана по следния начин:

П Q P ∨ Q Q ∨ P
T T T T
T Е T T
Е T T T
Е Е Е Е

Тази таблица съдържа еднакви стойности на истината в колоните на P ∨ Q и Q ∨ P.

Следователно можем да кажем, че P ∨ Q ? Q ∨ P.

Същото, както можем да докажем P ∧ Q ? Q ∧ P.

Асоциативен закон:

Трите твърдения се използват за показване на асоциативния закон. Съгласно този закон, ако комбинираме три твърдения с помощта на скоби със символа ∧(и) или ∨(или), тогава резултантното твърдение ще бъде същото, дори ако променим реда на скобите. Това означава, че този закон е независим от групи или асоциации. Да предположим, че има три твърдения P, Q и R. Предложението на тези твърдения ще бъде невярно, когато P, Q и R са неверни. Във всички останали случаи ще е вярно. За обозначаване на асоциативния закон се използва следната нотация:

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

Таблицата на истината за тези обозначения е описана по следния начин:

П Q Р P ∨ Q Q ∨ R (P ∨ Q) ∨ R P ∨ (Q ∨ R)
T T T T T T T
T T Е T T T T
T Е T T T T T
T Е Е T Е T T
Е T T T T T T
Е T Е T T T T
Е Е T Е T T T
Е Е Е Е Е Е Е

Тази таблица съдържа същите стойности на истината в колоните на 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) ∧ (P ∨ R)

вмъкнете в клавиатурата

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

Таблицата на истината за тези обозначения е описана по следния начин:

П Q Р Q ∧ R P∨(Q ∧R) P ∨ Q P ∨ R (P ∨ Q) ∧ (P ∨ R)
T T T T T T T T
T T Е Е T T T T
T Е T Е T T T T
T Е Е Е T T T T
Е T T T T T T T
Е T Е Е Е T Е Е
Е Е T Е Е Е T Е
Е Е Е Е Е Е Е Е

Тази таблица съдържа същите стойности на истината в колоните на P ∨ (Q ∧ R) и (P ∨ Q) ∧ (P ∨ R).

Следователно можем да кажем, че P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)

Същото, както можем да докажем P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)

Закон за самоличността:

Единична декларация се използва за показване на закона за идентичността. Съгласно този закон, ако комбинираме изявление и истинска стойност със символа ∨(или), тогава това ще генерира истинската стойност. Ако комбинираме израз и стойност False със символа ∧(и), тогава той ще генерира самия израз. По същия начин ще направим това с противоположните символи. Това означава, че ако комбинираме изявление и истинска стойност със символа ∧(и), тогава ще генерира самото изявление, а ако комбинираме изявление и невярна стойност със символа ∨(или), тогава ще генерира Фалшива стойност. Да предположим, че има съставно твърдение P, истинска стойност T и невярна стойност F. Следната нотация се използва за обозначаване на закона за идентичност:

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

Таблицата на истината за тези обозначения е описана по следния начин:

П T Е P ∨ T P ∨ F
T T Е T T
Е T Е T Е

Тази таблица съдържа еднакви истинностни стойности в колоните на P ∨ T и T. Следователно можем да кажем, че P ∨ T = T. По подобен начин тази таблица също съдържа същите истинностни стойности в колоните на P ∨ F и P. Следователно можем да кажем, че P ∨ F = P.

Същото, както можем да докажем P ∧ T ? P и P ∧ F ? Е

Закон за допълнение:

Единична декларация се използва в закона за допълване. Съгласно този закон, ако комбинираме изявление с неговото допълващо изявление със символа ∨(or), тогава то ще генерира стойността True, а ако комбинираме тези изявления със символа ∧(and), тогава то ще генерира False стойност. Ако отхвърлим истинска стойност, тогава тя ще генерира фалшива стойност, а ако отхвърлим фалшива стойност, тогава тя ще генерира истинската стойност.

Следната нотация се използва за обозначаване на закона за допълване:

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

Таблицата на истината за тези обозначения е описана по следния начин:

шлока мехта образование
П ¬P T ¬Т Е ¬F P ∨ ¬P P ∧ ¬P
T Е T Е Е T T Е
Е T T Е Е T T Е

Тази таблица съдържа еднакви истинностни стойности в колоните на 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)
T Е T
Е T Е

Тази таблица съдържа еднакви стойности на истината в колоните на ¬(¬P) и P. Следователно можем да кажем, че ¬(¬P) = P.

От закона на Морган:

Двете твърдения се използват за показване на закона на Де Морган. Съгласно този закон, ако комбинираме две твърдения със символа ∧(AND) и след това извършим отрицанието на тези комбинирани твърдения, тогава резултантното твърдение ще бъде същото, дори ако комбинираме отрицанието на двете твърдения поотделно със символа ∨( ИЛИ). Да предположим, че има две съставни изявления, P и Q. Следната нотация се използва за обозначаване на закона на Де Морган:

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

Таблицата на истината за тези обозначения е описана по следния начин:

П Q ¬P ¬Q P ∧ Q ¬(P ∧ Q) ¬ P ∨ ¬Q
T T Е Е T Е Е
T Е Е T Е T T
Е T T Е Е T T
Е Е T T Е T T

Тази таблица съдържа същите стойности на истината в колоните на ¬(P ∧ Q) и ¬ P ∨ ¬Q. Следователно можем да кажем, че ¬(P ∧ Q) = ¬ P ∨ ¬Q.

Същото, както можем да докажем ¬(P ∨ Q)? ¬P ∧ ¬Q

Закон за абсорбция:

Двете твърдения се използват за показване на закона за поглъщане. Съгласно този закон, ако комбинираме изявление P чрез символ ∨(ИЛИ) със същото изявление P и друго изявление Q, които са свързани със символа ∧(И), тогава полученото изявление ще бъде първото изявление P. Същият резултат ще се генерира, ако разменим символите. Да предположим, че има две съставни твърдения, P и Q. Следната нотация се използва за обозначаване на Закона за абсорбция:

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

Таблицата на истината за тези обозначения е описана по следния начин:

П Q P ∧ Q P ∨ Q P ∨ (P ∧ Q) P ∧ (P ∨ Q)
T T T T T T
T Е Е T T T
Е T Е T Е Е
Е Е Е Е Е Е

Тази таблица съдържа еднакви стойности на истината в колоните на P ∨ (P ∧ Q) и P. Следователно можем да кажем, че P ∨ (P ∧ Q) ? П.

По подобен начин тази таблица също съдържа същите истинностни стойности в колоните на P ∧ (P ∨ Q) и P. Следователно можем да кажем, че P ∧ (P ∨ Q) ? П.

Примери за логическа еквивалентност

Има различни примери за логическа еквивалентност. Някои от тях са описани по следния начин:

Пример 1: В този пример ще установим свойството еквивалентност за изявление, което е описано по следния начин:

p → q ? ¬p ∨ q

Решение:

Ще докажем това с помощта на таблица на истината, която е описана по следния начин:

П Q ¬стр p → q ¬p ∨ q
T T Е T T
T Е Е Е Е
Е T T T T
Е Е T T T

Тази таблица съдържа същите стойности на истината в колоните на p → q и ¬p ∨ q. Следователно можем да кажем, че p → q ? ¬p ∨ q.

Пример 2: В този пример ще установим свойството еквивалентност за изявление, което е описано по следния начин:

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

Решение:

0,0625 като дроб
П Q P → Q Q → P P ↔ Q ( P → Q ) ∧ ( Q → P )
T T T T T T
T Е Е T Е Е
Е T T Е Е Е
Е Е T T T T

Тази таблица съдържа същите стойности на истината в колоните на P ↔ Q и (P → Q) ∧ (Q → P). Следователно можем да кажем, че P ↔ Q ? (P → Q) ∧ (Q → P).

Пример 3: В този пример ще използваме еквивалентното свойство, за да докажем следното твърдение:

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

Решение:

За да докажем това, ще използваме някои от гореописаните закони и от този закон имаме:

списък към масив java

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 ∧ ¬ q) ∨ (q ∧ p)

Сега ще използваме комутативния закон в това уравнение и ще получим следното:

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

Накрая уравнение (1) става следното:

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

И накрая, можем да кажем, че уравнението (1) става p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)