Elementy rachunku zdan i ...

Elementy rachunku zdan i kwantyfikatorów, studia, matematyka

[ Pobierz całość w formacie PDF ]
Elementyrachunkuzda«ikwantyfikatorów
IzoldaGorgol
wyci¡gzprezentacji
Zdaniawsensielogicznym
—
DEFINICJA
Zdaniewsensielogicznym
-zdanieoznajmuj¡ce,któremumo»naprzypisa¢jedn¡zdwóchwarto±ci-
prawdalubfałsz.Przyjmujemy,»esymbolemprawdyjest1,a0jestsymbolemfałszu.
—
DEFINICJA
Zmienn¡logiczn¡
nazywamyzmienn¡,wmiejscektórejwstawiamyzdania(prawdziwelubfałszywe),
otrzymuj¡czdaniawsensielogicznym.Najcz¦±ciejzmiennezdanioweoznaczamymałymiliterami:p,q,r,....
—Warto±¢logiczn¡zdaniapoznaczamysymbolemw(p):
w(p)=0–pjestzdaniemfałszywym
w(p)=1–pjestzdaniemprawdziwym
Funktoryzdaniotwórcze
Zezda«logicznychmo»emytworzy¢zdaniazło»oneprzypomocyspójnikówlogicznych(funktorówzdaniotwórczych)
oraznawiasów.
—negacja
niep
p ¬p
—koniunkcja
piq
p^q
—alternatywa
plubq
p_q
—implikacja
pimplikujeq
lub
je»elip,toq
p)q p!q
—równowa»no±¢
pjestrównowa»neq
lub
pwtedyitylkowtedy,gdyq
p,q p$q
–funktorjednoargumentowy
^,_,),,–funktorydwuargumentowe
Definicjewarto±ciowa«spójnikówlogicznych
w
(p)
w
(
p)
0 1
1 0
w
(
p
)
w
(
q
)
w
(
p^q
)
w
(
p_q
)
w
(
p)q
)
w
(
p,q
)
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1
Formułylogiczne
DEFINICJA
Formuł¡logiczn¡
nazywamywyra»eniezbudowanezezmiennychzdaniowych,funktorówzdaniotwór-
czychoraznawiasówwnast¦puj¡cyrekurencyjnysposób:
—zdaniaprosteizmiennezdaniowes¡formułamilogicznymi
—je»eliP iQs¡formułamilogicznymi,toP,(P^Q),(P_Q),(P)Q)oraz(P,Q)s¡równie»formułami
logicznymi.
Tautologie
DEFINICJA
Tautologi¡
lub
prawemrachunkuzda«
nazywamyformuł¦logiczn¡,którajestprawdziwabezwzgl¦du
nawarto±¢logiczn¡wyst¦puj¡cychwniejzmiennychzdaniowych.Ozn.t.
DEFINICJA
Zdaniemsprzecznym
nazywamyformuł¦logiczn¡,którajestfałszywabezwzgl¦dunawarto±¢logiczn¡
wyst¦puj¡cychwniejzmiennychzdaniowych.Ozn.f.
Niektóreprawarachunkuzda«
—prawaprzemienno±ci
—(p^q),(q^p)
1
—(p_q),(q_p)
—prawał¡czno±ci
—((p^q)^r),(p^(q^r))
—((p_q)_r),(p_(q_r))
—prawarozdzielno±ci
—((p^q)_r),((p_r)^(q_r))
—((p_q)^r),((p^r)_(q^r))
—prawaidempotentno±ci
—(p^p),p
—(p_p),p
—prawaidentyczno±ci
—(p^t),p
—(p^f),f
—(p_t),t
—(p_f),p
Niektóreprawarachunkuzda«–cd.
—(p),pprawopodwójnegoprzeczenia
—(p_p)prawowył¡czonego±rodka
—(p^p)prawosprzeczno±ci
—prawadeMorgana
—(p^q),(p_q)
—(p_q),(p^q)
—(p,q),((p)q)^(q)p))okre±lenierównowa»no±ci
—(p)q),(p_q)okre±lenieimplikacji
—(p)q),(p^q)zaprzeczenieimplikacji
—(p)q),(q)p)prawokontrapozycji
—[(p)q)^(q)r)])(p)r)prawosylogizmu
Implikacje
p)qimplikacjaprosta
q)pimplikacjaodwrotna
p)qimplikacjaprzeciwna
q)pimplikacjaprzeciwstawna.
Je»elipb¦dziemyuwa»a¢zazało»enie,aqzatez¦twierdzenia,tomamytwierdzenieproste,odwrotne,przeciwne
iprzeciwstawne.Napodstawieprawakontrapozycjitwierdzeniaprosteiprzeciwstawne(jakrównie»odwrotnei
przeciwne)s¡sobierównowa»neinatymfakcieopierasi¦metodadowodzenianiewprost.
Warunkikonieczneiwystarczaj¡ce
Ka»detwierdzeniematematycznemaposta¢implikacjilubrównowa»no±ci.Wformulep)q,pnazywamypoprzed-
nikiem,aqnast¦pnikiemimplikacji.
Wprzypadku,gdytwierdzeniemaposta¢implikacji(Je»eliZ,toT.),mówimy,»eZjest
warunkiemdostatecznym
(wystarczaj¡cym)
dlaT,za±Tjest
warunkiemkoniecznym
dlaZ.
Wprzypadku,gdytwierdzeniemaposta¢równowa»no±ci(Zwtedyitylkowtedy,gdyT.),mówimy,»eZ jest
warunkiemkoniecznymidostatecznym(wystarczaj¡cym)
dlaT(iodwrotnie).
Formyzdaniowe
DEFINICJA
Form¡zdaniow¡(funkcj¡zdaniow¡)
nazywamywyra»eniezawieraj¡cezmienn¡(zmienne),którestaje
si¦zdaniemwsensielogicznym,je»eliwmiejscezmiennej(zmiennych)podstawimynazw¦przedmiotu(ów).
Zka»d¡funkcj¡zdaniow¡zwi¡zanajestrodzinazbiorów,któres¡zakresamizmiennychwyst¦puj¡cychwfunkcjach
zdaniowych.Jestto
dziedzina
funkcjizdaniowej.
Kwantyfikatory
2
DEFINICJA
Kwantyfikatory
s¡tofunktoryzdaniotwórcze,któreprzekształcaj¡funkcjezdaniowewzdaniawsensie
logicznym.
—kwantyfikatorogólny
V
:
^
(x)–dlaka»degoxspełnionajestfunkcja(x)
—kwantyfikatorszczegółowy
W
:
x
_
(x)–istniejextaki,»espełnionajestfunkcja(x)
x
Kwantyfikatorogólnyjestuogólnieniemkoniunkcji,za±szczegółowy–alternatywy.NiechX={x
1
,x
2
,...,x
n
}b¦dzie
zakresemzmiennejxwfunkcjizdaniowej(x).Wówczas
^
!
—
(x)
()((x
1
)^(x
2
)^···^(x
n
))
_
x
!
—
(x)
()((x
1
)_(x
2
)_···_(x
n
))
x
Prawarozdzielno±cikwantyfikatorów
^
!
^
!
(x)^
^
x
—
[(x)^ (x)]
()
(x)
_
x
!
_
x
!
(x)_
_
x
—
[(x)_ (x)]
()
(x)
_
x
!
_
x
!
(x)^
_
x
—
[(x)^ (x)]
=)
(x)
iniezachodziimplikacjaodwrotna
^
x
!
^
!
(x)_
^
x
—
(x)
=)
[(x)_ (x)]
iniezachodziimplikacjaodwrotna
x
x
Zmianazakresukwantyfikatora
0
@
^
1
^
!
—
((x)) (x)
()
(x)
A
_
x
!
0
@
_
(x)
(x)
1
—
(x)^ (x)
()
(x)
A
x
^
!
_
!
PrawadeMorganadlakwantyfikatorów
—
(x)
()
(x)
_
x
!
^
x
!
—
(x)
()
(x)
x
x
Prawatesłusznes¡równie»dlakwantyfikatorówozasi¦guograniczonym.
Prawaprzemienno±cidlakwantyfikatorów
^
!
^
!
^
^
—
(x,y)
()
(x,y)
_
x
y
!
_
y
x
!
_
_
—
(x,y)
()
(x,y)
_
x
y
!
^
y
x
!
^
_
—
(x,y)
=)
(x,y)
iniezachodziimplikacjaodwrotna
x
y
y
x
3
x
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

dietanamase.keep.pl