Elementy logiki matematycznej Wrocław 2012 O czym będzie mowa? Wartości logiczne Rachunek zdań Wnioskowanie i dowodzenie Rachunek kwantyfikatorów Literatura ▶ Dariusz Wrzosek: Matematyka dla biologów . Wydawnictwa Uniwersytetu Warszawskiego. Warszawa 2008. Rozdział 1. ▶ Jan Kraszewski: Wstęp do matematyki . Wydawnictwa Naukowo–Techniczne. Warszawa 2007. Rozdziały 1. i 3. ▶ Marek Zaionc, Jakub Kozik, Marcin Kozik: Logika i teoria mnogości . http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci 2008. Rozdziały 1. i 2. Rachunek logiczny dwuwartościowy Wartości logiczne: Prawda ( Truth ), czyli T , czyli 1 (w praktyce: spełnienie), Fałsz ( False ), czyli F , czyli 0 (w praktyce: niespełnienie). Rachunek dwuwartościowy jest stosowany w logice klasycznej. Informacja o innych rachunkach logicznych ▶ Rachunek trójwartościowy bywa stosowany w niektórych systemach informatycznych (np. w bazach danych). Prawda ( Truth ), czyli T , czyli 1, Fałsz ( False ), czyli F , czyli 0, Nieznany ( Unknown ), czyli U , czyli ? (w praktyce: brak informacji). ▶ Intuicjonizm odrzuca niektóre reguły rachunku zdań obowiązujące w logice klasycznej, mające związek z dowodzeniem nie wprost (m.in. prawo wyłączonego środka). Intuicjonizm ma bliski związek z logiką trójwartościową, przy czym dodatkową wartość „?” należy interpretować raczej jako „Możliwa” niż „Nieznana”. ▶ Logika rozmyta zezwala na przypisywanie zdaniom wartości liczbowych pośrednich między 0 a 1. Bywa stosowana praktycznie w systemach inżynieryjnych. Zdania logiczne Zdanie logiczne jest to stwierdzenie, którego znaczeniu można przyporządkować wartość logiczną. ▶ Zdania prawdziwe mają przypisaną wartość logiczną 1. 2 jest najmniejszą liczbą pierwszą. ▶ Zdania fałszywe mają przypisaną wartość logiczną 0. Powierzchnia Ziemi jest płaska. ▶ Istnieją teksty, które nie są zdaniami. Czy pada śnieg? Dwa czternaście. ▶ Są też zdania bez sensu, którym nie da się przypisać znaczenia. Liczba π jest twardsza niż gęś. ▶ Niektórym sensownym zdaniom nie da się jednoznacznie przypisać wartości logicznej (patrz: ostatnia strona). Problem Które zdania uznawać za prawdziwe? Formuły zdaniowe i zdania złożone W rozważaniach dotyczących reguł logiki zamiast zdań często używamy formuł zdaniowych . W miejsce konkretnych zdań o konkretnym znaczeniu i wartości używa się w nich oznaczeń symbolicznych (np. p , q ). Formuła staje się zdaniem po zastąpieniu symboli zdaniami.
(…)
…
∧
x
∧
x
∨
x
∨
x
(p(x) ∧ q(x)).
(p(x) ∨ q(x)) (w przeciwną stronę:
p(x) ∧
p(x) ∨
∨
q(x) (w przeciwną stronę:
x
∨
q(x).
x
¬p(x) (prawo de Morgana).
¬p(x) (prawo de Morgana).
.
.
.
.
.
.
Kolejność kwantyfikatorów
Niech p(x, y) będzie funkcją zdaniową z dwiema zmiennymi.
Jeżeli przy pewnej ustalonej wartości a funkcja p(a, y) jest zawsze
spełniona, to dla dowolnej ustalonej wartości b funkcja p(x, b…
…, to zdanie ¬p nie jest spełnialne.
Formuła zdaniowa
¬(p ∨ q) ⇔ ¬p ∧ ¬q
(znana jako prawo de Morgana) jest tautologią.
Formuła
((p ⇒ q) ∧ q) ⇒ p
nie jest tautologią, mimo że jest spełnialna (tzn. przy
niektórych wartościach zdań składowych p i q staje się ona
zdaniem prawdziwym).
.
.
.
.
.
.
Metoda zerojedynkowa
Istnieje systematyczna metoda, pozwalająca sprawdzać spełnialność
formuł zdaniowych.
Polega…
…) w znormalizowanej postaci koniunkcyjnej ma formę
koniunkcji zdań, z których każde jest alternatywą zdań prostych (ew.
ich zaprzeczeń).
Każdą formułę logiczną da się przekształcić w sposób równoważny
do postaci koniunkcyjnej.
(Dowód na podstawie praw de Morgana.)
.
.
.
.
.
.
Normalizacja zdań logicznych — aspekt praktyczny
Istnieje prosta praktyczna metoda sprowadzania dowolnych formuł
zdaniowych do postaci…
…
0
0
↑
0
0
1
1
0
1
0
1
0
1
1
0
↑
1
0
0
1
1
0
1
1
1
1
0
0
↑
1
1
1
1
Każdy taki układ jest koniunkcją zdań prostych (w tym przypadku: p,
q, r) lub ich zaprzeczeń. W konsekwencji
f ⇔ ¬((¬p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r)).
Teraz korzystając z praw de Morgana przedstawiamy wynik w postaci
koniunkcji zdań, z których każde jest alternatywą zdań prostych lub
ich zaprzeczeń. Ostatecznie
f ⇔ (p ∨ q…
… się regułami logiki.
Może służyć do uzasadniania tez.
▶
Wnioskowanie indukcyjne wykorzystuje zdolności obserwacyjne
i analityczne. Przydaje się do formułowania hipotez, ale nie ma
mocy uzasadniania.
▶
Wnioskowanie statystyczne pozwala oszacować
prawdopodobieństwo danej sytuacji w warunkach niepełnej
wiedzy. Twierdzenia statystyki dowodzone są dedukcyjnie,
jednak wnioskowanie statystyczne nie daje uzasadnienia…
… o istnieniu obiektu bądź
obiektów danego rodzaju.
Istnieją różowe słonie.
Niech f : R → R będzie funkcją ciągłą. Jeżeli f(0) = −1
i f(1) = 1, to istnieje punkt c ∈ (0, 1) taki że f(c) = 0.
Przy formułowaniu twierdzeń egzystencjalnych stosuje się
kwantyfikatory szczegółowe.
Dla udowodnienia twierdzenia egzystencjalnego wystarczy wskazać
konkretny obiekt.
Wykazanie fałszywości twierdzenia egzystencjalnego…
…
1
p
0
0
1
1
q p⇔q
0
1
1
0
0
0
1
1
.
.
.
.
.
.
Właściwości działań logicznych (wybór)
Reguły rachunku logicznego są przykładem tzw. algebry Boole’a
(George Boole 1815–1864).
▶
p ∧ 1 ⇔ p,
▶
p ∧ 0 ⇔ 0,
p ∨ 1 ⇔ 1,
p ∨ 0 ⇔ p.
Idempotentność: p ∧ p ⇔ p,
▶
Samoodwrotność zaprzeczenia: ¬¬p ⇔ p.
▶
Przemienność: p ∧ q ⇔ q ∧ p, p ∨ q ⇔ q ∨ p.
▶
Łączność: (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r),
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r…
... zobacz całą notatkę
Komentarze użytkowników (0)