Garantie de satisfaction à 100% Disponible immédiatement après paiement En ligne et en PDF Tu n'es attaché à rien
logo-home
Recherché précédemment par vous
Recherché précédemment par vous
logo
Logica en formele systemen opgeloste oefeningen (alle hoofdstukken) €5,48
Ajouter au panier
Accédez rapidement à
Aperçu
  2.  
  3. Vrije Universiteit Brussel (VUB)
  4.  
  5. Computerwetenschappen
  6.  
  7. Logica en formele systemen

Réponses

Logica en formele systemen opgeloste oefeningen (alle hoofdstukken)

5 revues
 4 fois vendu

Dit document bevat de oefeningen en de oplossingen van deze oefeningen gegeven in het vak "Logica en formele systemen" gegeven door Olga De Troyer. Eindresultaat: 19/20

Dernier document publié: 4 année de cela

Aperçu 4 sur 52  pages

Infos sur le Document

  • 20 octobre 2018
  • 10 septembre 2020
  • 52
  • 2016/2017
  • Réponses
  • Inconnu

Sujets

École, étude et sujet

Tous les documents sur ce sujet (16)

5  revues

review-writer-avatar

Par: sacrmukoko • 2 année de cela

review-writer-avatar

Par: ausman • 2 année de cela

review-writer-avatar

Par: HmzPL • 5 année de cela

review-writer-avatar

Par: anissafaik • 5 année de cela

review-writer-avatar

Par: stefanoclaes • 6 année de cela

Vendeur

avatar-seller
divisionbyzero

Avis reçus

Aperçu du contenu

Oefeningen


1. Een alfabet is een verzameling symbolen, bvb. {a, b, c} of {1, 2, 3} of
{koe, paard, varken}. Als Σ een alfabet is, dan is Σi de verzameling van
alle woorden over Σ van lengte i.
Σ0 = {}
Σ1 = Σ
Σ2 = Σ × Σ
Σ3 = Σ × Σ × Σ
Algemeen:
Σ0 = {}
Σi = Σi−1 × Σ
Σ∗ = i≥0 Σi
S

Gegeven Σ = {a, b}. Bereken Σ0 , Σ1 , Σ2 , Σ3 .
2. Op Σ∗ is een ‘concatenatie’ operatie gedefineerd:
. : Σ∗ × Σ∗ → Σ∗
die 2 woorden over Σ∗ aaneenplakt (concateneert). Bvb., abc.de = abcde.
Verder is, voor w ∈ Σ∗ , wr de omgekeerde versie van w.
(a) Defineer .r .
(b) Bereken (abcd)r volgens de definitie.
(c) Toon aan dat (wa)r = awr .
r
(d) Toon aan dat wr = w.
3. Schrijf het alfabet van de λ-calculus op.
4. Schrijf het alfabet van de propositielogica op.
5. Definieer d : Σ∗ × Σ → Σ∗ door
d(, a) = 
d(a, a) = 
d(b, a) = b als b 6= a
d(cx, a) = d(c, a)d(x, a)
en dit ∀a, b, c ∈ Σ en ∀x ∈ Σ∗
(a) Wat doet d informeel ?
(b) Toon aan dat d en .r commuteren: (d(w, a))r = d(wr , a), ∀w ∈ Σ∗ en
∀a ∈ Σ.


1

, (c) Toon aan dat d commutatief is in haar 2de argument: d(d(w, a), b) =
d(d(w, b), a) voor alle w ∈ Σ∗ en voor alle a, b ∈ Σ.

6. Bekijk de definitie van de propositieformules P ROP ⊂ Σ∗ .
(a) Waarvoor dient de afsluitende stap ?
(b) Zijn de volgende formules geldige formules? Zo ja, teken hun con-
structieboom. Zo neen, zeg wat er fout loopt.
i. ((p → q) ∨ ¬r)
ii. (p ∨ q ∨ r)
iii. (((p ∨ q) ∧ r) → (r ∨ ¬p))
7. Geef de volgende zinnen weer in propositionele notatie:
(a) ‘Als de bus niet komt, komen de tram en de trein’
(b) ‘Als de tram komt als de trein niet komt, dan komen de trein en de
bus niet allebei’
8. Geef alle formules die met haakjes invoegen te maken zijn uit p ∧ ¬q → r,
met bijbehorende constructiebomen.

9. Kan je een efficiëntere representatie bedenken voor constructiebomen. Doe
dit voor de formules uit oefening 6b.
10. (a) Definieer inductief rijen gebalanceerde haakjes.
(b) Definieer op een inductieve manier een syntax voor natuurlijke rekenkundige
expressies. Maak gebruik van IN en van {(, ), +, −, ∗, /}.
Teken bomen in de stijl van oefening 9 voor volgende expressies.
i. (3 + 4) ∗ 7
ii. ((8 − 5) + (6/2))
11. Schrijf de volgende formules op in prefix en postfix notatie.

(a) (1 + ((2 ∗ 7) − 5))
(b) ((3 + 4) ∗ (8/2))
(c) (((q ↔ r) → p) ∧ ¬p)
12. Voer volgende substituties met de hand uit

(a) [(q ↔ r)/p]¬p
(b) [(q → s)/p](p → q)
(c) [((q ∨ s) → ¬p)/r](p → p)
13. Welke getallen x voldoen aan de volgende condities :

(a) (¬(p ∧ q) ∧ r)
(b) ((¬p ∧ q) ∧ r)
(c) ¬(p ∧ (q ∧ r))
waarbij p =“x ≤ 1”, q =“x ≤ 3” en r =“x ≥ 2”.


2

