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)

Zbiory mocy c0 i mocy continuum

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

Zbiory mocy c0 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)

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 )

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 2n 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ÌA2 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ÍU2 ® R = I­U   najmniejsza relacja w zbiorze U

R = U2 = 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 «...