Udsagnslogik (færdig) Flashcards
Hvordan kan man bruge De Morgans lov(e) inden for udsagnslogik?
Bevis De Morgans første lov.
De Morgans love siger noget logisk ækvivalens mellem forskellige udsagn.
Negation af konjunktioner og disjunktioner kan f.eks. bevises:
1) ¬( p ∧ q ) ≡ ¬p ∨ ¬q
2) ¬( p ∨ q) ≡ ¬p ∧ ¬q
Den første lov kan bevises via en sandhedstabel.
p q p∧q ¬(p∧q) ¬p ¬q ¬(p∨q)
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
Det er bevist da sandhedsværdierne i fjerde og syvende kolonne er ens og altså LOGISKE ÆKVIVALENTE.
Hvad er en sandhedstabel?
Hvordan kan den bruges?
Kom med et eksempel.
I en sandhedstabel skriver man alle mulige kombinationer af udfald ind.
F.eks. bruges til at bevise en modstrid og en tautologi.
Modstrid: Et udsagn, som aldrig er sandt.
Tautologi: Et udsagn, som altid er sandt.
Sandhedstabellen:
p ¬p p∧¬p p∨¬p
T F F T
F T F T
hvor p∧¬p er en modstrid
og p∨¬p er en tautologi
Hvad er kvantorer?
De betegner hvor mange elementer i en definitionsmængde, der gør et udsagn sandt.
”For alle elementer x er P(x) sand”
er betegnet med: ∀ x P(x)
”Der eksisterer et element x, hvilket gør P(x) sand” er betegnet med: ∃ x P(x)
Hvad er en udsagnsfunktion?
Kom med et eksempel.
Et udsagn bliver til en udsagnsfunktion, når man indsætter en variabel. Sandhedsværdien af udsagnet afhænger så af variablen.
Eksempel:
P(x): “Min cykel er x”, x ∈ {rød, blå, punkteret, hurtig}
Definitionsmængden har fire elementer, hvor x er variablen.
Hvad er et udsagn?
Et udsagn er noget som enten er sandt (T for true) eller falskt (F for false).
Man finder ud af om noget er T eller F ud fra matematiske argumenter - beviser.
Hvad er en negation?
Negationen af et udsagn beskriver det modsatte. Altså også et udsagn, der kan være T eller F.
f.eks. hvis p er et udsagn, så er ¬p dens negation
Hvad er en konjunktion?
En sammenfletning af udsagn via et logisk OG.
Dvs. p ∧ q
Hvad er en disjunktion?
En sammenfletning af udsagn via et logisk ELLER.
Dvs. p V q
Hvad er en implikation?
Det betyder af q er en konsekvens af p. “Hvis p… så q” –> p medfører q.
Dvs. p → q
Hvad er en biimplikation?
Det betyder at q udelukkende er en konsekvens af p (og omvendt, gælder begge retninger). “p hvis og kun hvis q”
Dvs. p ↔ q
Hvad er en modstrid?
Kom med et eksempel.
Et udsagn, som aldrig er sandt.
F.eks. sandhedstabellen.
p ¬p p∧¬p p∨¬p
T F F T
F T F T
hvor p∧¬p er en modstrid
og p∨¬p er en tautologi
Hvad er en tautologi?
Kom med et eksempel.
Et udsagn, som altid er sandt.
F.eks. sandhedstabellen.
p ¬p p∧¬p p∨¬p
T F F T
F T F T
hvor p∨¬p er en tautologi og
p∧¬p er en modstrid
Hvad er p ∧ q?
Det er en konjunktion.
En sammenfletning af udsagn via et logisk OG.
Hvad er p ∨ q?
Det er en disjunktion.
En sammenfletning af udsagn via et logisk ELLER.
Hvad er p → q?
Det er en implikation.
Det betyder af q er en konsekvens af p. “Hvis p… så q” –> p medfører q.
Hvad er p ↔ q?
Det er en biimplikation.
Det betyder at q udelukkende er en konsekvens af p (og omvendt, gælder begge retninger). “p hvis og kun hvis q”
Vis at noget er logisk ækvivalent.
Det viser De Morgans love.
De Morgans love siger noget logisk ækvivalens mellem forskellige udsagn.
Negation af konjunktioner og disjunktioner kan f.eks. bevises:
1) ¬( p ∧ q ) ≡ ¬p ∨ ¬q
2) ¬( p ∨ q) ≡ ¬p ∧ ¬q
Forklar distributivitet.
Det handler om hvordan man ganger ind i en parentes.
Loven siger:
a ⋅ ( b + c ) = a ⋅ b + a ⋅ c.
Hvad betyder ¬p?
Negationen af et udsagn beskriver det modsatte. Altså også et udsagn, der kan være T eller F.
f.eks. hvis p er et udsagn, så er ¬p dens negation
Bevis ¬( p ∧ q ) ≡ ¬p ∨ ¬q.
Hvad er det?
Den første lov af De Morgans.
Den kan bevises via en sandhedstabel.
p q p∧q ¬(p∧q) ¬p ¬q ¬(p∨q)
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
Det er bevist da sandhedsværdierne i fjerde og syvende kolonne er ens og altså LOGISKE ÆKVIVALENTE.
Er dette udsagn en modstrid eller en tautologi?
(p ∨ q) ∨ ¬p
Vis med en sandhedstabel.
p q ¬p ¬q p∨q (p∨q)∨¬p
T T F F T T
T F F T T T
F T T F T T
F F T T F T
Ovenstående udsagn er altså en tautologi, da tredje kolonne og femte kolonnes sandhedsværdier betyder at det fulde udsagn er sandt. Det er bare én af værdierne i én af de to kolonner, der skal være T for at det fulde udsagn er T.
Hvad er konjunktiv normalform?
En normalform er en måde at skrive udsagn op på.
Et ∧ kaldes for en konjunktion (et logisk OG)
Et udsagn på konjunktiv normalform (CNF) hvis det består af konjunktioner af elementære disjunktioner. (dvs. med V)
F.eks. (p V q) ∧ (p ¬p) ∧ (p V q V ¬r))
Hvad er disjunktiv normalform?
En normalform er en måde at skrive udsagn op på.
Et V kaldes for en disjunktion (et logisk ELLER)
Et udsagn på konjunktiv normalform (CNF) hvis det består af konjunktioner af elementære disjunktioner. (dvs. med V)
F.eks. (p ∧ q) V (p ∧ ¬p) V (p ∧ q ∧ ¬r))
Hvad er CNF?
En normalform er en måde at skrive udsagn op på.
Det står for konjunktiv normalform.
Et ∧ kaldes for en konjunktion (et logisk OG)
Et udsagn på konjunktiv normalform (CNF) hvis det består af konjunktioner af elementære disjunktioner. (dvs. med V)
F.eks. (p V q) ∧ (p V ¬p) ∧ (p V q V ¬r))
Hvad er DNF?
En normalform er en måde at skrive udsagn op på.
Det står for disjunktiv normalform.
Et V kaldes for en disjunktion (et logisk ELLER)
Et udsagn på konjunktiv normalform (CNF) hvis det består af konjunktioner af elementære disjunktioner. (dvs. med V)
F.eks. (p ∧ q) V (p ∧ ¬p) V (p ∧ q ∧ ¬r))
Hvad er PCNF?
En normalform er en måde at skrive udsagn op på.
Kanoniske normalformer er når man udskifter konjunktioner/disjunktioner med minterms og maxterms.
Maxterms: en disjunktion hvor hver variabel enten har variablen ELLER dens negation men ikke begge. (f.eks. p V ¬q V r og p V ¬q V ¬r)
Kanonisk konjunktiv normalform er når et udsagn består af konjunktioner af maxterms. (dvs. elementær disjunktioner er udskiftet med maxterms)
Hvad er PDNF?
En normalform er en måde at skrive udsagn op på.
Kanoniske normalformer er når man udskifter konjunktioner/disjunktioner med minterms og maxterms.
Minterms: en konjunktion hvor hver variabel enten har variablen ELLER dens negation men ikke begge. (f.eks. p ∧ ¬q ∧ r og p ∧ ¬q ∧ ¬r)
Kanonisk konjunktiv normalform er når et udsagn består af konjunktioner af maxterms. (dvs. elementær disjunktioner er udskiftet med minterms)
