KIF08

twierdzenia:

A x~P(x)-* ~ V xP(x).

(1)    A x~P(x)    (założenie)

(2) --V ^xP(^x)    (z.d.n.)

(3)    V xP{x)    (RRZ: 2)

(4)    P(V)    (0\/':3)

(5)    ~P(x«)    (O A": 1)

Otrzymaliśmy sprzeczność, a więc twierdzenie zostało udowodnione. Dołączając doń jego odwrotność (zob. przykład w zadaniu 85) i stosując regułę dołączania równoważności otrzymujemy prawo de Morgana dla kwantyfikatorów w postaci:

~ v ^xp(x)^sA x~^p(*y

Udowodnij drugie prawo de Morgana dla kwantyfikatoriw: ~ /\xP(x)=\/ x~P(x).

87. Wskaż źródło błędu w podanych niżej „dowodach".

(a)

(założenie)

(założenie)

(0A'^: i)

(RO: 2, 3)

(PA’^{: 4}>

(1)

(2)    P(x)

(3)    P(,x)-Q(x)

(4)    <2W

(5)    AxQ(x)

(b)    (V xP(x) a V *~A*))-+V x[P(x) a ~P{x)Y

0) V xP(x) a V x~P(x)    (założenie)

(2)    V xP(x)

(3)    \/x~P(x)

(4)    P(x*)

(5)    ~P(*•)

(OK: 1) (RRZ: U

(OV'^{; 2}> (OV’^{: 3}>

■■

(6)    P(.V*) A ~P(_X*)

(RRZ: 4, 5)

(DV'= 6)

(7)    V *^00 A-/»(*))

88.    Wykaż, że wyrażenia (a), (b) podane w zadaniu 87 nic są ani tautologiami, ani kontrtautologiami, oraz że następnik wyrażenia (b) jest kontrtautologią.

89.    W zastosowaniu do wyrażeń zawierającycli zmienne nicrównokształtne reguły dowodzenia podane w zadaniu 87 wymagają pewnych ograniczeń. Potrzebę tę ilustruje możliwość dowiedzenia za ich pomocą, na przykład następującego wyrażenia (o którym łatwo wykazać, że nic jest tautologią):

/\x\/ yR{x, y)->\/ xR{x. x).

(założenie)

(O A': O (OV': 2) (D\/': 3)

(0

(2)    \JyR(x,y)

(3)    R{x, x♦)

(4)    V ^xR(^x> ^x)

Aby sformułować odpowiednie ograniczenie nałożone na D \f przyjmujemy następującą umowę: wprowadzając na mocy OV' nazwę nieokreśloną będziemy ją opatrywać jako indeksami symbolami wszystkich zmiennych wolnych w wyrażeniu, do któicgo stosujemy 0\J'. Warunek ograniczający stosowanie D\/' brzmi: do formuły, w której zmienna a występuje jako indeks, nie wolno dołączać małego kwantylika-tora wiążącego zmienną a.

Wykaż, że warunek analogiczny do nałożonego wyżej na D N/^ł. należy nałożyć również na D /\\ bowiem nic respektując go można udowodnić nictautologiczną formułę:

A *V    y)-\/y A ^xR(^x> y)-

90. Reguła O/Y wymaga również pewnego ograniczenia w zastosowaniu do wyrażeń zawierających zmienne nierówno-

71