1105140231

12

ROZDZIALI. RACHUNEK ZDAŃ

Uwaga. Z udowodnionego twierdzenia wynika, że jeśli w trakcie badania pewnego systemu formalnego natrafimy choćby raz na sprzeczność, to dyskwalifikuje ona całkowicie ten system.

Jak już zauważyliśmy, alternatywę możemy zdefiniować za pomocą negacji oraz koniunkcji. Z prawa eliminacji implikacji wynika, że implikację możemy zdefiniować za pomocą negacji oraz alternatywy. Zatem implikację można zdefiniować za pomocą negacji oraz koniunkcji. Podobna obserwacja zachodzi również dla równoważności. Skoro można ją zdefiniować za pomocą implikacji i koniunkcji, więc do jej zdefiniowania wystarcza tylko negacja oraz koniunkcja.

Inne Spójniki Logiczne

Istnieją dwa operatory logiczne, za pomocą których można zdefiniować wszystkie pozostałe operatory. Jednym z nich jest spójnik zwany spójnikiem Pierce 'a, zdefiniowany jako

p±q = (-.p A-.®).

Drugim z nich jest tak zwana kreska Sheffera zdefiniowana wzorem

p\q = (-,pV-.«).

Uwaga. Zauważmy, że (p X q) = ->(p V q) oraz (p\q) = ->(p A q). Spójnik Pierce’a znany jest w informatyce pod nazwą NOR, zaś kreska Sheffera jako operacja NAND.

Bardzo pożyteczny jest również spójnik logiczny © zdefiniowany następująco:

p ® q & (~q> Ag) V (pA -<q).

Odpowiada on, mniej więcej, konstrukcji językowej ”albo” języka polskiego. Posiada on kilka interesujących własności, które czynią go przydatnym w informatyce do kodowania i dekodowania informacji.

1.		= _L,
2.	p@q	= q®p,
3.	(p © q) ® r	= p® (q®r]
4.	p@q	= ->{p ++ q)-

Pierwsze dwie własności tego spójnika wynikają bezpośrednio z definicji. Trzecią własność, łączność, najprościej można pokazać za pomocą tabelki zero-jedynkowej. Czwarta własność wynika z praw de Morgana i z drugiego prawa eliminacji równoważności.

Uwaga. W informatyce spójnik logiczny "albo” znany jest pod nazwą XOR.

1.3 Metody Dowodzenia Twierdzeń

Większość twierdzeń matematycznych jest zbudowana z pewnej listy założeń oraz z tezy. Mają one postać implikacji

(Vl A ... A ip_n) —► ip.