UTF-8''LOG 110 zagadnienia i opracowanie(FINAL), 06-DLOGLI0 Podstawy logiki i teorii mnogości

[ Pobierz całość w formacie PDF ]
Zagadnienia i ich opracowanie na egzamin z
LOG110
"Wstęp do logiki i teorii mnogości"
1.Definicja i przykłady tautologii KRZ.
Def.
Tautologią KRZ nazywamy formułę KRZ, która ma wartość logiczną 1 przy każdym wartościowaniu.
Przykłady:
Prawo sprzeczności
¬
p
∧¬
p

Prawo wyłączonego
środka
p
∨¬
p
Prawo podwójnej negacji
p
⇔¬¬
p
Prawo transpozycji

p
⇒
q
⇔¬
q
⇒¬
p

Prawa idempotentności
p
∧
p
⇔
p
p
∨
p
⇔
p
Prawa przemienności
p
∧
q
⇔
q
∧
p
p
∨
q
⇔
q
∨
p

p
⇔
q
⇔
q
⇔
p

Prawa łączności(podobnie
dla alternatywy oraz
równoważności
p
∧
q
∧
r
⇔
p
∧
q
∧
r
Prawa rozdzielności
p
∧
q
∨
r
⇔
p
∧
q
∨
p
∧
r

p
∨
q
∧
r
⇔
p
∨
q
∧
p
∨
r

Prawa de'Morgana
¬
p
∧
q
⇔¬
p
∨¬
q
¬
p
∨
q
⇔¬
p
∧¬
q
Prawo odrywania
p
∧
p
⇒
q
⇒
q
Prawo odrzucania

p
⇒
q
∧¬
q
⇒¬
p
Prawa sylogizmu

p
⇒
q
⇒[
q
⇒
r
⇒
p
⇒
r
]

q
⇒
r
⇒[
p
⇒
r
⇒
p
⇒
r
]

p
⇒
q
∧
q
⇒
r
⇒
p
⇒
r

Prawa osłabiania
p
∧
q
⇒
p
p
∧
q
⇒
q
p
⇒
p
∨
q
q
⇒
p
∨
q
Prawa definiowania

p
⇒
q
⇔¬
p
∨
q

p
⇔
q
⇔
p
⇒
q
∧
q
⇒
p


p
⇔
q
⇔
p
∧
q
∨¬
p
∧¬
q

p
∧
q
⇔¬
p
⇒¬
q

Definicje równoważności formuł i stosunku wynikania w KRZ.
Def.
Formuła
A
jest logicznie równoważna formule
B
w KRZ, jeśli dla każdego wartościowania
w
zachodzi
w

A
=
w

B

Def.
Mówimy, że formuła
A
wynika logicznie z formuł
A
1,

,A
n
w KRZ, jeżeli
nie
istnieje wartościo-
wanie
w
takie, że
w

A
1
==
w

A
n
=1
, natomiast
w

A
=0
Wynikanie a tautologie.
Tw.
Jeśli
A
wynika logicznie z
A1,
...
,An
w KRZ oraz
A
1,

,A
n
są tautologiami KRZ, to
A
też
jest tautologią KRZ.
Semantyczne twierdzenie o podstawianiu dla KRZ.
Lemat (o podstawianiu w KRZ).
Dla dowolnych
A,B
∈
FOR
,
p
∈
V
oraz wartościowania
w
:
w

A
[
p
/
B
]=
w
[
p
/
w

B
]
A

Tw.
Dla wszystkich
A,B
∈
FOR
,
p
∈
V
, jeśli
A
jest tautologią KRZ, to
A
[
p
/
B
]
też jest tautolo-
gią KRZ.
Aksjomatyczny system KRZ.
Aksjomaty systemu KRZ:
A1
Prawo poprzednika
A
⇒
B
⇒
A

A2
Prawo Frege'go
[
A
⇒
B
⇒
C
]⇒[
A
⇒
B
⇒
A
⇒
C
]
A3
Odwrotne prawo
transpozycji
¬
B
⇒¬
A
⇒
A
⇒
B

A4
Prawo symplifikacji
A
∧
B
⇒
A
A5
j.w.
A
∧
B
⇒
B
A6
Prawo mnożenia
następników

A
⇒
B
⇒[
A
⇒
C
⇒
A
⇒
B
∧
C
]
A7
Prawo addycji
A
⇒
A
∨
B
A8
j.w.
B
⇒
A
∨
B
A9
Prawo dodawania
poprzedników

A
⇒
C
⇒[
B
⇒
C
⇒
A
∨
B
⇒
C
]
A10

A
⇔
B
⇒
A
⇒
B

A11

A
⇔
B
⇒
B
⇒
A

A12

A
⇒
B
⇒[
B
⇒
A
⇒
A
⇔
B
]
Jedyna reguła dowodowa – modus ponens
A
A
⇒
B
B
Def
. Dowodem formuły A w systemie KRZ ze zbioru założeń
X
⊂
FOR
nazywamy ciąg formuł
A
1,

,A
n
,
n
≥1
, taki że
A
n
≡
A
oraz dla każdego
i
=1,
,n
zachodzi(przynajmniej) jeden z wa-
runków:
a)
A
i
jest aksjomatem systemu,
b)
A
i
∈
X
,
c) istnieją
0
j
,
k

