Scan0027

3.2 Elementy logiki pierwszego rzędu 35

•    f\ Q (x) — dla każdego x spełniającego P (x) jest Q (x),

P(x)

•    \J Q (x) — istnieje x spełniające P{x), takie że Q{x).

P{x)

Formuły z kwantyfikatorami ograniczonymi można zastąpić formułami, w których takie kwantyfikatory nie występują:

/\Q(x) = /\[P (x) => Q (z)],

P{x)    X

V ^ (z) = V i^p (^X) ^A Q (^X)] •

P{x)

Przykład 3.7

•    A (z² > o) = A [(x A o) => (x² > o)]

x^0    x

•    V (x² — 1 = 0) = V [(x < 0) A (x² — 1 = 0)]

£<0    X

3.2.5 Tautologie logiki pierwszego rzędu

Tautologiami logiki pierwszego rzędu są formuły, które są prawdziwe dla dowolnych funkcji zdaniowych. Do konstruowania takich formuł można wykorzystać następujące twierdzenie.

Twierdzenie 3.4 Jeśli A jest prawem rachunku zdań, to podstawiając w A za atomy dowolne funkcje zdaniowe lub zdania zbudowane z funkcji zdaniowych otrzymujemy funkcję zdaniową lub zdanie prawdziwe.

Przykład 3.8 Dla p V ~ p mamy, np.:

podstawienie za p	tautologia
P(x)	P (x) V ~ P (x)
A P{x) X	f\P{x) V ~ A P(x) X X

P (x) może oznaczać np. ”x jest podzielne przez 2”, gdzie x G Z.

Do sprawdzania, czy dana formuła jest tautologią można w tym przypadku zastosować metodę zero-jedynkową. Istnieją jednak tautologie, których nie da się otrzymać za pomocą podanego twierdzenia. Wymagają one odrębnych dowodów, np.: