LOGIKA
Klasyczny Rachunek Zdań
Robert Trypuz
Katedra Logiki KUL
7 kwietnia 2011
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
Zarys
1
Krótka historia klasycznego rachunku zdań (KRZ)
2
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
Zarys
1
Krótka historia klasycznego rachunku zdań (KRZ)
2
3
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
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 Łukasiewicz, Alfred Tarski
Alfabet KRZ
Alfabet KRZ zawiera:
nieskończony zbiór zmiennych zdaniowych:
p, q, r , ..., p
1
, q
1
, r
1
, ..., p
2
, q
2
, r
2
, ...
skończony zbiór funktorów prawdziwościowych: ¬, ∧, ∨, →, ≡,
nawiasy: (, ).
Zmienne zdaniowe będziemy dalej również nazywać atomami.
Alfabet KRZ
Alfabet KRZ zawiera:
nieskończony zbiór zmiennych zdaniowych:
p, q, r , ..., p
1
, q
1
, r
1
, ..., p
2
, q
2
, r
2
, ...
skończony zbiór funktorów prawdziwościowych: ¬, ∧, ∨, →, ≡,
nawiasy: (, ).
Zmienne zdaniowe będziemy dalej również nazywać atomami.
Alfabet KRZ
Alfabet KRZ zawiera:
nieskończony zbiór zmiennych zdaniowych:
p, q, r , ..., p
1
, q
1
, r
1
, ..., p
2
, q
2
, r
2
, ...
skończony zbiór funktorów prawdziwościowych: ¬, ∧, ∨, →, ≡,
nawiasy: (, ).
Zmienne zdaniowe będziemy dalej również nazywać atomami.
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 , ..., p
1
, q
1
, r
1
, ... jest formułą KRZ
2
Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq
3
Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq
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 , ..., p
1
, q
1
, r
1
, ... jest formułą KRZ
2
Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq
3
Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq
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 , ..., p
1
, q
1
, r
1
, ... jest formułą KRZ
2
Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq
3
Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq
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 , ..., p
1
, q
1
, r
1
, ... jest formułą KRZ
2
Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq
3
Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq
Przykład formuł KRZ
Umowa:
W ciągu symboli: ¬, ∧, ∨, →, ≡ 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 ))
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. Łukasiewicza (lub innych równoważnych)
takich, że istnieje tablica analityczna zamknięta dla ich negacji
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. Łukasiewicza (lub innych równoważnych)
takich, że istnieje tablica analityczna zamknięta dla ich negacji
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. Łukasiewicza (lub innych równoważnych)
takich, że istnieje tablica analityczna zamknięta dla ich negacji
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. Łukasiewicza (lub innych równoważnych)
takich, że istnieje tablica analityczna zamknięta dla ich negacji
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)
≡ — . . . wtedy i tylko wtedy, gdy . . . (równoważność)
Język KRZ jako schemat niektórych zdań języka polskiego
Zrozumieć KRZ przez prawidłowe odczytanie formuł
Nie jest tak, że
|
{z
}
¬
słońce świeci
|
{z
}
p
.
Świeci słońce
|
{z
}
p
i
|{z}
∧
nie (jest tak, że)
|
{z
}
¬
pada deszcz
|
{z
}
q
.
Jeżeli pada deszcz,
|
{z
}
p
to
|{z}
→
szosa jest mokra
|
{z
}
q
.
Pójdziemy do kina
|
{z
}
p
lub
|{z}
∨
zabiorę cię na zakupy
|
{z
}
q
.
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 ≡ 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
Wartościowanie
Wartościowanie
Wartościowaniem nazywamy funkcję v
ze zbioru atomów {p, q, r , . . . , p
1
, . . . } w zbiór {1, 0}:
v : {p, q, r , . . . , p
1
, . . . } −→ {1, 0}
A zatem funkcja wartościowania v przypisuje każdej zmiennej zdaniowej
p, q, r , . . . , p
1
, . . . 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.
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
Prawo logiki (na gruncie rachunku zdań) – uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2
n
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)
Prawo logiki (na gruncie rachunku zdań) – uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2
n
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)
Prawo logiki (na gruncie rachunku zdań) – uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2
n
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)
Prawo logiki (na gruncie rachunku zdań) – uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2
n
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)
Prawo logiki (na gruncie rachunku zdań) – uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2
n
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)
Prawo logiki (na gruncie rachunku zdań) – uwagi
Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2
n
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)
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
|{z}
1
4
→
|{z}
1
5
|{z}
0
q
|{z}
0
7
) ∧
|{z}
1
2
¬
|{z}
1
5
q
|{z}
0
6
→
|{z}
0
1
¬
|{z}
0
2
p
|{z}
1
3
Uwaga!
Indeks n w 1
n
i 0
n
oznacza n-ty krok postępowania.
Wykaż, że poniższe formuły są prawami logiki (1)
1
p → p
2
p ≡ 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 𠪪p)
12
(p → q) ∧ (r → s) → (p ∧ r → q ∧ s)
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) ≡ ¬p ∧ ¬q
6
p ∧ ¬p → q
7
¬(p ∧ q) ≡ 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 ≡ q) ≡ (p → q) ∧ (q → p)
13
q → (p → q)
Wykaż, że poniższe formuły są prawami logiki (3)
1
p ∧ q → r ≡ p ∧ ¬r → ¬q
2
(p → q) ∧ ¬q → ¬p
3
(p → q) ≡ (¬q → ¬p)
4
¬(p ∧ q) ≡ ¬p ∨ ¬q
5
p → q ≡ ¬p ∨ q
6
p ∧ q → r ≡ p → (q → r )
7
(p → q) ∧ (q → r ) → r )
8
¬(p ∧ q) ≡ ¬p ∨ ¬q
9
p → q ≡ ¬p ∨ q
10
p ∧ q → r ≡ p → (q → r )
11
(p → q) ∧ (q → r ) → (p → r )
Document Outline
Wyszukiwarka
Podobne podstrony:
2010 01 Wykład 6 Obwód LC drgania swobodne (2)
01 wykład
Ekologiczne Systemy Chowu i Żywienia Zwierząt - Wykład 01, WYKŁAD I- EKOLOGICZNE SYSTEMY CHOWU I ZYW
22 01 wykład
zalacznki 01, Wykłady-teoria, Ogólne zasady ruchu oraz piesi
wykłady, 01, WYKŁAD 1
01 wyklad1 (1) Flisid 3011 ppt
01 Wykład 1
01 Wykłady Pisma Świętego C. T. Russella (cz. 1-4), Wykłady Pisma Świętego C. T. Russella (cz. 1-4)
Projekt 01, Wykład 01
hme 05 10 01 wykład03
01 Wykład?chy umowy leasinguid006
więcej podobnych podstron