logo

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

Претпоставимо да постоје два сложена исказа, Кс и И, који ће бити познати као логичка еквиваленција ако и само ако табела истинитости оба садржи исте вредности истинитости у њиховим колонама. Уз помоћ симбола = или ⇔ можемо представити логичку еквивалентност. Дакле, Кс = И или Кс ⇔ И ће бити логичка еквиваленција ових исказа.

Уз помоћ дефиниције логичке еквиваленције, разјаснили смо да ако су сложени искази Кс и И логичка еквиваленција, у овом случају, Кс ⇔ И мора бити таутологија.

Закони логичке еквиваленције

У овом закону користићемо симболе 'АНД' и 'ОР' да објаснимо закон логичке еквиваленције. Овде је И означено уз помоћ симбола ∧, а ОР је назначено помоћу симбола ∨. Постоје различити закони логичке еквиваленције, који су описани на следећи начин:

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

У идемпотентном закону користимо само једну изјаву. Према овом закону, ако комбинујемо два иста исказа са симболом ∧(и) и ∨(или), онда ће резултујући исказ бити сам исказ. Претпоставимо да постоји сложени исказ П. Следећи запис се користи за означавање идемпотентног закона:

 P ∨ P ? P P ∧ P ? P 

Табела истинитости за овај закон је описана на следећи начин:

П П П ∨ П П ∧ П
Т Т Т Т
Ф Ф Ф Ф

Ова табела садржи исте вредности истинитости у колонама П, П ∨ П и П ∧ П.

Отуда можемо рећи да је П ∨ П = П и П ∧ П = П.

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

Два исказа се користе да покажу комутативни закон. Према овом закону, ако комбинујемо два исказа са симболом ∧(и) или ∨(или), онда ће резултујући исказ бити исти чак и ако променимо позицију исказа. Претпоставимо да постоје два исказа, П и К. Пропозиција ових исказа ће бити нетачна када су обе изјаве П и К нетачне. У свим осталим случајевима биће истина. Следећи запис се користи да означи комутативни закон:

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

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

П П П ∨ К К ∨ П
Т Т Т Т
Т Ф Т Т
Ф Т Т Т
Ф Ф Ф Ф

Ова табела садржи исте вредности истинитости у колонама П ∨ К и К ∨ П.

Отуда можемо рећи да је П ∨ К ? К ∨ П.

Исто као што можемо доказати П ∧ К ? К ∧ П.

поравнавање слике у цсс-у

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

Три исказа се користе да покажу асоцијативни закон. Према овом закону, ако комбинујемо три исказа уз помоћ заграда симболом ∧(и) или ∨(или), онда ће резултујући исказ бити исти чак и ако променимо редослед заграда. То значи да је овај закон независан од груписања или удруживања. Претпоставимо да постоје три исказа П, К и Р. Пропозиција ових исказа ће бити нетачна када су П, К и Р нетачни. У свим осталим случајевима биће истина. Следећа нотација се користи за означавање асоцијативног закона:

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

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

П П Р П ∨ К К ∨ Р (П ∨ К) ∨ Р П ∨ (К ∨ Р)
Т Т Т Т Т Т Т
Т Т Ф Т Т Т Т
Т Ф Т Т Т Т Т
Т Ф Ф Т Ф Т Т
Ф Т Т Т Т Т Т
Ф Т Ф Т Т Т Т
Ф Ф Т Ф Т Т Т
Ф Ф Ф Ф Ф Ф Ф

Ова табела садржи исте вредности истинитости у колонама П ∨ (К ∨ Р) и (П ∨ К) ∨ Р.

Отуда можемо рећи да је П ∨ (К ∨ Р) ? (П ∨ К) ∨ Р.

Исто као што можемо доказати П ∧ (К ∧ Р) ? (П ∧ К) ∧ Р

Дистрибутивни закон:

Три исказа се користе да покажу дистрибутивни закон. Према овом закону, ако комбинујемо исказ симболом ∨(ОР) са два друга исказа која су спојена симболом ∧(АНД), онда ће резултујући исказ бити исти чак и ако одвојено комбинујемо исказе са симбол ∨(ОР) и комбиновање спојених исказа са ∧(АНД). Претпоставимо да постоје три исказа П, К и Р. Следећа нотација се користи да означи закон дистрибуције:

П ∨ (К ∧ Р) ? (П ∨ К) ∧ (П ∨ Р)

П ∧ (К ∨ Р) ? (П ∧ К) ∨ (П ∧ Р)

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

П П Р К ∧ Р П∨(К ∧Р) П ∨ К П ∨ Р (П ∨ К) ∧ (П ∨ Р)
Т Т Т Т Т Т Т Т
Т Т Ф Ф Т Т Т Т
Т Ф Т Ф Т Т Т Т
Т Ф Ф Ф Т Т Т Т
Ф Т Т Т Т Т Т Т
Ф Т Ф Ф Ф Т Ф Ф
Ф Ф Т Ф Ф Ф Т Ф
Ф Ф Ф Ф Ф Ф Ф Ф

Ова табела садржи исте вредности истинитости у колонама П ∨ (К ∧ Р) и (П ∨ К) ∧ (П ∨ Р).

Отуда можемо рећи да је П ∨ (К ∧ Р) = (П ∨ К) ∧ (П ∨ Р)

Исто као што можемо доказати П ∧ (К ∨ Р) ? (П ∧ К) ∨ (П ∧ Р)

Закон о идентитету:

Једна изјава се користи да покаже закон идентитета. Према овом закону, ако комбинујемо исказ и тачну вредност са симболом ∨(или), онда ће се генерисати тачна вредност. Ако комбинујемо исказ и вредност Фалсе са симболом ∧(и), онда ће он сам генерисати исказ. Слично, то ћемо урадити са супротним симболима. То значи да ако комбинујемо исказ и тачну вредност са симболом ∧(и), онда ће он генерисати саму изјаву, а ако комбинујемо исказ и вредност Фалсе са симболом ∨(или), онда ће генерисати Лажна вредност. Претпоставимо да постоји сложена изјава П, тачна вредност Т и лажна вредност Ф. Следећи запис се користи да означи закон идентитета:

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

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

П Т Ф П ∨ Т П ∨ Ф
Т Т Ф Т Т
Ф Т Ф Т Ф

Ова табела садржи исте вредности истинитости у колонама П ∨ Т и Т. Дакле, можемо рећи да је П ∨ Т = Т. Слично, ова табела такође садржи исте вредности истинитости у колонама П ∨ Ф и П. Отуда можемо рећи да је П ∨ Ф = П.

Исто као што можемо доказати П ∧ Т ? П и П ∧ Ф ? Ф

Закон о допуни:

Појединачни исказ се користи у закону комплемента. Према овом закону, ако комбинујемо исказ са његовим комплементарним исказом са симболом ∨(или), онда ће он генерисати вредност Тачна, а ако комбинујемо ове исказе са симболом ∧(и), онда ће генерисати Нетачно вредност. Ако негирамо тачну вредност, онда ће она генерисати лажну вредност, а ако негирамо лажну вредност, онда ће генерисати праву вредност.

цсс мења величину слике

Следећа нотација се користи да означи закон комплемента:

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

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

П ¬П Т ¬Т Ф ¬Ф П ∨ ¬П П ∧ ¬П
Т Ф Т Ф Ф Т Т Ф
Ф Т Т Ф Ф Т Т Ф

Ова табела садржи исте вредности истинитости у колонама П ∨ ¬П и Т. Дакле, можемо рећи да је П ∨ ¬П = Т. Слично, ова табела такође садржи исте вредности истинитости у колонама П ∧ ¬П и Ф. Отуда можемо рећи да је П ∧ ¬П = Ф.

Ова табела садржи исте вредности истинитости у колонама ¬Т и Ф. Дакле, можемо рећи да је ¬Т = Ф. Слично, ова табела садржи исте вредности истинитости у колонама ¬Ф и Т. Стога можемо рећи да ¬Ф = Т.

Закон двоструке негације или закон инволуције

Једна изјава се користи да покаже закон двоструке негације. Према овом закону, ако урадимо негацију негираног исказа, онда ће резултујући исказ бити сам исказ. Претпоставимо да постоји исказ П и негирани исказ ¬П. Следећа нотација се користи да означи закон двоструке негације:

 ¬(¬P) ? P 

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

П ¬П ¬(¬П)
Т Ф Т
Ф Т Ф

Ова табела садржи исте истините вредности у колонама ¬(¬П) и П. Отуда можемо рећи да је ¬(¬П) = П.

уклоните први знак у Екцел-у

Из Моргановог закона:

Ове две изјаве се користе да покажу Де Морганов закон. Према овом закону, ако комбинујемо два исказа са симболом ∧(АНД), а затим урадимо негацију ових комбинованих исказа, онда ће резултујући исказ бити исти чак и ако комбинујемо негацију оба исказа одвојено са симболом ∨( ИЛИ). Претпоставимо да постоје два сложена исказа, П и К. Следећа нотација се користи да означи Де Морганов закон:

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

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

