Logika PDF

Logiky Výrok -- Tvrzení, o kterém má smysl uvažovat zda je, či není pravdivé. Elementární výrok -- Výrok, který neobsahuje žádnou logickou spojku. Výroková proměnná -- množina Vo. Symboly jazyka VL (Výroková logika) -- 1. Prvky množiny Vo 2. Logické spojky 3. Kulaté závorky pro prioritu P...

Logiky Výrok -- Tvrzení, o kterém má smysl uvažovat zda je, či není pravdivé. Elementární výrok -- Výrok, který neobsahuje žádnou logickou spojku. Výroková proměnná -- množina Vo. Symboly jazyka VL (Výroková logika) -- 1. Prvky množiny Vo 2. Logické spojky 3. Kulaté závorky pro prioritu Pravdivost hodnoty elementarnoho výroku -- 0 či 1 0 to je nepravda, 1 -- true -- pravda ~a~ ~b~ ~¬a~ ~a∧b~ ~a∨b~ ~a⇒b~ ~a⇔b~ ----- ----- ------ ------- ------- ------- ------- ~1~ ~1~ ~0~ ~1~ ~1~ ~1~ ~1~ ~1~ ~0~ ~0~ ~0~ ~1~ ~0~ ~0~ ~0~ ~1~ ~1~ ~0~ ~1~ ~1~ ~0~ ~0~ ~0~ ~1~ ~0~ ~0~ ~1~ ~1~ a ~∨¬~ a - zákon o vyloučení třetího ~¬¬~ a~⇔~a - zákon o dvojí negace ~¬\ (~a~∧¬~a) - vyloučení sporu a~⇔~a - zákon totožnosti (~¬~a~⇒~a)~⇒~a - Claviův zákon (a~∧¬~a)~⇒~b - Zákon Dunse Scotta Shefferova spojka -- Negace logického součinu (NAND) -- (a↑b) ~⇔~ ~¬~ (a~∧~b) Piersova spojka -- Negace logického součtu (NOR) -- (a↓b) ~⇔~ ~¬~ (a~∨~b) Prefixový zápis -- -34 Infixový zápis -- 3-4 Postfixový zápis -- 34- Disjunktivní normální forma (DNF) -- Forma je zapsána, jako disjunkce závorek (termů). Konjunktivní normální forma (KNF) - Forma je zapsána, jako konjunkce závorek (termů). Tabulka DNF a KNF -- P Q R f (p,q,r) --- --- --- ----------- 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 Při převodu do DNF si bereme jen řádků, jen kde f (p,q,r) = 1 A to budé jako -- (~¬~p~∧¬~q~∧~r) ~∨~ (~¬~p~∧~q~∧~r) ~∨~ (p~∧¬~q~∧~r). Při převodu do KNF si bereme jen řádků, jen kde f (p,q,r) = 0 A to budé jako -- (p~∨~q~∨~r) ~∧~ (p~∨¬~q~∨~r) ~∧~ (~¬~p~∨~q~∨~r) ~∧~ (~¬~p~∨¬~q~∨~r) ~∧~ (~¬~p~∨¬~q~∨¬~r). Jazyk predikátové logiky Definice termu -- Každá proměnná je term. Každá konstanta je term. x1,x2... jsou termy, pak f je funkční symbol, pak i f(x1,x2...) jsou termy. Nic jiného není term. Definice formuly -- Je-li P predikátove symbol a t1,t2,tn jsou termy, pak P(t1,t2,tn) je atomická formule Jsou-li P1 a P2 formule , pak i ~¬P1,\ P1∧P2,\ P1∨P2,\ P1⇒P2,\ P1⇔P2\ jsou\ formule.~ ~Je-li~ x proměnna a P je formula, pak i (∀)P a (∃)P jsou formule. Nic jiného není formule Negace predikátových formuli ~¬~ ((∀x)(A(x))) ~⇔~ (∃x)( ~¬~ A(x)) ~¬~ ((∃x)(A(x))) ~⇔~ (∀x)( ~¬~ A(x)) Množiny Množina -- Souhrn objektů majicich nějakou vlastnost. Počet prvků A značíme symbolem lAl Prázdná množina. Množina nemá žadný prvky, se nazývá prázdna. Značime ji symbolem 0, nebo {}. Skutečnost, že prvky x patři do množiny A, značíme symbolem x ∈A Skutečnost, že prvky x nepatři do množiny A, značíme symbolem x ∉ A Podmnožina. Když množina A podmnožinou množiny B (pišeme A ⊆ B), prave tehdy když každý prvek množiny A je prvkem množiny B. Množinová algebra. A∪B={ x l x∈A ∨ x∈B} - sjednocení A∩B={ x l x∈A ∧ x∈B} - průnik A-B={ x l x∈A∧ x∉B} -- rozdíl Doplněk. A ⊆ M, pak Doplněk množiny A v množině M je množina všech prvků z M, které nepatří do A. Potenční množina Potenční množinu značíme ρ (A) Pokud A = 0, pak ρ (A) = {∅} Pokud A = {a}, pak ρ (A) = {∅, {a}} Relace a zobraení Kartézský součin definujeme AxB = {(a,b) l a∈A ∧ b∈B }, přičemž AxB ≠ BxA. Je-li A = {a1....an} n-prvková a B = {b1,.... , bm} m-prvková, pak AxB má n.m prvků. Binární relace A≠∅, pak Binarni relace na množině A rozumíme libovolnou podmnožinou p kartézského součinu AxA (p⊆ AxA). Skutečnost, že (x,y) ∈ p, zapisujeme xpy. Operace N-árni operace je zobrazení [*A*^*n*^]{.math.inline} -\> A pro n=0,1,2.... Podle čisla n dáváme operacím nazvy (nularní, unární, binarní, ternarní... atd) Teorie Grafů Základní pojmy Graf je uspořadona trojice G= (U,H,f), kde - U je neprázdná množina uzlů(vrcholů), - H je konečná množina hran, - f každá hran má dvojicí uzlů Druhy grafů- 1. Úplný -- pokud mezi každými dvěma uzly existuji právě jedna hrana a graj je neorientovaný 2. Pokud gran neorientovaný, tak vždy souvislý Souvislost -- slába, silně 3. Prostý graf bez kružnic -- les Souvislý graf je strom Hledání nejkratší cesty Dijkstrův a Bellmanův-Fordův algoritmusy. Dijkstra- Hledá nejkratší cestu z počatku S do ostatních uzlů grafu. Algoritmus udržuje množinu S uzlů, pro které se už vypočítala délka nejkratší cesty. Bellman udržuje u každého uzlu značku (d,p), kde d je delka nejkratší dosud cesty (z počatku do daného uzlu) a p je předcházející uzel na této cestě.