Klasyczny rachunek zdań



Pobieranie 1,67 Mb.
Strona2/16
Data25.03.2018
Rozmiar1,67 Mb.
1   2   3   4   5   6   7   8   9   ...   16

DEFINICJA DOWODU


Dowodem D zdania B w oparciu o zbiór zdań X przyjętych jako założenia nazywamy ciąg zdań, takich, że D={D1, D2, ..., Dn }spełniających następujące warunki:

a) B= Dn (ostatnie zdanie tego ciągu jest identyczne z B);

b) każde zdanie Dk ciągu D, gdzie (1  k  n ) albo należy do X albo jest tautologią, albo jest wyprowadzone z wcześniejszych zdań ciągu za pomocą reguł wnioskowania.
NOTACJA BEZNAWIASOWA ŁUKASIEWICZA
Beznawiasowa notacja Łukasiewicza zwana też notacja polską, polega na tym, że każdy funktor prawdziwościowy zarówno jednoargumentowy jak i dwuargumentowy poprzedza swe argumenty, zamiast, jak w przypadku dwuargumentowych, znajdować się między nimi. Argumenty zaś wypisuje się od lewa do prawa. Strukturalne własności zdania złożonego są zachowane bez używania nawiasów. Przy tym dla oznaczenia operatorów logicznych stosuje się duże litery alfabetu. I tak, dla oznaczenia negacji( N), dla koniunkcji (K), dla alternatywy (A), dla implikacji (C), dla równoważności (E).
Ex10 . (a) Niech zdanie P=”(p p). Przedstaw go w notacji beznawiasowej.

Ustalamy najpierw kolejność symboli w zdaniu P, zaczynając od funktorów

1 3 2 4 5

P=” ( p   p), a zatem wypisując te elementy zdania w zaznaczonej kolejności otrzymujemy zdanie P’=”NKpNp” identyczne z P.

4 3 5 2 6 7 1 8 9

P=”[( p  q)   q]   p, a zatem otrzymujemy postępując jak wyżej zdanie P’

P’=”CKCpqNqNp” identyczne z P.
Ex11.

a) Przedstaw zdanie złożone P podane w symbolice beznawiasowej w postaci strukturalnej, gdzie P=”CKApqrKCprCqr”.

1 a1 a2

4 d1 d2 5 e1 e2 6 f1 f2


P=”C K A p q r K C p r C q r

2 b1 b2 3 c1 c2
Zdanie P’= [(pq)  r ] [(p  r)  (q  r)]
(b) Niech zdanie P=”CKKCprCqrApqr”
1 a1 a2

3 c1 c2 4 d1 d2


P=” C K K C p r C q r A p q r

2 b1 b2

Zdanie P’= [(p  r)  (q  r)  (p  q)] r



Notacja polska ma duże zastosowanie przy translacji wyrażeń arytmetycznych na język wewnętrzny maszyny, przy równoczesnym wykorzystaniu stosowej organizacji pamięci komputera.
Zadanie: Przedstaw aksjomaty Łukasiewicza dla klasycznego rachunku zdań w postaci notacji polskiej.

LOGIKA WIELOWARTOŚCIOWA


U podstaw klasycznego rachunku zdań legło założenie o dwuwartościowości wszystkich zdań w sensie logicznym. Uwolnienie się od tego założenia prowadzi do rachunków zdań wielowartościowych. I tak np. J. Łukasiewicz wprowadzając trzecią wartość logiczną zbudował trójwartościowy rachunek zdań Ł3. Podobnie jak on a niezależnie od niego postą pił E. Post. Jeśli przyjąć, że n oznacza ilość dopuszczalnych wartości logicznych, w systemie wielowartościowym, to system taki ma następujące wartości:

Dla n = 3 mamy następujące wartości logiczne: 0, ˝, 1

Dla n = 4 mamy zaś: 0, 1/3, 2/3,1

Główna inspiracją zbudowania przez Łukasiewicza logiki trójwartościowej były rozważania dotyczące determinizmu. Zdania, które dotyczyły przyszłości mogły przyjmować jedną z trzech wartości logicznych. I tak:

0 - przyjmują te zdania, dla których istnieje obecnie przyczyna wykluczająca ich zajście;

1- przyjmują te zdania, dla których istnieje obecnie przyczyna powodująca ich zajście

1/2 -przyjmują te zdania, dla których nie istnieje obecnie przyczyna powodująca ich zajście, ani też przyczyna wykluczająca ich zajście.
Ex.12 Weźmy przykład zdań dotyczących przyszłości i oceńmy je pod względem wartości logicznych. Niech

p = ”Ziemia będzie kulista”;

q = ” Ziemia będzie nieruchoma”

r = „Ludzie w 2100 r. pobudują osiedla na Marsie”

a) zdanie „p” jest prawdziwe, gdyż istnieje obecnie przyczyna powodująca zajście zdarzenia, że Ziemia jest kulista

b) zdanie „q” jest fałszywe, gdyż istnieje obecnie przyczyna wykluczająca zajście zdarzenia że Ziemia jest nieruchoma”

c) r jest niezdeterminowane, czyli posiada wartość 1/2, gdyż nie istnieje obecnie przyczyna powodująca zajście zdarzenia budowania osiedli przez ludzi na Marsie, ani też przyczyna wykluczająca zajście takiego zdarzenia.
Podstawową sprawą pozostaje zbudowanie matryc dla zdań złożonych w Ł3. Oczywiście tabelki charakteryzujące klasyczne operatory są tutaj niewystarczające. Jednakże Łukasiewicz podając takie charakterystyki zachował dotychczasowe „zdrowe” intuicje logiczne jakie tkwiły w L, chodzi tu głównie o implikację, która o ile poprzednik posiada wartość logiczna mniejszą lub równą następnikowi o tyle całe przyjmuje wartość 1.

Oto główne warunki dla matryc Ł3

Np.=1-p

Apq = max{p, q}

Kpq = min{p, q}

jeśli pq, to Cpq=1

jeśli p>q, to Cpq=1-p+q
Na tej podstawie możemy zbudować matryce dla zdań złożonych w Ł3


  1. dla negacji

p Np

1 0


½ ½

  1. 1




  1. dla koniunkcji (Kpq)




q p

1

½

0

1

1

½

0

½

½

½

0

0

0

0

0




  1. dla alternatywy (Apq)




q p

1

½

0

1

1

1

1

½

1

½

½

0

1

½

0

4) dla implikacji ( Cpq)




q p

1

½

0

1

1

1

1

½

½

1

1

0

0

½

1


Ex. 13 Zbuduj matrycę dla Epq wiedząc, że Epq=KCpqCqp. Najpierw zbudujemy dwie matryce dla P = Cpq i Q = Cqp, a następnie dla KPQ

p q P Q KPQ

1 1 1 1 1

1 0 0 1 0

0 1 1 0 0

0 0 1 1 1

1 ½ ½ 1 ½

½ 1 1 ½ ½

0 ½ 1 ½ ½

½ 0 ½ 1 ½


Wyniki z powyższej matrycy można więc zebrać, i przedstawić podobnie jak dla pozostałych operatorów logicznych dla Ł3.


q p

1

½

0

1

1

½

0

½

½

1

½

0

0

½

1

Rachunek zdań Ł3 można budować metoda matrycową podobnie jak w przypadku L, czyli klasycznego rachunku. Zdanie jest tautologia Ł3 gdy przyjmuje wartość 1 (prawdę) . W innych rachunkach wielowartościowych, ze względu na trudności w interpretacji nowych wartości logicznych nie mówi się o prawdzie, lecz tzw. wartości wyróżnionej. Dokonano też aksjomatyzacji tego rachunku.


Ex14. Sprawdź, czy zdanie P=” p p „oraz zdanie Q =”(p  p)” są tautologiami Ł3.
Ex3. Sprawdź, czy zdanie P=” p p „oraz zdanie Q =”(p  p)” są tautologiami Ł3.


  1. P= ApNp