П П ¬П ¬К П ∧ К ¬(П ∧ К) ¬ П ∨ ¬К
Т Т Ф Ф Т Ф Ф
Т Ф Ф Т Ф Т Т
Ф Т Т Ф Ф Т Т
Ф Ф Т Т Ф Т Т

Ова табела садржи исте вредности истинитости у колонама ¬(П ∧ К) и ¬ П ∨ ¬К. Отуда можемо рећи да је ¬(П ∧ К) = ¬ П ∨ ¬К.

Исто као што можемо доказати ¬(П ∨ К) ? ¬П ∧ ¬К

Закон о апсорпцији:

Ова два исказа се користе да покажу закон апсорпције. Према овом закону, ако комбинујемо исказ П са симболом ∨(ОР) са истим исказом П и још једним исказом К, који су спојени симболом ∧(АНД), онда ће резултујући исказ бити први исказ П. Исти резултат ће бити генерисан ако заменимо симболе. Претпоставимо да постоје два сложена исказа, П и К. Следећа нотација се користи да означи закон апсорпције:

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

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

П П П ∧ К П ∨ К П ∨ (П ∧ К) П ∧ (П ∨ К)
Т Т Т Т Т Т
Т Ф Ф Т Т Т
Ф Т Ф Т Ф Ф
Ф Ф Ф Ф Ф Ф

Ова табела садржи исте вредности истинитости у колонама П ∨ (П ∧ К) и П. Отуда можемо рећи да је П ∨ (П ∧ К) ? П.

Слично, ова табела такође садржи исте вредности истинитости у колонама П ∧ (П ∨ К) и П. Отуда можемо рећи да је П ∧ (П ∨ К) ? П.

Примери логичке еквиваленције

Постоје разни примери логичке еквиваленције. Неки од њих су описани на следећи начин:

Пример 1: У овом примеру ћемо успоставити својство еквиваленције за изјаву, која је описана на следећи начин:

п → к ? ¬п ∨ к

Решење:

Ово ћемо доказати уз помоћ табеле истинитости, која је описана на следећи начин:

П П ¬п п → к ¬п ∨ к
Т Т Ф Т Т
Т Ф Ф Ф Ф
Ф Т Т Т Т
Ф Ф Т Т Т

Ова табела садржи исте истините вредности у колонама п → к и ¬п ∨ к. Отуда можемо рећи да је п → к? ¬п ∨ к.

Пример 2: У овом примеру ћемо успоставити својство еквиваленције за изјаву, која је описана на следећи начин:

П ↔ К ? ( П → К ) ∧ ( К → П )

Решење:

П П П → К К → П П ↔ К ( П → К ) ∧ ( К → П )
Т Т Т Т Т Т
Т Ф Ф Т Ф Ф
Ф Т Т Ф Ф Ф
Ф Ф Т Т Т Т

Ова табела садржи исте вредности истинитости у колонама П ↔ К и (П → К) ∧ (К → П). Отуда можемо рећи да је П ↔ К? (П → К) ∧ (К → П).

Пример 3: У овом примеру, користићемо еквивалентно својство да бисмо доказали следећу изјаву:

п ↔ к ? ( п ∧ к ) ∨ ( ¬ п ∧ ¬к )

Решење:

Да бисмо ово доказали, користићемо неке од горе описаних закона и из овог закона имамо:

п ↔ к ? (¬п ∨ к) ∧ (¬к ∨ п) ...........(1)

Сада ћемо користити комутативни закон у горњој једначини и добити следеће:

? (п ∨ к) ∧ (п ∨ ¬к)

Сада ћемо користити Дистрибутивни закон у овој једначини и добити следеће:

? (¬ п ∧ (п ∨ ¬к)) ∨ (к ∧ (п ∨ ¬к))

уради вхиле петљу јава

Сада ћемо користити дистрибутивни закон у овој једначини и добити следеће:

? (п ∧ п) ∨ (п ∧ ¬к) ∨ (к ∧ п) ∨ (к ∧ ¬к)

Сада ћемо користити закон комплемента у овој једначини и добити следеће:

? Ф ∨ (¬п ∧ ¬к) ∨ (к ∧ п) ∨ Ф

Сада ћемо користити закон о идентитету и добити следеће:

? (¬ п ∧ ¬ к) ∨ (к ∧ п)

Сада ћемо користити комутативни закон у овој једначини и добити следеће:

? (п ∧ к) ∨ (¬ п ¬к)

Коначно, једначина (1) постаје следећа:

п ↔ к ? (п ∧ к) ∨ (¬ п ¬к)

Коначно, можемо рећи да једначина (1) постаје п ↔ к ? (п ∧ к) ∨ (¬ п ∧ ¬к)