Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 11
Logika
lub to
1 Ä… 4 " Ä…=2 Ä…=3 . Jeżeli Ä…=2 á=3 , nieprawda, że á=3 .
3 1 2 "
StÄ…d Ä…`"2 Ä…=2 Ä…=3 Ò! Ä…=3, á=2
, lub
4 á 3 "
2 4 1 3
·Ä…Ò! ¸Ä… ,Ź¸Ä… ·Ä…("¸Ä… , Ź·Ä…
, - schematy wynikania
Ź·Ä… ¸Ä…
Każdy osioł ma 4 nogi
Sokrates nie ma 4 nóg rozumowanie poprawne
Sokrates nie jest osłem
Każdy osioł ma 4 nogi
Sokrates nie jest osłem rozumowanie niepoprawne
Sokrates nie jest osłem
·Ä…("¸Ä…("Ä…Ä… ,Ź·Ä…
·Ä…("¸Ä…("Ä…Ä… ,Ź·Ä… , Ź¸Ä…
= ¸Ä…("Ä…Ä… , Ź¸Ä… - schematy wynikania
Ä…Ä…
Ä…Ä…
p Ź p
0 1
1 0
Koniunkcja:
p q p'"q
0 0 0
0 1 0
1 0 0
1 1 1
Alternatywa:
p q p("q
0 0 0
0 1 1
1 0 1
1 1 1
Implikacja:
p q p Ò! q
0 0 1
0 1 1
1 0 0
1 1 1
Jeżeli suma kątów w trójkącie wynosi to suma kątów w czworokącie wynosi  1
179o 358o
Jeżeli Paryż jest stolicą Francji to Warszawa leży nad Sekwaną  0
Ò!
63 dzieli siÄ™ przez 7 64 dzieli siÄ™ przez 8  1  Implikacja - tak, wynikanie  nie
Równoważność:
p q p Ô! q
0 0 1
0 1 0
1 0 0
1 1 1
Reguły wnioskowania, tautologie, metoda zerojedynkowa
·Ä…("¸Ä… , Ź·Ä…
- nad kreską przesłanki, pod kreską wniosek
¸Ä…
·Ä…1 ,·Ä…2 ,... , ·Ä…n
Ogólnie regułą wnioskowania nazywamy schemat taki, że z prawdziwości
¸Ä…
·Ä…1 ,·Ä…2 ,... , ·Ä…n
·Ä…1 , ·Ä…2 ,... , ·Ä…n
¸Ä…
wynika prawdziwość . Innymi słowy jest regułą
¸Ä…
wnioskowania (=poprawnym schematem wnioskowania), wtedy i tylko wtedy, gdy
śą·Ä…1 , ·Ä…2 , ...·Ä…nźąÔ! ¸Ä…
przyjmuje zawsze wartość 1.
·Ä… , ·Ä…("śąŹ¸Ä…źą , śą·Ä…Ò! ¸Ä…źąÒ! Ä…Ä…
Formuła rachunku zdań (np. itp.) jest tautologią, jeśli dla
dowolnej wartości zmiennych (0 lub 1) formuła przyjmuje wartość 1.
p("q ,Ź p
Sprwdz
my, czy jest poprawnym schematem wnioskowania. Tzn. czy
q
[śą p("qźą'"Ź p]Ò!q
jest tautologiÄ….
I Metoda: tabelka zerojedynkowa:
p q p("q Ź p śą p("q źą'"śąŹ pźą [śą p("qźą'"śąŹ pźą]Ò!q
0 0 0 1 0 1
0 1 1 1 1 1
1 0 1 0 0 1
1 1 1 0 0 1
II Metoda:
Załóżmy, że formuła ta może być fałszywa,
[śą p("qźą'"śąŹ pźą]=1 q=0
tzn , a
śą p("q źą=1
Ź p=1
Sprzeczność
p=0
p("q=0
pÒ! q , Ź p
Czy jest poprawnym schematem?
Źq
3#"1001Ò!1001 3$"1001Ò!1001
NIE, np. jest złożona, nie jest złożona  błędne
wnioskowanie ponieważ 1001=7"11"13 .
[śą pÒ! qźą'"śąŹ p źą]Ò!Źq
Czy jest tautologiÄ…?
Źq q=1 śą p Ò! qźą=1 Ź p=1 p=0
p=0, q=1 daje wartość 0 więc nie jest tautologią
Dwie ważne tautologie:
Źśą p'"qźą Ò![śąŹ p źą("śąŹqźą]
- Prawa de Morgana
Źśą p("qźą Ò![śąŹ p źą'"śąŹqźą]
Kwantyfikatory
" x Aśą xźą - dla każdego zachodzi ( - odwrócone ALL)
x Aśą xźą "
" x Aśą xźą - istnieje takie, że zachodzi ( - odwrócone EXISTS)
x Aśą xźą "
" xśąO śą x źąŚąC śą xźąźą ,ŹC śąSokratesźą
gdzie C oznacza 4 nogi, a O osła.
ŹO śąSokratesźą
" x Aśą xźąÒ! " x Aśą xźą
Musimy zakładać, że uniwersum (=świat o którym mówimy) jest niepusty.
Aśą xźąÔ! x pierwsza dwucyfrowa
" x śą Aśą xźąÒ! Bśą xźąźą ,ŹAśąc źą
- niepoprawny, bo np. jeÅ›li Bśą xźąÔ! x jest nieparzyste
ŹB śącźą
c=3
" x [ x pierwsza dwucyfrowaÒ! x nieparzyste] ,Źśą3 pierwsza dwucyfrowaźą
Źśą3 nieparzysteźą
Z prawdziwych przesłanek wynika fałszywy wniosek więc schemat jest niepoprawny.
" x" y Rśą x , yźąÒ! " y " x Rśą x , yźą - niepoprawny, bo nie zachodzi dla
Rśą x , yźąÔ! x#"y
" x" y x#"yÒ!" y " x x#"y Rśą x , yźąÔ! x= y
mimo że zachodzi dla
" y" x Rśą x , yźąÒ! " x " y Rśą x , yźą - poprawny
" x" y " z śą x=z(" y=zźą - poprawny
" x " y " z śą x= z(" y=zźą - niepoprawny
Prawa de Morgana
Ź" x Aśą xźąÔ!" x ŹAśą xźą
Ź" x Aśą xźąÔ!" x ŹAśą xźą
Ź" x " y " z "tśą Ax , y , z , t źąÔ!" x " y" z " t ŹAśą x , y , z , tźą
Twierdzenie:
Gra dwuosobowa skończona, zdeterminowana, z pełną informacją, bez remisów zapewnia
strategię zwycięstwa jednego z graczy
"b1 " c1 "b2 " c2 ... "bn " cn Białe wygrywają
" b1 "c1 " b2 "c2 ... " bn "cn ~Białe wygrywają, tzn. czarne wygrywają