Matryce KRZ, tautologie, podstawy PDF

Preview

Summary

LOGIKA...

Description

ALTERNATYWA ZWYKŁA

KONIUNKCJA

BINEGACJA

p

q

p∧q

p

q

p∨q

1

1

1

1

1

1

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

0

0

0

p

q

1

1

0

1

0

0

0

1

0

0

0

1

p⬇q

*czasami nazywana łączną lub nierozłączną

*inny symbol: ALTERNATYWA ROZŁĄCZNA

IMPLIKACJA p

q

p→q

p

q

p⊥q

1

1

1

1

1

0

1

0

0

1

0

1

0

1

1

0

1

1

0

0

1

0

0

0

*inne symbole:

RÓWNOWAŻNOŚĆ

DYSJUNKCJA p

q

p/q

p

q

p≡q

1

1

0

1

1

1

wartościowanie I

1

0

1

1

0

0

wartościowanie II

0

1

1

0

1

0

wartościowanie III

0

0

1

0

0

1

wartościowanie IV

*inny symbole: ↔ 

*jej funktor nazywany jest funktorem Sheffera

NEGACJA

ASERCJA/AFIRMACJA

p

~p

~~p

~~~p

p

≈p

1

0

1

0

1

1

0

1

0

1

0

0

*inny symbol: ¬

IMPLIKACJA ODWROTNA p

q

p←q

1

1

1

1

0

1

0

1

0

0

0

1

Mówiąc wartościowanie, mamy na myśli jeden, spójny zestaw przypisywania wartości różnym zmiennym. Zmienna to p, q, r… Spójny, czyli taki, że w jednym zdaniu, jeśli przypiszemy p wartość 1, to będzie tak dla każdego p w tym zdaniu, a nie tak, że niektóre p=1, a niektóre p=0.

1. W klasycznym rachunku zdań mamy funktory: a. Jednoargumentowe: takie, które działają od jednego argumentu. Najpowszechniejszym jest negacja. Możemy tutaj także zaliczyć verum lub falsum, czyli odpowiednio, funktory które zawsze od argumentu „robią” prawdę lub fałsz. i. Negacja: „nieprawda, że …”, „nie jest prawdą, że …”, „nie”. ii. Asercja: „prawdą jest, że …” b. Dwuargumentowe: takie, które działają od dwóch argumentów: koniunkcja, alternatywa zwykła i rozłączna, binegacja, dysjunkcja (dyzjunkcja), implikacja i równoważność. i. Koniunkcja (współprawdziwość): „i”, „a”, „także”, „lecz”, „ale”, „choć”, „chociaż”, „mimo, że”, „pomimo tego, że”, „nie wyłączając”, etc. ii. Alternatywa zwykła (niewspółfałszywość): „lub”. iii. Alternatywa rozłączna (niezgodność dwóch zdań pod względem prawdy lub fałszu): „albo”. iv. Dysjunkcja (niewspółprawdziwość): „bądź …, bądź …”, „bądź”. v. Binegacja (współfałszywość): „ani …, ani …”, „ani nie… ani nie…”. vi. Implikacja (ekstensywna, zwykła): „jeżeli …, to …”, „jeśli …, to …”, „o ile …, to …”, „gdyby …, to …”, „… zatem …”, „… tak/a więc …”, „ponieważ…”, „skoro …”. Tutaj mamy rozumienie „zawsze, jeżeli x, to y” – orzekamy o warunku wystarczającym. 1. Tutaj należy uważać, bowiem czasem zdania mają przestawiony szyk; np. „Przedawnienie nie biegnie, jeśli przepis ustawy nie zezwala na wszczęcie postępowania.” vii. Implikacja odwrotna (intensywna): „tylko, jeżeli …, to …” – warunek konieczny, lecz niewystarczający. (Przykład: „Jeśli ktoś ukończył 17 lat, to odpowiada karnie.” – jest to zdanie zawierające warunek konieczny, lecz niewystarczający). Uwaga: tutaj strzałka jest odwrotna, lecz czytamy zdanie i tak: „tylko, jeżeli p, to q”. viii. Równoważność (zgodność zdań pod względem prawdy i fałszu): „wtedy i tylko wtedy, gdy (wtw) …”, „zawsze i tylko wtedy, gdy…”. 2. Zdanie to coś, czemu możemy przypisać wartość logiczną, a więc orzec czy jest to prawda (1) czy fałsz (0). Zauważmy, że zdaniami w sensie logicznym nigdy nie będą pytania ani wykrzyknienia (rozkazy), gdyż nie można orzec, czy są one prawdziwe czy fałszywe.

3. W KRZ mamy do czynienia ze zdaniami atomowymi (prostymi). Są to takie zdania, które możemy schematycznie/formalnie zapisać pod postacią jakiejś umowne litery, jak np. p, q, r, b, l, z, m, o, c. Wybór litery jest w pełni dowolny. Jedno zdanie atomowe musi wyrażać sąd, czyli coś orzekać. Ze zdań atomowych budujemy zdania złożone. 4. Funkcja zdaniowa spełnialna – możemy jej przypisać wartość prawdy lub fałszu. 5. Funkcja zdaniowa – wyrażenie, po którego konkretyzacji otrzymujemy zdanie języka naturalnego. Może to być formuła logiczna lub np. „Każde S jest P”, „jeżeli q to r”. 6. Funkcja logiczna 7. Powyższe matryce pokazują, jakie są warunki prawdziwości dla zdań złożonych, w zależności od wartości logicznej ich zdań atomowych. 8. Wyrazy takie, jak „zarówno” czy „zarazem” sugerują, że powinniśmy wszystkie objęte tym wyrazem zdania atomowe objąć nawiasem. 9. Kolejność stosowania nawiasów (w kolejności od „środka” na zewnątrz): ( ), [ ], {}, . 10. Co to jest funktor ekstensjonalny (prawdziwościowy): jest to funktor dzięki, któremu potrafimy orzec o wartości logicznej zdania złożonego, znając jedynie wartość logiczną zdań atomowych – abstrahujemy od ich treści. Takie są funktory w KRZ. 11. Funktory intensjonalne/nieprawdziwościowe: „wiedział, że …”, „koniecznie jest, że …”, „możliwe jest, że …”, „należy sądzić, że …”. 12. Tautologia klasycznego rachunku zdań, to takie zdanie które jest zawsze prawdziwe. Jest to gwarantowane przez formę zdania, treść nie wpływa tutaj na prawdziwość tego zdania. Czyli zdanie jest prawdziwe dzięki temu, jak jest ułożone a nie dzięki temu, jaką treść niesie. a. Przykład: „Karol jest papieżem lub nie jest papieżem” czy „samochód jest Volkswagenem lub nie jest Volkswagenem” – oba zdania możemy zapisać logicznie jako „𝑝 ∨ ~𝑝”. Takie zdanie jest tautologią, jest ono zawsze prawdziwe – nie wynika to jednakże z jego treści, z tego, że ktoś jest papieżem lub z faktu, że nim nie jest – zwyczajnie takie skonstruowanie zdania (jego forma) gwarantuje to, że zawsze będzie ono prawdziwe – każdy zawsze jest lub nie jest papieżem. Tertium non datur, trzeciej opcji nie ma i dlatego zdanie to jest tautologią. Jest to prosta tautologia, jednakże czasem, by przekonać się czy zdanie jest tautologią, będziemy potrzebowali nieco trudniejszych metod. 13. Kontrtautologia to zdanie, które jest zawsze fałszywe, niemożliwe jest takie wartościowanie (czyli przypisanie wartości: 0/1) jest poszczególnym zdaniom atomowym, by całe zdanie było prawdziwe. 14. Poza tautologią czy kontrtautologią, zdanie może być logicznie niezdefiniowane, czyli w zależność od wartościowań zdań atomowych może być w sumie prawdziwe lub fałszywe. Prawda lub fałsz tego zdania nie są zdeterminowane samą jego formą logiczną. ĆWICZENIE: 1. Zapisz w postaci logicznej następujące zdania: a. Jan idzie na spacer. b. Motyl rozwinął skrzydła. c. Pójdę na mecz i na spacer. d. Wezmę lody lub bakłażana.