i
, takie że
A
j
≡
A
k
⇒
A
i
tzn.
A
i
jest wnioskiem z
A
j
i
A
k
w oparciu o regułę MP.
Mówimy, że formuła
A
jest kosekwencją zbioru
X
w systemie KRZ, jeżeli istnieje dowód
A
w KRZ
ze zbioru
X
; piszemy wówczas:
X
⊢
KRZ
A
Oznaczamy
Cn
KRZ

X
={
A
∈
FOR
:
X
⊢
KRZ
A
}
.
Formułę
A
nazywamy tezą systemu KRZ, jeżeli:
∅
⊢
KRZ
A
piszemy wtedy
⊢
KRZ
A
Definicje termów i formuł języka elementarnego.
i. Każda zmienna indywiduowa i stała indywiduowa jest termem
ii. Jeśli

1
,

,

n
są termami, to
F
n

1
,

,

n

jest termem (dla dowolnych n i k)
iii. Nie ma innych termów poza zmiennymi indywiduowymi, stałymi indywiduowymi i takimi, które po-
wstają na mocy reguły (ii)
Formułą zdaniową atomową jest każde wyrażenie postaci
P
n

1
,

,

n

, gdzie

1
,

,

n
są dowolnymi
termami
i. Każda formuła zdaniowa atomowa jest formułą zdaniową rachunku predykatów.
ii. Jeśli

,

są formułami zdaniowymi języka rachunku predykatów to
¬
,
∧
,
∨
,
⇔
,
⇒
,
∀
x
i

i
∃
x
j

są formułami zdaniowymi języka ra-
chunku predykatów
iii. Nie ma innych formuł zdaniowych języka rachunku predykatów poza formułami atomowymi i takimi
formułami, które powstają dzięki zastosowaniu reguły (ii)
Definicja podstawiania w języku elementarnym.
Niech

,
∈
TER
L
,
x
∈
Var
,
A
∈
FOR
L
.
Definiujemy
[
x
/]
,
A
[
x
/]
– wynik podstawienia termu

do, odpowiednio, termu

i for-
muły
A
.
a)
y
[
x
/]≡
{

x
=
y
b)
c
[
x
/]≡
c
dla
c
∈
Con
L
c)
f

1
,

,

n
[
x
/]≡
f

1
[
x
/]
,

,

n
[
x
/]
y x
≠
y
d)
R

1
,

,

n
[
x
/]≡
R

1
[
x
/]
,

,

n
[
x
/]
e)
¬
A
[
x
/]≡¬
A
[
x
/]
f) Dla
@
∈{∧
,
∨
,
⇒
,
⇔}:

A@B
[
x
/]≡
A
[
x
/]
@

B
[
x
/]
g) Dla
Q
∈{∀
,
∃}
:

Qy

