Flitskaarten Logical methodes

Geef het teken van conjuctie, en wanneer geeft het 1?

^, ‘‘en’’ , als beide waar

Geef het teken van disjuctie, en wanneer geeft het 1?

v ‘‘of’’, minstens een van de twee is waar, kan ook beide

Geef het teken van equivalentie, en wanneer geeft het 1?

←> , ‘‘als en alleen als’’ ‘‘just in case’’ dezelfde waarheidswaarde

Geef het teken van implicatie of conditional, en wanneer geeft het 1?

→ ‘‘als … dan’’ ‘‘only if’’ Alleen onwaar als A waar en B onwaar

∀

Kwantitatoor ‘‘voor alle’’

∃

Kwantitatoor ‘‘er bestaat’’

∈

is een element van

⊆

subset, is een deelverzameling van

→ bvb L ⊆ K, alles in L zit ook in K

∅

empty set

{1, 2} ∩ {3, 4} = ∅. De twee verzamelingen hebben geen gemeenschappelijke elementen, dus hun doorsnede is leeg.

∩

Doorsnede, verzameling elementen die in beide verzamelingen zitten

∪

Je neemt alles samen wat in de ene óf in de andere verzameling zit, of in allebei.

bvb {1, 2, 3} ∪ {3, 4} = {1, 2, 3, 4}

x ∈ ∅ waar of onwaar?

onwaar, niets zit in de lege verzameling, wat je ook invult

∅ ⊆ A waar of onwaar?

altijd waar. De lege verzameling is een deelverzameling van élke verzameling

⊥

altijd onwaar (tegenspraak)

⊤

altijd waar (tautologie)

⊨

conclusie volgt daadwerkelijk uit premissen

⊢

afleidt baar uit, of bewijst

Ω

de verzameling van alle mogelijke uitkomsten van een experiment.

A↔B kan je ook schrijven als

(¬A ∨ B) ∧ (¬B ∨ A)

rain → sun kan je ook schrijven als

¬rain ∨ sun

Deductively valid

Als premissen waar zijn moet conclusie waar zijn

Deductively invalid

Premissen kunnen waar zijn terwijl de conclusie onwaar is

geldig

conclusie volgt uit premissen

Sound

geldig en premissen zijn echt waar

modus ponens

Als A, dan B. A dus B

modus tollens

Als A, dan B. Niet B, dus niet A

disjunctief syllogisme

A of B. Niet a Dus B

DNF

→ waar het 1 is
(A ∧ B) ∨ (¬A ∧ C) ‘‘∧”

CNF

(A v B) ∧ (¬A v C) ‘‘v’’ teken. Waar het 0 is

NOR

2 × 0

Nand

een 0, of 2 nuls

XOR

één 1

XNOR

beide 1, beide 0

or

minstens een 1

NOT

omgekeerd

AND

BEIDE 1

default-on

uit staan voor stroom geleiden

default off

aan staan voor stroom geleiden

De morgan

negatie in de haakjes wegwerken

dubbele negatie

dubbele negatie wordt geen negatie

associativiteit

haakjes weghalen met geen effect

tautologische clausule

\neg R v R is altijd waar dus clausule valt weg

Horn

één positieve in één clausule, of geen

perceptron

kunstmatig neuron

imput vermenigvuldigd met gewicht

Positief gewicht duwt de uitkomst?

omhoog

Negatief gewicht duwt de uitkomt?

omlaag

stapfunctie

is z groter dan 0, dan is de output 1, anders 0

z = w₁x₁ + w₂x₂ + … + b

Welke zijn linear scheidbaar

AND, OR NOT, →

Niet linear scheidbaar

XOR

XOR OPDELEN

(x1 OR x2) AND NOT (x1 AND x2)

verborgen neuron h1. OR
verborgen neuron h2. AND

Met één verborgen laag kun je élke logische functie maken

1. Schrijf de waarheidstabel op.

2. Maak voor elke rij met output 1 een verborgen neuron dat alleen bij precies die rij “aan” gaat.
   Geef gewicht +1 waar de rij een 1 heeft, gewicht −1 waar de rij een 0 heeft, en bias 0,5 − (aantal enen in de rij).

3. Het output-neuron is een grote OR over al die verborgen neuronen.

bvb→ voor de rij (1, 0, 1), oftewel P ∧ ¬Q ∧ R, wordt dat h = step(x₁ − x₂ + x₃ − 1,5).

2^n . wanneer gebruik je?

n= het aantal inputs

het antwoord is de mogelijke combinaties

supervised learning

je geeft voorbeelden met het juiste antwoord erbij

kan een perceptron XOR leren?

nee, want hij is niet linear scheidbaar

Sigmoïde

σ(z) = 1/(1+e⁻ᶻ)

Universele benaderingsstelling

Een neuraal netwerk kan in theorie bijna elke vloeiende functie nadoen, zolang je maar genoeg neuronen gebruikt. Maar de stelling zegt alleen dát er goede instellingen bestaan, niet hoe je ze vindt. Die instellingen vinden is wat je doet als je het netwerk traint. En ook als het netwerk goed werkt op de voorbeelden waarmee je het getraind hebt, moet je nog testen of het ook goed werkt op nieuwe voorbeelden.

Input (1,0) geeft 1 → regel:

regel: (P ∧ ¬Q) → Y.

Input (1,1) geeft 0 → regel:

regel: (P ∧ Q) → ¬Y.

Fidelity

hoe goed de gevonden regels overeenkomen met wat het netwerk echt doet

Surrogaatmodel

je fit een beslisboom op de antwoorden van het netwerk. Elk pad van de wortel naar een blad is dan een als-dan-regel.

rule extraction

