Egzamin Flashcards
Kategorie syntaktyczne
Wyrażenia nazwowe
-stałe nazwowe (nazwy)
- zmienne nazwowe
-funkcje nazwowe
Wyrażenia zdaniowe
- stałe nazwowe (zdania)
- zmienne zdaniowe
- funkcje zdaniowe
Operatory
-nazwotwórcze
-zdaniotwórcze
Funktory
- nazwotwórcze
- zdaniotwórcze
- operatorotwórcze
- funktorotwórcze
Kategorie pierwotne
- wyrażenia nazwowe
- wyrażenia zdaniowe
Kategorie wtórne
- Operatory
- Funktory
Nazwa
Nazwa - wyrażenie które może być podmiotem lub orzeczeniem
Nazwa jednostkowa
Nazwa która ma dokładnie jeden desygnat
Nazwa pusta
Nazwa, która nie ma żadnych prawdziwych desygnatów
Np. Pegaz, krasnoludek etc
Nazwa ogólna
Nazwa niepusta i niejednostkowa
Denotacja
Zbiór wszystkich desygnatów danej nazwy
Zmienne nazwowe
Zmienne za które można wstawić nazwy
Funkcje nazwowe
Wyrażenie, w którym po wstawieniu stałej za zmienną, otrzymujemy nazwę
Zdanie
Wypowiedź prawdziwa lub falszywa
Każde zdanie ma tylko jedną wartość logiczną!!
Funkcja zdaniowa
Wyrażenie w którym po podstawieniu stałej za zmienną otrzymujemy zdanie
Funktory
Wyrażenia, które w połączeniu z innymi wyrażeniami (argumentami) tworzą sensowne wyrażenia złożone
Spójniki logiczne
Funktory zdaniotwórcze o argumentach zdaniowych
~ negacja -
A asercja +
/\ koniunkcja 2/2
|/ binegacja 0/2
| dysjunkcja maks 1/2
| alternatywa rozłączna 1/2
<-> równoważność L=P
-> implikacja
Predykaty
Funktory zdaniotwórcze o argumentach nazwowych
Superfunktory
Funktory funktorotwórcze o argumentach funktorowych
Np. Bardzo
System trafny
System dowodzenia jest trafny witw gdy wszystkie twierdzenia tego systemu są tautologiami
Jeżeli |-A to |=A
System semantycznie pełny
System jest semantycznie pełny witw gdy wszystkie tautologie są jego twierdzeniami
Jeżeli |=A to |-A
System syntaktycznie niesprzeczny
System jest syntaktycznie niesprzeczny witw gdy wśród jego twierdzeń nie ma 2 formuł sprzecznych
Tzn.
~(|-A /\ |-~A)
Systemy równoważne
Dwa systemy dowodzenia nazywamy równoważnymi witw gdy mają identyczne zbiory formuł i twierdzeń oraz dowolna reguła pierwotna każdego z systemów jest regułą (pierwotną bądź wtórną) drugiego systemu
Systemy równoważne
Dwa systemy dowodzenia nazywamy równoważnymi witw gdy mają identyczne zbiory formuł i twierdzeń oraz dowolna reguła pierwotna każdego z systemów jest regułą (pierwotną bądź wtórną) drugiego systemu
System rozstrzygalny
System jest rozstrzygalny jeżeli istnieje EFEKTYWNA metoda pozwalająca w skończonej liczbie kroków rozstrzygnąć dla dowolnej formuły pytanie czy ta formuła jest, czy też nie jest twierdzeniem tego systemu
System negacyjnie zupełny
System jest negacyjnie zupełny witw gdy dla każdej formuły A albo ona albo jej negacja jest twierdzeniem systemu
|-A \/ |- ~A
System syntaktycznie zupełny
System jest syntaktycznie zupełny witw gdy każda formuła niedowodliwa w tym systemie dołączona do niego jako aksjomat czyni go sprzecznym
System funkcjonalnie zupełny
System jest funkcjonalnie zupełny witw gdy za pomocą jego terminów pierwotnych można zdefiniować każdy funktor prawdziwościowy rachunku zdań
Zbiór formuł semantycznie sprzeczny
Zbiór formuł logicznych nazywamy semantycznie sprzecznym witw gdy koniunkcja tych formuł jest kontrtautologią
Zbiór x jest sprzeczny witw gdy wynikają z niego logicznie dwie formuły sprzeczne
X|=A /\ X|=~A
Modus ponendo ponens
Prawo odrywania
[(p->q)^p]->q
Modus tollendo ponens
Sylogizm alternatywny
[(p v q) ^~p] -> q
[(p v q) ^~q] -> p
Modus tollendo tollens
Sylogizm destrukcyjny
[(p->q) ^ ~q] -> ~p
Modus ponendo tollens
[(~p v ~q) ^ p] -> ~q
[p|q ^ p] ->~q
Metoda zerojedynkowa skrócona (nie wprost)
Czy A?
~A #założenie
…
Sprzeczność! ~(~A)->A
Równoważność: rozbicie na 2 scenariusze (L=0 lub P=0)
p->(q->p)
————-0
—1-> ——-0
1->0
p - 1 q - 1 p - 0
|————-|sprzeczność!!
Prawda logiczna | fałsz logiczny
Prawda logiczna - zdanie którego schematem jest tautologia
Fałsz logiczny - zdanie którego schematem jest kontrtautologia
Zbiór zdań semantycznie sprzeczny
Zbiór zdań jest semantycznie sprzeczny witw gdy koniunkcja tych zdań jest fałszem logicznym
Schemat niezawodny
Od prawdziwych przesłanek możemy przejść jedynie do prawdziwych wniosków
Wynikanie logiczne
Aby wykazać że jedna formuła wynika logicznie z drugiej, należy wykazać że odpowiednia formuła jest tautologią
Wnioskowanie dedukcyjne przykład
Czy wniosek wynika logicznie z przesłanek?
{p, p^q ->r, ~q} |= ~r ?
Czy odpowiednia implikacja jest tautologią?
|= [p^(q^p->r)^~q] -~r?
[p ^ (q^p->r) ^ ~q] -> ~r
———————————0
————————1->—-0
p - 1 q - 0 r - 1
Brak sprzeczności - NIE tautologia
Schemat: zawodny
p
q^p->r
~q
———-
~r
Odp. Wnioskowanie nie jest dedukcyjne
Wnioskowanie redukcyjne
Wnioskowanie redukcyjne:
Przesłanka wynika logicznie z wniosku
Indukcja enumeracyjna niezupełna:
Na podstawie kilku przesłanek uznajemy że wszystkie takie obiekty mają daną cechę
Wnioskowanie entymematyczne
Wnioskowanie entymematyczne to wnioskowanie, w którym pominięte zostały pewne przesłanki, uważane za oczywiste lub powszechnie znane
Wnioskowanie
Wnioskowanie:
>Zawodne (indukcja)
- redukcyjne
L indukcja enumeracyjna niezupełna
L inne redukcje - przez analogię
L I typu (n przesłanek ma wspólną cechę, więc n+1 też ją ma)
L II typu (dwa obiekty mają wspólną cechę, więc skoro jeden z nich ma kolejną cechę, to drugi też ją ma) - statystyczne (o całej społeczności na podstawie dużej, losowej próby)
> niezawodne
- indukcja enumeracyjna zupełna (przesłanki to kolejne zdania jednostkowe, zawierające wszystkie możliwości - zatem uznajemy wniosek)
- indukcja eliminacyjna
1 przesłanka jest alternatywą, zaś pozostałe przesłanki obalają wszystkie składniki tej alternatywy poza jednym - wnioskiem - dedukcyjne
Wniosek wynika logicznie z przesłanek
dowód założeniowy wprost
dowód założeniowy wprost wniosku B z założeń A1 A2…An jest ciąg formuł logicznych:
- pierwszymi formułami są jego założenia
- każda następna formuła jest wcześniej udowodnionym twierdzeniem albo formułą otrzymaną z poprzednich formuł
Ostatnią formułą dowodu jest wniosek
dowód założeniowy nie wprost
dowód założeniowy nie wprost wniosku B z założeń A1 A2…An jest ciąg formuł logicznych:
- pierwszymi formułami są jego założenia oraz NEGACJA WNIOSKU
- każda kolejna formuła jest albo wcześniej udowodnionym twierdzeniem albo formułą otrzymaną z poprzednich
Ostatnią formułą dowodu jest formuła sprzeczna z jakąś formułą ją poprzedzającą
Reguła dołączenia koniunkcji
DK
Jeżeli w dowodzie są dwie formuły A i B to można dołączyć ich koniunkcję
A
B
—-
A^B
Reguła opuszczania koniunkcji
OK
Jeżeli w dowodzie jest koniunkcja formuł A^B to możemy dołączyć jej czynniki osobno
A^B. A^B
—— ——-
A B
Reguła dołączenia alternatywy
DA
Jeżeli w dowodzie jest formuła A to możemy dołączyć jej alternatywę z dowolną formułą
A
—-
A v B
Reguła opuszczania alternatywy
OA
Jeżeli w dowodzie jest alternatywa formuł oraz negacja jednego składnika, możemy dołączyć drugi składnik
A v B
~A
———
B
Reguła dołączenia równoważności
DR
Jeżeli w dowodzie są dwie implikacje: prosta i odwrotna, to możemy dołączyć odpowiadającą im równoważność
A->B
B->A
——-
A<->B
Reguła opuszczania równoważności
OR
Jeżeli w dowodzie jest równoważność, to można dołączyć odpowiadającą implikację prostą lub odwrotną
A<->B A<->B
——— ——
A->B B->A
Reguła transpozycji
RT
Jeżeli w dowodzie jest implikacja prosta, to można dołączyć odpowiadającą jej implikację przeciwstawną
A->B
——-
~B->~A
Reguła sylogizmu hipotetycznego (reguła wtórna)
SH
(A->B)^(B->C) (A->B)^(B->C)
A
—————- ———————
A->C C
A->B A->B
B->C B->C
——— A
A -> C –——
C
Reguła de Morgana (reguła wtórna)
dMK (dla koniunkcji)
~(A^B)
————
~A v ~B
dMA (dla alternatywy)
~(A v B)
————
~A ^ ~B
Model formuły
Interpretacja dla której formuła zdaniowa rachunku predykatów jest prawdziwa
Kontrmodel formuły
Interpretacja dla której formuła jest fałszywa
Prawdziwość zdania egzystencjalnego
Podanie przykładu modelu
Fałszywość zdania uniwersalnego
Podanie kontrprzykładu
Tautologia i Kontrtautologia KRP
Tautologia: formuła której nie istnieje kontrmodel
Kontrtautologia: nie istnieje jej model
Rozszerzone pojęcie prawdy dla KRP
Funkcję zdaniową uważamy za prawdziwą, gdy jest spełniona przez każdy obiekt z uniwersum
Prawo dictum de omni
Prawo opuszczania dużego kwantyfikatora
/x\P(x)->P(x)
Prawo dictum de singulo
P(x)->\x/P(x)
Prawo subalternacji
Prawo zastępowania kwantyfikatora ogólnego przez szczegółowy
/x\P(x)->\x/P(x)
Prawo dictum de nullo
Jeśli wszystkie obiekty nie są P, to istnieją obiekty które nie są P
/x\~P(x)->\x/~P(x)
Dowód założeniowy nie wprost KRP
Dowodem zalozeniowym nie wprost nazywamy ciąg formuł:
- pierwsze formuły to założenia oraz negacja wniosku
- kolejne formuły to wcześniej udowodnione twierdzenia
- formuły otrzymane z formuł poprzednich
- ostatnia formuła jest sprzeczna z jakąś formułą poprzedzającą
Dowód zaliczeniowy wprost KRP
Ciąg formuł zaczynający się od założeń, w którym jako kolejne formuły mogą wystąpić:
- wcześniej udowodnione twierdzenia
- formuły otrzymane z poprzednich
Ostatnią formułą jest wniosek
Reguły pierwotne i wtórne systemu założeniowego rachunku zdań
Reguły pierwotne:
- reguła odrywania
- reguła dołączania i opuszczania koniunkcji
- reguła dołączania i opuszczania aleternatywy
- reguła dołączania i opuszczania równoważności
- reguła transpozycji
Reguły wtóre:
- reguła sylogizmu hipotetycznego
- reguły de Morgana
- reguły dołączania i opuszczania podwójnej negacji
- reguła modus tollendo tollens
Reguła opuszczania kwantyfikatora ogólnego
O/\
/u\A
——
A(u/α) <- nie trzeba!
Reguła opuszczania kwantyfikatora szczegółowego
\u/A(u)
————
A(u/a)* pod warunkiem że nazwa a nie występowała jeszcze w żadnym wierszu dowodu
Reguła dołączania kwantyfikatora szczegółowego
D V
A(u/α)
———-
\u/A* pod warunkiem że u nie jest indeksem
Reguła dołączania kwantyfikatora ogólnego
D /\
A
—
/u\A* pod warunkiem że zmienna u nie jest wolna w założeniach ani nie jest indeksem
Reguła odrywania
RO
A->B
A
——-
B
Reguła MTT
(A->B) ^ ~B
—————
~A