A
[
x
/]≡
{

Qy

A
:
x
=
y

Qy

A
[
x
/]:
x
≠
y
[
x
1
/
1
,

,x
n
/
n
]≡[
x
1
/
y
1
][
x
n
/
y
n
][
y
1
/
1
][
y
n
/
n
]
, gdzie
y
1
,

, y
n
są zmiennymi nie występują-
cymi w
A,

1
,

,

n
oraz wśród
x
1
,

,x
n
Definicja i przykłady podstawialności.
Term

jest podstawialny za zmienną
x
do formuły
A
(Podstawienie
[
x
/]
jest dopuszczalne dla
formuły
A
), jeśli żadne wolne wystąpienie zmiennej
x
w
A
nie znajduje się w zasięgu kwantyfika-
tora wiążącego którąkolwiek ze zmiennych występujących w

Aksjomatyczny system FOL.
L – ustalony język
Aksjomaty logiczne:
- prawa podstawiania:
(L1)
∀
xA
⇒
A
[
x
/
t
]
(L1')
A
[
x
/
t
]⇒∃
xA
dla wszystkich formuł
A
, termów
t
i zmiennych
x
, pod warunkiem, że term
t
jest podstawialny
za
x
w
A
- prawa dołączania kwantyfikatorów:
(L2)
∀
x

A
⇒
B
⇒
A
⇒∀
xB

- dla wszelkich formuł
A
,
B
i zmiennej
x
pod warunkiem, że
x
nie jest wolne w
A
(L2')
∀
x

A
⇒
B
⇒∃
xA
⇒
B

- dla wszelkich formuł
A
,
B
i zmiennych x takich, że nie jest wolne
w
B
- prawa KRZ:
(L3) wszystkie formuły języka
L
powstające z tautologii KRZ prezz podstawienie formuł języka
L
za
zmienne zdaniowe
Reguły dowodzenia:
-
reguła odrywania (Modus Ponens = MP)
A
⇒
B
A
-
reguła generalizacji (GEN)
B
A
∀
x A
dla wszelkich formuł
A
,
B
i zmiennych
x
Definicja dowodu, stosunku konsekwencji i tezy dla systemu FOL.
Def.
Dowodem formuły A w systemie KRL, ze zbioru założeń
X
⊂
FOR
L
nazywamy ciąg formuł
A
1
,

,A
n
,n
≥1
, taki że
A
≡
A
n
oraz dla każdego
i
=1,
,n
zachodzi przynajmniej jeden z warun-
ków:
a)
A
i
jest aksjomatem systemu KRL
b)
A
i
∈
X
c)isteniją
j
0
,
k
1
, takie że
A
j
≡
A
k
⇒
A
i
d)istnieje
j

i
oraz
x
∈
Var
, takie że
A
i
≡∀
x

A
j
Mówimy, że formuła
A
jest konsekwencją zbioru
X
w systemie KRL(symbolicznie
X
⊢
KRL
A
), jeśli
istnieje dowód formuły
A
w systemie KRL, ze zbioru
X
.
Symbolem
Cn
KRL

X

oznaczać będziemy zbiór wszystkich konsekwencji zbioru
X
w systemie KRL
Prawa rozdzielności kwantyfikatorów (pełne i niepełne).
Prawo rozdzielności dużego
kwantyfikatora względem koniunkcji
∀
x
[
x
∧
x
]⇔∀
x

x
∧∀
x

x

Prawo rozdzielności małego
kwantyfikatora względem
alternatywy
∃
x
[
x
∨
x
]⇔∃
x

x
∨∃
x

x

Prawo rozdzielności dużego
kwantyfikatora względem
alternatywy
UWAGA: Kwantyfikator duży
nie
jest w tym przypadku
rozdzielny!
∀
x

x
∨∀
x

x
⇒∀
x
[
x
∨
x
]
Prawo rozdzielności małego
kwantyfikatora względem koniunkcji
UWAGA: Kwantyfikator duży
nie
jest w tym przypadku
rozdzielny!
∃
x
[
x
∧
x
]⇒∃
x

x
∧∃
x

x

Prawo rozdzielności dużego
kwantyfikatora względem implikacji
∀
x
[
x
⇒
x
]⇒[∀
x

x
⇒∀
x

x
]
Prawo rozdzielności małego
kwantyfikatora względem implikacji
∀
x
[
x
⇒
x
]⇒[∃
x

x
⇒∃
x

x
]
(Brak nazwy)
∀
x
[
x
⇔
x
][∀
x

x
⇔∀
x

x
]
(Brak nazwy)
∀
x
[
x
⇔
x
][∃
x

x
∃
x

x
]
Prawa De Morgana i prawa ekstensjonalności dla kwantyfikatorów.
Prawa De Morgana
¬∀
x

x
⇔∃
x
¬
x

  [ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • emaginacja.xlx.pl

    •