W tej części kursu będziemy wyprowadzać wniosek z przesłanek w oparciu o zestaw reguł (o których zakładamy bez dowodu, że są poprawne). Idea wyprowadzenia polega na tym, że przekształcamy wejściowe formuły (przesłanki) w oparciu o te dozwolone reguły tak, że w wyniku takiego przekształcania uzyskujemy wniosek.
By to zrobić, należy podać numerowaną listę formuł, w której:
pierwsze numerowane linijki to przesłanki;
wolno dodawać numerowane linijki TYLKO poprzez reguły wnioskowania zastosowane do tego, co JUŻ masz (na przykład: by dodać linijkę z numerem 3, wolno ci korzystać z reguł zastosowanych do linijek 1 i 2; by dodać linijkę z numerem 4, wolno ci korzystać z reguł zastosowanych do linijek 1, 2, 3 itd.);
dodajesz numerowane linijki formuł do momentu, póki nie uzyskasz wniosek. Linijka z wnioskiem musi być ostatnią.
Taka numerowana lista formuł rozpoczynająca się od przesłanek i kończąca się wnioskiem nazywa się "dowodem" (jest to właśnie dowód wyprowadzenia wniosku z przesłanek).
W tej części będziemy sprawdzać poprawność rozumowań metodą syntaktyczną w oparciu o zbiór reguł "1 & 2 kreski". Przyjmujemy bez dowodu, że określone schematy wnioskowań są niezawodne:
📌Zauważ: ŻADNA z reguł dla implikacji α→β nie pozwala uzyskać poprzednika α:
dostaniemy albo następnik β w wyniku RO;
albo dostaniemy zanegowany poprzednik ¬α (w wyniku MT bądź reguły 2-ch kresek)
⛔ NIE MOŻESZ
przesłanka
⊕→Δ
⊕ (RO 2) --- BŁĄD I ZŁO
Jeśli czujesz się zupełnie pogubiony,
nie rozumiesz, jak działają reguły,
to popatrz na tłumaczenie reguł
przez Misia Dedu(-kcji).
Spróbuj zrobić proste ćwiczenia ze znaczkiem Gandalfa.
Zawsze będziemy sprawdzać, czy z przesłanek da się wyprowadzić wniosek, metodą nie wprost (czyli zawsze celem dowodu będzie sprzeczność - wyprowadzenie sprzecznych formuł z przesłanek).
Staraj się przede wszystkim używać reguł "1 kreski", a jeśli już naprawdę nie masz pomysłu, jak dalej poprowadzić dowód, to sięgnij po reguły "2 kresek". UWAGA: przy stosowaniu reguł "2 kresek" dowód rozgałęzi się na dwie części.
Definicja: założeniowym dowodem nie wprost formuły β ze zbioru przesłanek {δ1, δ2, ..., δn} jest dowolny skończony ciąg formuł taki, że jego początkowymi elementami są formuły δ1, δ2, ..., δn, kolejnym elementem jest formuła ¬β, a pozostałymi jego elementami są wnioski z reguł, których przesłanki znajdują się wcześniej w tym ciągu lub tezy udowodnione wcześniej. Dowód jest zakończony, gdy w tym ciągu występuje para formuł nawzajem sprzecznych.
Dowód nie wprost to numerowana lista formuł, w której:
pierwsze numerowane linijki to przesłanki;
kolejna numerowana linijka to zanegowany wniosek (z.d.n. - założenie dowodu nie wprost);
wolno dodawać numerowane linijki TYLKO poprzez reguły wnioskowania zastosowane do tego, co JUŻ masz (na przykład: by dodać linijkę z numerem 3, wolno ci korzystać z reguł zastosowanych do linijek 1 i 2; by dodać linijkę z numerem 4, wolno ci korzystać z reguł zastosowanych do linijek 1, 2, 3 itd.);
dodajesz numerowane linijki formuł do momentu, póki nie uzyskasz na liście dwie formuły, które są ze sobą sprzeczne.
📌A co wtedy, jeśli sprzecznych formuł nie uzyskamy?
Może być tak, że w oparciu o reguły "1&2" pozbyłeś się wszystkich formuł ze spójnikami → ↔ ∨ ∧. Zostały wyłącznie zmienne bądź negacje zmiennych (pojedyncze literki i ich negacje). Nie da się już dołączyć kolejnej numerowanej linijki, natomiast na liście formuł nie znajdują się dwie formuły, które są ze sobą sprzeczne. Taka sytuacja oznacza, że nie da się wyprowadzić takiego wniosku z takich przesłanek (zauważ, że w takiej sytuacji dowód de facto nie istnieje, ponieważ nie byliśmy w stanie go stworzyć - nie potrafiliśmy stworzyć numerowanej listy formuł, w której byłyby przesłanki, zanegowany wniosek i dwie sprzeczne ze sobą formuły uzyskane poprzez przekształcenie przesłanek i zanegowanego wniosku w oparciu o reguły "1&2").
📌UWAGA: ZAWSZE PRZY KORZYSTANIU Z REGUŁ "1&2" DOWODZIMY NIE WPROST
Jak prowadzić dowód?
Musisz w oparciu o reguły "1&2" pozbyć się wszystkich formuł ze spójnikami → ↔ ∨ ∧ tak, by na "gałęziach" zostały wyłącznie zmienne bądź negacje zmiennych.
Przykład. Badamy, czy wniosek s→(p∨q) da się wyprowadzić z przesłanek ¬p→¬s oraz ¬q→¬s:
Cel: sprzeczność
¬p→¬s przesłanka
¬q→¬s przesłanka
¬(s→(p∨q)) z. d. n.
s (NI 3)
¬(p∨q) (NI 3)
¬¬q (MT 2 i 4)
¬p (NA 5)
¬q (NA 5)
SPRZECZNOŚĆ: 6 i 7. Cel dowodu osiągnięty. Oznacza to, że da się wyprowadzić wniosek z tych przesłanek.
Przykład. Badamy, czy wniosek ¬p da się wyprowadzić z przesłanek (p∧q)→(q∨r) oraz ¬q:
Cel: sprzeczność
(p∧q)→(q∨r) przesłanka
¬q przesłanka
¬¬p z. d. n.
p (O2N 3)
---(reguła "2 I" rozgałęzia dowód na 2 gałęzie)----------------
¬(p∧q) || q∨r ("2 I", 1)
6. ¬p∨¬q (NK 5) || r (OA 2 i 5)
7. ¬q (OA 6 i 4) || Brak sprzeczności w prawej gałęzi. Na tej gałęzi zostały rozpisane wszystkie formuły (pozbyliśmy się wszystkich spójników → ↔ ∨ ∧). Więcej nic nie da się w niej zrobić. Brak sprzeczności w gałęzi oznacza, że wniosku nie da się wyprowadzić (i drugą gałęzią możemy nie zajmować się).
📌Jeśli masz dwie (bądź więcej) gałęzi dowodu, to:
wybierz którąś z gałęzi;
prowadź ją tak, by pozbyć się w niej wszystkich formuł ze spójnikami (za pomocą reguł "1&2"). Pozbyłeś się i:
w gałęzi brak sprzecznych formuł. Wtedy nie musisz zajmować się drugimi gałęziami. Brak sprzeczności oznacza, że WNIOSEK NIE WYNIKA z tych przesłanek (zawodne rozumowanie);
ALBO
w gałęzi są sprzeczne formuły. Wtedy "utnij" tę gałąź i sprawdzaj inną. Jeśli WSZYSTKIE gałęzie są sprzeczne, oznacza to, że WNIOSEK WYNIKA z tych przesłanek (niezawodne rozumowanie).
Czasami (a zobaczysz, że nawet dość często) dowód się rozgałęzi. Nie trzeba się bać rozgałęzień, ponieważ są rzeczą normalną. Zobacz instruktażowy filmik, co należy zrobić, jeśli w dowodzie jest więcej niż jedno rozgałęzienie.
Pamiętaj: nogi należy trzymać w cieple, głowę w chłodzie, a formuły z różnych gałęzi... w osobnych gałęziach!
W tej części będziemy sprawdzać, czy dedukcyjne wnioskowanie jest poprawne formalnie - czyli będziemy sprawdzać, czy da się z przesłanek rozumowania wyprowadzić twierdzenie, które stanowi wniosek tego rozumowania. Jak to zrobić? Rozważmy następujące rozumowanie:
JB: "Powiadają, kapitanie, że jeśli spotkasz na morzu syrenę, to nie wrócisz do portu."
JW: "Bzdury, wrócisz. A na morzu spotkasz albo syrenę, albo Krakena."
JB: "Jak spotkasz Krakena, to zaciągnie cię na samiutkie dno."
Kapitan de Morgan walnął pięścią w stół: "A niech mnie koniunkcja! Przecież z tego, co pleciecie, wynika, że Kraken zaciągnie cię na dno!"
Jak sprawdzić, czy wniosek wynika z tych przesłanek?
ZZZ.... 1. Zapisz schemat. 2. Zaneguj wniosek. 3. Zbuduj dowód
Zapisz schemat
Zacznij analizę od zapisu schematu rozumowania (zapisanego w postaci formuł KRZ). Rozumowania są przeprowadzane w języku potocznym; przesłankami są pełne zdania (od dużej literki do kropki), które mogą być złożone:
Jeśli spotkasz na morzu syrenę, to nie wrócisz do portu.
Wrócisz.
Na morzu spotkasz albo syrenę, albo Krakena.
Jeśli spotkasz Krakena, to zaciągnie cię na dno.
------------
Kraken zaciągnie cię na dno.
Schemat rozumowania:
s→¬p przesłanka
p przesłanka
s∨q przesłanka
q→r przesłanka
-----------------
r wniosek
s - spotkasz na morzu syrenę;
p - wrócisz do portu;
q - spotkasz na morzu Krakena;
r - Kraken zaciągnie cię na dno.
Zaneguj wniosek
W następnym kroku zaneguj wniosek i dołącz go do numerowanej listy jako kolejną przesłankę ("z. d. n.", założenie dowodu nie wprost). Jak już rozumiesz, będziemy sprawdzać, czy z przesłanek da się wyprowadzić wniosek, metodą nie wprost. Zawsze cel dowodu będzie ten sam:
pokazać, że ze zbioru przesłanek da się wyprowadzić formuły, które są ze sobą sprzeczne.
Cel: sprzeczność
s→¬p przesłanka
p przesłanka
s∨q przesłanka
q→r przesłanka
¬r z. d. n.
📌Cel dowodu: pokazać, że z przesłanek da się wyprowadzić sprzeczne formuły.
Udało się: rozumowanie jest formalnie poprawne.
Nie udało się: rozumowanie nie jest formalnie poprawne.
⛔ Stój! Upewnij się, że nie dołączyłeś do dowodu wniosku razem z zanegowanym wnioskiem!!!
Wniosku nie wolno dołączać do dowodu!
Zbuduj dowód
W następnym kroku dołączaj formuły do listy numerowanej w oparciu o reguły dedukcji "1 & 2". Musisz pozbyć się wszystkich formuł z dwuargumentowymi spójnikami, takimi jak → ↔ ∨ ∧. Na numerowanej liście wtedy zostaną wyłącznie zmienne (pojedyncze literki) oraz negacje zmiennych. W następnym kroku je sprawdzamy - czy znajduje się wśród nich para formuł wzajem sprzecznych.
Formuły w krokach 6, 7 i 8 zostały dołączone do listy numerowanej (naszego dowodu) w oparciu o reguły "1 & 2" (a de facto o reguły dedukcji naturalnej). Doszliśmy do sprzeczności, co pokazuje, że badane rozumowanie jest formalnie poprawne.
Cel: sprzeczność
s→¬p przesłanka
p przesłanka
s∨q przesłanka
q→r przesłanka
¬r z. d. n.
¬q (MT 4 i 5)
s (OA 3 i 6)
¬p (RO 1 i 7)
SPRZECZNOŚĆ: 2 i 8
Rozważmy kolejne rozumowanie:
Majtek Jaś Wędrowniczek i bosman Jim Beam popatrzyli na siebie, na Kapitana de Morgana, na papugę Tautologię, nalali sobie po szklanicy jamajskiego rumu i kontynuowali morskie opowieści:
JB: "Ech, gdybym miał magiczny kompas, to bym znalazł Wyspę Skarbów albo ożeniłbym się z rusałką."
JW: "Z rusałką nie ożenisz się, gamoniu."
Kapitan de Morgan roześmiał się: "Ho-ho-ho, a niech mnie spójniki! Czyli magicznego kompasu mieć nie będziesz!"
Czy jest ono poprawne formalnie? - Sprawdźmy poprzez dowodzenie.
Zapisz schemat
Zacznij analizę od zapisu schematu rozumowania. Jeśli masz problem z zapisem przesłanek, to spróbuj skopiować rozumowanie do notatnika i oddziel zdania Enterem.
Gdybym miał magiczny kompas, to bym znalazł Wyspę Skarbów albo ożeniłbym się z rusałka.
Nie ożenisz się z rusałką.
-----------------------------
Nie będziesz miał magicznego kompasu.
Schemat rozumowania:
q→(s∨r) przesłanka
¬r przesłanka
–----------
¬q wniosek
q - Jim Beam posiada magiczny kompas;
s - Jim Beam znajduje Wyspę Skarbów;
r - Jim Beam żeni się z rusałką.
Zaneguj wniosek
Zaneguj wniosek i dołącz go do numerowanej listy jako kolejną przesłankę. Cel dowodu jest ten sam: pokazać, że z takich przesłanek da się wyprowadzić sprzeczne formuły. Jeśli się to nie uda, oznacza to, że rozumowanie nie jest poprawne.
Schemat rozumowania:
q→(s∨r) przesłanka
¬r przesłanka
¬¬q z. d. n.
Zbuduj dowód
Dołączaj kolejne formuły do listy numerowanej w oparciu o reguły dedukcji "1 & 2". Postaraj się uzyskać na liście numerowanej zmienne bądź ich negacje (czyli musisz pozbyć się wszystkich formuł z dwuargumentowymi spójnikami, takimi jak → ↔ ∨ ∧). Masz na liście wszystkie zmienne, które wystąpiły w rozumowaniu bądź ich negacje, nie ma już formuł ze spójnikami i nie uzyskałeś sprzeczności, to rozumowanie nie jest formalnie poprawne.
Cel: sprzeczność
q→(s∨r) przesłanka
¬r przesłanka
¬¬q z. d. n.
q (O2N 3)
s∨r (RO 1 i 4)
s (OA 5 i 2)
Nic więcej nie da się zrobić. Brak sprzeczności. Rozumowanie nie jest formalnie poprawne.
O częstych błędach w dowodach możesz przeczytać w tej części kursu.
Oglądnij krótki filmik podsumowujący, jak należy robić dowody i jakich błędów unikać.
Jest jedno pożyteczne twierdzenie, a mianowicie Twierdzenie o dedukcji (TD), które w połączeniu z metodą nie wprost tworzy niezłe kombo (i znacznie ułatwia dowód). Twierdzenie o dedukcji (w uproszczonej postaci) jest następujące:
Twierdzenie o dedukcji (w uproszczonej postaci):
Z PRZESŁANEK jest wyprowadzalny wniosek α→β wtedy i tylko wtedy, gdy z PRZESŁANEK oraz α jest wyprowadzalny wniosek β.
Na mocy tego twierdzenia w sytuacji, kiedy wniosek ma postać implikacji, wolno "oderwać" jej poprzednik i przenieść go do przesłanek i wyprowadzać następnik. No a metoda nie wprost pozwala zanegować następnik, dodać do przesłanek i wyprowadzać sprzeczność.
Przykład:
Spróbujmy udowodnić, że z przesłanki (p∧q)→r da się wyprowadzić wniosek p→(q→r). Wniosek ma postać implikacji, więc wolno na mocy TD "oderwać" jej poprzednik i przenieść do przesłanek (czyli udowadniać, że z przesłanek (p∧q)→r, p da się wyprowadzić wniosek q→r). Ale zaraz: ten nowy wniosek też ma postać implikacji, więc wolno na mocy TD "urwać" poprzednik i przenieść go do przesłanek i wyprowadzać samo r (czyli dowodzić, że z przesłanek (p∧q)→r, p, q da się wyprowadzić wniosek r). Ale możemy dowodzić nie wprost, czyli zanegować r i wyprowadzać sprzeczność, czyli:
Dowód nie wprost:
(p∧q)→r przesłanka
p przesłanka
q przesłanka
¬r z. d. n.
¬(p∧q) (MT 1 i 4)
¬p∨¬q (NK 5)
¬q (OA 6 i 2)
Sprzeczność.
Jeśli wniosek, który mamy wyprowadzić, ma postać implikacji, to twierdzenie o dedukcji w połączeniu z dowodzeniem nie wprost może stanowić niezłe KOMBO.
⛔ NIE MOŻESZ, podszywając się pod TD:
"urywać" PRZESŁANKOM poprzedników (TD działa tylko na wniosek). Zauważ: w dowodzie nie "rozrywaliśmy" przesłanki 1, ponieważ TD nie dotyczy przesłanek i byłby to błąd;
"rozrywać" wnioski, które nie są implikacjami (TD działa wyłącznie na implikacje).
Jeśli nie wiesz do końca, jak działają reguły wyprowadzania, to możesz policzyć na kalkulatorze. Wprowadź formułę. W polu "musisz mieć" wyświetli się formuła, którą musisz mieć wcześniej w dowodzie. Kalkulator policzy, jaką formułę możesz dodać do dowodu (pole "wynik").
Implikacja
Alternatywa
Negacje
Zacznij od tego filmiku, a następnie spróbuj rozwiązać zadanie z Wiedźminem niżej
Obejrzyj sobie filmik na Youtube, który stanowi mini-wykład do tej części kursu
Rozwiąż zadanie z Wiedźminem i Klątwą Faraona, a potem poćwicz sobie sprawdzanie poprawności rozumowań w oparciu o testy z tej części kursu.
Interaktywny kurs logiki autorstwa Harry'ego Genslera. Jest to kurs za darmo ale po angielsku. LINK Do tej części kursu - zestaw ćwiczeń F i G (inference rules). Ćwiczymy reguły jednej kreski w zestawie F, a dowody w zestawie G (E - easy level).
Uwaga: w Logicoli formuły są ujmowane w zewnętrzne nawiasy, a na oznaczenie spójników są używane następujące symbole:
na spójnik koniunkcji: ·
na spójnik alternatywy ∨
na spójnik negacji: ~
na spójnik implikacji: ⊃
na spójnik równoważności: ≡
Na oznaczenie "a więc" (znaku wskazującego wniosek) jest używany symbol ∴ . Zamiast "z.d.n." jest używany skrót asm.