Załóżmy, że istnieją dwa stwierdzenia złożone, X i Y, które będą znane jako równoważność logiczna wtedy i tylko wtedy, gdy tabela prawdy obu z nich zawiera te same wartości logiczne w swoich kolumnach. Za pomocą symbolu = lub ⇔ możemy przedstawić równoważność logiczną. Zatem X = Y lub X ⇔ Y będzie logiczną równoważnością tych stwierdzeń.
Za pomocą definicji równoważności logicznej wyjaśniliśmy, że jeśli zdania złożone X i Y są równoważnością logiczną, w tym przypadku X ⇔ Y musi być tautologią.
Prawa równoważności logicznej
W tym prawie będziemy używać symboli „AND” i „OR”, aby wyjaśnić prawo równoważności logicznej. Tutaj AND jest oznaczony za pomocą symbolu ∧, a OR jest oznaczony za pomocą symbolu ∨. Istnieją różne prawa równoważności logicznej, które opisano w następujący sposób:
Prawo idempotentne:
W prawie idempotentnym używamy tylko jednego stwierdzenia. Zgodnie z tym prawem, jeśli połączymy dwa takie same stwierdzenia z symbolami ∧(i) i ∨(lub), to wynikowe zdanie będzie samym stwierdzeniem. Załóżmy, że istnieje zdanie złożone P. Poniższa notacja służy do wskazania prawa idempotentnego:
P ∨ P ? P P ∧ P ? P
Tabela prawdy dla tego prawa jest opisana w następujący sposób:
| P | P | P ∨ P | P ∧ P |
|---|---|---|---|
| T | T | T | T |
| F | F | F | F |
Ta tabela zawiera te same wartości prawdy w kolumnach P, P ∨ P i P ∧ P.
Stąd możemy powiedzieć, że P ∨ P = P i P ∧ P = P.
Prawa przemienne:
Obydwa stwierdzenia służą do pokazania prawa przemienności. Zgodnie z tym prawem, jeśli połączymy dwa stwierdzenia o symbolu ∧(i) lub ∨(lub), to zdanie wynikowe będzie takie samo, nawet jeśli zmienimy położenie zdań. Załóżmy, że istnieją dwa stwierdzenia P i Q. Twierdzenie tych stwierdzeń będzie fałszywe, gdy oba stwierdzenia P i Q będą fałszywe. We wszystkich pozostałych przypadkach będzie to prawdą. Do wskazania prawa przemienności stosuje się następującą notację:
P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | Q | P ∨ Q | Q ∨ P |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | F |
Ta tabela zawiera te same wartości prawdy w kolumnach P ∨ Q i Q ∨ P.
Zatem możemy powiedzieć, że P ∨ Q ? Q ∨ P.
Tak samo jak możemy udowodnić P ∧ Q ? Q ∧ P.
Prawo stowarzyszeniowe:
Te trzy stwierdzenia służą do pokazania prawa skojarzeń. Zgodnie z tym prawem, jeśli połączymy trzy stwierdzenia za pomocą nawiasów symbolem ∧(i) lub ∨(lub), to wynikowe stwierdzenie będzie takie samo, nawet jeśli zmienimy kolejność nawiasów. Oznacza to, że to prawo jest niezależne od ugrupowania lub stowarzyszenia. Załóżmy, że istnieją trzy stwierdzenia P, Q i R. Twierdzenie tych stwierdzeń będzie fałszywe, gdy P, Q i R będą fałszywe. We wszystkich pozostałych przypadkach będzie to prawdą. Do wskazania prawa skojarzeń używa się następującej notacji:
P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | Q | R | P ∨ Q | Q ∨ R | (P ∨ Q) ∨ R | P ∨ (Q ∨ R) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | T | T | T | T |
| T | F | F | T | F | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | F | T | T | T |
| F | F | F | F | F | F | F |
Ta tabela zawiera te same wartości prawdy w kolumnach P ∨ (Q ∨ R) i (P ∨ Q) ∨ R.
Zatem możemy powiedzieć, że P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.
Tak samo, jak możemy udowodnić P ∧ (Q ∧ R)? (P ∧ Q) ∧ R
Prawo rozdzielne:
Te trzy stwierdzenia służą do pokazania prawa rozdzielności. Zgodnie z tym prawem, jeśli połączymy zdanie o symbolu ∨(OR) z dwoma innymi stwierdzeniami, które są połączone symbolem ∧(AND), to wynikowe zdanie będzie takie samo, nawet jeśli osobno połączymy zdania z symbol ∨(OR) i łączenie połączonych instrukcji za pomocą ∧(ORAZ). Załóżmy, że istnieją trzy stwierdzenia P, Q i R. Do wskazania prawa rozdzielności stosuje się następującą notację:
abstrakcja w Javie
P ∨ (Q ∧ R)? (P ∨ Q) ∧ (P ∨ R)
P ∧ (Q ∨ R)? (P ∧ Q) ∨ (P ∧ R)
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | Q | R | Q ∧ R | P∨(Q ∧R) | P ∨ Q | P ∨ R | (P ∨ Q) ∧ (P ∨ R) |
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
Ta tabela zawiera te same wartości prawdy w kolumnach P ∨ (Q ∧ R) i (P ∨ Q) ∧ (P ∨ R).
Stąd możemy powiedzieć, że P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
Tak samo, jak możemy udowodnić P ∧ (Q ∨ R)? (P ∧ Q) ∨ (P ∧ R)
Prawo tożsamości:
Aby pokazać prawo tożsamości, stosuje się pojedyncze stwierdzenie. Zgodnie z tym prawem, jeśli połączymy stwierdzenie i wartość True z symbolem ∨(lub), wówczas wygenerowana zostanie wartość True. Jeśli połączymy instrukcję i wartość False z symbolem ∧(i), wówczas wygenerowana zostanie sama instrukcja. Podobnie zrobimy to z przeciwnymi symbolami. Oznacza to, że jeśli połączymy instrukcję i wartość True z symbolem ∧(i), to wygeneruje samo stwierdzenie, a jeśli połączymy instrukcję i wartość False z symbolem ∨(lub), to wygeneruje Fałszywa wartość. Załóżmy, że istnieje zdanie złożone P, prawdziwa wartość T i fałszywa wartość F. Poniższa notacja służy do wskazania prawa tożsamości:
P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | T | F | P ∨ T | P ∨ F |
|---|---|---|---|---|
| T | T | F | T | T |
| F | T | F | T | F |
Tabela ta zawiera te same wartości logiczne w kolumnach P ∨ T i T. Można zatem powiedzieć, że P ∨ T = T. Podobnie tabela ta zawiera również te same wartości logiczne w kolumnach P ∨ F i P. Stąd możemy powiedzieć, że P ∨ F = P.
Tak samo jak możemy udowodnić P ∧ T ? P i P ∧ F? F
Prawo uzupełniające:
W prawie dopełniacza stosuje się pojedyncze stwierdzenie. Zgodnie z tym prawem, jeśli połączymy zdanie z jego uzupełnieniem o symbolu ∨(lub), to wygenerujemy wartość Prawdziwą, a jeśli połączymy te stwierdzenia z symbolem ∧(i), to wygenerujemy Fałsz wartość. Jeśli zanegujemy wartość prawdziwą, wygenerowana zostanie wartość fałszywa, a jeśli zanegujemy wartość fałszywą, wygenerowana zostanie wartość prawdziwa.
Do wskazania prawa dopełniacza stosuje się następującą notację:
P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | ¬str | T | ¬T | F | ¬F | P ∨ ¬P | P ∧ ¬P |
|---|---|---|---|---|---|---|---|
| T | F | T | F | F | T | T | F |
| F | T | T | F | F | T | T | F |
Tabela ta zawiera te same wartości logiczne w kolumnach P ∨ ¬P i T. Zatem możemy powiedzieć, że P ∨ ¬P = T. Podobnie, tabela ta zawiera również te same wartości logiczne w kolumnach P ∧ ¬P i F. Stąd możemy powiedzieć, że P ∧ ¬P = F.
Ta tabela zawiera te same wartości logiczne w kolumnach ¬T i F. Zatem możemy powiedzieć, że ¬T = F. Podobnie, ta tabela zawiera te same wartości logiczne w kolumnach ¬F i T. Zatem możemy powiedzieć, że ¬F = T.
Prawo podwójnej negacji lub prawo inwolucji
Pojedyncze stwierdzenie służy do pokazania prawa podwójnej negacji. Zgodnie z tym prawem, jeśli dokonamy negacji zdania zanegowanego, wówczas zdanie wynikowe będzie samym zdaniem. Załóżmy, że istnieje zdanie P i zdanie negujące ¬P. Do wskazania prawa podwójnej negacji używa się następującej notacji:
¬(¬P) ? P
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
konwersja ciągu na json w Javie
| P | ¬str | ¬(¬P) |
|---|---|---|
| T | F | T |
| F | T | F |
Ta tabela zawiera te same wartości logiczne w kolumnach ¬(¬P) i P. Zatem możemy powiedzieć, że ¬(¬P) = P.
Z prawa Morgana:
Obydwa stwierdzenia służą do pokazania prawa De Morgana. Zgodnie z tym prawem, jeśli połączymy dwa stwierdzenia symbolem ∧(AND), a następnie wykonamy negację tych połączonych zdań, to wynikowe zdanie będzie takie samo, nawet jeśli połączymy negację obu zdań osobno symbolem ∨( LUB). Załóżmy, że istnieją dwa zdania złożone, P i Q. Poniższa notacja służy do wskazania prawa De Morgana:
¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | Q | ¬str | ¬Pyt | P ∧ Q | ¬(P ∧ Q) | ¬ P ∨ ¬Q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | F | T | T | F | T | T |
Ta tabela zawiera te same wartości prawdy w kolumnach ¬(P ∧ Q) i ¬ P ∨ ¬Q. Zatem możemy powiedzieć, że ¬(P ∧ Q) = ¬ P ∨ ¬Q.
To samo, co możemy udowodnić ¬(P ∨ Q)? ¬P ∧ ¬P
Prawo absorpcji:
Obydwa stwierdzenia służą do pokazania prawa absorpcji. Zgodnie z tym prawem, jeśli połączymy instrukcję P za pomocą symbolu ∨(OR) z tą samą instrukcją P i jeszcze jedną instrukcją Q, które połączymy symbolem ∧(ORAZ), wówczas otrzymana instrukcja będzie pierwszą instrukcją P. Ten sam wynik zostanie wygenerowany, jeśli zamienimy symbole. Załóżmy, że istnieją dwa zdania złożone, P i Q. Poniższa notacja służy do wskazania prawa absorpcji:
P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P
Tabela prawdy dla tych oznaczeń jest opisana w następujący sposób:
| P | Q | P ∧ Q | P ∨ Q | P ∨ (P ∧ Q) | P ∧ (P ∨ Q) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | T | T |
| F | T | F | T | F | F |
| F | F | F | F | F | F |
Tabela ta zawiera te same wartości prawdy w kolumnach P ∨ (P ∧ Q) i P. Zatem możemy powiedzieć, że P ∨ (P ∧ Q) ? P.
Podobnie, tabela ta zawiera również te same wartości prawdy w kolumnach P ∧ (P ∨ Q) i P. Stąd możemy powiedzieć, że P ∧ (P ∨ Q) ? P.
Przykłady równoważności logicznej
Istnieją różne przykłady logicznej równoważności. Niektóre z nich opisano w następujący sposób:
Przykład 1: W tym przykładzie ustalimy właściwość równoważności instrukcji, która jest opisana w następujący sposób:
p → q? ¬p ∨ q
Rozwiązanie:
Udowodnimy to za pomocą tabeli prawdy, która jest opisana w następujący sposób:
| P | Q | ¬s | p → q | ¬p ∨ q |
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Ta tabela zawiera te same wartości logiczne w kolumnach p → q i ¬p ∨ q. Zatem możemy powiedzieć, że p → q ? ¬p ∨ q.
Przykład 2: W tym przykładzie ustalimy właściwość równoważności instrukcji, która jest opisana w następujący sposób:
P ↔ P? ( P → Q ) ∧ ( Q → P )
Rozwiązanie:
| P | Q | P → P | P → P | P ↔ P | ( P → Q ) ∧ ( Q → P ) |
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | T | F | F | F |
| F | F | T | T | T | T |
Ta tabela zawiera te same wartości prawdy w kolumnach P ↔ Q i (P → Q) ∧ (Q → P). Można zatem powiedzieć, że P ↔ Q ? (P → Q) ∧ (Q → P).
Przykład 3: W tym przykładzie użyjemy równoważnej właściwości, aby udowodnić następujące stwierdzenie:
p ↔ q? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q )
Rozwiązanie:
Aby to udowodnić, skorzystamy z niektórych z wyżej opisanych praw i z tego prawa mamy:
p ↔ q? (¬p ∨ q) ∧ (¬q ∨ p)............(1)
Teraz skorzystamy z prawa przemienności w powyższym równaniu i otrzymamy co następuje:
? (p ∨ q) ∧ (p ∨ ¬q)
Teraz skorzystamy z prawa rozdzielności w tym równaniu i otrzymamy, co następuje:
? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))
Teraz skorzystamy z prawa rozdzielności w tym równaniu i otrzymamy, co następuje:
? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)
Teraz skorzystamy z prawa dopełnienia w tym równaniu i otrzymamy, co następuje:
? fa ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F
Teraz skorzystamy z prawa tożsamości i otrzymamy, co następuje:
? (¬ p ∧ ¬ q) ∨ (q ∧ p)
Teraz skorzystamy z prawa przemienności w tym równaniu i otrzymamy, co następuje:
? (p ∧ q) ∨ (¬ p ¬q)
Ostatecznie równanie (1) przyjmuje postać:
p ↔ q? (p ∧ q) ∨ (¬ p ¬q)
Na koniec możemy powiedzieć, że równanie (1) przyjmuje postać p ↔ q ? (p ∧ q) ∨ (¬ p ∧ ¬q)