Opracowanie zagadnień PDF

Preview

Summary

Opracowanie zagadnień...

Description

Materiał do egzaminu

Zagadnienia do egzaminu z podstaw logiki i teorii mnogości Semestr zimowy

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.

Definicja tautologii KRZ[1] , przykłady. Metody sprawdzania, czy formuła KRZ jest tautologią. Poprawne schematy wnioskowania KRZ. KPN[2] i APN[3] formuły. Aksjomatyczny system KRZ. Definicja termu, formuły atomowej, formuły i przykłady . Prawa LPR[4] – definicja, przykłady. Aksjomatyczny system LPR. Aksjomaty Zermelo-Fraenkela. Definicja działań na zbiorach i prawa algebry zbiorów . Antynomia Russela. Definicja zbioru potęgowego, przykłady. Iloczyn kartezjański, przykłady i podstawowe prawa . Funkcje jako relacje. Obraz, przeciwobraz, przykłady i prawa . Relacja, dziedzina, przeciwdziedzina, relacja odwrotna, złożenie relacji . Typy relacji na zbiorach. Relacja równoważności, klasa abstrakcji, zasada abstrakcji. Zbiory częściowo i liniowo uporządkowane, przykłady . Elementy najmniejsze, największe, minimalne, maksymalne, przykłady . Kres dolny i górny zbioru, definicja kraty. Równoliczność zbiorów, liczby kardynalne, zbiory przeliczalne, zbiory mocy continuum. [1]

Klasyczny Rachunek Zdań Koniunkcyjna Postać Normalna [3] Alternatywna Postać Normalna [4] Logika Pierwszego Rzędu (Rachunek Kwantyfikatorów) [2]

Definicja tautologii KRZ, przykłady 22 stycznia 2013 12:29

Tautologią KRZ nazywamy formułę, która przyjmuje wartość logiczną 1 przy każdym wartościowaniu.

Metody sprawdzania, czy formuła KRZ jest tautologią 22 stycznia 2013 12:29

Wartościowanie

Metoda polegająca na przypisaniu zmiennym konkretnych wartości logicznych.

Metoda skrócona "nie wprost" W tej metodzie założeniem jest, że metoda nie jest tautologią. Następnie należy sprawdzać, czy zgodnie z takim założeniem, otrzymamy sprzeczność, czy nie. Sprzeczność oznacza, że formuła jest tautologią i vice versa.

Metoda tablic analitycznych Przede wszystkim, w metodzie tej zaprzeczamy całej formule. Następnie, zgodnie z regułami, rozpisujemy poszczególne formuły na atomowe, tworząc drzewa. Na gałęziach drzew szukamy sprzeczności. Drzewo - graf skończony z wyróżnionymi wierzchołkami i końcami, taki że dowolne dwa wierzchołki łączy dokładnie jedna droga. Drogę od końca do liścia (wierzchołek, który nie ma żadnych następników), nazywamy gałęzią.

Drzewo nazywamy zamkniętym, jeżeli każda gałąź jest zamknięta.

Fakt 1. Jeżeli A ma dowód, to A jest tautologią KRZ.

Fakt 3. Aby nie komplikować dowodu, najlepiej stosować najpierw reguły, w których nie występuje podział na gałęzie.

Poprawne schematy wnioskowania KRZ 22 stycznia 2013 12:29

Reguły poprawnego wnioskowania KRZ Odrywania (modus ponens - MP)

Sylogizmu warunkowego (SYL)

Wprowadzania koniunkcji

Opuszczania koniunkcji

Wprowadzania alternatywy

Eliminacji alternatywy

Odrywania dla alternatywy

Wprowadzania równoważności

KPN i APN formuły 22 stycznia 2013 12:29

Literały - zmienne zdaniowe i ich negacje. Koniunkcyjna postać normalna formuły - koniunkcja alternatyw literałów. Ozn. KPN. Alternatywna postać normalna - alternatywa koniunkcji literałów. Ozn. APN. Dla każdej formuły KRZ istnieje formuła, która jest do niej równoważna i jest w KPN oraz formuła do niej równoważna, w APN.

Prawa stosowane do sprowadzania do postaci APN i KPN (ważniejsze)

Aksjomatyczny system KRZ 22 stycznia 2013 12:29

Aksjomaty Implikacji

Negacji

Koniunkcji

Alternatywy

Równoważności

Reguły dowodzenia Odrywania (modus ponens - MP)

Podstawiania (POD)

Definicja termu, formuły atomowej, formuły i przykłady 22 stycznia 2013 12:29

KRZ Termami nazywamy formuły, które posiadają dowód. Formułami (schematami zdaniowymi) KRZ nazywamy wyrażenia zdefiniowane w poniższy sposób: a. Każda zmienna zdaniowa jest formułą. b. Jeżeli a jest formułą, to negacja a też jest formułą. c. Formuła atomowa - najprostsza formuła.

LPR Termami nazywamy wyrażenia określone przez następujące warunki: a. Każda zmienna i stała przedmiotowa jest termem. b.

TERL - zbiór wszystkich termów języka L.

Formuły LPR spełniają następujące warunki:  Każda formuła atomowa jest formułą.   FORL - zbiór wszystkich formuł języka L.

Prawa LPR – definicja, przykłady 22 stycznia 2013 12:29

Prawem LPR (tautologią) nazywamy formułę prawdziwą we wszystkich interpretacjach danego języka.

Ważniejsze prawa LPR Prawo podstawiania

Uwaga: nie ma kolizji przy podstawianiu.

Prawa przestawiania kwantyfikatorów

Prawa rozdzielności kwantyfikatorów

Prawa zamiany zmiennych związanych

Ograniczenie: y nie występuje w A.

Prawa de Morgana

Prawa ekstensjonalności

Metoda tablic analitycznych Metodą sprawdzania, czy formuła jest prawem (tautologią LPR) jest metoda tablic analitycznych, w której obowiązują reguły metody tablic analitycznych KRZ, a także cztery dodatkowe reguły:

Reguły KRZ

Reguły LPR

t - dowolny term stały a - nowa stała, niewystępująca wcześnieij

Aksjomatyczny system LPR

22 stycznia 2013 12:29

Aksjomaty logiczne A0: Wszystkie formuły logiczne są prawdziwe na gruncie rachunku zdań.

Ograniczenie: nie ma kolizji zmiennych przy podstawianiu. Ograniczenie: nie ma kolizji zmiennych przy podstawianiu.

Prawa pustych kwantyfikatorów Ograniczenie: x nie jest wolne w A.

Aksjomaty Zermelo-Fraenkela 22 stycznia 2013 12:29

Ekstensjonalności Jeżeli zbiory A i B mają takie same elementy, są równe.

Zbioru pustego

Podzbiorów ("wyróżniania") Dla każdego zbioru A istnieje zbiór wszystkich elementów zbioru A, które spełniają warunek w(x).

Inkluzja Mówimy, że zbiór X zawiera się w zbiorze Y, jeżeli wszystkie elementy X należą do Y.

Własności inkluzji 1. 2. 3. 4.

Pary

Dla wszelkich przedmiotów a, b, istnieje zbiór, którego jedynymi elementami są a i b.

Sumy

Zbioru potęgowego Dla każdego zbioru A, istnieje zbiór wszystkich podzbiorów zbioru A. Oznaczamy P(A) lub 2A. Zbiór potęgowy zbioru n-elementowego ma 2n elementów.

Definicja działań na zbiorach i prawa algebry zbiorów 22 stycznia 2013 12:29

Przemienność sumy Przemienność iloczynu Łączność sumy Łączność iloczynu Rozdzielność iloczynu względem sumy Rozdzielność sumy względem iloczynu Prawa de Morgana dla zbiorów

Antynomia Russela 22 stycznia 2013 12:29

Definicja zbioru potęgowego, przykłady 22 stycznia 2013 12:29

Dla każdego zbioru A istnieje zbiór wszystkich podzbiorów zbioru A.

P(A) lub 2A nazywamy zbiorem potęgowym zbioru A. Jeżeli zbiór A ma n elementów, to P(A) ma 2 n elementów.

Iloczyn kartezjański, przykłady i podstawowe prawa 22 stycznia 2013 12:30

Iloczyn kartezjański nie jest przemienny!

Przykładowe prawa 1. 2. 3.

Funkcje jako relacje 22 stycznia 2013 12:30

Definicja funkcji

a. b. c.

Suriekcja

Iniekcja Funkcję nazywamy różnowartościową (wzajemnie jednoznaczną iniekcją), jeżeli dodatkowo spełnia warunek lewostronnej jednoznaczności (jest jednocześnie prawo- i lewostronnie jednoznaczna, czyli wzajemnie jednoznaczna:

Relacja odwrotna do funkcji nie zawsze jest funkcją. Dla każdej funkcji f, f -1 jest funkcją wtedy i tylko wtedy, gdy f jest iniekcją.

Bijekcja Bijekcją nazywamy funkcję, która jest jednocześnie suriekcją i iniekcją.

Złożenie funkcji

Obraz, przeciwobraz, przykłady i prawa 22 stycznia 2013 12:30

Prawa

Relacja, dziedzina, przeciwdziedzina, relacja odwrotna, złożenie relacji 22 stycznia 2013 12:30

Definicja

Typy relacji na zbiorach 22 stycznia 2013 12:30

Mówimy, że relacja R jest:       

Relacja równoważności, klasa abstrakcji, zasada abstrakcji 22 stycznia 2013 12:30

Relacją równoważności nazywamy relację, która jest jednocześnie zwrotna, symetryczna i przechodnia.

Definicja klasy abstrakcji Własności klas abstrakcji 1. 2. 3.

Zasada abstrakcji Każda relacja równoważności R w niepustym zbiorze X ustala podział zbioru X na rozłączne i niepuste podzbiory (mianowicie na klasy abstrakcji) w taki sposób, że dwa elementy x , y zbioru X należą do tego samego podzbioru wtedy i tylko wtedy gdy x R y. 1. Np. w geometrii p, q, r - proste p || q wtw gdy p=q lub p jest równoległa do q Kierunki na płaszczyźnie - klasy abstrakcji tej relacji. 2.

a.

b.

c.

Zbiory częściowo i liniowo uporządkowane, przykłady 22 stycznia 2013 12:30

Relację R na zbiorze A nazywamy częściowo porządkującą, jeżeli jest:  zwrotna,  słabo antysymetryczna,  przechodnia. Tzn. 1. 2. 3. Relację R na zbiorze A nazywamy liniowo porządkującą, jeżeli jest:  zwrotna,  słabo antysymetryczna,  spójna. Tzn. 1. 2. 3. Parę (A, R), gdzie A jest zbiorem, a R relacją częściowo porządkującą na zbiorze A, nazywamy zbiorem częściowo uporządkowanym. Parę (A, R), gdzie A jest zbiorem, a R relacją liniowo porządkującą na zbiorze A, nazywamy zbiorem liniowo uporządkowanym.

Elementy najmniejsze, największe, minimalne, maksymalne, przykłady 22 stycznia 2013 12:30



   Element najmniejszy (największy), o ile istnieje, to jest jedyny. Element najmniejszy jest minimalnym, a największy maksymalnym.

Kres dolny i górny zbioru, definicja kraty 22 stycznia 2013 12:30

Równoliczność zbiorów, liczby kardynalne, zbiory przeliczalne, zbiory mocy continuum 22 stycznia 2013 12:30

Zbiorom skończonym przypisane są liczby naturalne.

Zbiory skończone oraz równoliczne ze zbiorem liczb naturalnych nazywamy przeliczalnymi. Pozostałe zbiory nie są przeliczalne....