100% tevredenheidsgarantie Direct beschikbaar na je betaling Lees online óf als PDF Geen vaste maandelijkse kosten
logo-home
Eerder door jou gezocht
Eerder door jou gezocht
logo
Logic and Sets Summary €7,49
In winkelwagen
Snel navigeren naar
Voorbeeld
  2.  
  3. Vrije Universiteit Amsterdam (VU)
  4.  
  5. Logic and Sets (X_401090)

Samenvatting

Logic and Sets Summary

3 beoordelingen
 18 keer verkocht

Summary of the slides of Wan Fokkink and Oliver Fabert. Some details were taken from the following books: "Logic in Computer Science" by Michael Huth and Mark Ryan "Set Theory for Computer Science" by Sandjai Bhulai The summary is divided into two parts, the first part (1 to 3) discusses the st...

[Meer zien]

Voorbeeld 2 van de 13  pagina's

Document informatie

  • 22 oktober 2021
  • 13
  • 2020/2021
  • Samenvatting

Onderwerpen

Geschreven voor

Alle documenten voor dit vak (1)

3  beoordelingen

review-writer-avatar

Door: joyfiltenborg • 1 jaar geleden

review-writer-avatar

Door: douweboonstoppel1 • 1 jaar geleden

review-writer-avatar

Door: teodorioancalin • 2 jaar geleden

Verkoper

avatar-seller
syntryx

Ontvangen beoordelingen

Voorbeeld van de inhoud

X_401090 Logic and Sets
Index

Logic 1 - Propositional Logic ...........................................................................................................................1
Logic 2 - Semantic Entailment..........................................................................................................................2
Logic 3 - DNF & CNF ......................................................................................................................................3
Sets 1 - Sets .......................................................................................................................................................4
Sets 2 - Relations...............................................................................................................................................6
Sets 3 - Ordering Relations ...............................................................................................................................8
Logic 4 - Axioms & Equivalence classes..........................................................................................................9
Logic 5 - OBDD ..............................................................................................................................................10
Logic 6 - Predicate Logic ................................................................................................................................11
Sets 4 - Equivalence Relations ........................................................................................................................11
Sets 5 - Functions ............................................................................................................................................12
Sets 6 - Induction & Recursion .......................................................................................................................13

Logic 1 - Propositional Logic

➤1.1 Declarative sentences
• Propositional logic: A language that is based on propositions, or declarative sentences. These can
either be true or false. A sentence is declarative if it is capable of being declared ‘true’ or ‘false’.
• A declarative statement can be made by any natural, or artificial language.
• Statements: Precise declarative sentences. These are checked by a calculus of reasoning which will
help to draw conclusions from given assumptions that could preserve the truth.
• If all assumptions are true, the conclusion is ought to be true as well.
• The logics are symbolic in nature. ‘Normal’ declarative sentences are translated into strings of
symbols. This gives a compressed, but still complete encoding of the sentences.
• This is important since specifications of systems or software are sequences of such declarative
sentences.

• A certain declarative sentence can be considered being atomic, or indecomposable. Then, certain
distinct symbols p, q, r … are assigned to each of these atomic sentences. These are the propositional
variables.
• More complex sentences can be formed according to the connectives below:
- ¬ : Negation, ‘not’
- ∨ : Disjunction, ‘or’
- ∧ : Conjunction, ‘and’
- → : Implication, ‘if p then q’ where p is the assumption and q the
conclusion
- ⊕ : Exclusive or, ‘either… or…’
- ↔ : Bi-implication, ‘if and only if’
• Negation is the only unary connective, the rest are binary connectives. Fig 1.3.1 Parse Tree
• Every propositional variable is a formula that can be places within parentheses. These help to
determine the way how the sentence was meant to be understood.
• To omit parentheses from formulas, without causing ambiguity, the connectives have binding
priorities; ¬ binds more tightly than ∨ and ∧, and the latter two bind more tightly than → and ↔.
• Implications are right associative, meaning operations are grouped from the right. Ex. p → (q → r)

➤1.2 Propositional Logic as a Formal Language
• While working with propositional formulas, Greek symbols ϕ, ψ, and χ are used.
• Inductive definitions from well-formed formulas can be given in a Backus Naur Form (BNF).
• For example ϕ ::= p | (¬ ϕ) | (ϕ ∧ ϕ) | (ϕ ∨ ϕ) | (ϕ → ϕ) where p stands for any atomic proposition and
each occurrence of ϕ to the right of ::= stands for any already constructed formula.
• Inversion principle: Invert the process of building formulas.
• With a parse tree the declarative sentence can be represented. See Fig.1.3.1.
• To see whether a formula is well-formed, making a parse tree is the easiest way to test it.
• Subformulas correspond to the subtrees in the parse tree, these give the steps in how the tree is formed.
• If parentheses are not there, the in-order representation will dedicate the form of the tree.

1

, ➤1.3 Semantics of Propositional Logic
• Syntax: How a word (or formula) is written. Semantic: Its meaning.
• Truth values T and F are determined by an assignment of truth values to its propositional variables.
Such an assignment is called a valuation. Each connective is expressed by its truth table.
• A valuation is one row in the truth table. There are 2n rows, n being the number of variables.

• When combining two declarative sentences, said p and q with a logical connective, said ∧, the truth
value of p ∧ q is determined by 3 things: truth value of p, truth value of q, and the meaning of ∧.
• In this case, p ∧ q is only true when p and q are both true.
• All logical connectives have their own truth tables where everything becomes fairly obvious.
• The meaning of the implication, →, should be seen as whether the truth is being preserved. That’s why
T → F is False ,and F → T and F → F are True because in these cases there is no truth to be preserved.

• Semantically equivalent (≡): Declaration that two formulas have identical columns in the truth table.
Thus, the formulas are identical to each other.
• There are a few important semantic equivalences, explained by examples:
- Commutativity: ϕ ∧ ψ ≡ ψ ∧ ϕ
- Idempotence: ϕ ∧ ϕ ≡ ϕ
- Associativity: ( ϕ ∧ ψ ) ∧ χ ≡ ϕ ∧ ( ψ ∧ χ )
- De Morgan: ¬ ( ϕ ∧ ψ ) ≡ ¬ ϕ ∨ ¬ ψ
- Involution: ¬ ¬ ϕ ≡ ϕ
• Conjunction and disjunction are both associative, so parentheses can be skipped.
• Semantics are compositional, meaning that if the truth values of the sub formulas are known, the truth
value of the formula can be determined by the implications of the sub formulas.

• Tautology: Always true. When a formulas column has T on every row.
• Contradiction: Always false. When a formulas column has F on every row.
• Contingent: Sometimes true, sometimes false. So neither a tautology nor a contradiction.

Logic 2 - Semantic Entailment

➤2.1 Semantic Entailment & Soundness of Propositional Logic
• A formula ψ is semantically entailed by formulas ϕ1,…, ϕn, denoted by ϕ1,…, ϕn ⊨ ψ, if each
valuation makes ϕ1,..., ϕn true, also makes ψ true. If the premises and conclusion are true, the semantic
entailment is valid.
• If ϕ1,…, ϕn ⊨ ψ does not hold, it’s denoted by ⊭. That happens if there’s a valuation v such that v
makes ϕ1,…, ϕn true, but not ψ. v is a counterexample, something that can prove the entailment wrong.

• Properties of ⊨ :
- ⊨ ϕ denotes that ϕ is a tautology
- ⊨ is reflexive; ϕ ⊨ ϕ
- ⊨ is transitive; If ϕ ⊨ ψ and ψ ⊨ χ, then ϕ ⊨ χ
• ϕ ≡ ψ holds precisely if both ϕ ⊨ ψ and ψ ⊨ ϕ. Semantic equivalence can be broken up into semantic
entailments.
• Semantic equivalence is identical to provable equivalence. The tautologies are exactly the valid
formulas to look at while determining the equivalence of formulas.
• Distributivity law: Gives a relation between conjunction and disjunction. To prove if the formulas are
actually semantic equivalent, it needs to be tested from left to right and from right to left.
• Metalogic concerns the truths that may be derived about the languages and systems that are used to
express truths.

➤2.2 Logic puzzles
• On the island of liars and truth speakers, every inhabitant is either always lying or always telling the
truth. They speak in declarative sentences and answer only with yes and no.
• For each islander x, the propositional variable tx expresses that x is a truth speaker, ¬tx a liar.
• If an islander makes an assertion ϕ; the assertion is true when x is a truth speaker and false when x is a
liar. Thus, this is a case of bi-implication.


2

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

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

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

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 syntryx. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €7,49. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 69052 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis
€7,49  18x  verkocht
  • (3)
In winkelwagen
Toegevoegd