Tautologie rachunku zdań

Wartościowanie - Dowolne podporządkowanie wartości logicznych zmiennym zdaniowym

Tautologia - Schemat zdaniowy przyjmujący wartość 1 przy każdym wartościowaniu. Schemat zdania zawsze prawdziwego

Prawa:

Prawa przemienności

1. p∨q ⇔ q∨p

2. p∧q ⇔ q∧p

Prawa łączności

3. (p∧q)∧r ⇔ p∧(q∧r)

4. (p∨q)∨r ⇔ p∨(q∨r)

5. [(p⇔q)⇔r] ⇔ [p⇔(q⇔r)]

Prawa rozdzielności

6. p∧(q∨r) ⇔ (p∧q)∨(p∧r)

7. p∨(q∧r) ⇔ (p∨q)∧(p∨r)

Prawa de Morgana

8. ­­­­­­­¬(p∧q) ⇔ ¬p∨¬q

9. ¬(p∨q) ⇔ ¬p∧¬q

Prawo eksportacji-importacji

10. (p∧q⇒r) ⇔ [p⇒(q⇒r)]

Prawa indentpotentności

11. p∧p ⇔ p

12. p∨p ⇔ p

Prawo transpozycji

13. (p⇒q) ⇒ (¬q⇒¬p)

Prawo sylogizmu warunkowego

14. (p⇒q)∧(q⇒r) ⇒ (p⇒r)

Prawa definiowania

15. (p⇒q) ⇔ ¬p∨q

16. (p⇔q) ⇔ (p⇒r)∧(q⇒p)

Prawa LPR - definicja, przykłady

Prawem LPR w danym języku nazywamy formuły tego języka, które są prawdziwe przy wszystkich interpretacjach tego jęz. i wartościach zmiennych wolnych.

Ważniejsze prawa:

Przestawiania kwantyfikatorów

∧_x ∧_y P(x,y) ↔ ∧_y ∧_x P(x,y)

∨_x ∨_y P(x,y) ↔ ∨_y ∨_x P(x,y)

∨_x ∧_y P(x,y) → ∧_y ∨_x P(x,y)

Rozdzielności kwantyfikatorów

∧_x ( P(x) ∧ Q(x) ) ↔ ∧_x P(x) ∧ ∧_x Q(x)

Niepełne rozdzielczości

∧­_x P(x) ∨ ∧_x Q(x) → ∧_x (P(x) ∨ Q(x))

∨_x (P(x) ∧ Q(x)) → ∨_x P(x) ∧ ∧∨_x Q(x)

Kwantyfikatory przy implikacji

∧_x (P(x) → Q(x)) → (∧_x P(x) → ∧_x Q(x))

∧_x (P(x) → Q(x)) → (∨_x P(x) → ∨_x Q(x))

De Morgana dla kwantyfikatorów

¬∧_x P(x) ↔ ∨_x ¬P(x)

¬∨_x P(x) ↔ ∧_x ¬P(x)

Wyłączania kwantyfikatorów przed nawias (Q nie zależy od x)

∧_x P(x) ∧ Q ↔ ∧_x (P(x)∧Q)

∨_x P(x) ∧ Q ↔ ∨_x (P(x)∧Q)

∧_x P(x) ∨ Q ↔ ∧_x (P(x)∨Q)

∨_x P(x) ∨ Q ↔ ∨_x (P(x)∨Q)

Definicja zbioru potęgowego, przykłady

Dla każdego zbioru A istnieje zbiór wszystkich podzbiorów zb. A

∧_A∨_X∧_Y (Y∈X⇔Y⊂A

P(A)={Y : Y⊂A)

Np. P({a})={{a},∅}

P(∅)={∅}

P({a,b})={∅,{a},{b},{a,b}}

Tw. Jeżeli zb. A ma n elementów, to zb. potęgowy zbioru A ma 2ⁿ elementów.

Iloczyn kartezjański, podstawowe prawa

Dla zbiorów A i B określamy zbiór

A x B = { (x,y) : x ∈ A ∧ y ∈ B }

Prawa:

1. Ax∅ = ∅xA = ∅

2. Na ogół AxB ≠ BxA

3. (A∪B)xC = (AxC)∪(BxC)

4. (A∩B)xC = (AxC)∩(BxC)

5. (A-B)xC = (AxC)-(BxC)

6. Ax(B∪C) = (AxB)∪(AxC)

7. Ax(B∩C) = (AxB)∩(AxC)

8. Ax(B-C) = (AxB)-(AxC)

Relacje równoważności, klasy abstrakcji, zasada abstrakcji

Def. Relację R⊂A² nazywamy relacją równoważności zbioru U jeżeli :

1) R jest zwrotna ∧_x∈U x R x

2) R jest symetryczna ∧_x,u∈U ( x R y → y R x )

3) R jest przechodnia ∧_x,y,z∈U (x R y ∧ y R z → x R z )

Przykłady

x R y ↔ x = y ; R⊆U² → R = I­_U najmniejsza relacja w zbiorze U

R = U² = U x U relacja totalna na zbiorze U

Klasy abstrakcji relacji równoważności

Niech R będzie relacją równoważności na zbiorze U

Dla każdego elementu a∈U określony zbiór
[a]_R = { b ∈ U : a R b }

Nazywamy klasą abstrakcji relacji R wyznaczoną przez element a

Przykład

na zbiorze {-3,-2,-1,0,1,2,3} x R y ↔ |x| = |y|

[0]_R = { 0 }

[1]_R = {1,-1} = [-1]_R

[2]_R = {2,-2} = [-2]_R

[3]_R = {3,-3} = [-3]_R

Zasada abstrakcji

Jeżeli R jest relacją równoważności na zb. A, to zbiór A/R jest podziałem zb. A.

Poprawne schematy wnioskowania rachunku zdań

Poprawny schemat wnioskowania (logiczna reguła wnioskowania) - wniosek wynika z przesłanek na gruncie KRZ nie istnieje takie wartościowanie,

przy którym wszystkie przesłanki są prawdziwe, a wniosek fałszywy

Prawa:

(p⇒q)∧p⇒q - reguła odrywania

(p⇒q)∧(q⇒r)⇒(p⇒r) - reg. Sylogizmu warunkowego

(p∨q)∧(p⇒r)∧(q⇒r)⇒r - reg. Eliminacji alternatywy

(p∨q)∧(¬p)⇒q - reg. Otrzymywania dla alternatywy

(p⇒q)∧(q⇒p)⇒(p⇔q) - reg. Wprowadzania równoważności

Aksjomaty systemu LPR

(A₀) wszystkie formy jezyka elementarnego, które są podstawieniami tautologi KRZ

(A₁) ∧_x A → A[x/t]

(A₁`) A[x/t] → ∨_x A

(A₂) ∧_x (A→B) → (∧_x A → ∧_x B)

(A₂`) ∧_x (A→B) → (∨_x A → ∨_x B)

(A₃) A → ∧_x A

(A₃`) ∨_x A → A

(A₁)(A₁`) -prawa podstawiania

(A₂)(A₂`) -prawa rozstawiania kwantyfikatorów przy implikacji

(A₃)(A₃`) -prawa zbytecznych kwantyfikatorów

Relacje, dziedzina, przeciwdziedzina, relacja odwrotna, złożenie relacji

Relacją n - wyrazową nazywany dowolny zbiór, którego elementami są n-wyrazowe układy uporządkowane.

Dziedziną R nazywamy zbiór DR = { x ∈ A : ∨_y∈B ( x,y ) ∈ R }

Przeciwdziedziną relacji R nazywamy zbiór D*R = { y∈B : ∨_x∈A ( x , y ) ∈ R }

Odwrotność relacji R^-1 = { ( y , x ) : ( x , y ) ∈R }
R^-1 relacja odwrotna do relacji R
Przykład:
R = { (0,1) , (1,2) } ; R^-1 = { (1,0), (2,1) }
R = { (x,y)∈R² : x<y } ; R^-1 = { (y,x)∈R² : x<y } = {(x,y) ∈R y<x }

Złożenie (superpozycja) relacji

S ∘ R = { ( x , y ) : ∨_z ( ( x , z ) ∈ R ∧ ( z , y ) ∈ S ) }

Przykład

R = { ( 0,1 ) , ( 1,2 ) } ; S = { ( 1,0 ) , ( 2,3 )}

S ∘ R = { (0,0 ) , ( 1,3 ) } ; R ∘ S = { ( 1,1 ) }

Na ogół S ∘ R ≠ R ∘ S

Relacje porządkujące i liniowo porządkujące

Relację R⊂A² nazywamy relacją częściowo-porządkującą na zb. A, jeżeli jest zwrotna, słabo-antysymetryczna i przechodnia.

Relację R⊂A² nazywamy r. liniowo-porządkującą na zb. A, jeżeli jest zwrotna, słabo-antysymetryczna, przechodnia i spójna.

Koniunkcyjna i alternatywna postać normalna

Formuła w alternatywnej postaci normalnej (apn) - alternatywa skończenie wielu koniunkcji elementarnych

K₁∨K₂∨...∨K_n

Formuła w koniunkcyjnej postaci normalnej (kpn) - koniunkcja skończenie wielu alternatyw elementarnych

A₁∧A₂∧...∧A_n

Arytmetyka Peano

Język: =², +², ∗² - symbole relacyjne

S¹ - symbol funkcyjny

0 - stała przedmiotowa

S(n) = n+1

Aksjomaty równości Aksjomaty następnika Aksjomaty mnożenia

(R1) x = x (P1) ¬S(x) = 0 (P5) x ∗ 0 = 0

(R2) z = y => y = x (P2) S(x) = S(y) => x = y (P6) x ∗ S(y) = x ∗ y + x

(R3) (x = y)∧(y = z) => (x = z) Aksjomaty dodawania Aksjomat indukcji matematycznej

(R4) (x = y) => S(x) = S(y) (P3) x + 0 = x (P7) A[x/0]∧ ^_x(A=>A[x/S(x)])=> ^_xA

(P4) x + S(y) = S(x + y)

Definicja i podstawowe własności stosunku zawierania zbiorów

Stosunek inkluzji

Def.

A ⊆ B ↔ ∧_x ( x ∈ A → x ∈ B)

Zbiór A jest zawarty w zbiorze B (A⊆B), jeżeli każdy element zbioru A jest elementem zbioru B

Własności stosunków zawierania

1) A ⊆ A zawartość

2) A ⊆ B ∧ B ⊆ A → A = B antysymetria

3) A ⊆ B ∧ B ⊆ C → A ⊆ C przechodniość

4) ^_A (∅⊂A)

Funkcje jako relacje

Relację R nazywamy funkcją jeżeli spełnia warunek prawostronnej jednoznaczności:

∧_x,y1,y2 ( x R y₁ ∧ x R y₂ → y₁ = y₂ )

Def. Mówimy, że f jest funkcją ze zbioru A w zbiór B (f: A→B) jeżeli spełnione są warunki:

1. f jest funkcją

2. D_f = A

3. D*f ⊂ B

Def. Funkcję f nazywamy różnowartościową ( wzajemnie jednoznaczną ) jeżeli :
∧_x1,x2 ( f(x₁) ∧ f(x₂) → x₁ = x₂ )

Stosunek równoliczności zbiorów i jego własności

Def. Zbiór X jest równoliczny ze zb. Y wtw., gdy istnieje bijekcja zb. X na zb. Y

X|_rY ∨_f X _1-1→^”na” Y

Np. N~{n∈N : n ≥ 10}

{x∈Z : x ≥ 0}~{x∈Z : x ≤ 0}

Relacja równoliczności jest relacją równoważności.

Def. Rodzinę wszystkich zbiorów równolicznych ze zb. X nazywamy mocą zb. X i oznaczamy ⁼X.

Def. Zb. X nazywamy skończonym wtw., gdy jest pusty lub dla każdego el. x∈X, zbiory X i X\{x} nie są równoliczne.

Zbiory, które nie są skończone nazywamy nieskończonymi.

Aksjomatyczny system rachunku zdań.

Def. System posługujący się aksjomatami i zbiorem udowodnionych zdań, uznanych za prawdziwe, a wyprowadzonych właśnie z tych aksjomatów.

Aksjomaty implikacji: (A1) p=>(q=>p) (A2) [p=>(q=>r)]=>[(p=>q)=>(p=>r)]

Aksjomat negacji: (A3) [¬q=>¬p]=>(p=>q)

Aksjomaty koniunkcji: (A4) p∧q=>p (A5) p∧q=>q (A6) (p=>q)=>[(p=>r)=>(p=>q∧r)]

Aksjomaty alternatywy: (A7) p=>p∨q (A8) q=>p∨q (A9) (p=>r)=>[(q=>r)=>(p∨q=>r)]

Aksjomaty równoważności: (A10) (p⇔q)=>(p=>r) (A11) (p⇔q)=>(q=>p) (A12) (p=>q)=>[(q=>p)=>(p⇔q)]

Metoda tablic analitycznych dla LPR

MTA to dowodzenie A przez odrzucanie. Gałąź nazywamy sprzeczną jeśli zawiera parę sprzecznych formuł, drzewo nazywamy zamkniętym jeśli każda gałąź jest zamknięta. Dowód formuły A to drzewo zamknięte, którego korzeń oznaczony jest przez A. Stosuje się reguły dowodzenia.

Definicje działań na zbiorach i prawa algebry zbiorów.

Algebra zbiorów

Działania:

Suma : x∈ A ∪ B ↔ x ∈ A ∨ x ∈ B

Iloczyn: x∈ A ∩ B ↔ x ∈ A ∧ x ∈ B

Różnica : x∈ A - B ↔ x ∈ A ∧ ¬ x ∈ B

Prawa

De Morgana A - (B ∪ C) = (A - B) ∩ (A - C) ; A - (B ∩ C) = (A - B) ∪ (A - C)

Dla różnicy (A-B)-C = A-(B∪C) ; A-(B-C) = (A-B)∪(A∩C) ; (A∪B)-C = (A-C)∪(B-C)

Dla sumy i iloczynu A⊂B∪A ; B⊂B∪A ; A⊂C∧B⊂C => A∪B⊂C ; A∩B⊂A ; A∩B⊂B ; C⊂A∧C⊂B => C⊂A∩B

Przykład dowodu założeniowego

(T3) (p=>q)=>[(q=>r)=>(p=>r)]

1. p=>q zał.

2. q=>r zał.

3. p zał.

4. MP (1,3) q

5. MP (2,4) r

Antynomia Russell'a

Nie istnieje zbiór wszystkich zbiorów

W(x) ≡ X∉X

Tworzymy zbiór R={x : X∉X}

^y (Y∈R⇔Y∉R)

Y/R (R∈R) ⇔ (R∉R)

Aksjomaty algebry Boole'a

(B1) A ∪ B = B ∪ A (B1`) A ∩ B = B ∩ A

(B2) (A ∪ B) ∪ C = A ∪ (B ∪ C) (B2`) (A ∩ B) ∩ C = A ∩ (B ∩ C)

(B3) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (B3`) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

(B4) A ∪ Ř = A (B4`) A ∩ U = A

(B5) A ∪ -A = U (B5`) A ∩ -A = Ř

Obraz, przeciwobraz i prawa

Dla A⊂X określamy:

f[A] = { y ∃x (x∈A ∧ y=f(x)} = {f(x) x∈A} f[A] nazywamy obrazem zb. A danym przez funkcję f.

Dla B⊂Y określamy:

f ^-1[B] = {x∈X : f(x)∈B} f ^-1[B] nazywamy przeciwobrazem zb. B danym przez funkcję f.

Np. f : R→R f(x)=x²

A = {x∈R : -1≤ x ≤1}

Prawa:

f [A₁∪A₂] = f [A₁] ∪ f [A₂]

f [A₁∩A₂] ⊂ f [A₁] ∩ f [A₂]

f ^-1[B₁ ∪/∩ B₂] = f ^-1[B₁] ∪/∩ f ^-1[B₂]

f ^-1[B'] = f ^-1[B]'

Aksjomat ekstensjonalności i jego zastosowania

Def. Jeżeli zbiory mają te same elementy to są równe.

^z (z∈X ⇔ z∈Y) => X=Y

Np.

A={x : x∈R ∧ x>0} B={x : x∈R ∧ x³>0}

A=B

Para uporządkowana i lemat o parach uporządkowanych

Def.

( a , b ) = { {a} , {a,b} } para uporządkowana elementów a i b

Lemat o parach uporządkowanych

( a , b ) = ( c , d ) ↔ a = c ∧ b = d

Wniosek : a ≠ b → ( a , b ) ≠ ( b , a )

Typy relacji na zbiorze A

Def. Relację R ⊆ A² nazywamy relacją w zbiorze A

Piszemy x R y zamiast ( x,y ) ∈ R

Relację R w zbiorze A nazywamy
zwrotną, jeżeli ∧_x∈A x R x
symetryczną, jeżeli ∧_{x,y ∈A} ( x R y → y R x )
przechodnią, jeżeli ∧_x,y,z∈A (x R y ∧ y R z → x R z )
przeciwzwrotną, jeżeli ∧_x∈A ¬ x R x
przeciwsymetryczną, jeżeli ∧_{x,y ∈A} ( x R y → ¬ y R x )
(słabo) antysymetryczną, jeżeli ∧_{x,y ∈A} ( x R y ∨ y R x → x = y)
spójną, jeżeli ∧_x,y∈A ( x R ∨ y R x )
ostro spójną, jeżeli ∧_x,y∈A (x R y ∨ x = y ∨ y R x )

Zbiory mocy χ₀ i mocy continuum

Zb. X jest mocy χ₀ wtw., gdy X jest zbiorem wszystkich wyrazów pewnego nieskończonego ciągu (bez powtórzeń).

Zbiory mocy χ₀ to: N (naturalne), Z (całkowite), Q (wymierne), bo są równoliczne ze zbiorem liczb naturalnych

Zbiory mocy continuum: R (rzeczywiste), (0,1), (-1/2,1/2)

---