matdyskr3.pdf

(138 KB) Pobierz
3. Elementy logiki matematycznej, rachunek zdań,
funkcje zdaniowe, metody dowodzenia, rachunek
predykatów
Logika matematyczna, dział matematyki zajmujący się badaniem
własności wnioskowania (dowodzenia) matematycznego oraz modeli
teorii matematycznych. Początki logiki matematycznej sięgają drugiej
połowy XIX w. (G.Boole, Ch.Peirce, G.Peano), ale jej uformowanie
się i rozwój przypadają na wiek XX (G.Frege, D.Hilbert, B.Russell).
Najciekawsze odkrycia w logice matematycznej poczynili K.Gödel
i A.Tarski w latach 30 XX wieku. Oprócz logiki ogólnej (obejmującej
także logikę intuicjonistyczną, logiki modalne i in.) wyodrębnia się
w logice matematycznej następujące działy:
teorię modeli, badającą związki między zbiorami zdań (formuł)
a ich modelami, a także podającą konstrukcje modeli o specjalnych
własnościach (A.Tarski, R.Vaught, T.Skolem);
teorię rekursji, badającą efektywność konstrukcji matematycznych
i logicznych oraz rozstrzygalność teorii; teoria ta bazuje na pojęciu
funkcji obliczalnej (rekurencyjnej) wprowadzonym przez K. Gödla
i niezależnie przez A. Turinga;
teorię dowodu, badającą strukturę dowodów matematycznych
i zagadnienia konstruktywności w matematyce (D.Hilbert,
J.Herbrand, L.E.J.Brouwer, G.Gentzen).
 
Logika zdań, rachunek zdań
Zdanie logiczne jest to wypowiedź, w której orzeka się coś
o czymś, czyli w terminach tradycyjnej gramatyki jest to
zdanie oznajmujące.
W logice dwuwartościowej (klasycznej) zakłada się, że każde
poprawnie zbudowane zdanie jest albo prawdziwe albo
fałszywe jest to tak zwana zasada sprzeczności.
„Prawdę” bądź „fałsz” nazywamy wartością logiczną (stałą
logiczną) zdania i oznaczamy odpowiednio przez P lub 1 oraz
F lub 0.
Logika zdań bada prawdziwość zdań złożonych zależnie od
wartości logicznych zdań składowych. Przy czym rozpatruje
się tylko złożenia ekstensjonalne, czyli takie których
prawdziwość zależy wyłącznie od wartości logicznych zdań
składowych i łączących ich spójników zdaniowych.
 
Zmienna zdaniowa (najczęściej oznaczana p, q, r …) jest
literą reprezentującą dowolne zdanie lub inaczej zmienna
zdaniowa wskazuje wolne miejsce, które może zostać
wypełnione przez dowolne wyrażenie należące do kategorii
zdań.
Wartościowaniem nazywamy funkcję, która każdej zmiennej
zdaniowej przyporządkowuje wartość logiczną 0 lub 1.
Funkcję taką można uogólnić na zbiór wszystkich formuł
rachunku zdań.
Tautologią nazywamy formułę, która przy dowolnym
wartościowaniu przybiera wartość logiczną 1.
Wartość logiczna wyrażenia zdaniowego może być
wyznaczona za pomocą wartości logicznych klasycznych
funktorów zdaniowych.
Funktorem zdaniowym n-argumentowym (spójnikiem
zdaniowym) nazywamy funkcję, która każdemu układowi
(p 1 ,p 2 ,…,p n ), gdzie p i jest prawdą bądź fałszem,
przyporządkowuje wartość logiczną 0 lub 1. Istnieje
n
2
2
n-argumentowych funktorów zdaniowych.
 
Dla n=1 istnieją cztery funktory, nazywamy je funktorami
jednoargumentowymi:
0
1
A 0
0
0
A 1
0
1
A 2
1
0
A 3
1
1
Dla n=2 jest szesnaście funktorów, które nazywamy
funktorami dwuargumentowymi:
00
01
10
11
0
B 0
0
0
0
B 1
0
0
0
1
B 2
0
0
1
0
B 3
0
0
1
1
0
B 4
0
1
0
B 5
0
1
0
1
B 6
0
1
1
0
B 7
0
1
1
1
0
B 8
1
0
0
B 9
1
0
0
1
B 10
1
0
1
0
B 11
1
0
1
1
0
B 12
1
1
0
B 13
1
1
0
1
B 14
1
1
1
0
B 15
1
1
1
1
796555320.029.png 796555320.001.png 796555320.002.png 796555320.003.png 796555320.004.png 796555320.005.png 796555320.006.png 796555320.007.png 796555320.008.png 796555320.009.png 796555320.010.png 796555320.011.png 796555320.012.png 796555320.013.png 796555320.014.png 796555320.015.png 796555320.016.png 796555320.017.png 796555320.018.png 796555320.019.png 796555320.020.png 796555320.021.png 796555320.022.png 796555320.023.png 796555320.024.png 796555320.025.png 796555320.026.png 796555320.027.png 796555320.028.png
 
Tylko niektóre funktory są używane w systemach logicznych
jako odpowiadające spójnikom zdaniowym występującym
w dalszych wnioskowaniach.
I tak funktor jednoargumentowy
A 2 nazywa się negacją (nie) i oznaczamy go „” lub „”,
oraz funktory dwuargumentowe:
B 1 nazywa się koniunkcją (i, funkcją AND) i oznacza „”,
B 7 nazywa się alternatywą (lub, funkcją OR) i oznacza „”,
B 9 nazywa się równoważnością (wtedy i tylko wtedy) i oznacza „”,
B 13 nazywa się implikacją (jeżeli … to …) i oznacza „”,
B 8 nazywa się strzałką Peirce’a (funktorem jednoczesnego
zaprzeczenia) i oznacza „”,
B 14 nazywa się dysjunkcją (funkcją NAND, funktorem Sheffera,
kreską Sheffera) i oznacza „”.
Funktory te porządkuje się następująco: , , , , .
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin