Summary Modelling Computing Systems Hoofdstuk 5 Faron Moller & Georg Struth
22 vistas 0 compra
Grado
Logica (INFOB1LI)
Institución
Universiteit Utrecht (UU)
Book
Modelling Computing Systems
Logic for Computer Science / Logica voor computertechnolgie hoofdstuk 5. Samenvatting van het boek Modelling Computing Systems geschreven door Faron Moller en Georg Struth. Samenvatting geschreven in het Engels. Aan de hand van voorbeelden en plaatjes wordt de stof en theorie verduidelijkt. Gegeven...
modelling computing systems faron moller georg struth
modelling computing systems hoofd
Libro relacionado
Título del libro:
Autor(es):
Edición:
ISBN:
Edición:
Más resúmenes para
Samenvatting alle stof logica voor informatica
Samenvatting Logica voor Informatica (INFOB1LI)
Samenvatting Logica voor informatica
Todos para este libro de texto (13)
Escuela, estudio y materia
Universiteit Utrecht (UU)
Informatica
Logica (INFOB1LI)
Todos documentos para esta materia (6)
Vendedor
Seguir
luukvaa
Comentarios recibidos
Vista previa del contenido
Hoofdstuk 5:
A proof of a (true) statement is a demonstration of its validity which contains sufficient detail to
convince someone that the statement is true. Statements which are provable are called theorems.
Recap:
- syntax describes what terms are well-formed;
- semantics describes the meaning of terms (or in the context of logic, what statements are
true);
We defined the syntax of propositional logic:
- T and F are a propositions;
- an atomic propositional variable, such as P and Q
- if p is a proposition, so is ¬p
- if p and q are propositions, so are p ∧ q, p ∨ q, p ⇒ q, and p ⇔ q
This fixes the language that we consider. We can rule out non-sensical terms such as ∧p(∨¬) – but it
doesn’t tell us what the meaning is of a formula such as p ∨ q ⇒ p.
The semantics of propositional logic is given by truth tables. We defined truth tables for all the
operators, such as ∧ and ⇒, and showed how to use these to write a truth table for any syntactically
valid formula in propositional logic.
Theorem Let A, B, and C be sets. Then A ⊆ C ∧ B ⊆ C ⇒ A ∪ B ⊆ C. If we unfold the definition of
subsets and translate this statement to predicate logic, this gives rise to a sizeable formula:
∀A ∀B ∀C ((∀a (a ∈ A ⇒ a ∈ C))∧(∀b (b ∈ B ⇒ b ∈ C)) ⇒ (∀x (x ∈ A∪B ⇒ x ∈ C)))
How should we go about proving this? We could draw a Venn diagram to convince ourselves that
this is true – but let’s look at what a written proof looks like.
Proof:
- Suppose A ⊆ C and B ⊆ C. We must show A ∪ B ⊆ C. By definition of set inclusion, this
amounts to proving:
- ∀x x ∈ A ∪ B ⇒ x ∈ C
- Let x be some element of A ∪ B. We need to show that x ∈ C.
- From x ∈ A ∪ B, we know that either x ∈ A or x ∈ B:
o if x ∈ A, we know that x ∈ C by our assumption that A ⊆ C
o if x ∈ B, we know that x ∈ C by our assumption that B ⊆ C
Hence, we can conclude that x ∈ C as required.
There are different proof strategies or proof templates that can be used to write such formal proofs.
Typically, there will be two proof strategies for each such logical operator and quantifier:
1. a introduction strategy tells you how to prove a goal of the form “example: p ∧ q”
2. a elimination strategy tells you how to use an assumption of the form
To find a proof, you: 1. write down all you assumptions and apply elimination strategies. 2. write
down the conclusion you wish to prove and use introduction strategies. By repeating these two
steps, the proof goals should get simpler – until the proof is finished.
, In the example prove, we showed that A ⊆ C ∧ B ⊆ C ⇒ A ∪ B ⊆ C in the following fashion:
General templates for prove strategies:
Implication Introduction: When I have to prove an implication which has the
form P => Q. We assume that P holds, and then we give a prove of Q. From
that we can conclude that P => Q. Example: We call a number a even if a = 2 ×
k for some number k. Theorem: The product of two even numbers is also
even. Question:
Make this statement precise and finish this proof. Be explicit about the proof
strategy used. Proof We need to show that if a and b are even, then so is a × b.
Assume a and b are even. By definition, we know a = 2 × n and b = 2 × m. The
product of a and b is (2 × n) × (2 × m). Using simple arithmetic, we can rewrite
this as: 2 × (2 × n × m). Therefore the product of a and b can be written in the
form 2 × k and is also even.
Implication elimination:
As part of the proof done earlier, we showed that if a ∈ A and A ⊆ C, we can
conclude that a ∈ C.
Los beneficios de comprar resúmenes en Stuvia estan en línea:
Garantiza la calidad de los comentarios
Compradores de Stuvia evaluaron más de 700.000 resúmenes. Así estas seguro que compras los mejores documentos!
Compra fácil y rápido
Puedes pagar rápidamente y en una vez con iDeal, tarjeta de crédito o con tu crédito de Stuvia. Sin tener que hacerte miembro.
Enfócate en lo más importante
Tus compañeros escriben los resúmenes. Por eso tienes la seguridad que tienes un resumen actual y confiable.
Así llegas a la conclusión rapidamente!
Preguntas frecuentes
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
100% de satisfacción garantizada: ¿Cómo funciona?
Nuestra garantía de satisfacción le asegura que siempre encontrará un documento de estudio a tu medida. Tu rellenas un formulario y nuestro equipo de atención al cliente se encarga del resto.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller luukvaa. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for $3.44. You're not tied to anything after your purchase.