Nie prawda, że tak powiedziałem. Jeżeli w czerwcu będzie deszczowo, to nie pojedziemy na wakacje. Gdybym tam był, to bym pomógł. Nie jest prawdą, że był tam zarówno Wojciech, jak i Marian. Jeśli nie byłbyś kłamcą, to byłoby nam łatwiej. O ile dobrze pamiętam, twój długopis się zagubił w przepastnej torbie Kamili. Widzę i ptaki, i niebo, a nawet słońce. Jeśli zarazem wygram na loterii i kupię książkę, to będę najszczęśliwszym człowiekiem na świecie. Nieprawda, że jej to powiedział lub ona kłamie. Jeżeli się nie przygotuję do egzaminu, to go nie zdam. Jeśli nie wyjadę na ferie z moją dziewczyną, to ona pojedzie ze swoimi znajomymi i pozna kogoś innego lub zostanie w domu i będzie rozczarowana tak zmarnowanymi feriami. p. Nieprawda, że jeśli zarazem przeczytam cały podręcznik z logiki w jeden dzień i rozwiążę kilka zadań, to na luzie zdam egzamin. q. Nie jest prawdą, że otrzymanie upomnienia od strażnika miejskiego, ma jakiekolwiek znaczenie. r. Jeśli nie jest prawdą, że wczoraj nie było niedzieli, to nie jest nieprawdą, że jutro nie będzie poniedziałku. s. Rozwiążę zadania, o ile wysłucham wykładu lub przeczytam podręcznik. t. Nieprawda, że pada deszcz lub świeci słońce i nieprawda, że jem lody i pizzę. e. f. g. h. i. j. k. l. m. n. o.

JAK ZBADAĆ, CZY IMPLIKACJA JEST TAUTOLOGIĄ? 1. Zauważmy, że implikacja to taki typ zdania, który jest fałszywy jedynie w jednym wypadku, mianowicie, kiedy poprzednik jest prawdziwy, zaś następnik jest fałszywy. To spostrzeżenie będzie dla nas niezwykle przydatne, gdyż będziemy tutaj korzystali z metody dowodu nie wprost a. Na czym polega dowód nie wprost? Otóż: i. Chcemy sprawdzić, czy przykładowo, dane zdanie jest prawdziwe, ii. W tym celu zakładamy przeciwność, czyli zakładamy, że zdanie jest fałszywe i zobaczymy, do czego nas takie założenie doprowadzi, iii. Jeśli nasze założenie przeciwne do tego, co chcemy dowieść, okaże się fałszywe/sprzeczne/niemożliwe do utrzymania, dowiedzie to, że w rzeczywistości prawdą jest to, czego chcieliśmy dowieść. 1. Dowód ten bazuje na prostej myśli: są tylko dwie opcje, jeśli udowodnimy, że jedna z tych opcji jest niemożliwa, to z pewnością jest tak, że zachodzi ta druga możliwość. 2. Dowód ten nie cieszy się pełnym poparciem wśród matematyków i logików, ale nas to nie obchodzi, gdyż w tak elementarnych rzeczach, jak dowodzenie tautologiczności zdań sprawdza się perfekcyjnie. iv. Przykład:

1. Teza: p 2. Wiemy, skądinąd, że: albo p, albo q (nie może być tak, że prawdziwe są jednocześnie i p, i q) 3. Zakładamy dla dowodu nie wprost, że: q 4. Dowodzimy, że niemożliwe jest, że q 5. Zatem musi być tak, że p v. Lepszy przykład: 1. Teza: 𝑝 ≡ ~~𝑝 2. Założenie dla dowodu nie wprost (czyli zakładamy, coś przeciwnego): 𝑝 ≡ ~𝑝 3. Wiemy, skądinąd, że założenie to jest fałszywe, co wynika z matrycy negacji. Dowiedliśmy, zatem, że przeciwieństwo naszej tezy nie może być prawdziwe, zatem musi być tak, że nasza teza jest prawdziwa. Czyli 𝑝 ≡ ~~𝑝 4. Polega to wszystko na reductio ad absurdum, sprowadzeniu założenia (w tym wypadku przeciwnego) do absurdu, czyli na wykazaniu jego niemożliwości. 2. Skoro już wiemy, jak wygląda dowód nie wprost i wiemy, że implikacja jest fałszywa tylko przy jednym wartościowaniu, możemy się zastanowić, jak pomoże nam to badać tautologiczność zdań, w których funktorem głównym jest implikacja. 3. Wiemy, że tautologia to zdanie zawsze prawdziwe, zatem założymy nie wprost, że dana implikacja jest fałszywa. Jeśli nie uda nam się tego założenia utrzymać (jeśli w czasie przypisywania wartości okaże się, że nie udaje się utrzymać spójności zdania), to zdanie musi być prawdziwe, bowiem innej opcji nie ma. 4. Z drugiej strony, jeśli uda nam się owo zdanie „ufałszywić”, a więc zachować spójność w wartościowaniu zdania przy założeniu, że jest ono fałszywe, to znaczy, że możliwa jest fałszywość zdania, zatem nie jest ono tautologią. JAK ZBADAĆ, CZY RÓWNOWAŻNOŚĆ JEST TAUTOLOGIĄ? 1. Zauważmy, że zdanie (𝑝 ∨ 𝑞) ≡ (𝑞 ∨ 𝑝) jest prawdziwe wtedy i tylko wtedy, gdy prawdziwe są zarówno zdania: a. (𝑝 ∨ 𝑞) → (𝑞 ∨ 𝑝) b. (𝑞 ∨ 𝑝) → (𝑝 ∨ 𝑞) 2. Mówiąc swobodnie, rozbijamy równoważność na dwie, przebiegające w obu kierunkach implikacje i badamy ich tautologiczność w sposób opisany powyżej. Jeśli wykażemy tautologiczność zarówno pierwszej formuły, jak i drugiej, oznacza to, że cała równoważność jest tautologią. 3. Jeśli, natomiast, chociaż w wypadku jednej implikacji okaże się, że zdanie nie jest tautologiczne, oznacza to, że cała równoważność także nie jest tautologią.

Schematycznie:

A

≡

B

(𝑝 ∨ 𝑞) ≡ (𝑞 ∨ 𝑝)

Więc sprawdzamy czy tautologią są zdania: A → B oraz B → A. Jeśli oba zdania są tautologią, to tautologią jest równoważność. Warunek tautologiczności równoważności możemy także zapisać w ten sposób: {[(𝑝 ≡ 𝑞 )] ≡ [(𝑝 → 𝑞) ∧ (𝑞 → 𝑝)]}

ĆWICZENIA: 1. Zapisz w formie logicznej i zbadaj tautologiczność następujących zdań: a. Nie jest prawdą, że jednocześnie zjem pięć kanapek i będę w stanie iść wtedy i tylko wtedy, gdy nie będę w stanie iść lub nie zjem pięciu kanapek. b. Jeżeli nie jest prawdą, że zarazem Marek był wczoraj na wykładzie i miło spędził czas, to Marek nie był wczoraj na wykładzie lub nie spędził miło czasu. c. Jeśli Onufry popełnił wykroczenie, to jest kryminalistą, zatem jeśli Onufry nie jest kryminalistą, to wykroczenia nie popełnił. d. Jeśli rozwiążę to zadanie i nie będę zmęczony, to zagram w Fifę, zatem jeśli rozwiąże to zadanie, to będę zmęczonym to zagram w Fifę. e. Jeśli nie mam przy sobie portfela, to zgubiłem go lub ktoś mi go ukradł. Zatem, jeśli nikt mi go nie ukradł, a go nie mam, to znaczy, że zgubiłem go. f. Jeśli spotkam Wiktorię, to pójdę na spacer, a jeśli spotkam Przemka, to pójdę na piwo, zatem, jeśli spotkam Wiktorię lub Przemka, to pójdę na piwo lub na spacer. 2. Zbadaj tautologiczność następujących zdań: a. (𝑝 ∧ 𝑞) → (𝑞 ∧ 𝑝) b. (𝑝 ↔ 𝑞) → (𝑞 → 𝑝) c. (𝑝 → 𝑞) → (~𝑞 → ~𝑝) d. (𝑞 → 𝑝) → (𝑝 ∨ 𝑞) e. (𝑝 ⊥ 𝑞) → (𝑝 → ~𝑞) f. (𝑝/𝑞) → (𝑞 → ~𝑝) g. (~𝑝 ≡ 𝑞) → (𝑝 ∨ 𝑞) h. ~(𝑝 ∨ 𝑞) → (~𝑞 ⊥ 𝑝)

i. j. k. l. m. n. o. p. q. r. s. t. u. v. w. x. y. z. aa. bb. cc.

~(𝑞 ∨ 𝑝) → (𝑝 ∧ ~𝑞) ~(𝑝 → 𝑞) → (𝑝 ∧ ~𝑞) (𝑝 ∧ ~𝑞) → ~(𝑝 → 𝑞) ~(𝑝 ≡ ~𝑞) → ~(~𝑝 ∧ ~𝑞) (𝑝 ∨ 𝑞) → (~𝑞 ≡ ~𝑝) [(𝑝 ∨ 𝑞) → (𝑝 → ~𝑞)] → (𝑞 → ~𝑝) [(𝑝/𝑞) ∨ ~𝑝] → (𝑝 ⬇ ~𝑞) [(𝑝 ⊥ 𝑞) ⬇ ~𝑝] → [(𝑝 ∧ 𝑞)/~(~𝑞 ∨ ~𝑝)] [𝑝 ⊥ ~(𝑞 ≡ ~𝑝)] → ~[(~𝑞/𝑝) ⬇ (𝑝 → 𝑞)] [(𝑝 ≡ 𝑞)/𝑟] → [(𝑝 ∧ 𝑞) → 𝑟] [(𝑝 → 𝑞) ∧ 𝑟] → [𝑞 ∨ ~(𝑝 ⬇ 𝑟)] [(𝑝 ≡ 𝑞) → 𝑟] → [(𝑞 ⬇ 𝑟)/(~𝑝 ∧ ~𝑞)] (~𝑝 ∨ 𝑞) → (𝑞 ∧ ~𝑝) (~𝑝 ∧ ~𝑞) ≡ (~𝑞 ⊥ 𝑝) (𝑝/~𝑞) → ~(𝑞/~~𝑝) ~(𝑝 → 𝑞) → (𝑝 ∧ ~𝑞) ~(~𝑝 ∨ ~𝑞) ≡ (𝑝 ∧ 𝑞) [(𝑝 → ~𝑞) ⊥ ~𝑝) → [~(𝑝 ⬇ ~𝑞)/(~𝑞 ≡ ~𝑝)] (𝑝 → ~𝑞) → [(~𝑞 → ~𝑟) → (𝑝 → 𝑟)] [(~𝑝 ∧ 𝑞) → ~𝑟] → [(~𝑝 ∧ 𝑞) → ~𝑟] {(𝑝 → 𝑞) ∧ [(𝑟 → 𝑠)⬇ (~𝑞 ∨ 𝑠)]} → (~𝑝 ∨ ~𝑟)...