# Subject description - B0B01LGR

Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions

B0B01LGR | Logic anad Graphs | Extent of teaching: | 3+2 | ||
---|---|---|---|---|---|

Guarantors: | Demlová M. | Roles: | PV,P | Language of teaching: | CS |

Teachers: | Dostál M. | Completion: | Z,ZK | ||

Responsible Department: | 13101 | Credits: | 5 | Semester: | Z,L |

**Anotation:**

**Study targets:**

**Content:**

1. | Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula. | |

2. | Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus. | |

3. | Semantic consequence. The rezolution method in propositionl logic. | |

4. | Syntax of predicate logic, a sentence, an open formula. | |

5. | Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence. | |

6. | The rezolution method in predicate logic. | |

7. | Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness. | |

8. | Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees. | |

9. | Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges. | |

10. | Euler graphs and their applications. | |

11. | Hamiltonian graphs and their applications. | |

12. | Independent sets, cliques, vertex and edge cover, Graph coloring. | |

13. | Plannar graphs. |

**Course outlines:**

1. | Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula. | |

2. | Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus. | |

3. | Semantic consequence. The rezolution method in propositionl logic. | |

4. | Syntax of predicate logic, a sentence, an open formula. | |

5. | Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence. | |

6. | The rezolution method in predicate logic. | |

7. | Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness. | |

8. | Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees. | |

9. | Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges. | |

10. | Euler graphs and their applications. | |

11. | Hamiltonian graphs and their applications. | |

12. | Independent sets, cliques, vertex and edge cover, Graph coloring. | |

13. | Plannar graphs. |

**Exercises outline:**

1. | Syntax and semantics of propositional logic, formulas, truth valuation, a tautology, a contradiction, a satisfiable formula. | |

2. | Tautological equivalence of two formulas. CNF a ndDNF, Boolean calculus. | |

3. | Semantic consequence. The rezolution method in propositionl logic. | |

4. | Syntax of predicate logic, a sentence, an open formula. | |

5. | Interpretation of predicate logic, tautological equivalence of sentences and semantic consequence. | |

6. | The rezolution method in predicate logic. | |

7. | Applications of rezolution method. Natural deduction as an example of a sound and complete deduction system.Theorem of completness. | |

8. | Undirected and directed graphs, basic notions. Connectivity, trees, spanning trees. | |

9. | Rooted trees, strong connectivity ,acyclic graphs, topological sort of vertices and edges. | |

10. | Euler graphs and their applications. | |

11. | Hamiltonian graphs and their applications. | |

12. | Independent sets, cliques, vertex and edge cover, Graph coloring. | |

13. | Plannar graphs. |

**Literature:**

[4] | Hodel, R. E.: An Introduction to Mathematical Logic, 2013, ISBN-13 978-0-486-49785-3 | |

[5] | Diestel, R.: Graph Theory, Springer-Verlag, 4th edition, 2010, ISBN 978-3-642-14278-9 |

**Requirements:**

**Webpage:**

**Keywords:**

**Subject is included into these academic programs:**

Program | Branch | Role | Recommended semester |

BPOI_BO_2018 | Common courses | P | 2 |

BPOI4_2018 | Computer Games and Graphics | P | 2 |

BPOI3_2018 | Software | P | 2 |

BPOI2_2018 | Internet things | P | 2 |

BPOI1_2018 | Artificial Intelligence and Computer Science | P | 2 |

BPOI1_2016 | Computer and Information Science | P | 2 |

BPOI_BO_2016 | Common courses | P | 2 |

BPOI4_2016 | Computer Games and Graphics | P | 2 |

BPOI3_2016 | Software | P | 2 |

BPOI2_2016 | Internet things | P | 2 |

BPBIO_2018 | Common courses | PV | 5 |

BPKYR_2016 | Common courses | P | 1 |

Page updated 24.5.2019 17:53:31, semester: Z,L/2020-1, L/2019-20, Z,L/2018-9, Z/2019-20, Send comments about the content to the Administrators of the Academic Programs | Proposal and Realization: I. Halaška (K336), J. Novák (K336) |