Embedded Files
W tej części kursu dowiesz się, jak liczyć, czy formuła jest tautologią, metodą nie wprost - czyli metodą skróconą oraz metodą drzewkową.
Sprawdzanie tautologii innymi metodami
Sprawdzanie tautologii innymi metodami
Zamiast sprawdzania, czy formuła jest tautologią za pomocą tabeli prawdziwościowej, można sprawdzić, czy formuła jest tautologią innymi metodami. Zazwyczaj inne metody są bardziej przydatne w sytuacji, kiedy formuła zawiera wiele zmiennych zdaniowych (na przykład 3 i więcej).
Skrócona metoda
Skrócona metoda
Sedno tej metody tkwi w znalezieniu jednego wiersza, w którym badana formuła przyjmuje wartość "0" (ponieważ znalezienie takiego wiersza wystarczy, by stwierdzić, że formuła nie jest prawdziwa we wszystkich wierszach). Jak to zrobić? Kluczowym krokiem jest założenie, że taki wiersz istnieje. Czyli zakładamy, że formuła jest fałszywa (przyjmujemy to warunkowo) i sprawdzamy, co musiałoby być przy takim założeniu. Kierujemy się definicją spójników. Jeśli w naszym rozumowaniu dochodzimy do sprzeczności (na przykład, że ta sama zmienna musi być jednocześnie prawdziwa i fałszywa), to odrzucamy założenie - sprzeczność oznacza, że nie może być tak, że badana formuła jest fałszywa, zatem jest to tautologia. Jeśli nie dojdziemy do sprzeczności, to znaleźliśmy wartości poszczególnych zmiennych, przy których formuła jest prawdziwa, czyli znaleźliśmy wartościowanie obalające, przy którym formuła nie jest tautologią (w takim wypadku nasze założenie jest słuszne).
📌Skrócona metodą jest metodą nie wprost. Zakładamy, że formuła NIE jest tautologią, i badamy konsekwencje:
wyszła SPRZECZNOŚĆ - oznacza to, że formuła JEST TAUTOLOGIĄ
nie wyszła sprzeczność - oznacza to, że formuła NIE JEST TAUTOLOGIĄ
Zobacz, jak sprawdzić metodą skróconą, czy formuła jest tautologią.
Zauważ, że doszliśmy w rozważaniach do sprzeczności, czyli wykazaliśmy, że formuła jest tautologią.
Zobacz, jak sprawdzić metodą skróconą, czy formuła jest tautologią.
Zauważ, że nie doszliśmy w rozważaniach do sprzeczności, czyli wykazaliśmy, że formuła nie jest tautologią. Wartościowanie obalające odczytujemy z "kratek" pod zmiennymi (pojedynczymi literkami).
📌UWAGA: nie zawsze metoda "skrócona" jest krótsza i nie zawsze jest tak, że przy założeniu nie wprost badamy tylko jeden przypadek, który jest konsekwencją tego założenia. Może być tak, że przypadków jest więcej (ale zawsze tylko dwa) i musimy rozważyć je wszystkie. Poniżej tabelki pokazują, jakie dwa przypadki musimy rozważyć, jeżeli założymy, że:
Koniunkcja jest fałszywa
Alternatywa jest prawdziwa
Implikacja jest prawdziwa
Równoważność jest prawdziwa
Równoważność jest fałszywa
Jeśli w którymś z przypadków nie uzyskujemy sprzeczności, to oznacza to, że udowodniliśmy, że założenie nie wprost jest do utrzymania (w związku z czym badana formuła nie jest tautologią). W takiej sytuacji nie musimy rozważać drugiego przypadka.
Jeśli natomiast po sprawdzeniu przypadka 1 uzyskaliśmy sprzeczność, to pokazaliśmy jedynie, że formuła nie może być fałszywa z uwagi na ten przypadek. W takiej sytuacji musimy zbadać przypadek 2.
By nie mylić się w metodzie skróconej, najlepiej jest podpisywać kratkę pod każdym symbolem.
W tym przykładzie dochodzimy do sprzeczności - tym samym pokazaliśmy, że formuła jest tautologią.
W tym przykładzie nie dochodzimy do sprzeczności - pokazaliśmy tym samym, że formuła nie jest tautologią. Wartościowanie obalające odczytujemy z kratek pod zmiennymi (pojedyncze literki, p, q, r)
W tym przykładzie musimy rozważyć dwa przypadki (zawsze jest tylko dwa, zobacz wyżej, jakie są te przypadki w zależności od spójnika).
Rozważyliśmy dwa przypadki i w każdym z nich doszliśmy do sprzeczności. Pokazaliśmy, że formuła jest tautologią.
W tym przykładzie również musimy rozważać przypadki. Ale zobaczymy, że nie jest to nic ciężkiego.
Mimo że przypadków jest kilka, wystarczy, że w jakimkolwiek nie dochodzimy do sprzeczności - wtedy pokazaliśmy, że nasza formuła nie jest tautologią (czyli tym samym już nie musimy rozważać pozostałych przypadków).
W tym przykładzie również idziemy przez przypadki (ale jak wcześniej, to nic ciężkiego)
Metoda drzewkowa
Metoda drzewkowa
Metoda drzewkowa, podobnie jak i metoda skrócona, polega na przyjęciu warunkowego założenia (zwanego założeniem nie wprost), że formuła jest fałszywa i badania konsekwencji takiego założenia. Nazywa się ona "drzewkową", ponieważ schemat sprawdzania, który powstaje, graficznie przypomina rozgałęziające się drzewo postawione pniem do góry.
Zauważmy, że definicje spójników przedstawione w postaci tabel prawdziwościowych mogą zostać przedstawione również w inny sposób, jako reguły "rozgałęziania" poniżej, gdzie pojedyncza gałąź oznacza tylko jedną możliwość (tak na przykład koniunkcja jest prawdziwa tylko w jednym przypadku, kiedy oba jej człony są prawdziwe), natomiast rozgałęzienie (dwie gałęzi) oznacza alternatywę dwóch możliwości (tak na przykład implikacja może być prawdziwa albo w przypadku, kiedy jej poprzednik jest fałszywy, albo w przypadku, kiedy jej następnik jest prawdziwy). Daje to następujące reguły rozgałęziania dla spójników (oczywiście, że w przypadku podwójnej negacji możemy zapisać formułę bez negacji):
Załóżmy, że chcemy sprawdzić, czy formuła (p∧(q∨r))→((p∧q)∨(p∧r)) jest tautologią. Tak jak i w przypadku skróconej metody - zaczynamy od założenia, że formuła nie jest tautologią. Oznacza to, że negacja tej formuły jest prawdziwa. Negujemy formułę i zapisujemy ją jako "trzon" naszego "drzewka". Następnie przeprowadzamy 1-sze rozgałęzienie zgodnie z zasadą rozgałęzienia dla zanegowanej implikacji. Formułę, którą rozgałęziliśmy, oznaczamy symbolem * (by się nie pogubić i nie zapomnieć rozgałęzić którejkolwiek z formuł).
Uzyskaliśmy na "drzewku" jedną "gałąź" z dwoma formułami. Najlepiej zawsze zaczynać rozgałęzienia od formuł, które generują pojedyncze gałęzie (daje to mniej skomplikowane drzewko). Dlatego zaznaczamy zanegowaną alternatywę symbolem * i przeprowadzamy jej rozgałęzienie zgodnie z zasadą rozgałęzienia dla zanegowanej alternatywy.
Koniunkcja p∧(q∨r) też nie generuje dwóch gałęzi; zaznaczamy ją symbolem * i przeprowadzamy rozgałęzienie zgodnie z zasadą rozgałęziania dla prawdziwej koniunkcji.
Formuły, które pozostały bez rozgałęzienia na drzewku (bez symbolu *), będą generowały dwie gałęzie (zgodnie z zasadami rozgałęziania dla tych formuł). Jest bez znaczenia, od której zaczniemy. Niech będzie to formuła q∨r. Zaznaczamy ją symbolem * i przeprowadzamy rozgałęzienie zgodnie z zasadą rozgałęziania dla prawdziwej alternatywy (od wspólnego "trzonu" robimy 2 gałęzie).
Uzyskaliśmy dwie gałęzie. Nad miejscem rozgałęzienia na drzewku znajdują się dwie formuły, ¬(p∧q) oraz ¬(p∧r), których jeszcze nie rozgałęziliśmy. Jest bez znaczenia, od której zaczniemy. Niech będzie to formuła ¬(p∧q). Zaznaczamy ją symbolem * i rozgałęziamy w dwóch gałęziach (zgodnie z zasadą dla zanegowanej koniunkcji) w identyczny sposób. W wyniku tego rozgałęziania powstaje 4 gałęzi.
Zauważmy, że otrzymaliśmy sprzeczność w dwóch gałęziach: jeśli w miejscu pierwszego rozgałęzienia "skręcimy" w lewo, a później w miejscu następnego rozgałęzienia jeszcze raz skręcimy "w lewo" (skrajnia lewa gałąź), to mamy sprzeczność między formułami p i ¬p w tej gałęzi. Podobną sytuację mamy w trzeciej od lewej gałęzi. Zaznaczamy, że w tych gałęziach uzyskaliśmy sprzeczność - "ucinamy" te gałęzie (zamykamy je) poprzez postawienie symbolu "⊥" (falsum). W drugiej od lewej gałęzi również występuje sprzeczność - między q i ¬q. Tę gałąź również "ucinamy" poprzez postawienie symbolu "⊥".
Jedyna formuła ze spójnikiem, która pozostała bez rozgałęzienia na drzewku (bez symbolu *), to formuła ¬(p∧r). Zaznaczamy ją symbolem * i rozgałęziamy w jedynej nieuciętej gałęzi, która pozostała zgodnie z zasadą rozgałęziania dla fałszywej koniunkcji. Powstały dwie nowe gałęzi, ale każda z nich zawiera sprzeczne formuły: w jednej mamy p i ¬p, a w drugiej mamy r i ¬r. Dlatego obie nowe gałęzie "ucinamy" poprzez postawienie symbolu "⊥".
W taki sposób wyjściowe założenie, że badana formuła nie jest tautologią, doprowadziło nas do sprzeczności - wszystkie gałęzie na drzewku zawierają sprzeczne formuły. Oznacza to, że nie jest możliwe, by badana formuła była fałszywa, a zatem jest ona tautologią.
Gdyby natomiast okazało się tak, że jakaś gałąź na drzewku nie zostaje ucięta (rozgałęziliśmy wszystkie formuły ze spójnikami i uzyskaliśmy gałąź bez sprzeczności), oznaczałoby to, że badana formuła nie byłaby tautologią. W takim przypadku odczytujemy wartościowanie obalające z gałęzi, w której nie uzyskaliśmy sprzeczności.
UWAGA: najczęstszym popełnianym błędem jest odczytywanie sprzeczności z różnych gałęzi. By tego błędu nie popełnić, najlepiej prześledzić długopisem gałęzie, kreśląc nieprzerywane linie (nie odrywając długopisu) od trzonu drzewka do końca gałęzi. W obrębie tych linii właśnie szukamy sprzecznych formuł.
Również częstym błędem jest rozgałęzianie w którejś z gałęzi formuł znajdujących się w innych gałęziach. Należy pamiętać, że o gałęzi możemy myśleć jak o jednej nieprzerywanej linii; rozgałęziamy formuły znajdujące się wyłącznie w obrębie tej linii.
FAQ: Co robić, kiedy przy odczytywaniu wartościowania obalającego z gałęzi nie znajdują się na niej wszystkie zmienne zdaniowe? Na przykład, w formule występują p, q, r, a na gałęzi, w której nie ma sprzeczności, są tylko p i q, a r nie ma?
Mistrz Yoda: Oznacza to, że r dowolnym może być, młody padawan. Wartościowanie r dowolne wpisz.
Przykłady
[przykłady są w .gif, poczekaj na komórce, aż się załadują - a się załadują]Przykłady
Krzyżówka
Krzyżówka
Spróbuj rozwiązać krzyżówkę: odpowiedziami są ciągi z 0 i 1 pokazujące skróconą metodą nie wprost, że formuły 1-8 nie są tautologiami. Powodzenia! (PS: hej, możesz wygrać pralkę)
Testy
Testy
Tutoriale z Youtube
Tutoriale z Youtube
📌 Metoda drzewkowa: pierwsze wideo - od 8:20 (można dodać do linka w przeglądarce &feature=youtu.be&t=500)
Praca domowa
Praca domowa
Informacja zwrotna
Informacja zwrotna
Page updated
Google Sites
Report abuse