1105140235

16

ROZDZIALI. RACHUNEK ZDAŃ

Jeśli x + y > O to \x+y\ = x+y < |x| + |y|. Jeśli x+y < O to \x+y\ = —(x+y) = (~x) + (-S/) < \x\ + |»|.

Pokazaliśmy więc, że

(x + y > O —> I* + y\ < |*| + |p|) A (->(* + y > 0) -> \x + y\ < |x| + |j/|), co kończy dowód.

1.4 Notacja Polska

W definicji zdania rachunku zdań korzystaliśmy z nawiasów. Istnieje metoda zapisywania zdań bez ich użycia. Metodą tą wprowadził polski matematyk i logik Łu-kasiewicz i nazywana jest obecnie notacją polską. Pokażemy w jaki sposób można przekształcić zdanie zapisane za pomocą nawiasów w zdanie beznawiasowe. Posłużymy się metodą rekurencyjną.

Dla zmiennych zdaniowych pi określimy [p*] = pi. Następnie definiujemy

1.    [pA-s/>] = [ip][V>]A

2.    [^Vt/>] = [¥>][^]V

3.    [v>-Ń] = MM ->■

4.    \tp <-> tp] = [v\[ilĄ 4+

5.    [-vp\ = [(?]-.

Zastosujmy tę metodę dla prawa de Morgana ~<(pAq) o (->pV-*q). Mamy wtedy

Np a q) O (-*> V -.?)] = [-.(p A ?)][(-*> V -.«)] o =

[p A 9]->hp][-9]V O = \p][q] A ->[pH«hV O = pq A -.p-.g-.V O .

Otrzymane zdanie pq A -¹p->q-N ** jest nieco mniej czytelne dla człowieka niż oryginalne zdanie ->(p Ag) H (-< p V ->q). Jednak znacznie łatwiej jest napisać program komputerowy, który operuje na wyrażeniach zapisanych w notacji polskiej niż operujący na wyrażeniach zapisanych w notacji nawiasowej. Ponadto programy takie są bardzo efektywne. Metoda ta znalazła zastosowanie w kalkulatorach firmy Hewlett-Packard, w języku programowania Forth, stosuje się ją często w interpreterach. Warto zauważyć, że można ją stosować nie tylko do wyrażeń rachunku zdań. Z powodzeniem można ją używać do zapisu dowolnych wyrażeń arytmetycznych i algebraicznych.

1.5 Ćwiczenia i zadania

Ćwiczenie 1.1 Pokaż, że dla dowolnych zmiennych zdaniowych p, q i r następujące zdania są tautologiami: