Summary Modelling Computing Systems Hoofdstuk 5 Faron Moller & Georg Struth
23 views 0 purchase
Course
Logica (INFOB1LI)
Institution
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
Connected book
Book Title:
Author(s):
Edition:
ISBN:
Edition:
More summaries for
Samenvatting alle stof logica voor informatica
Samenvatting Logica voor Informatica (INFOB1LI)
Samenvatting Logica voor informatica
All for this textbook (14)
Written for
Universiteit Utrecht (UU)
Informatica
Logica (INFOB1LI)
All documents for this subject (6)
Seller
Follow
luukvaa
Reviews received
Content preview
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
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.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes 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 these notes for $3.24. You're not tied to anything after your purchase.
