Klasyczny rachunek zadań - Formuły

Nasza ocena:

3
Pobrań: 77
Wyświetleń: 763
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Klasyczny rachunek zadań - Formuły - strona 1 Klasyczny rachunek zadań - Formuły - strona 2 Klasyczny rachunek zadań - Formuły - strona 3

Fragment notatki:

Klasyczny rachunek zdań Def. 1 (słownik). Następujące znaki tworzą słownik języka KRZ:
p 1, p 2, p 3,... (zmienne zdaniowe)
~, /\, \/, →, (spójniki)
), ( (nawiasy)
Def. 2 (Wyrażenie). Wyrażeniem języka KRZ jest każdy skończony ciąg znaków ze słownika języka KRZ.
Wyrażenia poprawnie zbudowane („sensownie”) języka KRZ nazywamy formułami (zdaniowymi).
Def 3. (Formuła)
Każda zmienna zdaniowa jest formułą języka KRZ.
Jeżeli A , B są formułami języka KRZ, to wyrażenia: ~( A ), ( A ) /\ ( B ), ( A ) \/ ( B ), ( A ) → ( B ), ( A ) ( B )
Nie ma żadnych formuł języka KRZ poza zmiennymi zdaniowymi i takimi formułami, które powstają dzięki zastosowaniu reguły 2.
Te trzy definicje nazywane są definicjami indukcyjnymi, lub def. rekurencyjnymi.
Są to definicje operujące na nieskończenie wielu elementów. Podaje się najpierw listę elementów elementarnych, a następnie listę reguł do tworzenia bardziej złożonych wyrażeń.
Notacja. Dla uproszczenia zamiast p 1 będziemy pisać niekiedy po prostu p zamiast p 2 - q , zamiast p3 - r, zamiast p 4 - s. Pojedynczej zmiennej nie bierzemy w nawiasy. Nie dodaje się nawiasu gdy umieszcza się znak negacji przed formułą już poprzedzoną znakiem negacji; tj. zamias ~(~(A)) pisze się ~~(A). Nie dodaje się nowego nawiasu, dodając nowy człon koniunkcji (alternatywy) do formuły będącej koniunkcją (alternatywą); tj. pisze się (A) /\ (B) /\ © zamiast ((A) /\ (B)) /\ (C ) i zamiast (A) /\ ((B) /\ (C)). Spójnik ~ wiąże najsilniej. Spójniki /\ i \/ wiążą silniej niż spójniki → i ; np. zamiast (~(p) /\ q) → (r \/ ~ (s)) wolno pisać: ~p /\ q → r \/ ~s. Przykład. Formułami są: p, ~p, ~~p, p \/ ~q, ~(p → ~q), p /\ q → ~~p. Formułami nie są: p ~ q , p ~ → q , ~ p /\ → q , v pq .
Def. 4 (Podformuła). Dowolną część formuły A, która sama jest formuła nazywamy podformułą formuły A. Do podformuły formuły A zaliczamy też samą formułę A.
Przykład. Podformułami formuły p → ~(q /\ ~r) są:
p, q, r, ~r, q /\ ~r, ~(q /\ ~r), p → ~(q /\ ~r).
Budowę każdej formuły można zilustrować za pomocą grafu będącego drzewem (drzewo synktatyczne):
(p → q) /\ (~p → q) → q → (p → q) /\ (~p → q) q
p → q ~p → q
Formuły języka KRZ są schematy zdań jakiegoś języka etnicznego. Każda formula jest schematem nieskończonej klasy zdań. Aby zbudować schematy zdania:


(…)

… negowania implikacji.
~ (p <-> q) <-> (p /\ ~q) \/ (q /\ ~p) prawo negowania równoważności.
Tautologie dotyczące implikacji:
(p → q) /\ (q → r) → (p → r) prawo sylogizmu hipotetycznego.
(p → q) /\ p → q modus ponendo ponens.
(p → q) /\ ~q → ~p modus tollendo tollens
(p \/ q) /\ ~p → q modus tollendo ponens'
(p → q) ↔ (~q → ~p) prawo transpozycji
(p → q) /\ (p → ~q) → ~p prawo redukcji do absurdu (dylematu…
…, tautologie to schematy zdań wyłącznie prawdziwych, zaś kontrtautologie to schematy zdań wyłącznie fałszywych, np. wewnętrznie sprzecznych (negacje tautologii).
Kontrtautologia:
p /\ ~p
1 0 0
0 0 1
!Znajomość OBOWIĄZKOWA!
Rola tautologii polega na tym, że wykorzystywane one są do określenia niezawodnych reguł wnioskowania. Oto niektóre tautologie.
Tautologie dot. zdań sprzecznych:
p \/ ~ p prawo wyłączonego
... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz