Logika formalna – nauka badająca poprawność rozwiązań



Pobieranie 0,96 Mb.
Strona1/9
Data30.05.2018
Rozmiar0,96 Mb.
  1   2   3   4   5   6   7   8   9



Logika formalna – nauka badająca poprawność rozwiązań.

Logika matematyczna – wynik zastosowania języka matematyki i jej metod do logiki formalnej (zajmuje się m.in. pewnymi ogólnymi własnościami teorii matematycznej).

Metoda dedukcyjna – wyprowadzenie jednych twierdzeń z innych, wcześniej udowodnionych bądź z aksjomatów.

Rachunek zdań – fragment logiki formalnej.
W rozumowaniach matematycznych spotykane zdania zbudowane są z prostych zdań twierdzących bądź ich zaprzeczeń za pomocą tzw. spójników zdaniowych. Rachunek zdań zajmuje się budową zdań złożonych tzn. takich, w których występuje przynajmniej jeden spójnik zdaniowy, nie odwołując się do treści zdań prostych, z których te zdania złożone są zbudowane. Zakładamy, że każde z tych zdań prostych jest prawdziwe lub fałszywe.
Zdania proste oznaczamy literami p, q, r... są to symbole tzw. zmiennych zdaniowych)

Wartość logiczna., w(p) = 1, gdy p prawdziwe

w(p) = 0, gdy p fałszywe

w(p) – wartość zdania p


Spójniki zdaniowe


~ (negativ) – negacja – spójnik jednoargumentowy


p

~p

0

1

1

0

pq – koniunkcja (oba prawdziwe)

pq - alternatywa (co najmniej jedno)

pq – implikacja (0 gdy poprzednik 1 a następnik 0)

pq – równoważnia (te same znaki)



p


q

pq

pq

pq

pq

0

0

0

0

1

1

1

0

0

1

0

0

0

1

0

1

1

0

1

1

1

1

1

1

Uwaga !

Zdanie pq czyta się czasem jako „p” jest warunkiem wystarczającym by „q” lub „q” jest warunkiem koniecznym by „p”.

Zdanie pq czytamy „p” jest warunkiem koniecznym i wystarczającym by „q”.

Rola nawiasów


Umowa:

~ (negacja) wiąże silniej niż  i , te zaś silniej niż  i .

Przykład:

~ pq to (~p)q a nie ~(pq)



Skróty


pqr skrót wyrażenia (pq)(qr)

pqr skrót wyrażenia (pq)(qr)
Uwaga !

Wyrażenie rachunku zdań jest poprawnie zbudowane, jeśli jest jedną z liter p, q, r,... lub jest postaci ~ , , , , gdzie ,  są poprawnie zbudowane.


Przykład:

  1. (pq)((pr) ~(~p)) – to jest poprawnie zbudowane wyrażenie

  2. (pq) p – nie jest poprawnie zbudowane, bo w drugim członie brakuje drugiego argumentu.



Funkcja zdaniowa


xø

Definicja:
Wyrażenie (x), w którym występuje zmienna x i które staje się zdaniem (prawdziwym lub fałszywym) po podstawieniu za zmienną x nazwy dowolnego elementu z X nazywamy funkcją zdaniową zmiennej x o zakresie zmienności X.

X – przestrzeń funkcji zdaniowej (ozn. (x), xX)


Definicja:

Element aX spełnia funkcję zdaniową (x), xx, gdy zdanie (a) jest prawdziwe.

{xX, (x)} – zbiór wszystkich elementów przestrzeni X spełniających funkcję zdaniową (x).
Uwaga !

Jeśli (x), xX i (x), xX są funkcjami zdaniowymi, to

~(x), xX

(x)(x), xX

(x)(x), xX

(x)(x),xX

(x)(x), xX

są funkcjami zdaniowymi.

Analogicznie określa się funkcje zdaniowe „n” zmiennej.

(x1,...,xn), x1X1,..., xnXn jest funkcją zdaniową n zmiennych, gdy podstawiając za x1,..., xn odpowiednie elementy X1,....,Xn otrzymujemy zdanie prawdziwe lub fałszywe.

(x;y), xX, yY

TAUTOLOGIE

Tautologie ( prawa rachunku zdań).

Za pomocą spójników zdaniowych, zmiennych zdaniowych oraz nawiasów można budować różne schematy zdań złożonych. Niektóre z tych schematów mają tę własność, że każde ze zdań podpadające pod taki schemat jest prawdziwe niezależnie od prawdziwości zdań użytych do jego budowy. Schematy takie nazywamy tautologiami lub prawami rachunku zdań.

Podstawowe tautologie rachunku zdań





  1. pp – prawo tożsamości dla implikacji

  2. pp – p. tożsamości dla równoważności

  3. p~p – p. wyłączonego środka

  4. ~(p~p) – p. wyłączonej sprzeczności

  5. (pq)(qp)- p. przemienności koniunkcji (pq)(qp) – p. przemienności alternatywy

  6. (p(qr))((pq)r)) – p. łączności koniunkcji (p(qr))((pq)r) – p. łączności alternatywy

  7. p. rozdzielności

    • (p(qr))((pq)(pr))

    • (p(qr))((pq)(pr))

  8. p. idempotentności

    • (pp)p

    • (pp)p

  9. ~(~p)p – p. podwójnej negacji

  10. p. de Morgana w rachunku zdań

    • ~(pq)(~p~q)

    • ~(pq)(~p~q)

  11. (pq)(~q~p) – p. kontrapozycji

  12. (pq)(qp) – p. przemienności równoważności

  13. ((pq)(qr))(pr) – p. przechodności implikacji

  14. p. pochłaniania

    • p(pq)p

    • p(pq)p

15.(pq)((pq)(qp))

16.(pq)(~pq)

17. ~(pq)(p~q) – p. zaprzeczenia implikacji

18. ~(pq)((p~q)(q~p)) - p. zaprzeczenia równoważności

19(~pp)p – p. Claviusa

20. ~p(pq) – p. Dunsa Scotusa




Skrócona metoda sprawdzenia czy dane wyrażenie jest tautologią.
Przykład:
((pq)(qr))(pr)
Załóżmy, że dla pewnych p,q,r wartość logiczna

((pq)(qr))(pr)=0

wtedy w((pq)(qr))=1 i w(pr)=0 stąd w(pq)=w(qr)=1 i w(p)=1, w(r)=0

Ponieważ


W(pq)=1 i w(p)=1 to w(q)=1

Także


w(qr)=1 i w(r)=0 to w(q)=0

sprzeczność

Założenie, że wartość nie jest tautologią prowadzi do sprzeczności, stąd dane wyrażenie jest tautologią.


Twierdzenie

Niech (p1,…,pn) będzie schematem zbudowanym ze zmiennych zdań p1,…,pn, spójników zdaniowych i ewentualnie nawiasów.

Jeśli schemat (p1,…,pn) jest prawem rachunku zdań, to podstawiając w schemacie (p1,…,pn) za p1,…,pn odpowiednio schematy 1,…,n otrzymamy schemat, który jest prawem rachunku zdań (1,…,n – nie muszą być tautologiami).
Dowód:

Niech * będzie schematem otrzymanym z (p1,…,pn) przez podstawienie schematów 1,…,n odpowiednio za p1,…,pn zaś q1,…,qm będą wszystkimi zmiennymi zdaniowymi występującymi w 1,…,n. Dowolny układ wartości logicznych w(q1),…,w(qm) przyporządkowanych zmiennych zdaniowych q1,…,qm. Wyznaczam w(1),…,w(m) a więc także w(*). Niech w(p1)=w(1),…,w(pn)=w(n) wtedy w()=w(*).

Ale (p1,…,pn) jest tautologią więc w()=1 stąd w(*)=1 przy dowolnym podstawieniu wartości logicznych za zmienne zdaniowe q1,…,qm a więc * jest prawem rachunkowym.
Twierdzenie
Jeśli  i  są tautologiami to  jest tautologią.

( -czytamy - schemat „fi”)


Dowód

Przy dowolnym podstawieniu wartości logicznych za zmienne zdaniowe występujące w  jest spełniony warunek


w()=1 i w()=1

a więc na mocy własności implikacji musi być wartość logiczna w()=1.


Konsekwencje. Reguły dowodzenia.
Definicja:

Niech 1,…,n,  będą schematami zdaniowymi ze zmiennych zdaniowych, spójników zdaniowych i nawiasów. Schemat  jest konsekwencją (sementyczną) schematów 1,…,n (zbiorem schematów {1,…,n}) jeśli przy każdym układzie wartości logicznych przyporządkowanych zmiennym zdaniowym występującym w schematach 1,…,n,  przy których schematy 1,…,n przedstawiają zdanie prawdziwe także  przedstawia zdanie prawdziwe.

