课件5
.................................... 5 .................................... 8
13
1 Quelques rappels . . .
2 Ensemblesordonnés ..................................... 15
3 Maj,bornesup,max..................................... 16
4 Ensemblebienfondé ..................................... 16
3 Terminaison 17
1 LaconjecturedeSyracuse.................................. 17
2 Lespointsfixes........................................ 18
3 Ordresbienfondés ...................................... 19
4 Exemples ........................................... 19
4 Outils pour la logique 21
1 Termes............................................. 21
2 AlgèbredeBoole....................................... 22
3 Fonctionsbooléennes..................................... 23
4 Formesnormales ....................................... 24
5 Fonctionsduales ....................................... 24
5 Calcul propositionnel 25
1 Syntaxe............................................ 25
2 Sémantique .......................................... 26
3 Conséquencesémantique................................... 28
4 Conséquencelogique(oudéduction) ............................ 30
6 Logique du premier ordre 31
1 Introduction . . . . . ..................................... 31
2 Syntaxe ....... ..................................... 31
3 Variableslibresetliées.................................... 32
4 Sémantique .......................................... 33
5 Propriétéssémantiques. . . . . . . . . . . ......................... 35
6 Déduction.................. ......................... 37
1 Récursion, induction
1 Récurrence sur N . . .
2 Induction structurelle
根据提供的文件内容，以下是相关的知识点详细阐述：
1. 离散结构（Structures Disjectives）
- 课程编号：LI214-STRUCTURES DISCRETES
- 讲师：Benjamin BARON
- 所属院校：UPMC-L2 Informatique
- 笔记日期：2010年11月4日
2. 递归和归纳
- 递归的基本概念：在离散数学中，递归用于定义函数或数据结构，它通过自身来解决问题。
- 归纳原理：数学归纳法是证明数学性质在自然数集上成立的一种方法，包括归纳基础和归纳步骤。
- 结构归纳法：类似于数学归纳法，用于证明与树或图结构相关的性质。
3. 偏序集合（Ensembles ordonnés）
- 偏序关系的定义：集合中的一种二元关系，满足自反性、反对称性和传递性。
- 偏序集合的例子：自然数、整数、实数都可视为偏序集合，当考虑它们的自然序时。
4. 最大元素、界限和上确界（Maj, bornes sup, max）
- 最大元素：在偏序集中，如果存在某个元素a，使得对于集合中所有元素x，都有x ≤ a，则称a为最大元素。
- 界限：在偏序集中，元素a是上界如果对于所有x，x ≤ a；元素b是下界如果对于所有x，b ≤ x。
- 上确界：集合所有上界中的最小元素，如果存在的话。
5. 良序集合（Ensemble bien fondé）
- 定义：一个集合是良序的，如果它的任何非空子集都有最小元素。
- 良序原理：每个非空良序集合中的每个元素都可以和自然数建立一个一一对应关系。
6. 终止性（Terminaison）
- 终止性的概念：在计算过程中，终止性指的是程序能够最终停止运行的性质。
- 叙拉古猜想（Conjecture de Syracuse）：一个关于迭代函数序列的终止问题，其结果至今未解。
- 固定点：在数学中，函数的固定点是指满足f(x)=x的点。
7. 逻辑工具（Outils pour la logique）
- 项（Terms）：在逻辑表达式中，变量或常量的名称。
- 布尔代数（Algèbre de Boole）：一种数学代数系统，用于处理逻辑运算，有与、或、非等运算。
- 布尔函数（Fonctions booléennes）：接受布尔值输入并产生布尔值输出的函数。
- 范式（Formes normales）：在布尔逻辑中，通过逻辑运算组合的表达式形式，如析取范式和合取范式。
- 对偶函数（Fonctions duales）：布尔函数的一种，通过交换与、或运算来获得。
8. 命题逻辑（Calcul propositionnel）
- 语法（Syntaxe）：命题逻辑中用于构建公式的规则。
- 语义（Sémantique）：解释命题逻辑公式的方法，通常使用真值表或可能世界语义。
- 语义蕴含（Conséquences sémantiques）：从一组命题中推导出结论的过程，关注命题之间的逻辑蕴含关系。
- 逻辑蕴含（Conséquences logiques）：形式逻辑中，命题之间的蕴含关系。
9. 一阶逻辑（Logique du premier ordre）
- 引言（Introduction）：对一阶逻辑进行介绍。
- 变量：在逻辑中，用于表示对象或概念的符号，可分为自由变量和绑定变量。
- 语义（Sémantique）：解释一阶逻辑公式的方法。
- 语义属性（Propriétés sémantiques）：一阶逻辑的模型、一致性和完备性等属性。
- 推理（Déduction）：从已有的逻辑前提中推导出新的结论的方法。
10. 自动机理论（Automates finis）
- 动机和例子：讨论自动化理论的动机和实例。
- 定义：描述有限自动机的结构和如何操作。
- 确定性（Détermination）：确定性自动机和非确定性自动机的区别。
- 操作：包括自动机的并、交、补等操作。
- 有理语言（Langages rationnels）：由有限自动机识别的语言。
- 最小化（Minimisation）：将自动机简化为最小状态的过程。
以上知识点涵盖了离散结构的基础理论、递归和归纳原理、偏序集、良序集合、逻辑工具、命题逻辑、一阶逻辑和有限自动机理论的基本概念和重要原理。这些概念和原理在计算机科学和信息学领域具有广泛的应用价值，是理解更高级数学和逻辑问题的基础。