, 14. Zij v de waardering gedefinieerd door v(p) = 0 en v(q) = 1.
(a) Wat is v(p ∧ q) en v(p ↑ q) ?
(b) Toon aan waar het boek te kort schiet in de definitie van semantiek.
(c) Probeer de exacte definities te formuleren.
(d) Geef exacte semantiek aan de standaardconnectieven.
(e) Bereken v(((p ∧ q) → r)) als v(p) = 0, v(q) = 1 en v(r) = 0.
15. Geef waarheidtabellen op twee manieren voor
(a) (¬p ∨ ¬q)
(b) p ∧ (q ∧ p)
(c) (¬p ∧ (¬q ∧ r)) ∨ ((q ∧ r) ∨ (p ∧ r))
16. We voeren een nieuw connectief ∆ in waarvan de betekenis door de vol-
gende waarheidstabel is gegeven:
p q p∆q
0 0 0
0 1 1
1 0 1
1 1 0

(a) Vind nu een propositie waarin alleen p, q en de connectieven ¬, ∧, ∨
voorkomen, die dezelfde eindkolom in een waarheidstabel oplevert.
(b) Wat is de intuı̈tieve betekenis van ∆?
(c) Druk ook → en ↔ uit m.b.v. ¬, ∧, ¬.
17. Rekenen binnen een computer gebeurt binair. Zij (p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 )
en zij (q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 ) twee binaire getallen (laten we afspreken
dat p1 en q1 de minst-significante cijfers voorstellen). Net zoals gewoon
decimaal optellen maakt binair optellen gebruik van twee mechanismen:
één mechanisme om een reeks cijfers te combineren tot een nieuw cijfer
(bvb voor 5 + 8 is het nieuwe cijfer 3) en een ander mechanisme om te
weten wat de overdracht is (bvb 5 + 8 heeft als overdracht 1, t.t.z. “één
onthouden”). Net zoals bij decimaal rekenen zowel het resulterend cijfer
als de overdracht begrensd zijn door 9, is bij binair rekenen de uitkomst
en de overdracht beperkt door 1.

p q p q p q p q p q p q p q p q
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
overflow
carry


result


Figure 1: De full adder



3

, (a) Vind een logisch connectief om het cijfer bij de optelling van twee
bits p en q te bepalen.
(b) Vind een logisch connectief om de overdracht bij optelling van 2 bits
te bepalen.
(c) Bovenstaande schakeling (de “full adder”) rekent de som uit van 2 bi-
naire getallen (p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 ) en (q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 ).
Geef voor iedere digit van het resultaat een logische formule en geeft
een logische formule voor de overflow. Er zal natuurlijk steeds gerek-
end worden met v(c1 ) = 0

18. Bepaal M OD(ϕ) voor volgende formules:

(a) ϕ = ((¬p ∨ q) ↔ (p → q))
(b) ϕ = (q ∧ (¬p ∨ p))
(c) ϕ = (q ∧ (¬p ∧ p))
19. Bepaal alle modellen van volgende formuleverzamelingen (t.t.z. M OD(Σ)):

(a) Σ = {((p ↔ q) ↔ ((p → q) ∧ (q → p)))}
(b) Σ = {((p ↔ q) ↔ ((p → q) ∧ (q → p))), (p ∨ q)}
Wat gebeurt er met M OD(Σ) als je Σ groter maakt ?
20. Gebruik modeleliminatie om de volgende problemen op te lossen:

(a) i. Als Formele Methoden veel blokwerk is, of een slechte assistent
heeft, dan is het een moeilijk vak.
ii. Als Formele Methoden plezant is, heeft het geen slechte assistent.
iii. Als Formele Methoden veel blokwerk is, of als het geen slechte
assistent heeft, dan is het een plezant vak.
iv. Formele Methoden is plezant enkel en alleen als er veel blokwerk
aan is. Bovendien doet de assistent het fantastisch.
Wat zijn de eigenschappen van het vak ?
(b) i. Als je bist was je gebuisd.
ii. Als je gebuisd was, ging je niet veel naar TD.
iii. Als je bist of gebuisd was, ging je veel naar TD.
iv. Als je niet bist, ging je veel naar TD.
Is het aangeraden om van TD weg te blijven ?
21. Zijn volgende formules tautologieën ? Zijn het contradicties ?

(a) (((p → q) ∧ (q → p)) ↔ (p ↔ q))
(b) (((p ∧ q) ∨ (r ∧ s)) ∧ ¬r)
(c) ((p ∧ ¬p) ∧ r)
22. Zijn volgende formules equivalent ?

(a) (p ∧ q) en (p → q)
(b) (p → (q → r) en (p → q) → (p → r))


4

Les avantages d'acheter des résumés chez Stuvia:

Qualité garantie par les avis des clients

Qualité garantie par les avis des clients

Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.

L’achat facile et rapide

L’achat facile et rapide

Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.

Focus sur l’essentiel

Focus sur l’essentiel

Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.

Foire aux questions

Qu'est-ce que j'obtiens en achetant ce document ?

Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.

Garantie de remboursement : comment ça marche ?

Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.

Auprès de qui est-ce que j'achète ce résumé ?

Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur divisionbyzero. Stuvia facilite les paiements au vendeur.

Est-ce que j'aurai un abonnement?

Non, vous n'achetez ce résumé que pour €5,48. Vous n'êtes lié à rien après votre achat.

Peut-on faire confiance à Stuvia ?

4.6 étoiles sur Google & Trustpilot (+1000 avis)

69411 résumés ont été vendus ces 30 derniers jours

Fondée en 2010, la référence pour acheter des résumés depuis déjà 15 ans

Commencez à vendre!

Récemment vu par vous

Resume ·

(0)

Samenvatting Sales Management
€5,48  4x  vendu
  • (5)
Ajouter au panier
Ajouté