wyklad 07, AGH, WFiIS, Informatyka stosowana, Semestr I, matma dyskretna-misztal, wyklad
[ Pobierz całość w formacie PDF ]
Wprowadzeniedologiki
napodstawie”Slides
c
2005,2010byM.J.Golin,G.Trippen”
Wykład7
24kwietnia2012
(Wykład7)
Wprowadzeniedologiki
24kwietnia2012 1/14
Outline
1
Równowa»no±¢zda«
2
Tablicaprawdy
3
PrawaDeMorgana
4
Implikacja
5
Równowa»no±¢
(Wykład7)
Wprowadzeniedologiki
24kwietnia2012 2/14
Równowa»no±¢zda«
Merge-sort-fragment
1:
if
((i+j
6
p+q)&&(i
6
p)&&((j
>
q)jj(L[i]
6
R[i])))
then
2:
A[k]=L[i]
3:
i i+1
4:
else
5:
A[k]=R[i]
6:
j
j
+
1
Merge-sort-fragment
1:
if
((i+j
6
p+q)&&(i
6
p)&&(j
>
q))jj((i+j
6
p+q)&&(i
6
p
)
&&
(
L
[
i
]
6
R
[
i
])))
then
2:
A[k]=L[i]
3:
i
i
+
1
4:
else
5:
A[k]=R[i]
6:
j j+1
(Wykład7)
Wprowadzeniedologiki
24kwietnia2012 3/14
Równowa»no±¢zda«
Czyzdanias¡równowa»ne?
(a)
((i+j
6
p+q)&&(i
6
p)&&((j
>
q)jj(L[i]
6
R[i])))
(b)
((i+j
6
p+q)&&(i
6
p)&&(j
>
q))jj((i+j
6
p+q)&&(i
6
p)&&(L[i]
6
R[i])))
Przepiszmyje,korzystaj¡cznast¦puj¡cejnotacji:
s(i+j
6
p+q)
,
t(i
6
p)
,
u(j
>
q)
,
v
(
L
[
i
]
6
R
[
i
])
.
(a)sandtand(uorv)
(b)(sandtandu)or(sandtandv)
Oznaczmyw
(sandt),czyli
(a)wand(uorv)
(b)(wandu)or(wandv).
Przetłumaczyli±myfragmentalgorytmunasymbolicznezdanie
zło»one.Jakokre±li¢czyzdania(a)i(b)s¡równowa»ne?
(Wykład7)
Wprowadzeniedologiki
24kwietnia2012 4/14
Równowa»no±¢zda«
s,t,u,w,v-zmienne.
^
-and,koniunkcja.
_
-or,alternatywa.
L
-exclusiveor,alternatywawykluczaj¡ca.
:
-not.
(,)-nawiasy.
Zmienne/zdanias,tmog¡by¢alboprawd¡albofałszem.
s
^
t
-jestprawd¡,je»elisits¡prawd¡.
s
_
t
-jestprawd¡,je»eliprzynajmniejjednazezmiennychslubtjest
prawd¡.
s
L
t
-jestprawd¡je»elidokładniejednazezmiennychslubtjest
prawd¡.
:
s
-jestprawd¡,je»elisjestfałszem.
Jakobliczy¢czyzdanie(a)
w
and
(u
or
v)!w^(u_v)
jest
prawd¡czyfałszemijakwykaza¢,»ejestrównowa»neinnemuzdaniu
(b)
(
w
and
u
)
or
(
w
and
v
)!(
w
^
u
)_(
w
^
v
)
?
(Wykład7)
Wprowadzeniedologiki
24kwietnia2012 5/14
[ Pobierz całość w formacie PDF ]
