Opracowanie:
Tautologia

Tautologia

Zweryfikowane

Tautologia to w rachunku zdań, zdanie lub schemat zdania zawsze prawdziwy. Jest to zatem taka formuła utworzona za pomocą funktorów zdaniotwórczych, że przy każdym doborze zmiennych zdaniowych ma wartość logiczną prawdziwą.

Obserwacja 1: Jeżeli formuła to tautologia(prawo rachunku zdań), wtedy dla wszystkich możliwych p i q, będących zmiennymi zdaniowymi jest ona zdaniem prawdziwym.

Pierwszym sposobem dowodzenia tautologii jest metoda zero-jedynkowa. Polega ona na wypisaniu w tabelce zmiennych zdaniowych, a pod nimi wszystkich możliwych wzajemnych wystąpień prawdy i fałszu, przy czym fałsz oznacza się cyfrą 0, a prawdę cyfrą 1.

Obserwacja 2: Ilość wierszy w tabelce zależy od ilości zmiennych zdaniowych. Dla zdania składającego się z n zdań składowych należy napisać wierszy.

Podam teraz kilka przykładów tautologii z ich dowodami przeprowadzonymi za pomocą metody zero-jedynkowej
I prawo de Morgana
prawo wyłączonego środka
Prawo podwójnej negacji
prawo identyczności
prawo zaprzeczenia implikacji

(1)

(2)

(5)

Przy większej ilości zmiennych zdaniowych rysowanie tabeli staje robi się bardzo długie. Wobec tego jeżeli formuła zawiera implikację, dowód można przeprowadzić używając skróconej metody zero-jedynkowej. Ponieważ implikacja jest fałszywa tylko w przypadku, gdy poprzednik jest prawdziwy, a następnik fałszywy, to zakładając prawdziwość poprzednika danej implikacji i wykazując, że następnik tez jest prawdziwy dowodzę, że implikacja ta jest tautologią(prawem logicznym). Analogicznie zakładając fałszywość następnika pewnej implikacji i wykazując, że jej poprzednik jest fałszywy, wykazuje tym samym, że dana implikacja jest prawem logicznym.
Podam teraz przykłady:
(1)

Zakładam, że następnik implikacji, czyli wyrażenie jest fałszywe. Alternatywa jest fałszywa tylko w przypadku, gdy obydwie zmienne zdaniowe są fałszywe, czyli oraz mają wartość 0. Wobec tego p i q mają wartość 1. Zatem ich koniunkcja jest prawdziwa, czyli negacja tej koniunkcji jest fałszywa. W związku z tym wyjściowa implikacja jest tautologią.
(2)

Powyższe przykład rozwiążę skróconą metodą zero-jedynkową. Wiadomo, że implikacja jest fałszywa tylko w przypadku, gdy poprzednik jest prawdziwy, a następnik fałszywy. Jeżeli nie istnieje takie wartościowanie, żeby formuła była fałszywa, to jest to tautologia(prawo logiczne).
Zakładam, że implikacja jest fałszywa. Wówczas p ma wartość 0, a wartość 1, co jest niemożliwe, bo koniunkcja jest prawdziwa tylko gdy obydwie zmienne zdaniowe są prawdziwe. Zatem nie można wskazać takiego wartościowania aby formuła była fałszywa, czyli jest to tautologia.
(3)

Analogicznie jak w poprzednim przykładzie przyjmuję, że implikacja jest fałszywa. Wówczas p ma wartość 1, a wartość 0. Wobec ostatniej implikacji q ma wartość 1, a ma 0. Nie jest to możliwe, bo w przypadku, gdy obydwa zdania p i q mają wartości 1, to ich koniunkcja też. Wobec tego wyjściowa formuła jest tautologią.

Zastosowania
Umiejętność sprawdzenia, czy dane zdanie lub sformułowanie jest tautologią jest przydatne, w przypadku, kiedy nie wiadomo jaką ma strukturę. Aby zobaczyć to w praktyce podam kilka przykładów.

Przykład 1
Jeśli nieprawdą jest, że byłem w kinie lub nie byłem w teatrze, to nie byłem w kinie i byłem w teatrze.
W zdaniu tym występują dwa zdania składowe:
m-byłem w kinie, n-byłem w teatrze
Zatem poprzednik implikacji mogę zapisać jako , a następnik , czyli całe zdanie przybierze postać
Do sprawdzenia, czy to zdanie jest zawsze prawdziwe wykorzystam metodę zerojedynkową

Czyli jest to tautologia.
To samo zadanie rozwiążę teraz skróconą metodą zero-jedynkową (mogę ją zastosować, gdyż jest to implikacja).
Zakładam, że poprzednik implikacji, czyli wyrażenie jest prawdziwe. Wobec tego
jest fałszywe. Zatem skoro alternatywa jest fałszywa tylko, w przypadku, gdy obydwa zdania proste są fałszywe, to zdanie m jest fałszywe, a n-prawdziwe. Wtedy zmienne zdaniowe n i są prawdziwe, czyli jest prawdziwe. Wobec tego jeśli poprzednik tej implikacji jest prawdziwy, to jej następnik też jest prawdziwy, czyli jest ona tautologią.
Przykład 2
Pozwolenia na parkowanie w parku nie wymaga się jeżeli ma się dziecko oraz jest się niepełnosprawnym.
Sprawdzę teraz czy sformułowanie to oznacza,(1) że parkować można w parku, gdy jest się osobą niepełnosprawną i ma się dziecko czy, (2)gdy jest się osobą niepełnosprawną lub ma się dziecko.
W zdaniu tym występują trzy zdania składowe:
p-wymaga się pozwolenia na parkowanie w parku
q-ma się dziecko
r-jest się osobą niepełnosprawną
Zauważam, ze zdanie ma następujący schemat . Ponadto sformułowanie (1) ma , a (2) ma . Aby sprawdzić, któremu z sformułowań jest równoważne pierwotne zdanie zastosuję metodę zerojedynkową.
(1)

Wobec tego przypadek (1)nie jest tautologią. Analogicznie rozwiązując otrzymuję, że jest to tautologia. Wobec tego wyjściowe sformułowanie należy rozumieć, że parkować w parku można bez pozwolenia jeżeli ma się dziecko albo gdy jest się osobą niepełnosprawną.
Przykład 3
Sprawdź, które z poniższych schematów zdaniowych są poprawnymi schematami zdania „Jeśli Maja nie idzie do szkoły, to nie przyjdzie zmęczona, o ile nie zerwie się z lekcji. ”Przyjmuję oznaczenia zdań składowych: p- Maja idzie do szkoły, q-przyjdzie zmęczona, r-zerwie się z lekcji.
(1)
(2)
(3)
Aby sprawdzić jaką wartość przyjmują podane schematy zdaniowe zastosuje metodę zero jedynkową

trzy formuły podane w zadaniu mają te same wartości, wobec czego są one sobie równoważne. Wobec czego wszystkie są schematami wyjściowego zdania.

Przykład 4
W pewnej piaskownicy, zamieszkałej przez żuki, których jedne zawsze kłamią, a inne zawsze mówią prawdę. Ponadto odpowiadają one na pytania tylko TAK lub NIE. Dziewczynka doszła do rozwidlenia dróg, z których jedna prowadzi na wschód, a druga na zachód, ale tylko jedna prowadzi na basen. Zapytała ona żuka o drogę. Jakie pytanie powinna zadać, aby na pewno wybrać właściwa drogę na basen?

Przyjmuję, ze odpowiedź twierdząca będzie oznaczała, że ma się ona udać na wschód, a przecząca na zachód. Niech p oznacza żuka prawdomównego, żuka kłamiącego. Niech ponadto q oznacza wybór drogi prowadzącej na wschód, a wybór drogi prowadzącej na zachód. Wobec tego pytanie, które zamierza zadać dziewczynka ma następującą tabelkę logiczną

Zatem jeżeli na pytanie odpowiedział prawdomówny, to postępuje tak, jak pokazuje to zmienna zdaniowa q. Jeżeli natomiast na pytanie odpowiedział kłamca, to postępuję odwrotnie do tego, co wskazuje zmienna q. Wobec tego pytanie powinno mieć postać. Zatem pytanie, które powinna zadać dziewczynka brzmi: Czy prawdziwe jest zdanie „Jesteś prawdomówny wtedy i tylko wtedy, gdy powinnam iść droga na wschód”?

Przykład 5
Czy z rozmowy:
pytanie-Czy to prawda, że jeżeli lubisz ciastka, to lubisz także banany?
odpowiedź- Jeżeli to prawda, to lubię ciastka.
można wywnioskować, że lubię ciastka?

W przedstawionej rozmowie występują dwa zdania składowe p-lubię ciastka i q-lubię banany. Rozmowę można zapisać w postaci i przyjmuję, że implikacja ta jest prawdziwa. Gdyby zdanie p było fałszywe, to byłaby prawdziwa(implikacja jest fałszywa tylko w przypadku, gdy poprzednik jest fałszywy, a następnik prawdziwy), ale wtedy byłaby fałszywa, wbrew założeniu. Zatem lubię ciastka.

Jak widać po przeczytaniu danych przykładów zdanie pojęcia tautologii i potrafienie go wykorzystać może być bardzo przydatne.

Powyższe zadanie zostało zweryfikowane przez nauczyciela

Opracowanie: Tautologia

Tautologia

Opracowanie:
Tautologia