(ozn. – {1,…,}╞ })
Przykład:

{,} ╞   


(czyt. -    jest konsekwencją zbioru schematów {;}).

Uwaga!

Jeśli 1,…,n są tautologiami i {1,…n}╞  to  jest tautologią.




Twierdzenie:

Każda tautologia jest konsekwencją pustego zbioru schematów. (Jeśli  jest tautologią to ø ╞  - także odwrotnie).


Dowód:

Każda tautologia przedstawia zdanie prawdziwe dla dowolnego podstawienia wartości logicznych za zmienne zdaniowe w ø  {} = {}




Uwaga!

Zamiast ø╞  piszemy ╞ .

(zapis ten oznacza, że  jest tautologią); (ø╞ - czyt. -  jest konsekwencją ø zbioru schematów).


Twierdzenie:

Dla dowolnych schematów ,

{}╞  ↔ ╞    (↔ - symbol z meta języka).
Dowód:

Niech {} ╞ 

Podstawmy w dowolny sposób wartości logiczne za zmienne zdaniowe w  i . Jeśli przy tym podstawieniu w()=0 to w(  )=1. Jeśli zaś przy tym podstawieniu

w()=1, to wtedy w()=1 (bo {} ╞ ). Stąd także wtedy w(  )=1. przy dowolnym podstawieniu jest więc w(  )=1. Stąd ╞   .

Odwrotnie, jeśli ╞    i w()=1 przy pewnym podstawieniu to musi być w()=1 przy tym podstawieniu bo inaczej implikacja    byłaby przy tym podstawieniu fałszywa.

Stąd {} ╞  (czyt. – schemat  jest konsekwencją schematu ).


Twierdzenie:

{1,…,n} ╞  ↔ {1 … n} ╞ 


Dowód:

Wynika z tego, że w(1 … n)=1 ↔ w(1)=…=w(n)=1

(1…n)↔(…(12)3…n)
Definicja:

Zbiór {1,…,n} schematów nazywamy niesprzecznym, jeśli istnieje przynajmniej jedno podstawienie logiczne za zmienne zdaniowe w 1,…,n przy którym w(1)=…=w(n)=1 (tzn. w(1…n)=1).

W przeciwnym przypadku {1,…,n} jest sprzeczny.
Uwaga!

Jeśli {1,…,n} jest sprzeczny to przy dowolnym podstawieniu wartości logicznych za zmienne zdaniowe w 1,…,n implikuje 1…n 0 gdzie 0 oznacza zdanie fałszywe.

Stąd {1,…,n} ╞ 0. Zatem jeśli {1,…,n} jest sprzeczne to sprzeczność 0 jest konsekwencją zbioru {1,…,n} (także odwrotnie).
Twierdzenie:

{1,…,n} ╞  ↔ zbioru schematów {1,…,n,~} jest sprzeczny.


Dowód:

Niech {1,…,n} ╞ . Podstawmy w dowolny sposób wartości logiczne za zmienne zdaniowe w 1,…,n,. Jeśli przy tym podstawieniu w(1)=…=w(n)=1 to także w()=1, bo {1,…,n} ╞ . Wtedy w(~)=0, a więc w(1 … n  ~)=0. Jeśli przy tym podstawieniu nie wszystkie schematy 1,…,n przedstawiają zdanie prawdziwe, to w(1 …n)=0 a więc w(1 … n  ~)=0. Zatem zbiór schematów {1,…,n,~} jest sprzeczny.

Załóżmy, że {1,…,n,~} jest sprzeczny i w(1)=…=w(n)=1 przy pewnym podstawieniu wartości logicznych w 1,…,n i . Wtedy musi być w(~)=0 bo inaczej byłaby w(1 … n  ~)=1 czyli {1,…,n,~} byłby niesprzeczny. Stąd w()=1 a więc {1,…,n}╞ .


Reguły dowodzenia.

Definicja:

Regułą dowodzenia nazywamy operację, które skończonym ciągom schematów przyporządkowuje schemat , tak że

{1,…,n} ╞ 

1,…,n – przesłanki

 - wniosek




- reguła dowodzenia




  1   2   3   4   5   6   7   8   9


©operacji.org 2017
wyślij wiadomość

    Strona główna