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

5

Ź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/