Logika i teoria mnogości/Wstęp do logiki 1
Logika i teoria mnogości/Wstęp do logiki Wstęp
Logika, mimo, że zaliczana jest do przedmiotów humanistycznych, jest jednym z najważniejszych działów matematyki. Jest ona dodatkowo działem, którego nieznajomość uniemożliwia pełne poznanie matematyki.
Znajomość logiki pozwala nam udowadniać twierdzenia, programować warunki itd.
Co to jest zdanie?
Zdanie logiczne to wyrażenie, którego wartość logiczną można jednoznacznie określić - stwierdzić, że jest ono prawdziwe lub fałszywe.
Zdaniami logicznymi nie są:
• pytania
Zdanie "Czy spadł dzisiaj deszcz?", choć poprawne w języku polskim, nie jest zdaniem logicznym, ponieważ nie można mu przyporządkować wartości prawda lub fałsz; co innego, jeżeli pod uwagę weźmiemy zdanie "Spadł
dzisiaj deszcz."
• wyrażenia ze zmienną
Tego typu wyrażenia mogą być fałszywe lub prawdziwe w zależności od danego parametru oraz wszelakie stwierdzenia w stylu "zimno mi", "ten kwiat jest piękny". Dodatkowo, wśród zdań wyróżnia się zdania proste (nie zawierające żadnych spójników logicznych) oraz zdania złożone (zawierające przynajmniej jeden spójnik logiczny).
Kwantyfikatory i spójniki logiczne
Wyróżnia się trzy kwantyfikatory:
• Dla każdego
• Istnieje
• Istnieje tylko jeden.
!
Spójniki dla każdego i istnieje są w opozycji wobec siebie. Czyli "Nieprawda, że dla każdego..." znaczy tyle co
"Istnieje taki, że..." Natomiast "Nieprawda, że istnieje..." znaczy "Dla każdego..."
Natomiast kwantyfikator Istnieje tylko jeden można zapisać
:
Uwaga: Kolejność takich samych kwantyfikatorów nie ma znaczenia, natomiast kolejność różnych już ma.
Uwaga 2: Jeżeli przed zmienną nie ma kwantyfikatorów, to domyślnie oznacza "dla każdego".
Spójniki logiczne - podstawowymi spójnikami logicznymi są:
• implikacja (
)
• równoważność (
)
• negacja (
) (not)
• alternatywa (
) (or)
• koniunkcja (
) (and)
• alternatywa wykluczająca (
) (xor)
Wartości logiczne zdań złożonych:
Logika i teoria mnogości/Wstęp do logiki 2
p q
1 1 1
1
1
1
0
1 0 0
0
1
0
1
0 1 1
0
1
0
1
0 0 1
1
0
0
0
Tautologie
Tautologie są to wyrażenie zawsze prawdziwe niezależnie od tego jakie zdania podstawimy. Tautologie są często wykorzystywanie w innych działach matematyki, na przykład przy dowodzeniu twierdzeń.
Najczęściej używane tautologie.
Prawo podwójnego zaprzeczenia
Prawa de Morgana
Prawo przechodności implikacji. Uwaga niektórzy mylą tą tautologie ze zdaniem
, które tautologią nie jest.
Prawo sylogizmu warunkowego
Prawo wyłączonego środka
Prawo sprzeczności
Prawo transpozycji
Prawo Pierce'a
Jak rozpoznać czy wyrażenie jest tautologią?
Sposób naiwny (totalny)
robimy tabele ze wszystkimi możliwościami wartości logicznych zdań prostych. Następnie dla wszystkich z tych możliwości wykonujemy zdanie które sprawdzamy np. sprawdźmy, czy zdanie W ostatniej kolumnie są same jedynki, więc zdanie jest tautologią.
Zalety sposobu naiwnego:
+ zdanie jest dokładnie sprawdzone
+ zadanie jest łatwiejsze dla komputera
+ trudniej się pomylić
Wady sposóbu naiwnego
- duża ilość obliczeń, gdyż ilość możliwości wynosi 2^n (dla 2 zmiennych to tylko 4, ale dla 100 to jest 2^100 czyli 1'267'650'600'228'229'401'496'703'205'376)
Logika i teoria mnogości/Wstęp do logiki 3
Sposób przez zaprzeczenie.
Szukamy sytuacji, w których wyrażenie może być fałszywe. W przypadku kiedy nie ma takich możliwości to orzekamy, że wyrażenie jest tautologią
Zalety sposobu przez zaprzeczenie:
+ szybszy, gdyż nie wymaga tylu obliczeń Wady sposobu przez zaprzeczanie:
- łatwo można przeoczyć ustawienie, w którym zdanie jest fałszywe
- sposób wymaga wprawy
- komputery nie mogą sprawdzać tym sposobem Po wyliczeniu wad i zalet obu systemów wydawać się by mogło, że sposób przez zaprzeczenie jest gorszym sposobem niż sposób naiwny, jednakże do sprawdzenia niezbyt skomplikowanych zdań sposób przez zaprzeczenie jest znacznie lepszym sposobem.
Funkcje Boolowskie
W funkcjach Boolowskich fałszowi przyporządkowano 0 a prawdzie - 1, koniunkcji mnożenie, alternatywie dodawanie natomiast równoważność została zastąpiona przez równa się. Z implikacji zrezygnowano. Dodatkowo przyjęto, że 1+1=1 (czyli prawda lub prawda to nadal prawda, a nie dwie prawdy).
Funkcje Boolowskie są szeroko stosowane w matematyce dyskretnej oraz w każdej dziedzinie techniki i fizyki, gdzie mierzy się prawdopodobieństwo awarii w przesyle sygnałów prądu strumienia magnetycznego itd. Osoby zainteresowane Algebrą Boola odsyłam właśnie do tych podręczników (kiedy powstaną).
Relacje logiczne a zbiory
Relacje logiczne w języku Pascal
Relacje logiczne używa się jako warunki oraz jako warunki pętli.
Przykładowy warunek if x>0 or y>0 znaczy tyle co jeżeli x>0 lub y>0
Inny przykład if x>0 or x<0 czyli jeżeli x>0 lub x<0 oczywiście można to zapisać łatwiej jako if not (x=0) Implikacja w językach programowania jest zastąpiona przez instrukcje warunkową if np.
w języku pascal zapiszemy if {warunek} do {instrukcja}. Jednakże w tym przypadku należy zrócić uwagę, że fałsz implikuje zarówno prawdę, jak i fałsz ,natomiast w instrukcji warunkowej tego nie ma.
Zadania
Przykład
Czy prawdziwe jest zdanie: Jeżeli liczba x jest pierwsza, to liczba x jest złożona to liczba x jest równa cztery. To pozornie bezsensowne zdanie sporóbujmy rozpisać logicznie. Przymujemy " liczba x jest pierwsza", "
liczba
x jest złożona", " liczba x jest równa 4". Przy czym jeśli zdania i nie mogą być prawdziwe jednocześnie.
Więc nasze zdanie po podstawieniu symboli będzie wyglądać tak
.
Tabela będzie wyglądać więc tak
Logika i teoria mnogości/Wstęp do logiki 4
Wynika więc, że jeśli x będzie liczbą złożoną różną od 4, to nasze zdanie jest fałszywe.
Zadania.
1. Jeżeli liczba naturalna x dzieli się przez 3, to z faktu, że liczba x nie dzieli się przez 3, wynika, że x dzieli się przez 5.
2. Jakie zdanie jest zaprzeczeniem zdania: Wszyscy Polacy i Niemcy żyją w Europie?
Notacja beznawiasowa
Notacja beznawiasowa (Jana Łukasiewcza nie mylić z Ignacym, wynalazcą lampy naftowej). W notacji beznawiasowej zdania są zapisywane za pomocą małych liter, a sybole logiczne przez pięć dużych liter -
C-konukcja, D-alternatywa, E-równoważność, I-implikacja oraz N-negacja.
Jeśli po symbolu N stoi zdanie, to oznacza, że zdanie należy zanegować np. Np znaczy to samo co Jeśli po symbolu C, D, E, I. stoją dwie zmienne zdaniowe, to spójnik dotyczy tych dwóch zdań np. Cpq znaczy Jeśli po symbolu C, D, E, I. stoi inny spójnik, to znaczy, że następne zdanie złożone traktujemy jako zdanie zagnieżdzone np. ICpqr znaczy tyle co
Źródła i autorzy artykułu
Logika i teoria mnogości/Wstęp do logiki Źródło: http://pl.wikibooks.org/w/index.php?oldid=160037 Autorzy: Cathy Richards, ERRONIKA, Karol Dąbrowski, Lethern, MTM, Rafalsky1313, Vatzec, Wikimi-dhiann, Yusek, 10 anonimowych edycji Licencja
Creative Commons Attribution-Share Alike 3.0 Unported
//creativecommons.org/licenses/by-sa/3.0/