Alfabet p, q, r, s, a, b...-zmienne(formuły atomowe)
-funktory zdaniotwórcze
( ) [ ] ,,-znaki techniczne
2.Gramatyka
I Każda zmienna jest formułą
II Jeśli i są formułami, to
(), ()(), ()(), ()(),
()() są formułami.
III Każda reguła jest zbudowana z formuł atomowych prze stosowanie skończoną ilość razy operacji łączenia funktorami tak jak to pokazano w regule II
Formuły są schematami wypowiedzi.
Kolejność działania:
1) negacja
2) koniunkcja
3) pq q-warunek konieczny zdania p
p-warunek dostateczny
(wystarczający)zd.q
W -język zbiór formuł
2.Wartościowanie zdań-funkcje prawdziwościowe. {0,1}
Funkcją prawdziwościową n-argumentową nazywamy funkcję, która każdemu układowi xi={10 i=1,2,....,n przyporządkowuje wartość 0 lub 1.
Istnieją 4 funktory jednoargumentowe 0 1 Ao 0 0
A1
0 1
A2
1 0
A3
1 1
A2 : funkcja prawdziwościowa negacji 00
01
10
11
Bo
0
0
0
0
B1
0
0
0
1
B2
0
0
1
0
B3
0
0
1
1
B4
0
1
0
0
B5
0
1
0
1
B6
0
1
1
0
B7
0
1
1
1
B8
1
0
0
0
B9
1
0
0
1
B10
1
0
1
0
B11
1
0
1
1
B12
1
1
0
0
B13
1
1
0
1
B14
1
1
1
0
B15
1
1
1
1
B1-funkcja koniunkcji B7-funkcja alternatywy B13-funkcja implikacji B9-funkcja równoważności (albo,albo)
B6-f. nierównoważności B14- dyzjunkcja( kreska Shefera)
B7-f.jednoczesnego zaprzeczenia
Jeśli przyjmujemy, że formuła atomowa jest prawdziwa(jest zdaniem prawdziwym) to przypisujemy jej wartość 1 , jeśli jest fałszywa -wartość 0.
(…)
… boku kwadratu logicznego. Pary implikacji połozonych wzdłuż jednego boku kwadratu noszą nazwę zamkniętego układu implikacji.
5.Formalne kryteria poprawności wnioskowań. Reguły wnioskowania.
Schematem wnioskowania nazywamy skończony ciąg formuł
-przesłanki-wniosek
Schemat wnioskowania jest regułą dowodzenia(regułą wnioskowania) wtedy i tylko wtedy gdy pzry każdym wnioskowaniu według tego schematu prawdziwy jest wniosek o ile tylko prawdziwe są przesłanki.
Wnioskowanie logicznie poprawne jest to takie wnioskowanie, które odbywa się według jakiejś reguły dowodzenia.
Reguły wnioskowania:
reguła odrywania
dowód nie wprost
jeżeli wiesz , że umarłeś to umarłeś
jeżeli wiesz , że umarłeś to nie umarłeś ----------------------------------------------
nie wiesz , że umarłeś
Twierdzenie o rozstrzygalności poprawności wnioskowania.
Schemat wnioskowania jest regułą wnioskowania wtedy i tylko wtedy gdy formuła jest tautologią. Twierdzenie o zamkniętości zbioru tautologii.
Zbiór tautologii jest zamknięty ze względu na reguły dowodzenia. tzn jeśli jest regułą dowodzenia oraz 1,2,...n są tautologiami to jest również tautologią.
Reguła podstawiania.
Jeżeli za zmienne tautologii na każdym miejscu gdzie one występują podstawimy odpowiednio ustalone formuły to otrzymana formuła też jest tautologią.
p: (avb)c
q: (avc)
[(pq)^(p~q)]~p
{[((avb)c))(avc)]^[(avbc)~(avc)]}~[(avb)c]
Reguła odrywania.
Jeżeli implikacja oraz poprzednik implikacji są tautologiami,to następnik implikacji też jest tautologią.
7.Kwantyfikatory.
Niech będzie dany niepusty zbiór X. Wyrażenie zawierające zmienną, które po wstawieniu dowolnego elementu xX jest zdaniem sensownym nazywamy funkcją zdaniową z argumentem logicznym ze zbioru X.
np. (x) : x jest liczbą pierwszą X=N
(x,y) xX yY
Rodzaje kwantyfikatorów.
dla każdego... kwantyfikator ogólny
inne sposoby notacji:
istnieje... kwantyfikator egzystencjalny
inne sposoby notacji:
Zaprzeczenie:
~[ x:(x)][ x: (x)]
~[ x:(x)][x :(x)]
Prawa de Morgana dla rachunku kwantyfikatorów:
Prawa przestawiania.
8…
… przestrzeni nazywamy ciałem zbiorów iff
rodzina K jest zamknięta za względu na dopełnienie, dodawanie , mnożenie Iloczyn kartezjański zbiorów Niech będą dane ZBiory A i B. iloczyn to zbiór tych wszystkich par uporządkowanych i tylko tych, których pierwsze elementy należą do A, a drugie do B. Trójka uporządkowana (x,y,z)={x,{x,y},{x,y,z}}
Relacja: dowolny podzbiór iloczynu kartezjańskiego zbiorów XxY…
... zobacz całą notatkę
Komentarze użytkowników (0)