Klasyczny Rachunek ZdaÅ„ LOGIKA Klasyczny Rachunek ZdaÅ„ Robert Trypuz Katedra Logiki KUL 7 kwietnia 2011 Klasyczny Rachunek ZdaÅ„ Zarys 1 Krótka historia klasycznego rachunku zdaÅ„ (KRZ) Klasyczny Rachunek ZdaÅ„ Zarys 1 Krótka historia klasycznego rachunku zdaÅ„ (KRZ) 2 JÄ™zyk KRZ Alfabet KRZ FormuÅ‚a KRZ Klasyczny Rachunek ZdaÅ„ Zarys 1 Krótka historia klasycznego rachunku zdaÅ„ (KRZ) 2 JÄ™zyk KRZ Alfabet KRZ FormuÅ‚a KRZ 3 Zrozumieć KRZ metoda 0-1 Czym jest KRZ? Odczytanie funktorów jÄ™zyka KRZ JÄ™zyk KRZ jako schemat niektórych zdaÅ„ jÄ™zyka polskiego Zrozumieć KRZ przez metodÄ™ 1-0 WartoÅ›ciowanie Prawo logiki, metoda 0-1 Metoda skróconego sprawdzania Ćwiczenia Klasyczny Rachunek ZdaÅ„ Krótka historia klasycznego rachunku zdaÅ„ (KRZ) Krótka historia klasycznego rachunku zdaÅ„ filozofia stoicka (III w. przed Chr.) zmienne zdaniowe! współczesna ujÄ™cie: Gottlob Frege (Begriffsschrift, 1879) Polacy: Jan Aukasiewicz, Alfred Tarski Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ Alfabet KRZ Alfabet KRZ Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ Alfabet KRZ Alfabet KRZ Alfabet KRZ zawiera: nieskoÅ„czony zbiór zmiennych zdaniowych: p, q, r, ..., p1, q1, r1, ..., p2, q2, r2, ... skoÅ„czony zbiór funktorów prawdziwoÅ›ciowych: Ź, '", (", , a", nawiasy: (, ). Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ Alfabet KRZ Alfabet KRZ Alfabet KRZ zawiera: nieskoÅ„czony zbiór zmiennych zdaniowych: p, q, r, ..., p1, q1, r1, ..., p2, q2, r2, ... skoÅ„czony zbiór funktorów prawdziwoÅ›ciowych: Ź, '", (", , a", nawiasy: (, ). Zmienne zdaniowe bÄ™dziemy dalej również nazywać atomami. Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ FormuÅ‚a KRZ Definicja indukcyjna formuÅ‚y KRZ FormuÅ‚a wyrażenie sensowene / gramatycznie poprawne KRZ. Niech Õ, È bÄ™dÄ… zmiennymi metajÄ™zykowymi reprezentujÄ…cymi dowolnÄ… formuÅ‚Ä™ KRZ. Wówczas: Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ FormuÅ‚a KRZ Definicja indukcyjna formuÅ‚y KRZ FormuÅ‚a wyrażenie sensowene / gramatycznie poprawne KRZ. Niech Õ, È bÄ™dÄ… zmiennymi metajÄ™zykowymi reprezentujÄ…cymi dowolnÄ… formuÅ‚Ä™ KRZ. Wówczas: 1 Każde z wyrażeÅ„ p, q, r, ..., p1, q1, r1, ... jest formuÅ‚Ä… KRZ Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ FormuÅ‚a KRZ Definicja indukcyjna formuÅ‚y KRZ FormuÅ‚a wyrażenie sensowene / gramatycznie poprawne KRZ. Niech Õ, È bÄ™dÄ… zmiennymi metajÄ™zykowymi reprezentujÄ…cymi dowolnÄ… formuÅ‚Ä™ KRZ. Wówczas: 1 Każde z wyrażeÅ„ p, q, r, ..., p1, q1, r1, ... jest formuÅ‚Ä… KRZ 2 Jeżeli Õ jest formuÅ‚Ä… KRZ, to jest też niÄ… Å¹Õ Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ FormuÅ‚a KRZ Definicja indukcyjna formuÅ‚y KRZ FormuÅ‚a wyrażenie sensowene / gramatycznie poprawne KRZ. Niech Õ, È bÄ™dÄ… zmiennymi metajÄ™zykowymi reprezentujÄ…cymi dowolnÄ… formuÅ‚Ä™ KRZ. Wówczas: 1 Każde z wyrażeÅ„ p, q, r, ..., p1, q1, r1, ... jest formuÅ‚Ä… KRZ 2 Jeżeli Õ jest formuÅ‚Ä… KRZ, to jest też niÄ… Å¹Õ 3 Jeżeli Õ i È sÄ… formuÅ‚ami KRZ, to sÄ… też nimi Õ È , Õ (" È , Õ '" È , Õ a" È Klasyczny Rachunek ZdaÅ„ JÄ™zyk KRZ FormuÅ‚a KRZ PrzykÅ‚ad formuÅ‚ KRZ Umowa: W ciÄ…gu symboli: Ź, '", (", , a" każdy symbol wiąże silniej niż symbole wystÄ™pujÄ…ce po nim. r (p q) '" p q Ź(p '" Źs) p (" Źp (p q) ((q r) (p r)) Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Czym jest KRZ? Czym jest KRZ? Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Czym jest KRZ? Czym jest KRZ? KRZ jest zbiorem pewnych formuÅ‚. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Czym jest KRZ? Czym jest KRZ? KRZ jest zbiorem pewnych formuÅ‚. KRZ jest zbiorem formuÅ‚. . . Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Czym jest KRZ? Czym jest KRZ? KRZ jest zbiorem pewnych formuÅ‚. KRZ jest zbiorem formuÅ‚. . . takich, które przyjmujÄ… wartość prawdy przy każdym wartoÅ›ciowaniu (metoda 0-1) takich, które dadzÄ… siÄ™ udowodnić na gruncie zaÅ‚ożeniowego rachunku KRZ takich, które dadzÄ… siÄ™ udowodnić na gruncie aksjomatycznego rachunku KRZ J. Aukasiewicza (lub innych równoważnych) takich, że istnieje tablica analityczna zamkniÄ™ta dla ich negacji Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Odczytanie funktorów jÄ™zyka KRZ Zrozumieć KRZ przez prawidÅ‚owe odczytanie formuÅ‚ Ź nie jest tak, że . . . (negacja) '" ... i ... (koniunkcja) (" . . . lub . . . (alternatywa) jeżeli . . . , to . . . (implikacja) a" . . . wtedy i tylko wtedy, gdy . . . (równoważność) Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 JÄ™zyk KRZ jako schemat niektórych zdaÅ„ jÄ™zyka polskiego Zrozumieć KRZ przez prawidÅ‚owe odczytanie formuÅ‚ Nie jest tak, że sÅ‚oÅ„ce Å›wieci . p Ź Åšwieci sÅ‚oÅ„ce i nie (jest tak, że) pada deszcz . p '" q Ź Jeżeli pada deszcz, to szosa jest mokra .
p q Pójdziemy do kina lub zabiorÄ™ ciÄ™ na zakupy . (" p q Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Zrozumieć KRZ przez metodÄ™ 1-0 Zrozumieć KRZ przez metodÄ™ 1-0 1 prawda 0 faÅ‚sz p Źp 1 0 0 1 p q p '" q p (" q p q p a" q 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 WartoÅ›ciowanie WartoÅ›ciowanie WartoÅ›ciowanie WartoÅ›ciowaniem nazywamy funkcjÄ™ v ze zbioru atomów {p, q, r, . . . , p1, . . . } w zbiór {1, 0}: v : {p, q, r, . . . , p1, . . . } - {1, 0} A zatem funkcja wartoÅ›ciowania v przypisuje każdej zmiennej zdaniowej p, q, r, . . . , p1, . . . wartość 1 albo 0. WartoÅ›ciowanie formuÅ‚y KRZ WartoÅ›ciowaniem formuÅ‚y Õ KRZ nazywamy funkcjÄ™ v, której dziedzina jest ograniczona do zmiennych zdaniowych wystÄ™pujÄ…cych w Õ. Na przykÅ‚ad wartoÅ›ciowaniem formuÅ‚y (p q) '" p q jest funkcja v której dziedzina jest identyczna z {p, q}. A zatem v przypisze każdej zmiennej zdaniowej p, q wartość 1 albo 0. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Metoda 0-1; prawo logiki Prawo logiki (na gruncie rachunku zdaÅ„) jest to wyrażenie zdaniowe, zbudowane wyÅ‚Ä…cznie ze staÅ‚ych logicznych, zmiennych i ewentualnie nawiasów, które przyjmuje wartość 1 przy każdym (tj. dowolnym) wartoÅ›ciowaniu. p Źp p (" Źp 1 0 1 0 1 1 p q p q (p q) '" p (p q) '" p q 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Prawo logiki (na gruncie rachunku zdaÅ„) uwagi Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Prawo logiki (na gruncie rachunku zdaÅ„) uwagi Dla wyrażenie zawierajÄ…cego n różnych zmiennych zdaniowych istnieje 2n różnych wartoÅ›ciowaÅ„, tj. sposobów przyporzÄ…dkowania im (tj. zmiennym zdaniowym) wartoÅ›ci 1 lub 0. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Prawo logiki (na gruncie rachunku zdaÅ„) uwagi Dla wyrażenie zawierajÄ…cego n różnych zmiennych zdaniowych istnieje 2n różnych wartoÅ›ciowaÅ„, tj. sposobów przyporzÄ…dkowania im (tj. zmiennym zdaniowym) wartoÅ›ci 1 lub 0. To, że posÅ‚ugujemy siÄ™ jedynie dwoma wartoÅ›ciami, 1 i 0, jest konsekwencjÄ… przyjÄ™tej przez nas zasady dwuwartoÅ›ciowoÅ›ci. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Prawo logiki (na gruncie rachunku zdaÅ„) uwagi Dla wyrażenie zawierajÄ…cego n różnych zmiennych zdaniowych istnieje 2n różnych wartoÅ›ciowaÅ„, tj. sposobów przyporzÄ…dkowania im (tj. zmiennym zdaniowym) wartoÅ›ci 1 lub 0. To, że posÅ‚ugujemy siÄ™ jedynie dwoma wartoÅ›ciami, 1 i 0, jest konsekwencjÄ… przyjÄ™tej przez nas zasady dwuwartoÅ›ciowoÅ›ci. Prawa logiki nazywa siÄ™ również tautologiami. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Prawo logiki (na gruncie rachunku zdaÅ„) uwagi Dla wyrażenie zawierajÄ…cego n różnych zmiennych zdaniowych istnieje 2n różnych wartoÅ›ciowaÅ„, tj. sposobów przyporzÄ…dkowania im (tj. zmiennym zdaniowym) wartoÅ›ci 1 lub 0. To, że posÅ‚ugujemy siÄ™ jedynie dwoma wartoÅ›ciami, 1 i 0, jest konsekwencjÄ… przyjÄ™tej przez nas zasady dwuwartoÅ›ciowoÅ›ci. Prawa logiki nazywa siÄ™ również tautologiami. O wyrażenie rachunku zdaÅ„, które jest prawem logiki mówimy, że jest prawdziwym wyrażeniem rachunku zdaÅ„. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Prawo logiki, metoda 0-1 Prawo logiki (na gruncie rachunku zdaÅ„) uwagi Dla wyrażenie zawierajÄ…cego n różnych zmiennych zdaniowych istnieje 2n różnych wartoÅ›ciowaÅ„, tj. sposobów przyporzÄ…dkowania im (tj. zmiennym zdaniowym) wartoÅ›ci 1 lub 0. To, że posÅ‚ugujemy siÄ™ jedynie dwoma wartoÅ›ciami, 1 i 0, jest konsekwencjÄ… przyjÄ™tej przez nas zasady dwuwartoÅ›ciowoÅ›ci. Prawa logiki nazywa siÄ™ również tautologiami. O wyrażenie rachunku zdaÅ„, które jest prawem logiki mówimy, że jest prawdziwym wyrażeniem rachunku zdaÅ„. Prawdziwość wyrażenia (nie tylko rachunku zdaÅ„) bÄ™dziemy oznaczać znakiem . Na przykÅ‚ad: p (" Źp (p q) (Źq Źp) Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Metoda skróconego sprawdzania Metoda skróconego sprawdzania Metoda postÄ™powania dla dowolnego wyrażenie KRZ: 1 ZakÅ‚adamy, że wyrażenie KRZ jest faÅ‚szywe. 2 WyciÄ…gamy konsekwencje tego zaÅ‚ożenia korzystajÄ…c z charakterystyki funktorów dostarczonej przez pojÄ™cia prawdy i faÅ‚szu. 3 Jeżeli nasze zaÅ‚ożenie doprowadzi do sprzecznoÅ›ci, to sprawdzane wyrażenie jest prawem logiki. 4 Jeżeli nie, to udaÅ‚o siÄ™ nam pokazać, że wyrażenie to nie jest zawsze prawdziwe, a zatem nie jest też prawem logiki. PrzykÅ‚ad ( p q ) '" Ź q Ź p 14 15 07 12 15 06 01 02 13 0 Uwaga! Indeks n w 1n i 0n oznacza n-ty krok postÄ™powania. Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Ćwiczenia Wykaż, że poniższe formuÅ‚y sÄ… prawami logiki (1) 1 p p 2 p a" p 3 p '" p p 4 p (" p p 5 p (" Źp 6 Ź(p '" Źp) 7 (p q) ((q r) (p r)) 8 (p (" q) (Źq p) 9 (ŹŹp p) 10 (p ŹŹp) 11 (p a" ŹŹp) 12 (p q) '" (r s) (p '" r q '" s) Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Ćwiczenia Wykaż, że poniższe formuÅ‚y sÄ… prawami logiki (2) 1 (p q '" r) (p q) '" (p r) 2 (p (" q r) (p r) '" (q r) 3 (p Źp) Źp 4 (p q '" Źq) Źp 5 Ź(p (" q) a" Źp '" Źq 6 p '" Źp q 7 Ź(p '" q) a" p Źq 8 (p q) '" (r s) (p (" r q (" s) 9 (p r) '" (q r) '" (p (" q) r 10 (p q) '" (r s) '" (p (" r) (q (" s) 11 (p q) '" (r s) '" Ź(q (" s) Ź(p (" r) 12 (p a" q) a" (p q) '" (q p) 13 q (p q) Klasyczny Rachunek ZdaÅ„ Zrozumieć KRZ metoda 0-1 Ćwiczenia Wykaż, że poniższe formuÅ‚y sÄ… prawami logiki (3) 1 p '" q r a" p '" Źr Źq 2 (p q) '" Źq Źp 3 (p q) a" (Źq Źp) 4 Ź(p '" q) a" Źp (" Źq 5 p q a" Źp (" q 6 p '" q r a" p (q r) 7 (p q) '" (q r) r) 8 Ź(p '" q) a" Źp (" Źq 9 p q a" Źp (" q 10 p '" q r a" p (q r) 11 (p q) '" (q r) (p r)