Węższy rachunek predykatów moder WRP a bazy danych

WRP, model i bazy danych
LOGIKA
Rachunek Predykatów, model i bazy danych
Robert Trypuz
Katedra Logiki KUL
11 maja 2011
WRP, model i bazy danych
Plan Wykładu
1 Spełnianie
2 Model WRP
3 WRP a bazy danych
WRP, model i bazy danych
Spełnianie
WRP, model i bazy danych
Spełnianie
Spełnianie
Spełnianie jest stosunkiem semantycznym zachodzącym pomiędzy
przedmiotem (lub ciągiem przedmiotów) a wyrażeniem zdaniowym, w
szczególności formą zdaniową.
WRP, model i bazy danych
Spełnianie
Spełnianie
Spełnianie jest stosunkiem semantycznym zachodzącym pomiędzy
przedmiotem (lub ciągiem przedmiotów) a wyrażeniem zdaniowym, w
szczególności formą zdaniową.
Mówi się, że
WRP, model i bazy danych
Spełnianie
Spełnianie
Spełnianie jest stosunkiem semantycznym zachodzącym pomiędzy
przedmiotem (lub ciągiem przedmiotów) a wyrażeniem zdaniowym, w
szczególności formą zdaniową.
Mówi się, że
przedmiot spełnia formę zdaniową o jednej zmiennej wolnej
WRP, model i bazy danych
Spełnianie
Spełnianie
Spełnianie jest stosunkiem semantycznym zachodzącym pomiędzy
przedmiotem (lub ciągiem przedmiotów) a wyrażeniem zdaniowym, w
szczególności formą zdaniową.
Mówi się, że
przedmiot spełnia formę zdaniową o jednej zmiennej wolnej
ciąg n przedmiotów spełnia formę zdaniową o n zmiennych wolnych
WRP, model i bazy danych
Spełnianie
Spełnianie
Spełnianie jest stosunkiem semantycznym zachodzącym pomiędzy
przedmiotem (lub ciągiem przedmiotów) a wyrażeniem zdaniowym, w
szczególności formą zdaniową.
Mówi się, że
przedmiot spełnia formę zdaniową o jednej zmiennej wolnej
ciąg n przedmiotów spełnia formę zdaniową o n zmiennych wolnych
Przykład
Ciąg (2, 3) spełnia formę zdaniową x < y przy przyporządkowaniu
x-owi liczby 2, y-owi liczy 3 i interpretacji < jako relacji mniejszości
między liczbami.
WRP, model i bazy danych
Model WRP
Ustalenia (I)
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
a : Var - " funkcja wartościująca przyporządkowująca
zmiennym indywidualnym przedmioty ze zbioru "
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
a : Var - " funkcja wartościująca przyporządkowująca
zmiennym indywidualnym przedmioty ze zbioru "
d gdy y = x
x
a (y) =
d
a(y) gdy y = x

x
a jest funkcją wartościującą różniącą się od a jedynie tym, że
d
przedmiot a(x) jest zastąpiony przez d.
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
a : Var - " funkcja wartościująca przyporządkowująca
zmiennym indywidualnym przedmioty ze zbioru "
d gdy y = x
x
a (y) =
d
a(y) gdy y = x

x
a jest funkcją wartościującą różniącą się od a jedynie tym, że
d
przedmiot a(x) jest zastąpiony przez d.
I jest funkcją interpretującą, która przyporządkowuje:
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
a : Var - " funkcja wartościująca przyporządkowująca
zmiennym indywidualnym przedmioty ze zbioru "
d gdy y = x
x
a (y) =
d
a(y) gdy y = x

x
a jest funkcją wartościującą różniącą się od a jedynie tym, że
d
przedmiot a(x) jest zastąpiony przez d.
I jest funkcją interpretującą, która przyporządkowuje:
predykatom n-argumentowym, n-argumentowe relacje określone na
zbiorze ", tj. I(�n) ą" "n, gdzie �n jest predykatem n-argumentowym
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
a : Var - " funkcja wartościująca przyporządkowująca
zmiennym indywidualnym przedmioty ze zbioru "
d gdy y = x
x
a (y) =
d
a(y) gdy y = x

x
a jest funkcją wartościującą różniącą się od a jedynie tym, że
d
przedmiot a(x) jest zastąpiony przez d.
I jest funkcją interpretującą, która przyporządkowuje:
predykatom n-argumentowym, n-argumentowe relacje określone na
zbiorze ", tj. I(�n) ą" "n, gdzie �n jest predykatem n-argumentowym
stałym indywidualnym określone elementy zbioru ", tj. I(ai) " ",
gdzie ai jest pewną stałą indywidualną
WRP, model i bazy danych
Model WRP
Ustalenia (I)
Var zbiór zmiennych indywidualnych
" zbiór przedmiotów/obiektów
a : Var - " funkcja wartościująca przyporządkowująca
zmiennym indywidualnym przedmioty ze zbioru "
d gdy y = x
x
a (y) =
d
a(y) gdy y = x

x
a jest funkcją wartościującą różniącą się od a jedynie tym, że
d
przedmiot a(x) jest zastąpiony przez d.
I jest funkcją interpretującą, która przyporządkowuje:
predykatom n-argumentowym, n-argumentowe relacje określone na
zbiorze ", tj. I(�n) ą" "n, gdzie �n jest predykatem n-argumentowym
stałym indywidualnym określone elementy zbioru ", tj. I(ai) " ",
gdzie ai jest pewną stałą indywidualną
Dla ułatwienia przyjmiemy, że I(ą) = a(ą), gdzie ą jest zmienną
indywidualną.
WRP, model i bazy danych
Model WRP
Ustalenia (II)
WRP, model i bazy danych
Model WRP
Ustalenia (II)
Model
Modelem M nazywamy parę uporządkowaną ", I , gdzie " jest zbiorem
obiektów i nosi nazwę uniwersum , zaś I jest funkcją interpretującą.
WRP, model i bazy danych
Model WRP
Ustalenia (II)
Model
Modelem M nazywamy parę uporządkowaną ", I , gdzie " jest zbiorem
obiektów i nosi nazwę uniwersum , zaś I jest funkcją interpretującą.
Spełnianie w modelu
Przez M, a |= � będziemy rozumieć, że wyrażenie � jest spełnione w
modelu M przy wartościowaniu a.
WRP, model i bazy danych
Model WRP
Ustalenia (II)
Model
Modelem M nazywamy parę uporządkowaną ", I , gdzie " jest zbiorem
obiektów i nosi nazwę uniwersum , zaś I jest funkcją interpretującą.
Spełnianie w modelu
Przez M, a |= � będziemy rozumieć, że wyrażenie � jest spełnione w
modelu M przy wartościowaniu a.
Term
Termem nazywamy zmienną indywidualną lub stałą indywidualną języka
WRP.
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
M, a |= � (" � a" M, a |= � (" M, a |= �
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
M, a |= � (" � a" M, a |= � (" M, a |= �
M, a |= � � a" M, a |= � M, a |= �
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
M, a |= � (" � a" M, a |= � (" M, a |= �
M, a |= � � a" M, a |= � M, a |= �
M, a |= � a" � a" M, a |= � a" M, a |= �
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
M, a |= � (" � a" M, a |= � (" M, a |= �
M, a |= � � a" M, a |= � M, a |= �
M, a |= � a" � a" M, a |= � a" M, a |= �
ą
M, a |= "ą � a" "d " " M, a |= �
d
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
M, a |= � (" � a" M, a |= � (" M, a |= �
M, a |= � � a" M, a |= � M, a |= �
M, a |= � a" � a" M, a |= � a" M, a |= �
ą
M, a |= "ą � a" "d " " M, a |= �
d
ą
M, a |= "ą � a" "d " " M, a |= �
d
WRP, model i bazy danych
Model WRP
Definicja warunków spełniania dla wyrażeń WRP
Dla modelu M = ", I i funkcji wartościującej a mamy:
M, a |= �n(�1, . . . , �n) a" I(�1), . . . , I(�n) " I(�n)
M, a |= �1 = �2 a" I(�1) = I(�2)
M, a |= Ź� a" Ź(M, a |= �)
M, a |= � '" � a" M, a |= � '" M, a |= �
M, a |= � (" � a" M, a |= � (" M, a |= �
M, a |= � � a" M, a |= � M, a |= �
M, a |= � a" � a" M, a |= � a" M, a |= �
ą
M, a |= "ą � a" "d " " M, a |= �
d
ą
M, a |= "ą � a" "d " " M, a |= �
d
Uwaga! �n reprezentuje predykaty n-argumentowe WRP, �i
reprezentuje termy WRP, zaś ą zmienne indywidualne
WRP.
WRP, model i bazy danych
Model WRP
Prawdziwość
WRP, model i bazy danych
Model WRP
Prawdziwość
Prawdziwość
Wyrażenie � WRP jest prawdziwe w modelu M (formalnie: M |= �)
wtedy i tylko wtedy, gdy wyrażenie � jest spełnione w M
przy każdym wartościowaniu (formalnie: "a M, a |= �).
WRP, model i bazy danych
Model WRP
Prawdziwość
Prawdziwość
Wyrażenie � WRP jest prawdziwe w modelu M (formalnie: M |= �)
wtedy i tylko wtedy, gdy wyrażenie � jest spełnione w M
przy każdym wartościowaniu (formalnie: "a M, a |= �).
Zbiór zdań prawdziwych WRP: E (M)
E (M) = {� " PZWWRP : M |= �}
WRP, model i bazy danych
Model WRP
Przykład (II)
WRP, model i bazy danych
Model WRP
Przykład (II)
Wezmy formułę WRP:
"x " y Większy-od(x, y)
WRP, model i bazy danych
Model WRP
Przykład (II)
Wezmy formułę WRP:
"x " y Większy-od(x, y)
Pokażemy, że formuła ta jest spełniona w modelu M = N, I , gdzie N
jest zbiorem liczb naturalnych, zaś I jest określona tak, że:
I(Większy-od) = >,
WRP, model i bazy danych
Model WRP
Przykład (II)
Wezmy formułę WRP:
"x " y Większy-od(x, y)
Pokażemy, że formuła ta jest spełniona w modelu M = N, I , gdzie N
jest zbiorem liczb naturalnych, zaś I jest określona tak, że:
I(Większy-od) = >,
tj. pokażemy, że:
M, a |= "x " y Większy-od(x, y)
WRP, model i bazy danych
Model WRP
Przykład (II)
Wezmy formułę WRP:
"x " y Większy-od(x, y)
Pokażemy, że formuła ta jest spełniona w modelu M = N, I , gdzie N
jest zbiorem liczb naturalnych, zaś I jest określona tak, że:
I(Większy-od) = >,
tj. pokażemy, że:
M, a |= "x " y Większy-od(x, y)
M, a |= "x " y Większy-od(x, y) a"
x y
"d " N "d " N M, a |= Większy-od(x, y) a"
d d
"d " N "d " N d > d .
WRP, model i bazy danych
Model WRP
Przykład (II)
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
Relacja dwuargumentowa Friend(x, y) x jest przyjacielem y .
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
Relacja dwuargumentowa Friend(x, y) x jest przyjacielem y .
Model:
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
Relacja dwuargumentowa Friend(x, y) x jest przyjacielem y .
Model:
" = {1, 2, 3, 4}
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
Relacja dwuargumentowa Friend(x, y) x jest przyjacielem y .
Model:
" = {1, 2, 3, 4}
Funkcja interpretująca jest określona jak następuje:
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
Relacja dwuargumentowa Friend(x, y) x jest przyjacielem y .
Model:
" = {1, 2, 3, 4}
Funkcja interpretująca jest określona jak następuje:
I(Alice) = 1
I(Bob) = 2
I(Carol) = 3
I(Robert) = 2
I(Friend) = F
WRP, model i bazy danych
Model WRP
Przykład (II)
Dodane do języka WRP:
Stałe indywidualne: Alice, Bob, Carol, Robert
Relacja dwuargumentowa Friend(x, y) x jest przyjacielem y .
Model:
" = {1, 2, 3, 4}
Funkcja interpretująca jest określona jak następuje:
I(Alice) = 1
I(Bob) = 2
I(Carol) = 3
I(Robert) = 2
I(Friend) = F
F = { 1, 2 , 2, 1 , 1, 4 , 4, 1 , 2, 4 , 4, 2 , 3, 4 , 4, 3 }
WRP, model i bazy danych
Model WRP
Przykład (II)
WRP, model i bazy danych
Model WRP
Przykład (II)
Tabela: I(Friend(x, y))
WRP, model i bazy danych
Model WRP
Przykład (II)
Tabela: I(Friend(x, y))
1 2
2 1
1 4
4 1
2 4
4 2
3 4
4 3
WRP, model i bazy danych
Model WRP
Przykład (II)
Tabela: I("y Friend(x, y))
WRP, model i bazy danych
Model WRP
Przykład (II)
Tabela: I("y Friend(x, y))
1
2
3
4
WRP, model i bazy danych
Model WRP
Przykład (II)
WRP, model i bazy danych
Model WRP
Przykład (II)
Tabela: I("y (Friend(x, y) '" x = y)

4
WRP, model i bazy danych
Model WRP
Przykład (II)
WRP, model i bazy danych
Model WRP
Przykład (II)
Niektóre fakty dotyczące modelu:
WRP, model i bazy danych
Model WRP
Przykład (II)
Niektóre fakty dotyczące modelu:
M, a |= Friend(Alice, Bob)
WRP, model i bazy danych
Model WRP
Przykład (II)
Niektóre fakty dotyczące modelu:
M, a |= Friend(Alice, Bob)
M, a |= Robert = Bob
WRP, model i bazy danych
Model WRP
Przykład (II)
Niektóre fakty dotyczące modelu:
M, a |= Friend(Alice, Bob)
M, a |= Robert = Bob
M, a |= "x "y Friend(x, y)
WRP, model i bazy danych
Model WRP
Przykład (II)
Niektóre fakty dotyczące modelu:
M, a |= Friend(Alice, Bob)
M, a |= Robert = Bob
M, a |= "x "y Friend(x, y)
M |= "y "x Friend(x, y), tj. Ź(M, a |= "y "x Friend(x, y))
WRP, model i bazy danych
Model WRP
Przykład (II)
Niektóre fakty dotyczące modelu:
M, a |= Friend(Alice, Bob)
M, a |= Robert = Bob
M, a |= "x "y Friend(x, y)
M |= "y "x Friend(x, y), tj. Ź(M, a |= "y "x Friend(x, y))
M, a |= "x, y (Friend(x, y) Friend(y, x))
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (I)
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (I)
Kiedy język WRP i uniwersum modelu (") są skończone, istnieje
wówczas oczywista analogia pomiędzy WRP a bazami danych:
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (I)
Kiedy język WRP i uniwersum modelu (") są skończone, istnieje
wówczas oczywista analogia pomiędzy WRP a bazami danych:
uniwersum " odpowiada zbiorowi wartości występujących w
tabelach bazy danych
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (I)
Kiedy język WRP i uniwersum modelu (") są skończone, istnieje
wówczas oczywista analogia pomiędzy WRP a bazami danych:
uniwersum " odpowiada zbiorowi wartości występujących w
tabelach bazy danych
funkcja interpretująca I odpowiada n-tkom uporządkowanym
należącym do relacji w bazie danych
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (I)
Kiedy język WRP i uniwersum modelu (") są skończone, istnieje
wówczas oczywista analogia pomiędzy WRP a bazami danych:
uniwersum " odpowiada zbiorowi wartości występujących w
tabelach bazy danych
funkcja interpretująca I odpowiada n-tkom uporządkowanym
należącym do relacji w bazie danych
formuły WRP odpowiadają zapytaniom kierowanym do bazy danych
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (I)
Kiedy język WRP i uniwersum modelu (") są skończone, istnieje
wówczas oczywista analogia pomiędzy WRP a bazami danych:
uniwersum " odpowiada zbiorowi wartości występujących w
tabelach bazy danych
funkcja interpretująca I odpowiada n-tkom uporządkowanym
należącym do relacji w bazie danych
formuły WRP odpowiadają zapytaniom kierowanym do bazy danych
interpretacja formuł WRP koresponduje z odpowiedziami
udzielonymi na zapytania kierowane do bazy danych.
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (II)
Tabela: Formuły WRP jako odpowiednik zapytań do bazy danych
WRP, model i bazy danych
WRP a bazy danych
WRP a bazy danych (II)
Tabela: Formuły WRP jako odpowiednik zapytań do bazy danych
WRP BAZA DANYCH
Friend CREATE TABLE FRIENDS (friend1 INT,
friend2 INT)
Friend(x, y) SELECT friend1 AS x, friend2 AS y
FROM FRIENDS
Friend(x, x) SELECT friend1 AS x
FROM FRIENDS
WHERE friends1 = friends2
Friend(x, y) '" x = y SELECT friend1 AS x, friend2 AS y
FROM FRIENDS
WHERE friends1 = friends2
"yFriend(x, y) SELECT friend1 AS x
FROM FRIENDS

Wyszukiwarka