UTF-8''LOG_110_zagadnienia_i_opracowanie(FINAL).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:

Prawo poprzednika A ⇒ B ⇒ A 

Prawo Frege'go

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

Odwrotne prawo

transpozycji

¬ B ⇒¬ A ⇒ A ⇒ B 

Prawo symplifikacji A ∧ B ⇒ A

j.w.

A ∧ B ⇒ B

Prawo mnożenia

następników

 A ⇒ B ⇒[ A ⇒ C ⇒ A ⇒ B ∧ C ]

Prawo addycji

A ⇒ A ∨ B

j.w.

B ⇒ A ∨ B

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 ⇒ 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

- reguła generalizacji (GEN)

∀ 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 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: