W tej części kursu dowiesz się, co to jest tautologia (przykłady), jak sprawdzić, czy formuła jest tautologią (czyli jak to policzyć tabelą) oraz znajdziesz zadania na tautologie.
W tabelce prawdziwościowej dla formuły każdy wiersz odpowiada możliwej kombinacji wartości logicznych zmiennych zdaniowych, które występują w tej formule (wierszy jest tyle, ile możliwych kombinacji). Dlatego formuła sama w sobie nie posiada wartości logicznej - ona posiada wartość logiczną (jedną konkretną) dopiero w którymś z wierszy, czyli przy konkretnej kombinacji wartości logicznych zmiennych zdaniowych.
W alfabecie KRZ jest nieskończenie wiele zmiennych zdaniowych. Wyobraźmy sobie, że chcemy mówić o sposobach, na które nieskończenie wielu zmiennym zdaniowym będziemy przyporządkowywać 0 bądź 1. Każdy taki sposób przyporządkowania zmiennym zdaniowym 0 bądź 1 nazywa się wartościowaniem, a dokładniej:
Wartościowaniem nazywamy funkcję, która każdej zmiennej zdaniowej przyporządkowuje wartość logiczną 0 (fałsz) albo 1 (prawda).
Mając pojęcie wartościowania, możemy sensownie mówić, że na przykład formuła p↔¬q ma wartość logiczną 0 przy każdym wartościowaniu v, które przypisze p wartość 1 oraz przypisze q wartość 1 (przy v(p)=1, v(q)=1 wartość p↔¬q będzie 0). Czyli możemy precyzyjnie powiedzieć, w którym wierszu tabeli prawdziwościowej dla p↔¬q będzie 0.
Są takie formuły, których wartość będzie 1 przy dowolnym wartościowaniu (czyli niezależnie od tego, jaką kombinację wartości zmiennych składowych rozważymy, formuły te są zawsze prawdziwe). W tabeli prawdziwościowej takich formuł we wszystkich wierszach będzie wartość 1. Formuły prawdziwe przy dowolnym wartościowaniu są nazywane tautologiami. Są one ważne z punktu widzenia rachunków formalnych, ponieważ wyrażają prawa takiego rachunku.
Tautologia: formuła, która przy dowolnym wartościowaniu zmiennych zdaniowych przyjmuje wartość Prawda ("1").
Formuły niżej są prawami logiki (są one tautologiami):
p→¬¬p | prawo podwójnego przeczenia
p∨¬p | prawo wyłączonego środka
¬(p∧¬p) | prawo sprzeczności
¬(p∧q)↔(¬p∨¬q) | prawo de Morgana
¬(p∨q)↔(¬p∧¬q) | prawo de Morgana
(p→q)↔(¬q→¬p) | prawo transpozycji
((p→q)→p)→p | prawo Pierce'a
(p→q)↔(¬p∨q) | materialna implikacja
¬p→(p→q) | prawo Dunsa Szkota
Możemy sprawdzić, czy formuła jest tautologią, znaną już metodą tabelkową. Tak na przykład, chcemy wiedzieć, czy formuła ((p∨q)∧¬p)→q jest tautologią. W tym celu robimy tabelę prawdziwościową tej formuły i patrzymy, czy w kolumnie dla głównego spójnika występują wyłącznie wartości "1":
W kolumnie dla głównego spójnika są wyłącznie wartości "1", a zatem formuła jest tautologią.
Sprawdźmy, czy formuła ¬(p∧(¬p→q)) jest tautologią za pomocą tabeli prawdziwościowej:
W kolumnie dla głównego spójnika mamy dwie wartości "0". Oznacza to, że formuła nie jest tautologią. Wartościowaniami zmiennych, przy których formuła nie jest tautologią, są v(p)=1, v(q)=1 bądź v(p)=1, v(q)=0 (odczytujemy je z wierszy, w których formuła otrzymała wartość "0". Wystarczy podać jedno takie wartościowanie).
Zwróć uwagę, że w tym przykładzie w słupku wartości formuły występuje dwa "0". Ponieważ słupek wartości nie zawiera samych jedynek, formuła nie jest tautologią. Wartościowanie obalające odczytujemy z tego wiersza, gdzie w WYNIKU jest "0". Jeśli takich wierszy jest kilka, to wystarczy podać jeden (dowolny z tych, w których jest "0"). Wartościowaniem obalającym w tym przykładzie jest wiersz numer 1 oraz 3; do odpowiedzi został wybrany wiersz 3 (w którym v(p)=1, a v(q)=0).
Zwróć uwagę, że w tym przykładzie w słupku wartości formuły występują same jedynki. Skoro tak, to jest to tautologia. Nie zapomnij podawać odpowiedź w zadaniach!
Definicja tautologii: jest to formuła, która przyjmuje wartość "1" przy dowolnym wartościowaniu. A w praktyce - tautologia to taka formuła, która ma wartość "1" w dowolnym wierszu tabeli.
Wydawać by się mogło, iż sprawdzanie, czy formuła jest czy nie jest tautologią, nie ma żadnego zastosowania praktycznego. Otóż nic bardziej mylnego! Umiejętność sprawdzania, czy jakiś schemat zdaniowy (formuła) jest schematem wyłącznie zdań prawdziwych (jest tautologią) może się przydać w sytuacji, kiedy nie jest oczywiste, jaką strukturę ma zdanie. Z sytuacją taką możemy mieć do czynienia na przykład przy interpretacji tekstów prawniczych. Rozważmy następujące sformułowanie z Ustawy o broni i amunicji:
"Pozwolenia na broń nie wymaga się w przypadku posiadania broni palnej rozdzielnego ładowania, wytworzonej przed rokiem 1885 oraz replik tej broni."
Czy wobec tego sformułowania, by posiadać broń bez pozwolenia, obywatel musi:
posiadać broń wytworzoną przed 1885 rokiem oraz posiadać repliki tej broni czy
posiadać broń wytworzoną przed 1885 rokiem albo posiadać repliki tej broni?
[by przejść do odpowiedzi kliknij na strzałkę po prawej]
Sprawdźmy nasze intuicje. Przyjmijmy za p zdanie 'pozwolenie na broń jest wymagane', za q - 'zachodzi przypadek posiadania broni palnej rozdzielnego ładowania wytworzonej przed rokiem 1885', za r - 'zachodzi przypadek posiadania repliki (broni palnej rozdzielnego ładowania wytworzonej przed rokiem 1885)'. Sformułowanie z Ustawy ma następujący schemat zdaniowy: (q∧r)→¬p. Schemat rozumienia 1: (q→¬p)∧(r→¬p). Schemat rozumienia 2: (q→¬p)∨(r→¬p). Możemy sprawdzić (na przykład, metodą tabelkową), że schemat oryginalnego sformułowania z ustawy jest równoważny schematowi 2: formuła ((q∧r)→¬p)↔((q→¬p)∨(r→¬p)) jest TAUTOLOGIĄ. Nie jest tak w przypadku schematu 1.
Pamiętasz zdanie z pracy domowej, "Jeśli Bartek nie pije piwa, to Piotr się nie gniewa, o ile nie ma burzy za oknem"? Przyjmując oznaczenia p - Piotr się gniewa; q - jest burza za oknem; r - Bartek pije piwo, jaki z poniższych schematów (które pojawiały się w odpowiedziach) jest poprawnym schematem tego zdania?
(1) ¬r→(¬q→¬p)
(2) ¬q→(¬r→¬p)
(3) (¬q∧¬r)→¬p
[by przejść do odpowiedzi kliknij na strzałkę po prawej]
Sprawdźmy metodą tabelkową, jaką wartość przyjmują formuły (1), (2) oraz (3).
Formuły (1), (2) oraz (3) mają dokładnie te same wartości, w związku z czym są one równoważne. Czyli wszystkie trzy formuły są poprawnymi schematami wyjściowego zdania.
Gdyby Łukasiewicz żył dzisiaj, to mówiłby, że p→p to