Jednym z głównych praw rachunku zdań jest prawo dedukcji. Mówi ono, że jeśli założenie, że zachodzi jakaś własność α, doprowadza nas do wniosku, że zachodzi też β, to tautologią jest implikacja \(\alpha\Rightarrow \beta\). Formalne uzasadnienie tego prawa wykracza poza prezentowany tutaj materiał.
Rozważmy na przykład implikację \((P\wedge Q)\Rightarrow P\). Jak łatwo sprawdzić, jest to tautologia rachunku zdań. Ale można przeprowadzić jej dowód, korzystając z prawa dedukcji:
- załóżmy, że zachodzi \(P\wedge Q\),
- wtedy w szczególności zachodzi też P,
- więc w oparciu o prawo dedukcji, prawdą jest implikacja \((P\wedge Q)\Rightarrow P\).
Kontrapozycja
Powiedzmy, że mamy dwie zmienne P,Q. Rozważmy dwie implikacje:
- \(P\Rightarrow Q\),
- \(\lnot Q\Rightarrow \lnot P\).
Okazuje się, że są one równoważne, tzn. zawsze zachodzi \(P\Rightarrow Q\equiv \lnot Q\Rightarrow \lnot P\).
Można to zrozumieć w następujący sposób: \(P\Rightarrow Q\) mówi, że ilekroć zachodzi P, musi też zachodzić Q. Pomyślmy co będzie, gdy \(Q\equiv\bot\)? Gdyby wtedy zachodziło P, to była by sprzeczność, bo było by P i nie było by Q. Więc jeśli \(P\Rightarrow Q\) i \(\lnot Q\) mają być prawdą, to musi też być prawdą \(\lnot P\). Czyli, żeby lewa strona równości była prawdą, musi nią też być prawa strona.
Analogicznie w drugą stronę, można pokazać, że jeśli prawdą ma być \(\lnot Q\Rightarrow \lnot P\), to prawdą też musi być \(P\Rightarrow Q\).
Warto zapamiętać powyższą równość, pozwala ona zamieniać jedną implikację na inną (z negacjami).
Implikacja w drugą stronę
Trzeba jednak uważać, gdyż implikacje \(P\Rightarrow Q\) i \(Q\Rightarrow P\), nie są równoważne. Pomylenie ich jest bardzo częstym błędem. Weźmy na przykład zdanie z życia codziennego:
- Jeśli zdam egzamin, to pójdę na lody.
Czy z tego zdania wynika, co będzie jak nie zdam egzaminu? Bardzo wiele osób odpowie:
- Oczywiście, jak nie zdasz egzaminu, nie pójdziesz na lody, bo nie będziesz miał nastroju.
Z punktu widzenia logiki, takie rozumowanie jest błędne. Oznaczmy przez E zdanie ,zdam egzamin', a przez L zdanie ,pójdę na lody'. Zacytowaną powyżej deklarację, możemy zapisać \(E\Rightarrow L\). Implikacja w drugą stronę to \(L\Rightarrow E\), czyli równoważnie \(\lnot E\Rightarrow \lnot L\).
Wyrażenie \(E\Rightarrow L\) jest prawdziwe w trzech przypadkach:
- \(E\equiv L\equiv\top\), czyli egzamin zdany, lody zjedzone.
- \(E\equiv L\equiv\bot\), czyli egzamin oblany, a zamiast lodów herbata w domu.
- \(E\equiv \bot\), \(L\equiv \top\), czyli egzamin oblany, ale mimo wszystko lody (na pociechę).
Czyli w szczególności, z logicznego punktu widzenia, prawdą jest deklaracja ,jeśli zdam, to zjem lody', w sytuacji gdy nie zdam egzaminu i mimo wszystko zjem lody. W logice przekłada się to na sytuację, gdy \(E=\bot, L=\top\), prawdą jest \(E\Rightarrow L\) i nie jest prawdą \(\lnot E\Rightarrow \lnot L\) (czyli też nie jest prawdą \(L\Rightarrow E\)).
Przykład ten ilustruje subtelną różnicę pomiędzy językiem codziennym, a logiką. Ludzie często wypowiadają zdania takie jak powyżej, starając się w ten sposób wyrazić więcej niż mówi logika. Na przykład mama mówi do dziecka:
- Jeśli nie sprzątniesz pokoju, nie będziesz mógł oglądać telewizji.
Mama w istocie powiedziała: (nie sprzątniesz pokoju) \(\Rightarrow\) (nie oglądasz telewizji). Ale dziecko wierzy, że (sprzątnę pokój) \(\Rightarrow\) (będę mógł oglądać telewizję), czego mama wcale nie powiedziała. Jako ćwiczenie warto zapisać te zdania w języku logiki i zobaczyć, jakie implikacje w których sytuacjach zachodzą, a w których nie zachodzą.
Implikacja \(\Leftrightarrow\)
Również operator podwójnej implikacji \(\Leftrightarrow\), ma swoje szczególne znaczenie. Mianowicie wyrażenie \(P\Leftrightarrow Q\) jest prawdziwe w dwóch sytuacjach:
- Gdy \(P\equiv Q\equiv \top\) (bo prawdziwa jest implikacja \(\top\Rightarrow \top\)).
- Gdy \(P\equiv Q\equiv \bot\) (bo prawdziwa jest implikacja \(\bot\Rightarrow \bot\)).
Czyli w sumie \(P\Leftrightarrow Q\) jest prawdą dokładnie wtedy, gdy \(P\equiv Q\). Z tego powodu, często symbole \(\Leftrightarrow\) i \(\equiv\) są mylone. Należy jednak pamiętać o różnicy:
- \(\Leftrightarrow\) to operacja, taka jak + , * , czy − . Gdy po obu stronach \(\Leftrightarrow\) postawi się jakieś wartości logiczne, całe wyrażenie też ma jakąś wartość logiczną.
- \(\equiv\) to równość w logice, analogiczna do znaku = w arytmetyce.
Rozumiejąc różnicę pomiędzy tymi symbolami, można z nich korzystać i pisać równoważnie:
- [...] wtedy wyrażenie \(\alpha \Leftrightarrow \beta\) ma wartość \(\top\). [...]
- [...] wtedy \(\alpha\equiv \beta\). [...]
Eliminacja implikacji
Z definicji implikacji, zdanie \(P\Rightarrow Q\) jest równoważne zdaniu \(Q\vee\lnot P\). Czyli w każdym miejscu gdzie występuje implikacja można ją zamienić na alternatywę i negację. Dzięki temu, każde wyrażenie rachunku zdań można doprowadzić do równoważnej postaci, w której występują tylko operacje \(\vee,\wedge,\lnot\).