Samenvatting Logica voor Informatica (INFOB1LI)

‌


Logic‌‌for‌‌Computer‌‌Science‌ ‌
‌
Propositional‌‌logic‌ 1‌ ‌

Sets‌ 2‌ ‌

Boolean‌‌algebra‌ 3‌ ‌

Predicate‌‌logic‌ 4‌ ‌

Proof‌‌strategies‌ 5‌ ‌

Functions‌ 8‌ ‌

Relations‌ 9‌ ‌

Induction/Recursion‌ 11‌ ‌
Proof‌‌by‌‌induction‌ 12‌ ‌
Labeled‌‌transition‌‌systems‌ 13‌ ‌

Natural‌‌deduction‌ 15‌ ‌

Semantics‌ 16‌ ‌
Semantics‌‌for‌‌propositional‌‌logic‌ 16‌ ‌
Semantics‌‌for‌‌expressions‌ 16‌ ‌
Semantics‌‌for‌‌programs‌ 17‌ ‌
Hoare‌‌logic‌ 19‌ ‌
‌
‌




‌

, ‌

Propositional‌‌logic‌ ‌
Invariant‌‌‌Something‌‌that‌‌remains‌‌unchanged‌‌over‌‌any‌‌change‌‌to‌‌the‌‌situation‌ ‌
Proposition‌‌ ‌Declarations‌‌that‌‌are‌‌either‌‌true‌‌or‌‌false;‌S ‌ tatements‌ ‌
- Propositional‌‌logic‌‌studies‌‌when‌‌such‌‌statements‌‌are‌‌true‌‌or‌‌false‌ ‌
- A‌d ‌ eduction‌‌‌can‌‌be‌‌made‌‌to‌‌infer‌‌the‌‌truth‌‌of‌‌the‌c‌ onclusion‌‌‌from‌‌the‌‌truth‌‌of‌‌the‌‌
first‌‌two‌‌statements,‌‌the‌p‌ remises‌ ‌
‌
Variables‌‌with‌‌capital‌‌letters‌‌P,‌‌Q‌‌or‌‌R‌‌denote‌a ‌ tomic‌‌propositions‌;‌‌Lower‌‌case‌‌variables‌‌such‌‌
as‌‌p ,‌‌q ‌or‌‌r ‌are‌‌not‌‌propositional‌‌formulas,‌‌but‌m ‌ etavariables‌.‌ ‌
‌
Order‌‌of‌‌priority:‌ ‌
1. Parentheses‌‌(‌‌)‌ ‌
2. Negation‌‌¬ ‌
3. Conjunction‌‌⋀ ‌
4. Disjunction‌‌⋁ ‌
5. Implication‌‌⇒
6. Equivalence‌‌⇔ ‌
→ p ⋀ q ⋁ ¬r ‌becomes‌‌(p ⋀ q ) ⋁ ¬r ‌
‌
Binary‌‌operator‌‌ ‌Propositional‌‌formula‌‌
that‌‌requires‌‌two‌‌arguments‌‌to‌‌form‌‌a‌‌new‌‌
proposition‌‌(‌⋀ ,‌‌⋁ )‌ ‌
Unary‌‌operator‌‌ ‌Propositional‌‌formula‌‌that‌‌
requires‌‌only‌‌one‌‌argument‌‌to‌‌form‌‌a‌‌new‌‌proposition‌‌(‌¬ )‌ ‌
‌




‌
‌
Tautology‌‌‌Proposition‌‌that‌‌is‌‌true‌‌regardless‌‌of‌‌the‌‌truth‌‌values‌‌of‌‌its‌‌atomic‌‌propositions‌ ‌
- Proposition‌‌(argument)‌‌is‌‌said‌‌to‌‌be‌v‌ alid‌ ‌
Contradiction‌‌ P
‌ roposition‌‌that‌‌is‌‌false‌‌regardless‌‌of‌‌the‌‌truth‌‌values‌‌of‌‌its‌‌atomic‌‌propositions‌ ‌
- Proposition‌‌is‌‌said‌‌to‌‌be‌u ‌ nsatisfiable‌ ‌
- Proposition‌‌that‌‌is‌‌true‌‌under‌‌some‌‌interpretation‌‌of‌‌its‌‌atomic‌‌propositions‌‌is‌s‌ atisfiable‌ ‌




1‌ ‌

, ‌

Sets‌ ‌
Set‌‌ ‌Collection‌‌of‌e‌ lements‌‌
(‌members‌)‌‌that‌‌typically‌‌share‌‌a‌‌
property‌ ‌
Cardinality‌‌ ‌Number‌‌of‌‌elements‌‌
in‌‌a‌‌set,‌‌noted‌‌as‌‌∣A∣ ‌for‌‌a‌‌set‌‌A ‌
‌
Standard‌‌mathematical‌‌sets‌ ‌
- Empty‌‌set:‌‌∅ = { } ‌
- Binary‌‌digits:‌‌�� = {0, 1‌}
- Natural‌‌numbers:‌‌ℕ = {0, 1, 2, 3, ...} ‌
- Integers:‌‌ℤ = {... ,− 3,− 2,− 1, 0, 1, 2, 3, ...} ‌
- Rational‌‌numbers:‌‌ℚ = { mn : m, n ∈ ℤ, n =/ 0} ‌
- m ‌and‌‌n ‌cannot‌‌both‌‌be‌‌even‌ ‌
- Real‌‌numbers:‌‌ℝ = {x : x i‌s‌‌a‌‌real‌‌number‌} ‌
‌
Operations‌‌on‌‌sets‌ ‌
- Membership‌o ‌ f‌‌a‌‌set:‌∈
‌ ‌‌and‌∉‌ ‌‌
- Subset‌:‌‌⊆ ‌
- A=B ⇔A⊆B⋀B ⊆A ‌
- Superset‌:‌‌⊇ ‌
- Proper‌‌subset/superset‌:‌‌⊂‌‌and‌‌⊃‌ ‌
- Union‌:‌‌⋃ ‌
- A ⋃ B ‌are‌‌all‌‌elements‌‌in‌‌either‌‌A ‌or‌‌B ‌
- ∣A ⋃ B∣ = ∣A∣ + ∣B ∣ − ∣A ∩ B ∣ ‌
- Intersection‌:‌‌⋂ ‌
- A ∩ B ‌are‌‌all‌‌elements‌‌in‌‌both‌‌A ‌and‌B ‌
- Two‌‌sets‌‌are‌d ‌ isjoint‌‌‌when‌‌A ∩ B = ∅ ‌
- Difference‌:‌‌∖ ‌
- A ∖ B ‌are‌‌all‌‌elements‌‌in‌‌A ,‌‌but‌‌not‌‌in‌‌B ‌
- Complement‌:‌‌Ā ‌
- Elements‌‌outside‌‌of‌‌A ‌(within‌u ‌ niverse‌‌of‌‌discourse‌‌U ‌)‌ ‌
- Powerset‌:‌‌P
- Powerset‌‌P (A) ‌of‌‌A ‌consists‌‌of‌‌all‌‌subsets‌‌of‌‌A ‌including‌‌
1‌‌subset‌‌∅ ‌
- A ∈ P (A) ,‌‌but‌‌NOT‌‌A ⊆ P (A) ‌
- P f in (A) ‌are‌‌all‌‌finite‌‌subsets‌‌of‌‌A ‌
- If‌‌∣A∣ = n ,‌‌then‌‌∣P (A)∣ = 2n ‌
‌
For‌‌an‌‌ordered‌‌pair‌‌(a, b) =/ (b, a) ,‌‌whereas‌‌{a, b} = {b, a} ‌
Cartesian‌‌product‌ ‌A × B = {(a, b) : a ∈ A and b ∈ B } ‌
- An = A × A × ... × A ,‌‌for‌‌example‌‌ℝ2 ‌denotes‌‌an‌‌x, y ‌plane‌‌and‌‌ℝ3 ‌a‌‌3D‌‌space‌‌ ‌
- You‌‌can‌‌define‌‌a‌‌point‌‌on‌‌a‌‌screen‌‌as‌‌the‌‌ordered‌‌pair‌‌((x, y), (r, g, b)) ,‌‌with‌‌the‌‌
second‌‌coordinate‌‌being‌‌the‌‌ordered‌‌triple‌‌for‌‌an‌‌RGB‌‌value‌ ‌




2‌ ‌