Klasyczny Rachunek Zdań (część I)
Logika dla informatyków
Klasyczny Rachunek Zdań (część I)
Robert Trypuz
Katedra Logiki KUL
17 marca 2011
Klasyczny Rachunek Zdań (część I)
Zarys
1 Krótka historia klasycznego rachunku zdań (KRZ)
Klasyczny Rachunek Zdań (część I)
Zarys
1 Krótka historia klasycznego rachunku zdań (KRZ)
2 Język KRZ
Alfabet KRZ
Formuła KRZ
Klasyczny Rachunek Zdań (część I)
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
Skrócona metoda P-F
Klasyczny Rachunek Zdań (część I)
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 A
ukasiewicz, Alfred Tarski
Klasyczny Rachunek Zdań (część I)
Język KRZ
Alfabet KRZ
Alfabet KRZ
Klasyczny Rachunek Zdań (część I)
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ń (część I)
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ń (część I)
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ń (część I)
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ń (część I)
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ń (część I)
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" È
Definicja formuła KRZ w BNF
::= | [ ( ][ ) ]
::=  p |  q |  r |  s |  p1 | . . . |  pn
::=  Ź |
::=  '" |  (" |   |  a"
Wyprowadzenie formuły z gramatyki można zilustrować za pomocą
drzewa wywodu i drzewa struktury.
Klasyczny Rachunek Zdań (część I)
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ń (część I)
Zrozumieć KRZ  metoda 0-1
Czym jest KRZ?
Czym jest KRZ?
Klasyczny Rachunek Zdań (część I)
Zrozumieć KRZ  metoda 0-1
Czym jest KRZ?
Czym jest KRZ?
KRZ jest zbiorem pewnych formuł.
Klasyczny Rachunek Zdań (część I)
Zrozumieć KRZ  metoda 0-1
Czym jest KRZ?
Czym jest KRZ?
KRZ jest zbiorem pewnych formuł.
KRZ jest zbiorem formuł. . .
Klasyczny Rachunek Zdań (część I)
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 P-F)
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. A
ukasiewicza (lub innych równoważnych)
takich, że istnieje tablica analityczna zamknięta dla ich negacji
Klasyczny Rachunek Zdań (część I)
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ń (część I)
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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Zrozumieć KRZ przez metodę P-F
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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Metoda P-F; 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 dla
każdego układu wartości 1 i 0 przyporządkowanych występującym w nim
zmiennym zdaniowym.
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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Prawo logiki (na gruncie rachunku zdań)  uwagi
Klasyczny Rachunek Zdań (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Prawo logiki (na gruncie rachunku zdań)  uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2n różnych
sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.
Klasyczny Rachunek Zdań (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Prawo logiki (na gruncie rachunku zdań)  uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2n różnych
sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Prawo logiki (na gruncie rachunku zdań)  uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2n różnych
sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Prawo logiki (na gruncie rachunku zdań)  uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2n różnych
sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
Prawo logiki (na gruncie rachunku zdań)  uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2n różnych
sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
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 (" r)
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ń (część I)
Zrozumieć KRZ  metoda 0-1
Język KRZ jako schemat niektórych zdań języka polskiego
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)
Klasyczny Rachunek Zdań (część I)
Zrozumieć KRZ  metoda 0-1
Skrócona metoda P-F
Skrócona metoda P-F
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