p Np ApNp

1 0 1


0 1 1

½ ½ ½



  1. Q= NKpNp

p Np KpNp NKpNp

1 0 0 1

0 1 0 1


½ ½ ½ ½

Logika trójwartościowa Łukasiewicza jest zawarta w logice klasycznej, tzn., że każda tautologia Ł3 jest tautologią L, lecz nie odwrotnie. Z powyższych matryc widać, że ważne prawa klasycznego rachunku zdań jak tzw. prawo wyłączonego środka i tzw. prawo niesprzeczności, posiadające przy tym ciekawe i zgodne z intuicjami interpretacje, a także długie tradycje w logice nie są tautologiami Ł3.


Szczególnie dużą klasę problemów, dla których systemy wielowartościowe znajdują zastosowanie stanowią problemy przyrodoznawstwa. Rozumowania bowiem dotyczące mikroświata prowadzone przy użyciu logiki klasycznej, okazują się rodzić sprzeczności na gruncie tych teorii, które go dotyczą. . Zauważono bowiem, że własności algebraiczne operatorów fizyki kwantowej mają charakter inny niż narzuca logika klasyczna. W tym celu m in. została zbudowana przez G. Birkhoffa i J. von Neumana tzw. logika kwantowa. Ciekawe są również analogie między logikami wielowartościowymi a tzw. logikami rozmytymi, znajdujące zastosowania w komputerowych systemach ekspertowych.

ANALIZA ROZUMOWAŃ
We wszystkich niemal rozumowaniach matematycznych i nie tylko opieramy się bezpośrednio lub pośrednio na prawach rachunku zdań. Spośród rozumowań do najważniejszych należą wnioskowanie i dowodzenie. W praktyce mamy często do czynienia z wnioskowaniami i dowodami poprawnymi i niepoprawnymi. Jeżeli rozumowanie - wnioskowanie bądź dowód spełniają warunki, które powinien spełniać wnioskowanie lub dowód wnioskowanie, to rozumowanie takie nazywamy poprawnym, w przeciwnym przypadku nazywamy go niepoprawnym. Przeprowadzane dotąd rozumowania miały charakter formalny, jednakże i faktycznie przeprowadzane rozumowania, mające charakter nieformalny, można poddać formalizacji.
Ex. 15 Mamy następujące rozumowanie: „Jeżeli będę się uczył lub jestem geniuszem, to zdam egzamin. Jeżeli zdam egzamin, to będę mógł uczęszczać na następne wykłady. Zatem, jeżeli nie zostanę dopuszczany do następnych wykładów, to nie jestem geniuszem.”
Niech

p= ”będę się uczył”

q = „jestem geniuszem”

r =” zdam egzamin”

s =”zostanę dopuszczony do następnych wykładów”
Przesłanki:

P1= ” Jeżeli będę się uczył lub jestem geniuszem, to zdam egzamin”

P2 = „ Jeżeli zdam egzamin, to będę mógł uczęszczać na następne wykłady”
Wniosek:

W= „ jeżeli nie zostanę dopuszczany do następnych wykładów, to nie jestem geniuszem.”


METODA MATRYCOWA
P1= ”p  q  r”

P2 = „r  s”


W =”s  q”


Jeżeli zdanie Q=„ P1  P2  ... Pn W ” jest tautologią, to wnioskowanie jest formalnie poprawne, tzn. w niosek wynika logicznie z przesłanek, w przeciwnym przypadku jest formalnie niepoprawne. Sprawdzimy metodą matrycową skróconą , czy zdanie Q jest tautologią.

1 0 0


1 1 1 0

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



1

01

0 0 0 0 0 0 11


Sprzeczność w wartościowaniu. Zdanie q=0 w pierwszym wystąpieniu, a w drugim wystąpieniu q= 1.



1   2   3   4   5   6   7   8   9   ...   16


©operacji.org 2019
wyślij wiadomość

    Strona główna