Strona główna

Logika klasyczny rachunek zdań


Pobieranie 379.49 Kb.
Strona1/6
Data17.06.2016
Rozmiar379.49 Kb.
  1   2   3   4   5   6





LOGIKA


KLASYCZNY RACHUNEK ZDAŃ
Podstawowymi elementami języka rachunku zdań są:

zmienne zdaniowe : p, q, r...

operatory logiczne (funktory prawdziwościowe):

- negacja

 - koniunkcja

 - alternatywa (zwykła)

 - implikacja

 - równoważność

nawiasy ( ), [ ], { },...
Ad.1 zmienne reprezentują zdania w sensie logicznym, tzn. zdania, którym przysługują wartości logiczne: prawdy i fałszu. Prawdziwość zdania oznaczamy przez T lub 1, zaś fałszywe przez F lub 0. Omawiany rachunek zdań nazywamy klasycznym, gdyż zakłada się, że, zdanie przyjmuje jedynie jedną z dwu wymienionych wartości logicznych. Powstały inne rachunki zdań, w których nie przyjmuje się tego założenia. Nazywamy je ogólnie wielowartościowymi rachunkami zdań.
Ad. 2 .Za pomocą operatorów logicznych budujemy zdania złożone ze zdań prostych. Wartość logiczna takich zdań złożonych zależy jedynie od wartości logicznych zdań składowych.. Stąd też dla danych zdań : p i q wartości logiczne zdań złożonych: p, p  q, p  q, p  q, p  q będą całkowicie wyznaczone za pomocą wartości. Mamy więc:



p

p

1

0


0

1


Czyt. „nieprawda, że”




p q

p  q




p q

p  q




p q


p  q




p q


p  q



  1. 1

  1. 0

  1. 1

0 0

1

0

0



0

  1. 1

  1. 0

  1. 1

0 0

1

1

1



0

  1. 1

1 0

  1. 1

0 0

1

0

1



1

1 1

1 0 0 1


0 0

1

0

0



1

czyt. „i” czyt. „lub” czyt. „jeżeli, to” czyt. „wtw”

Ad. 3. Nawiasy, jako znaki pomocnicze, zmieniają naturalną kolejność operacji logicznych, tzn. najmocniejsza jest negacja, później koniunkcja, alternatywa, implikacja i równoważność. Przykładowo: p  q  p oraz ( p  q )  p
Def. Matrycą logiczną zdania złożonego, zbudowanego ze zdań prostych p, q, r ..., nazywamy tablica podającą wartości logiczne tego zdania tego zdania złożonego, w zależności od wartości logicznych zdań prostych.
Wn. Wartość logiczną zdania złożonego możemy obliczyć, wyznaczając po kolei wartości logiczne zdań prostszych.
Ex. 1

Zapisz poniższe zdanie za pomocą symboliki logicznej, używając zmiennych zdaniowych: p, q, r, ... oraz operatorów logicznych: , , , ,  i podaj jego matrycę.„ Jeśli pada deszcz, to nie świeci słońce i na niebie są chmury”. Niech

p =” pada deszcz”;

q = „ świeci słońce”;

r = „na niebie są chmury”

Tak więc mamy zdanie: p  q  r

Budujemy matrycę tego zdania:

p q r

q

 q  r

p  q  r

1 1 1

1 1 0


1 0 1 1 0 0

0 1 1 0 1 0

0 0 1 0 0 0


0

0

1



1

0

0



1

1


0

0

1



0

0

0



1

0


0

0

1



0

1

1



1

1

Kolumna 4 zawiera wartości logiczne dla całego zdania złożonego. Zdanie złożone jest prawdziwe bądź to gdy nie pada deszcz, bądź to gdy pada deszcz lecz świeci słońce i na niebie są chmury. W pozostałych przypadkach jest fałszywe.
Def 2. Zdania złożone, które są zawsze prawdziwe, niezależnie od wartości logicznych zmiennych zdaniowych w nich występujących nazywamy tautologiami (prawami logiki); te zaś, które są zawsze fałszywe nazywamy kontrtautologiami lub też wewnętrznie sprzecznymi.