haal je uit een neuraal netwerk begrijpelijke als-dan-regels, zodat je kunt zien wat het netwerk eigenlijk doet.

In een waarheidstabel hoe meer 1 hoe meer de output richting 0 gaat. Wat is het gewicht?

Hoe meer inputs 1 zijn, hoe meer de output richting 0 gaat. De inputs duwen dus omlaag en krijgen een negatief gewicht. Neem −1 en −1.

natuurlijke deductie

met de hand bouwen

Γ ⊨ A

er bestaat geen situatie waarin de premissen waar zijn en de conclusie onwaar

Unificator

een substitutie σ die twee formules A en B letterlijk identiek maakt (Aσ = Bσ)

wat is een zin

een formule zonder vrije variabelen

Wanneer is iets een geldige redenering

als er geen enkele wereld bestaat waarin alle premissen waar zijn, en de conclusie onwaar

Regel: delete

s en t zijn al identiek (bijv. a ≐ a of x ≐ x)

→ Gooi het paar weg

Regel: decompose

Beide zijn geen variabele en hebben hetzelfde functie- of predicaatsymbool met evenveel argumenten

→Vervang f(s₁,…,sₙ) ≐ f(t₁,…,tₙ) door s₁ ≐ t₁, …, sₙ ≐ tₙ

Start: { P(x, f(x)) ≐ P(a, y) }

Decompose (beide P, twee argumenten): { x ≐ a, f(x) ≐ y }

Regel: clash

Beide zijn geen variabele, maar het symbool of het aantal argumenten verschilt (bijv. f(x) ≐ g(y), of a ≐ b)

→Falen: geen unificator

Regel: orient

Links staat geen variabele, rechts wel (bijv. f(a) ≐ x)

→Draai om: x ≐ f(a)

x ≐ a: leg [x/a] vast en vul in. Lijst: { f(a) ≐ y }

Orient: { y ≐ f(a) }

Regel: Occurs Check

Links staat variabele x, en x komt voor in t, terwijl t niet gewoon x is (bijv. x ≐ f(x))

→Falen: geen unificator

Regel: eliminate

Links staat variabele x, en x komt niet voor in t

→Leg [x/t] vast, vul x := t in overal in de rest van de lijst, en werk eerdere bindingen bij

{ x ≐ a, f(x) ≐ y }

Eliminate x ≐ a: leg [x/a] vast en vul in. Lijst: { f(a) ≐ y }

Orient: { y ≐ f(a) }

Eliminate y ≐ f(a): leg [y/f(a)] vast. Lijst is leeg.

Unificatie beslisbaar? of onbeslisbaar

Is beslisbaar→ algoritme stopt altijd

waarom is een lege clause onvervulbaar?

Een clause is waar als minstens één van zijn literalen waar is. Een lege clause heeft geen literalen, dus kan nooit waar zijn.

Equivervulbaar

Twee formules zijn equivervulbaar als ze óf allebei een model hebben, óf allebei geen model.

→ zwakker dan equivalent

NNF (negatie-normaal-vorm)

Duw negaties naar binnen, tot ze alleen nog direct voor atomen staan.

¬∀x A ≡ ∃x ¬A

("niet alles is A" = "iets is niet A")

¬∃x A ≡ ∀x ¬A

("niets is A" = "alles is niet A")

Skolemiseer

vervang elke ∃ door een getuige

vervang ∃y B door B[y / sk(x₁, …, xₙ)]

skolemiseer ∀x ∃y R(x, y)

∀x R(x, sk₁(x))

Skolemiseer ∃y ∀x R(x, y)

∀x R(x, sk₁)

skolemiseer ∃x Mens(x)

Mens(sk₁)

Niet equivalent

als nieuwe symbolen geintroduceert worden

verschillende waarheidswaarde

sk₁(x) in taal

een ding waar x niet groter dan is

Hoe bewijst resolutie een conclusie en hoezo geschrikt voor computers

door aan te tonen dat de premissen samen met de ontkenning van de conclusie tot een tegenspraak leiden.

Het is één enkele regel die je steeds herhaalt, en daarom geschikt voor computers.

wanneer is een atoom uniferseerbaar

Twee atomen zijn unificeerbaar als er een substitutie bestaat (een toekenning van termen aan variabelen) die ze letterlijk identiek maakt. Zo’n substitutie heet een unifier.

propositielogica (en wat is pivots)

A ∨ P en B ∨ ¬P volgt A ∨ B. P en ¬P vallen tegen elkaar weg.

P en \neg P zijn de pivots

Correct

vind je ⊥, dan is de verzameling echt onvervulbaar. Je bewijst nooit iets onwaars.

Weerleggingsvolledig

is de verzameling onvervulbaar, dan vind je ⊥ in eindig veel stappen.

als er een tegenspraak is vind je ⊥

Regel RAA (reductio ad absurdum)

Neem aan ¬φ → leid ⊥ af → concludeer φ

“Als het tegendeel van φ tot onzin leidt, dan geldt φ.”

SAT PROBLEEM

opstellen bij tegen model

premissen \land \neg conclusie

⊥ is

lege clausule

altijd onwaar

\neg ⊥

altijd waar

vervulbaar

minstens een toekenning van waar /onwaar aan de variabelen waarbij de formule waar wordt

equivalent vervulbaar

twee formules beide vervulbaar

of beide onvervulbaar

symbolisch systeem

verwerkt expliciete symbolen en regels

sub-symoblisch

kan informatie vastleggen in geleerde nummerrieke evenwichten

sound (correct)

geldig en premissen zijn echt waar
als A ⊢ C,
dan A ⊨ C, je kunt niks onwaars bewijzen

complete (volledig)

als A ⊨ C, dan A ⊢ C
Alles wat geldig is is ook te bewijzen