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
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
