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 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 « |x| = |y|

[0]R = { 0 }

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

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

[3]R...