Antwoorden
Tutorial Letter 203/0/2020
- Vak
- Instelling
- Boek
This Tutorial Letter contains SOLUTIONS TO ASSIGNMENT 3
[Meer zien]Voorbeeld 2 van de 6 pagina's
Voorbeeld 2 van de 6 pagina's
In winkelwagen
In winkelwagen
Gekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Verkoper
Volgen
passynsapo75
Voorbeeld van de inhoud
COS4807/203/0/2020Tutorial Letter 203/0/2020
Formal Logic
COS4807
Year module
Department of Computer Science
School of Computing
CONTENTS
Solutions to Assignment 3
university
Define Tomorrow. of south africa
, SOLUTIONS TO ASSIGNMENT 3
Question 1 (20)
(i) To prove that the formula A = ∃x¬(p(x) → q(x)) → ¬(∃xp(x) → ∀xq(x)) is valid, we must
show that it is true in all interpretations.
Let I be an interpretation in which the antecedent of the formula is true. In other words,
vI (∃x¬(p(x) → q(x))) = T . Then vσI (¬(p(x) → q(x))) = T for some assignment σI (by the
semantics of existential quantification, as stated in Theorem 7.22) and vσI (p(x) → q(x)) = F for
some assignment σI (by the truth values for negation). Then vσI (p(x)) = T and vσI (q(x)) = F
for some assignment σI (by the truth values for implication). But then vI (∃xp(x)) = T and
vI (∀xq(x)) = F (by Theorem 7.22). From this we conclude that vI (∃xp(x) → ∀xq(x)) = F
(by the truth values for for implication) and vI (¬(∃xp(x) → ∀xq(x))) = T (by the truth values
for negation).
We have shown that if the antecedent of the formula is true in I , then the consequent is true
in I . Since I is an arbitrary interpretation, we conclude that the who formula is true in any
interpretation.
(ii) To prove that B = ∃x∃yp(x, y) ↔ ∀x∀y¬p(x, y) is unsatisfiable, we must show that it is false in
all interpretations.
Let I be an arbitrary interpretation of B.
vI (∃x∃yp(x, y)) = T iff vσI (p(x, y)) = T for some assignment σI (by Theorem 7.22)
iff vσI (¬p(x, y)) = F for some assignment σI
(by the truth values for negation)
iff vI (∀x∀y¬p(x, y)) = F (by Theorem 7.22)
Since vI (∃x∃yp(x, y)) = T iff vI (∀x∀y¬p(x, y)) = F , we conclude that vI (∃x∃yp(x, y)) 6=
vI (∀x∀y¬p(x, y)), and thus that vI (∃x∃yp(x, y) ↔ ∀x∀y¬p(x, y)) = F (by the truth values for
equivalence). Since I is an arbitrary interpretation, we conclude that B is unsatisfiable.
Question 2 (10)
(i) Consider the formula A = ∀x(p(x) ↔ ∃y(q(y) ∧ r(x, y))). Under the given interpretation, this
formula states that for all natural numbers x, x is stange iff there is an odd number y such that
x has y distinct divisors.
(ii) To prove that A is falsifiable, we need to specify an interpretation in which it is false. There are
many possibilities. Here are a few:
(a) We can use the interpretation given for part (i), but just change the interpretation of pred-
icate p, say to the relation prime. Under this interprepretation, formula A states that all
prime numbers have an odd number of distinct divisors. This is obviously not true for any
prime number, because every prime number has exactly 2 distinct divisors, namely 1 and
itself.
(b) We can change the interpretation of predicate q, say to the unary relation even. Under
this interprepretation, formula A states that all strange numbers have an even number of
distinct divisors. This is obviously not true, according to the definition of strange numbers.
2
Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:
Bewezen kwaliteit door reviews
Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!
In een paar klikken geregeld
Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.
Direct to-the-point
Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper passynsapo75. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor $7.51. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 65040 samenvattingen verkocht
Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen
Laatst bekeken door jou
Samenvatting ·
DOM and SND quotes
College aantekeningen ·
Chapter 5 lecture notes
Samenvatting ·
Formas Bilineales