Ex. 2.

Zdanie „pp” jest tautologią, gdyż matryca przyjmuje zawsze wartość logiczną 1, zaś zdanie:

„p p” zaś jest kontrtautologią, gdyż matryca przyjmuje zawsze wartość 0.


P

p  p




p

p

p p

1

0


1

1


1

0


0

1


0

0



Ex. 3.

Zbuduj matryce logiczną dla zdania złożonego P o postaci (p  q) [ (p q)  (p  q)] i wskaż

czy jest ono tautologią, czy kontrtautologią.


p q

q

p  q

P q

p  q

(p q)  (p  q)

P




1 1

1 0


0 1

0 0


0

1

0



1

1

0

1



1

1

1

0



1

1

0

0



0

1

0

1



0

1

1

1



0

Ponieważ w ostatniej kolumnie w ostatnim wierszu pojawiło się 0 zatem zdanie P nie jest tautologią. Nie jest tez ono kontrtautologia, gdyż nie wystąpiły w ostatniej kolumnie same zera.


Tautologie do których często odwołujemy się w procesach dowodzenia , posiadają zwykle specjalne nazwy, nawiązujące do ich strukturalnych własności. Do tych najbardziej znanych zaliczają się

[(p  q) p] q modus ponendo ponens

[(p  q) q ] p modus tollendo tollens

 (p  q) p q prawa de Morgana

 (p  q ) p  q

p (p  q) prawo Dunsa Szkota

(p p) p prawo redukcji do absurdu

[(p  q ) r] [p  (q  r)] prawo eksportacji

[p  (q  r)] [(p  q ) r] prawo importacji

[(p  q)  (q  r)]  (p  r) prawo sylogizmu warunkowego


IDEA DEDUKCJI
Termin dedukcja wiążę się na ogół z wyprowadzaniem jednych zdań z drugich. Dedukcja daje się sprowadzić do wyprowadzania jednych zdań z drugich, za pomocą małych kroków tzw. Reguł wyprowadzania, co do których każdy jest w stanie się zgodzić, że są poprawne. Pozostaje tylko zgodzić się, co do tego, które reguły są poprawne na mocy samej oczywistości. Omówimy dwa ujęcia systemu klasycznego rachunku zdań, w których to ujęciach będziemy mieli do czynienia z procesem dedukcji. Ujęcia te pozwalają o każdym zdaniu klasycznego rachunku zdań rozstrzygnąć, czy jest ono tautologią, czy też nie. W jednym z tych ujęć zwanym założeniowym systemem rachunku zdań będziemy mieli do czynienia z tzw. założeniowymi dowodami wprost i nie wprost, w drugim zaś będziemy mieli do czynienia ze zwykłymi dowodami wprost i nie wprost. Obydwa ujęcia dają wyobrażenia o tym, co to znaczy dowód (w sensie matematycznym) oraz na czym polega proces dowodzenia.
A. Założeniowy system klasycznego rachunku zdań.
Dowód założeniowy jest najbliższy temu co nazywamy dedukcją w potocznym tego słowa znaczeniu, niekiedy zwaną dedukcja naturalną. Żadne ze zdań nie jest w tym ujęciu wyróżnione, a w procesie dedukcji główną rolę odgrywają reguły. Zakres stosowania tej metody jest jednak dość ograniczony, gdyż odnosi się jedynie do tych systemów, czy teorii, dla których obowiązuje tzw. twierdzenie o dedukcji. W dowodach założeniowych mamy do czynienia z dwoma typami reguł, z tak zwn. (1) Regułą tworzenia założeniowych dowodów wprost i nie wprost (RDZ) oraz z (2) Regułami pierwotnymi ( przyjętymi na mocy oczywistości) oraz wtórnymi ( przyjętymi poprzez udowodnienie) dołączania nowych wierszy do dowodu (RDNW).
RDZ : jeśli istnieje założeniowy dowód wprost zdania

P* =„ P1  (P2  ( P3 ... ( Pn-1  Pn )...))”

dla n  1 to zdanie to jest tezą tego rachunku( tautologia klasycznego rachunku zdań )


(2) RDNW:
P  Q P

(a) RO(reguła odrywania): P (b) DK (reguła dołączania koniunkcji) : Q

Q P  Q


P  Q P  Q

OK. (reguła opuszczania koniunkcji): P Q


P Q

DA (reguła dołącznia alternatywy: P Q P  Q

P  Q P  Q

OA (reguła opuszczania alternatywy): P Q



Q P
P  Q

DE ( dołączania równoważności): Q  P



P  Q

P  Q P  Q

(g) OE (opuszczania równoważności): P  Q Q  P


Założeniowy dowód wprost zdania P* tworzymy w następujący sposób:

Założeniowy dowód wprost zdania P* tworzymy w następujący sposób:


  1. W n-1 początkowych wierszach dowodu wypisujemy kolejno zdania, P1, ..., Pn-1 jako założenia dowodu.

  2. Do dowodu można dołączyć jako nowe wiersze:

  1. tezy wcześniej udowodnione;

  2. wyrażenia uzyskane na podstawie dotychczasowych wierszy według RDNW .

3. Dowód jest zakończony jeśli w ostatnim wierszu występuje wyrażenie Pn

Ex.4 P1 P2 P3 Pn

Zbuduj dowód założeniowy zdania P*=”(p  q)  [(q  r)  (p  r )]


1. p  q

2. q  r zał. dow.

3. p


4. q RO 1 i 2

5. r RO 2 i 4



Ex. 5 P1 P2 P3 Pn

Zbuduj dowód założeniowy zdania P*=”[p q  r]  [p  (q  r)]”


1. p q  r

2. p zał. dow.

3. q

4. p q DK 2 i 3



5. r RO 1 i 4

Założeniowe dowody nie wprost tworzymy podobnie jak założeniowe dowody wprost, z tym ,że dodatkowo w n- tym wierszu dowodu wpisujemy zdanie sprzeczne ze zdaniem Pn, tzn. gdy zdanie Pn nie posiada negacji lub posiada parzysta ich liczbę wpisujemy . Dowód jest zakończony po otrzymaniu w nim dwóch wierszy sprzecznych.



Ex. 6

P1 Pn


Zbuduj dowód założeniowy nie wprost zdania P*=”[(p  q)  q ]  p”


1. ( p  q)   q zał. dow.

2. p zał. dow. nwp.

3. p  q

 q OK. 1

5. q RO 3 i 2

sprzeczność wierszy 4 i 5


P1 Pn

Ex.7.

Zbuduj dowód założeniowy nie wprost zdania P*=”[(p  r)  (q  r)  (p  q )]  r”


1. (p  r)  (q)  (p q ) zał. dow.

2. r zał. dow. nwp.

3. p  r

4. q  r OK. 1

5. p q

q MTT. (reguła wtórna z modus tollendo tolens)



9. p OA 5 i 8

10. r RO 3 i 9

sprzeczność wierszy 2 i 10

Zadanie:

Zbuduj dowód założeniowy nie wprost zdania P*=”[(p  q )  r]  [(p r)   q ] „

Uwaga! Udowodnić najpierw implikacje w obydwie strony, a później zwykły dowód wprost.

AKSJOMATYCZNE UJĘCIE RACHUNKU ZDAŃ
Aksjomatyzacja logiki zdań nie jest zabiegiem koniecznym dla rozstrzygnięcia czy zdanie tego rachunku jest tautologią czy też nie. Do tego celu wystarczają metoda matrycowa albo założeniowa. Powstało jednak wiele aksjomatyzacji rachunku zdań, gdyż okazały się one dogodnym obiektem badań, posiadającym specyficzne własności, a ponadto takie ujęcie logiki zdań daje pewne korzyści dydaktyczne. Do elementów systemu aksjomatycznego zdań należą:

Aksjomaty, czyli zdania będące tautologiami tego rachunku.

Reguły pierwotne, które pozwalają przejść od jednych tautologii do innych.

Definicje, które pozwalają zastąpić terminy wtórne, a więc nie występujące w aksjomatach terminami pierwotnymi, występującymi w aksjomatach.

Istnieje wiele aksjomatyzacji rachunku zdań różniących się ilością aksjomatów jak i ich doborem. Jednym z najbardziej znanych aksjomatyzacji systemu klasycznego rachunku zdań jest system ( implikacyjno-negacyjny) polskiego logika J. Łukasiewicza.
SYSTEM AKSJOMATYCZNY ŁUKASIEWICZA

Aksjomaty

A1. (p  q)  [(q  r)  (p  r)]

A2. (p  p)  p

A3. p  (p  q)
Reguły pierwotne:

RP (reguła podstawiania): Jeżeli zdanie P jest tautologią, zawierającą zmienną zdaniową v, to po podstawieniu zdania E za każde wystąpienie zmiennej v w P otrzymujemy zdanie P*, które także jest tautologią.

RO: Jeżeli zdanie złożone P* =”P Q” jest tautologią i P jest tautologią, to Q jest też tautologią
Definicje:

D1. P Q = P  Q

D2. P Q =  (P Q)

D3. PQ = (P Q)  (Q P)


Tak sformułowane definicje są regułami zastępowania (RZ) w tezach systemu zdań zawierających terminy pierwotne, przez zdania zawierające terminy zdefiniowane i odwrotnie.

Dowód prowadzimy podobnie jak dowód założeniowy, z tym, że punktem wyjścia dowodu zamiast założeń przyjmujemy aksjomaty a zamiast reguł dołączania nowych wierszy do dowodu stosujemy reguły pierwotne (RP i RO) oraz (RZ)


Ex.8 Niech P = „p p”. Zbuduj dowód zdania P na gruncie aksjomatyki Łukasiewicza dla klasycznego rachunku zdań.
1. (p  q)  [(q  r)  (p  r)] A1.

2 .[p  (p  p)]  [((p  p)  r)  (p  r)] RP 1 (q/p  p)

[p  (p  p)]  [((p  p)  p)  (p  p)] RP 2 (r/p)

p  (p  q) A3

p  (p  p) RP 4 (q/p)

((p  p)  p)  (p  p) RO 3 i 5

(p  p)  p A2

p  p RO 6 i 7


EX. 9 Niech P = „p  p”. Zbuduj dowód zdania P na gruncie aksjomatyki Łukasiewicza dla klasycznego rachunku zdań.
1. p  p Teza udow.

2. p  p  p  p RP 1 (p/ p  p)

3. (p  p)  p  p RZ D1 i 2

4. p  p Teza udow.

5. p  p RP 4 (p/p)

6. p  p RO 3 i 5


Metoda założeniowa a aksjomatyzacja klasycznego rachunku zdań.

a) Zarówno metoda założeniowa jak i aksjomatyczna daje wyobrażenie o tym, czym jest dowód w

sensie matematycznym

b) każde zdanie dowodu w dowodzie aksjomatycznym jest tezą systemu, tymczasem w dowodzie założeniowym nie są tezami systemu;

c) w systemie aksjomatycznym siła inferencyjna zawarta jest w aksjomatach, w systemie założeniowym w regułach;

d) metoda aksjomatyczna ma charakter bardziej uniwersalny, metoda założeniowa ma zastosowanie na gruncie tych systemów, dla których obowiązuje twierdzenie o dedukcji.

e) metoda aksjomatyczna jest na ogół trudniejsza niż założeniowa- nie wiadomo z góry jakie powinny być początkowe wiersze dowodu;

  1   2   3   4   5   6


©snauka.pl 2016
wyślij wiadomość