M2.pdf

Wynikanie logiczne

i elementy rachunku kwantyﬁkatorów

Wstęp

1. Wynikanie semantyczne

2. Reguły inferencyjne i pojęcie dowodu formalnego

3. System dedukcji naturalnej

4. Dowody przez dodatkowe założenie

5. Formy zdaniowe

6. Kwantyﬁkatory

Bibliograﬁa

Wstęp

W niniejszej części materiałów przedstawimy ciąg dalszy rozważań dotyczących

rachunku zdań. Zdeﬁniowane zostanie — a także scharakteryzowane

odpowiednimi twierdzeniami — pojęcie wynikania semantycznego. Na tej bazie

wprowadzimy analogiczne pojęcie, jakim jest wynikanie syntaktyczne. Zdeﬁniujemy

zatem pojęcie dowodu formalnego wprost i nie wprost. Wprowadzimy pewien

układ reguł dedukcji naturalnej zupełny wobec prezentowanego w poprzednim

module semantycznego ujęcia rachunku zdań. Zdeﬁniowane zostanie też pojęcie

formy zdaniowej i wprowadzone kwantyﬁkatory. Omówimy pojęcia zmiennej

wolnej i zmiennej związanej. Zaprezentujemy przykładowe prawa rachunku

kwantyﬁkatorów.

1. Wynikanie semantyczne

Powiemy, że formuła α wynika semantycznie ze zbioru formuł X , co będziemy oznaczać

X ׀ = α, jeżeli formuła α jest prawdziwa dla wszystkich wartościowań dających

wartość 1 dla wszystkich formuł ze zbioru X .

Przykład 1

Rozważmy formułę p ⇒ q oraz zbiór formuł X = { p , q }. Rozważmy wszystkie

wartościowania v , w których są prawdziwe wszystkie formuły (zmienne) ze zbioru

X . Mamy wartościowanie v ( p ) = 1 oraz v ( q ) = 1. Ale wtedy mamy również

w ( p ⇒ q ) = 1. Zatem zdanie p ⇒ q wynika ze zbioru X = { p , q } ({ p , q } ׀ = p ⇒ q ).

Przykład 2

Rozważmy formułę ¬(¬ p ∧ q ) oraz zbiór formuł X = { p , ¬ q }. Rozważmy

wszystkie wartościowania v , w których są prawdziwe wszystkie zdania ze zbioru

X . Mamy wartościowanie v ( p ) = 1 oraz v ( q ) = 0. Dla tego wartościowania

jest: w (¬(¬ p ∧ q )) = 1. Zatem formuła ¬(¬ p ∧ q ) wynika ze zbioru

X = { p , ¬ q } ({ p , ¬ q } ׀ = ¬(¬ p ∧ q )).

Z deﬁnicji wynikania można wyprowadzić warunek na fakt, że dane zdanie nie

wynika z odpowiedniego zbioru zdań.

Powiemy, że formuła α nie wynika semantycznie ze zbioru formuł X ( X ׀ ≠ α), jeżeli dla

pewnego wartościowania v wszystkie zdania ze zbioru X są prawdziwe, zaś zdanie

α jest fałszywe ( w (α) = 0).

Przykład 3

Rozważmy formułę ¬ p ∧ q oraz zbiór formuł X = { p , q }. Rozważmy wszystkie

wartościowania v , w których są prawdziwe wszystkie zdania ze zbioru X .

Mamy wartościowanie v ( p ) = 1 oraz v ( q ) = 1. Dla tego wartościowania jest:

w (¬ p ∧ q ) = 0. Zatem formuła ¬ p ∧ q nie wynika ze zbioru X = { p , q } ({ p , q } ׀ ≠ ¬ p ∧ q ).

Zachodzą następujące twierdzenia:

Twierdzenie 1

Formuła α jest tautologią wtedy i tylko wtedy, gdy wynika semantycznie ze zbioru

pustego. Symbolicznie ∅ ׀ = α lub krócej ׀ = α (bez wypisywania zbioru przed

symbolem wynikania).

Twierdzenie 2

Formuła α wynika semantycznie ze skończonego zbioru formuł

X = {α 1 , α 2 , ..., α n } ( X ׀ = α) wtedy i tylko wtedy, gdy implikacja (α 1 ∧ α 2 ∧ ... ∧ α n ) ⇒ α

jest tautologią.

Dowód

Załóżmy, że formuła α wynika semantycznie ze skończonego zbioru formuł

X = {α 1 , α 2 , ..., α n }. Wtedy dla dowolnego wartościowania, dla którego formuły

α 1 , α 2 , ..., α n przyjmują wartość 1, również formuła α przyjmuje wartość 1.

Rozważmy implikację (α 1 ∧ α 2 ∧ ... ∧ α n ) ⇒ α. Wszystkie wartościowania możemy

podzielić na dwie grupy: takie, dla których wartość koniunkcji α 1 ∧ α 2 ∧ ... ∧ α n

wynosi 0 oraz takie, dla których wartość tej koniunkcji jest równa 1. W pierwszym

przypadku mamy fałszywy poprzednik rozpatrywanej implikacji, jest ona

zatem prawdziwa. W drugim przypadku zauważmy, że jeżeli wartość koniunkcji

α 1 ∧ α 2 ∧ ... ∧ α n jest równa 1, to każda z formuł α 1 , α 2 , ..., α n musi również

przyjmować wartość 1. Możemy wtedy skorzystać z założenia, że również formuła

α (następnik rozpatrywanej implikacji) ma wartość 1, zatem implikacja jest

także prawdziwa. Widzimy, że dla dowolnych wartościowań wartość implikacji

(α 1 ∧ α 2 ∧ ... ∧ α n ) ⇒ α jest równa 1. Zatem jest ona tautologią.

Załóżmy teraz, że implikacja (α 1 ∧ α 2 ∧ ... ∧ α n ) ⇒ α jest tautologią. Rozważmy

wszystkie wartościowania, dla których formuły ze zbioru X = {α 1 , α 2 , ..., α n } mają

wartość 1. Oczywiście, dla tych wartościowań formuła α nie może mieć wartości

0, gdyż byłoby to sprzeczne z tautologicznością implikacji (α 1 ∧ α 2 ∧ ... ∧ α n ) ⇒ α.

Zatem formuła α musi mieć wartość 1. Oznacza to oczywiście, że formuła α wynika

semantycznie ze skończonego zbioru formuł X = {α 1 , α 2 , ..., α n } ( X ׀ = α).

2. Reguły inferencyjne

i pojęcie dowodu formalnego

W dotychczasowych rozważaniach przedstawiliśmy tzw. semantyczne ujęcie

rachunku zdań. Oznacza to, że odwoływaliśmy się do pojęcia wartości logicznych,

wartościowania zmiennych i wartości formuł dla danych wartościowań zmiennych.

Przedstawimy teraz tak zwane syntaktyczne ujęcie omawianego rachunku

logicznego. W ujęciu tym nie odwołujemy się do pojęć semantycznych (wartości

logicznych itp.), ale wykonujemy wnioskowanie, wyprowadzając (dedukując) jedne

formuły z innych.

Odpowiednikiem omawianego wyżej pojęcia wynikania semantycznego jest tutaj

pojęcie wynikania syntaktycznego związane ściśle z pojęciami reguł inferencyjnych

oraz dowodu formalnego.

Reguły inferencyjne to schematy pozwalające wyprowadzać (dedukować) formuły

z innych formuł. Schematy te przedstawiać będziemy w następującej postaci:

, gdzie formuły α 1 , α 2 , ..., α n będziemy nazywać przesłankami , zaś

formułę β — wnioskiem . Ogólnie reguła o schemacie: pozwala z for-

muł (przesłanek) α 1 , α 2 , ..., α n wyprowadzić (wydedukować) formułę β (wniosek).

Dla uproszczenia zapisu będziemy czasem stosować następującą notację

dla symetrycznych par reguł postaci: oraz .

Przykład 4

Jako przykład przedstawimy reguły E liminacji K oniunkcji ( EK ) o schematach:

oraz . Reguły te pozwalają z dowolnej koniunkcji α ∧ β (zauważmy, że α

oraz β mogą być dowolnymi formułami) wyprowadzać czynniki tej koniunkcji.

I tak — jeżeli rozważymy formułę (¬ r ∨ p ) ∧ ¬(¬ p ∨ q ⇒ s ) — to na mocy reguł EK

możemy z tej formuły wyprowadzić oba jej czynniki: ¬ r ∨ p oraz ¬(¬ p ∨ q ⇒ s ).

Oczywiście, dane reguły nie zawsze możemy stosować do dowolnych formuł.

Powyższych reguł EK nie możemy zastosować na przykład do formuły

¬(¬ p ∨ q ⇒ s ), gdyż ta nie jest koniunkcją.

Przykład 5

Reguły E liminacji A lternatywy ( EA ) mają następujące schematy:

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: