Skrócona metoda 0-1. można przedstawić w postaci następującego algorytmu:
Załóż, ze badana formuła nie jest tautologią (tj. istnieje przyporządkowanie wartości logicznych zmiennych zdaniowym, przy którym przyjmuje ona wartość 0).
Wnioskując „wstecz” ustal, jakie wartości logiczne musiałyby przybrać zmienne zdaniowe, aby otrzymać wartość 0.
Wyciągnij wnioski: a. Jeśli można znaleźć przynajmniej jedną kombinację takich wartości logicznych dla zmiennych zdaniowych, to badana formuła nie jest tautologią . b. Jeśli natomiast nie można znaleźć kombinacji takich wartości logicznych dla zmiennych zdaniowych (tj. każda próba prowadzi do sprzeczności), to badany schemat jest tautologią .
Przykład. 1. (p → q) /\ ~p → ~q
1 1 1 0 0 01
0 → 1
1
formuła nie jest tautologią.
2. (p → q) /\ ~q → ~p
1 1 11 0 01
1 → 0
0
formuła jest tautologią.
3. (p → q) /\ (q → r) → (~r → ~(p \/ q))
0 1 0 1 0 1 0 0 10 0 1 1
0 \/ 0 1 formuła jest tautologią.
4. a. ((p \/ q) /\ ~r) ↔ ((r → p) \/ (r → q))
1 0 1 0 0 0 1 0 0
(0 \/ 0) /\ 0
0 b. ((p \/ q) /\ ~r) ↔ ((r → p) \/ (r → q))
1 1 1 0 01 0 1 1 1 1 1 1 1
formuła nie jest tautologią.
Zdefiniujmy obecnie relację wynikania logicznego (konsekwencji semantycznej). Będzie to tzw. implikacyjna koncepcja wynikania. Odwołamy się bowiem do pojęć implikacji i tautologii.
Def. 6. (Wynikanie logiczne). Z formuł A1, …, An wynika logicznie formuła B (na gruncie KRZ), wtw implikacja A1 /\ … /\ An → B
jest tautologią KRZ.
Symbolicznie: {A1, …, An} |= B wtw (A1 /\ … /\ An → B) Trz
Przypomnijmy, formuły języka KRZ są schematami zdań. Pojęcie wynikania logicznego możemy odnieść więc również do zdań.
Powiemy, że ze zdań o schematach A1,..., An wynika logicznie (na gruncie KRZ) zdanie o schemacie B wtw implikacja
A1 /\ … /\ An → B
jest tautologią.
(…)
… logiczny:
p /\ q wykluczanie ~p /\ ~q
Przypomnijmy: Logika = teoria form (schematów, reguł) poprawnych wnioskowań.
Wnioskowaniem nazywamy jakąkolwiek skończoną - co najmniej dwuwyrazową - sekwencję zdań, z których ostatnie jest wnioskiem, a wcześniejsze są przesłankami. Wnioskowanie nazywamy formalnie poprawnym lub dedukcyjnym wtw jego schematem jest niezawodna reguła wnioskowania, czyli taka która od przesłanek prawdziwych prowadzi zwsze do prawdziwego wniosku. Ogólnie mówiąc, przez regułę wnioskowania rozumie się instrukcję stwierdzającą, z jakiego rodzaju zdań jako przesłanek, jakie zdanie można otrzymać jako wniosek. Przy tym instrukcja ta podaje na ogół tylko strukturę owych zda, nie wnikając w ich treść.
Reguły wnioskowania zwykle notuje się w postaci ułąmkowej.
A, …, An
--------- B
gdzie A1, …, An…
…,..., An uzyskują wartość 1, to formuła B też uzyskuje wartość 1.
Dowód. Załóżmy, że reguła
A1,...,An
----------
B
jest niezawodna, a formuły A1,...,An uzyskuje 1, zaś dla dowodu nie wprost załóżmy, że formuła B uzyskuje wartość 0. Wtedy implikacja
A1 /\ … /\ An → B
uzyskuje wartość 0 (bo poprzednik uzyskuje wart. 1, a następnik wart. 0), czyli nie jest tautologią KRZ. W takim razie - z uwagi na def. 8…
... zobacz całą notatkę
Komentarze użytkowników (0)