LOGIKA 1 - definicje

Alfabet KRZ

Do alfabetu języka KRZ należą następujące znaki, i tylko one:

p1, p2, p3, ... (zmienne zdaniowe)

~, ∧, ∨ , → , ↔ (spójniki)

( ) (nawiasy)

Wyrażenie języka KRZ

Wyrażeniem języka KRZ jest każdy skończony ciąg elementów alfabetu języka KRZ.

zbiór FORM

Zbiór FORM formuł języka KRZ jest najmniejszym zbiorem spełniającym następujące warunki:

(i) VAR ⊆ FORM, (wartości są podzbiorem lub są równe zbiorowi formuł KRZ)

(ii) jeżeli wyrażenie A należy do FORM, to wyrażenie mające postać ~A należy do FORM,

(iii) jeżeli wyrażenia A, B należą do FORM, to wyrażenia mające postać: (A∧B), (A∨B) , (A→B) , (A↔B) również należą do FORM.

formuła KRZ

Każdy element zbioru FORM nazywamy formułą języka KRZ.

(wyrażenie “sensowne”)

n-argumentowa funkcja prawdziwościowa

Pod pojęciem n-argumentowej (n ≥ 1) funkcji prawdziwo-

ściowej

rozumiemy funkcję n zmiennych przebiegających zbiór {0, 1} i o wartościach należących do zbioru {0, 1}.

wartościowanie

Wartościowaniem nazywamy każdą funkcję

v: FORM |→ {0, 1} taką, że:

(i) dla każdej zmiennej zdaniowej z: v(z) = 1 albo v(z) = 0;

(ii) v(~A) = 1 wtw v(A) = 0;

(iii) v(A ∧ B) = 1 wtw v(A) = 1 oraz v(B) = 1;

(iv) v(A ∨ B) = 1 wtw v(A) = 1 lub v(B) = 1;

(v) v(A → B) = 1 wtw v(A) = 0 lub v(B) = 1;

(vi) v(A ↔ B) = 1 wtw v(A) = v(B).

obliczanie wartości formuły przy wartościowaniu

Niech A będzie formułą, natomiast v i v* będą wartościowaniami takimi, że:

($) dla dowolnej zmiennej zdaniowej z występującej w formule A,

v(z) = v*(z).

Wówczas v(A) = v*(A).

tautologia KRZ

Formuła A jest tautologią KRZ wtw dla każdego wartościowania v zachodzi v(A) = 1.

VAR

to zbior wszystkich zmiennych zdaniowych języka KRZ

(wynikanie logiczne – na gruncie KRZ - formuły z formuły)

A ╞ KRZ B wtw dla każdego wartościowania v zachodzi:

jeżeli v(A) = 1, to v(B) = 1.

(wynikanie logiczne - na gruncie KRZ – formuły ze zbiory formuł)

X ╞ KRZ B wtw dla każdego wartościowania v zachodzi:

jeżeli v(A) = 1 dla każdego A ∈ X, to v(B) = 1.

formuły sygnowane

(i) Jeżeli A jest formułą, to TA i FA są formułami sygnowanymi.

(ii) Nie ma żadnych innych formuł sygnowanych poza tymi, które można utworzyć przy pomocy warunku (i).

binarne drzewo nieuporządkowane

Mianem binarnego drzewa nieuporządkowanego będziemy na-

zywali dowolną trójkę uporządkowaną D = <Z, f, P>

, gdzie Z jest niepustym

zbiorem, którego elementy nazywamy węzłami, f jest funkcją przyporządkowu-

jącą każdemu elementowi x zbioru Z liczbę całkowitą dodatnią (wartość funkcji

f dla argumentu x będziemy nazywać poziomem x-a), natomiast P jest dwu-

członową relacją określoną na zbiorze Z (xPy czytamy „x jest bezpośrednim

poprzednikiem y” lub ”y jest bezpośrednim następnikiem x”), która spełnia na-

stępujące warunki:

a) istnieje dokładnie jeden węzeł poziomu 1; węzeł ten będziemy

nazywać korzeniem drzewa;

b) każdy węzeł nie będący korzeniem ma dokładnie jeden

bezpośredni poprzednik;

c) każdy węzeł ma co najwyżej dwa bezpośrednie następniki;

d) dla dowolnych elementów x, y zbioru Z: jeśli y jest bezpośrednim

następnikiem x, to f(y)=f(x)+1.

prosty węzeł

Prostym węzłem będziemy nazywać węzeł, który ma dokładnie jeden bezpośredni następnik, a węzłem rozgałęzionym - węzeł posiadający dwa bezpośrednie następniki.

Węzeł, który nie ma żadnych bezpośrednich następników nazywamy liściem.

gałąź

5.3. Przez gałąź binarnego drzewa nieuporządkowanego będziemy rozumieć niepusty ciąg węzłów, którego pierwszym elementem jest korzeń, każdy kolejny element jest bezpośrednim następnikiem poprzedniego i ostatni element ciągu – jeśli takowy istnieje - jest liściem.

binarne drzewo uporządkowane

Mianem binarnego drzewa uporządkowanego będziemy nazywali

parę uporządkowaną D = <D, h> taką, że:

D jest binarnym drzewem nieuporządkowanym, a h jest funkcją, która przyporządkowuje każdemu węzłowi rozgałęzionemu x drzewa D ciąg dwuelementowy h(x), nie zawierający powtórzeń, którego wyrazami są bezpośrednie następniki x-a, nazywane odpowiednio prawym i lewym.

Węzłami i gałęziami drzewa uporządkowanego <D, h> są węzły i gałęzie drzewa D.

tabela analityczna dla formuly a

Tabelą analityczną dla formuły A jest dowolne binarne drzewo

uporządkowane, którego węzłami są wystąpienia formuł sygnowanych, kon-

struowane następująco:

1. Rozpoczynamy konstrukcję od budowy 1-elementowego drzewa, którego

jedynym węzłem jest formuła sygnowana FA; drzewo to jest tabelą analityczną

dla A.

2. Niech  będzie już skonstruowaną tabelą dla A, niech g będzie gałęzią

drzewa  i niech  będzie ostatnim wyrazem g. Wówczas drzewo (uporząd-

kowane) powstające z  poprzez:

(a) wprowadzenie, jako bezpośredniego następnika , formuły sygnowa-

nej, którą można otrzymać poprzez zastosowanie reguły nierozgałęziającej

do pewnej formuły sygnowanej będącej wyrazem g, lub

(b) wprowadzenie, jako bezpośrednich następników  (odpowiednio, pra-

wego i lewego), formuł sygnowanych, które można otrzymać poprzez za-

stosowanie reguły rozgałęziającej do pewnej formuły będącej wyrazem g

jest tabelą analityczną dla formuły A.

galaz zamknieta i otwarta

Gałąź g tabeli analitycznej nazywamy zamkniętą wtw istnieje taka formuła B, że wystąpienia formuł sygnowanych FB, TB są wyrazami gałęzi g; w przeciwnym przypadku mówimy, że gałąź g jest otwarta.

dowod formuly a

Dowodem formuły A jest dowolna tabela analityczna dla formuły A taka, że każda gałąź tej tabeli jest zamknięta.

semantyczne twierdzenie o odrywaniu

Jeżeli formuła

postaci A → B jest tautologią KRZ oraz formuła A jest tautologią KRZ,

to formuła B jest tautologią KRZ.

semantyczne twierdzenie o podstawianiu

Jeżeli formuła

A jest tautologią KRZ, to formuła A[pi /B] jest tautologią KRZ.

teza krz 

Każda teza KRZ jest tautologią KRZ.

kiedy formuła jest tezą

Formułę nazywamy tezą KRZ wtw:

jest ona aksjomatem KRZ lub

ma co najmniej jeden dowód w oparciu o aksjomaty KRZ.