p |
q |
∧ |
v |
→ |
↔ |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
Sprawdzamy czy dana formuła jest tautologią.
Tautologia - to formuła klasycznego rachunku zdań, która przyjmuje wartość 1 (jest prawdziwa) dla każdego wartościowania
Rozpatrzmy takie zdanie:
[p→(q→r)] → [(p∧q) →r]
W takim wypadku podam mój sposób, który wydaje mi się jednym z prostszych
Musimy zapamiętać (lub mieć w notatkach), że:
p |
q |
r |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
Są to wszystkie możliwości, które przyjmuje p, q, r inaczej mówiąc, gdy zdanie składa się z trzech dających się wyróżnić części (w tym wpadaku tymi częściami są p, q, r) te części moga przyjąc takie wartości
A teraz do rzeczy. Zdanie, które przyjęliśmy na początku:
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
Pod każdym p wypisujemy podane wyżej możliwości, które ta zmienna przyjmuje, pod każdym q piszemy zmienne dla niej wlaściwe, tak samo postępujemy z r.
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
1 1 1 1 1 1
1 1 0 1 1 0
1 0 1 1 0 1
1 0 0 1 0 0
0 1 1 0 1 1
0 1 0 0 1 0
0 0 1 0 0 1
0 0 0 0 0 0
Teraz potrzebna będzie pierwsza tabelka.
Jak pamiętacie (lub nie) na matematyce w szkole podstawowej działania zaczynało się liczyć od tych które były w najmniejszych nawiasach, potem przechodzilo się do większych, aż w końcu do całości działania.
Tutaj nie ma żadnej zmiany, zaczynamy od najmniejszych działań. W naszym przykładzie są dwa małe (okrągłe) nawiasy i je rozpatrzymy:
1 mały nawias to:
( q → r )
1
0
1
0
1
0
1
0 0
Jak widzimy mamy tu do czynienia z IMPLIKACJĄ ( → )
Patrzymy do pierwszej tabelki i sparwdzamy jaką wartość ma implikacja gdy oba jej składniki są prawdziwe czyli przyjmuja watrość 1 (tak jak w pierwszym rzędzie naszego przykładu).
Odkrywamy, że gdy oba składniki implikacji są prawdziwe to jej wartość przyjmuje 1. Ta jedynkę wpisujemy pod znaczek implikacji (→), a więc nasz pierwszy rząd powinien wyglądać tak:
( q → r )
1 1 1
z drugim i każdym kolejnym rzędem postępujemy tak samo, patrzymy do tabeli i ustalamy jaką wartość ma implikacja w różnych przypadkach, watro zapamietać, że implikacja jest fałszywa tylko wtedy, gdy jej następnik jest fałszywy, a więc gdy drugi jej skladnik przyjmuje wartość 0 (to znacznie ulatwi i usprawni rozwiązywanie)
poprawnie rozwiązany nawias powinien wyglądać tak:
( q → r )
1 1 1
1 0 0
0 1 1
0 1 0
1 1 1
1 0 0
0 1 1
0 1 0
Kolorem czerwonym zaznaczyłam wyliczone wartości
2 mały nawias:
( p ∧ q )
1 1
1 1
1 0
1 0
0 1
0 1
0 0
0 0
Tutaj jak widzisz, znów wypisałam wartości z drugiej tabeli, pod kazdym p, wartości dla niego właściwe i pod każdym q wartości dla tej zmiennej wlaściwe
W tym wypadku mamy do czynienia z koniunkcją ( ∧ )
A więc znów tak samo jak w pierwszym małym nawiasie patrzymy do tabeli i sprawdzamy jaką wartość ma koniunkcja, gdy oba jej składniki (w tym wypadku) sa prawdziwe
( p ∧ q )
1 1
Zauważamy, że takie zestawinie jest prawdzwe (przyjmuje wartość 1)
I znów tak samo jak to bylo z implikacją pod znaczkiem koniunkcji ( ∧ ) piszemy jej wartość gdy oba składniki są prawdziwe:
( p ∧ q )
1 1 1
z kolejnymi rzędami postepujemy dokladnie tak samo, sprawdzamy jaką wartość ma koniunkcja dla poszczególnych jej składników czyli p i q
poprawny zapis to:
( p ∧ q )
1 1 1
1 1 1
1 0 0
1 0 0
0 0 1
0 0 1
0 0 0
0 0 0
Warto zauważyć, że koniunkcja jest prawdziwa wtedy, gdy jej oba skladniki są prawdziwe!
Tak doszliśmy do rozpatrzenia małych i najmniej złozonych nawiasow, teraz pora na zastanowienie się nad pozostałymi działaniami.
Jak już napisałam najpierw zaczynamy od najmniejszych (okrąglych) nawiasów, gdyż bez nich nie jesteśmy w stanie dalej pociągnąć zadania i sprawdzić czy jest ono tautologią.
Przypomnijmy nasze zdanie wyjściowe:
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
Zdanie wyjściowe po rozpisaniu 1 i 0 z drugiej tabeli:
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
1 1 1 1 1 1
1 1 0 1 1 0
1 0 1 1 0 1
1 0 0 1 0 0
0 1 1 0 1 1
0 1 0 0 1 0
0 0 1 0 0 1
0 0 0 0 0 0
Zdanie po wyliczonych wcześniej wartościach:
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 0
1 0 0 1 1 0 0 1
1 0 0 0 1 0 0 0
0 1 1 1 0 0 1 1
0 1 1 0 0 0 1 0
0 0 1 1 0 0 0 1
0 0 1 0 0 0 0 0
Jak już napisałam, sprawdzanie czy dane zdanie jest tautologią zaczynamy od najmniejszych nawiasów, teraz przyszła pora na zastanowienie sie nad większymi nawiasami (kwadratowymi)
Nawiasów kwadratowych nie bylibyśmy w stanie ruszyć, bez wcześniejszego rozwiązania działań w nawiasach okrągłych (ich wyniki są zaznaczone na czerwono)
Rozpatrzmy pierwszy nawias kawdratowy:
[ p → ( q → r ) ]
1 nawias kawdratowy z rozpisanymi wartościami, które przyjmują p, q i r oraz z wyliczoną wcześniej implikacją q i r (wynik implikacji na czerwono)
[ p → ( q → r ) ]
1 1 1 1
1 1 1 0
1 0 0 1
1 0 0 0
0 1 1 1
0 1 1 0
0 0 1 1
0 0 1 0
Specjalnie wynik implikacji z małego nawisu zaznaczyłam na inny kolor, by teraz było prościej liczyć
Mały nawias teraz traktujemy jako całość, ponieważ mamy wyliczony juz jego wynik (kolor czerwony), w tej chwili nie ma już osobnego q i r, to jest całość!
Znów przydatna okarze się pierwsza tabela, patrzymy na nasze zdanie, na nasz nawias kwadratowy, który rozpatrujemy i zauważamy, że jego głównym „spójnikiem” jest IMPLIKACJA (→)
Tabela pierwsza w ruch i analogicznie do wcześniejszych dzialań sprawdzamy, kiedy jaką wartość ma implikacja, gdy oba jej składniki są prawdziwe (w tym wypadku p sprawdzamy z wynikiem, który obliczyliśmy z małego nawiasu, tym zaznaczonym na czerwono )
[ p → ( q → r ) ]
1 1 1 1 1
Nasz wynik teraz zaznaczyłam kolorem niebieskim dla odróżnienia.
Kolejne rzędy liczymy w dokładnie ten sam sposób
Poprawne rozwiąznie powinno zostać zapisane w ten sposób:
[ p → ( q → r ) ]
1 1 1 1 1
1 1 1 1 0
1 0 0 0 1
1 0 0 0 0
0 1 1 1 1
0 1 1 1 0
0 1 0 1 1
0 1 0 1 0
PAMIĘTAMY o tym, że teraz rozpatrujemy wynik małego nawiasu (kolor czerwony) z wartościamy p!
Mamy w ten sposób obliczony pierwszy kwadratowy nawias, należałoby teraz przyjrzeć się drugiemu nawiasowi kwadratowemu:
[ ( p ∧ q ) → r ]
1 1 1 1
1 1 1 0
1 0 0 1
1 0 0 0
0 0 1 1
0 0 1 0
0 0 0 1
0 0 0 0
W tym kwadratowym nawiasie znow mamy na czerwono zaznaczony wynik okrągłe nawiasu i znów będzie on potrzebny. W tym wypadku rozumowanie jest identyczne do tego zastosowanego w pierwszym kwadratowym nawiasie, gdyż spójnikiem głównym jest znów IMPLIKACJA, a okrągły nawias traktujemy jako całość, interesując sie tylko jego wynikiem (kolor czerwony)
Znow sprawdzamy jaka wartość ma implikacja gdy oba jej składniki są prawdziwe (wynik otrzymany z małego nawiasu zaznaczony na kolor czerwony i r), patrzymy do tabeli i stwierdzaony, że implikacja jest prawdziwa. Pod znaczkiem implikacji (→) zapisujemy otrzymany wynik
[ ( p ∧ q ) → r ]
1 1 1 1 1
Poprawny zapis rozwiązania wszystkich rzędow powinien wyglądać tak:
[ ( p ∧ q ) → r ]
1 1 1 1 1
1 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 0 1 1 1
0 0 1 1 0
0 0 0 1 1
0 0 0 1 0
Powtarzam, teraz sprawdzaliśmy wynik malego nawiasu (kolor czerwony) z r, wynik dla odróżnienia zapisany kolorem niebieskim.
Teraz już pójdzie z górki, mamy obliczone dwa duze nawiasy więc pozostaje nam tylko rozpatrzenie całego zdania
Oto nasze wypociny ;) :
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 0
1 0 0 1 1 1 0 0 0 1
1 0 0 1 0 1 0 0 0 0
0 0 1 1 1 0 1 1 1 1
0 0 1 1 0 0 1 1 1 0
0 0 0 1 1 0 1 0 1 1
0 0 0 1 0 0 1 0 1 0
Teraz najłatwiejsze - wyniki uzyskane z kawdratowcyh nawiasów (kolor niebieski) konfrontujemy ze sobą za pomocą IMPLIKACJI, ktora jest spójnikiem głównym całego zdania.
W pierwszym rzędzie sprawdzamy jaką wartość ma implikacja gdy oba jej składniki sa prawdziwe (sprawdzamy w tabelce)
Poprawny pierwszy rząd to:
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
1 1 1 1 1 1 1 1 1 1 1
Cale zdanie poprawnie rozwiązane powinno mieć postać:
[ p → ( q → r ) ] → [ ( p ∧ q ) → r ]
1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 0
1 0 0 1 1 0 1 0 0 0 1
1 0 0 1 0 0 1 0 0 0 0
0 0 1 1 1 1 0 1 1 1 1
0 0 1 1 0 1 0 1 1 1 0
0 0 0 1 1 1 0 1 0 1 1
0 0 0 1 0 1 0 1 0 1 0
Jak widzimy pod spólnikiem głównym (→) nie wyszly nam same jedynki, a więc wniosek nasuwa się z tego jeden TO NIE JEST TAUTOLOGIA w myśl jej definicji przytoczonej na samym początku.
P.S. To tylko tak kosmicznie wygląda, ale w gruncie rzeczy jeśli załapiesz o co chodzi, to żadne sprawdzenie tautologii nie będzie Ci straszne :P
I jeszcze jedna uwaga na marginesie, to co ja zaznacząłam sobie kolorami możesz rożnie dobrze wziąść o kóło (żeby wyróżnić wyniki), bo na kolorowanki nie będzie zapewne czasu na poprawce.
Życzę powodzenia