Faisons connaissance avec la notion de superposition (ou imposition) de fonctions, qui consiste à substituer une fonction par un autre argument à la place de l'argument d'une fonction donnée. Par exemple, une superposition de fonctions donne une fonction, et les fonctions sont obtenues de la même manière

En général, supposons qu'une fonction soit définie dans un certain domaine et que la fonction soit définie dans un domaine et que ses valeurs soient toutes contenues dans le domaine. Alors la variable z, comme on dit, via y, est elle-même une fonction de.

Étant donné une valeur donnée, ils trouvent d'abord la valeur y qui lui correspond (selon la règle caractérisée par un signe), puis fixent la valeur y correspondante (selon la règle

caractérisé par un signe, sa valeur est considérée comme correspondant au x sélectionné. La fonction résultante d'une fonction ou d'une fonction complexe est le résultat d'une superposition de fonctions

L'hypothèse selon laquelle les valeurs de la fonction ne dépassent pas les limites de la région Y dans laquelle la fonction est définie est très significative : si elle est omise, alors une absurdité peut en résulter. Par exemple, en supposant que nous ne pouvons considérer que les valeurs de x pour lesquelles autrement l'expression n'aurait aucun sens.

Il nous semble utile de souligner ici que la caractérisation d’une fonction comme complexe n’est pas liée à la nature de la dépendance fonctionnelle de z à l’égard de x, mais seulement à la manière dont cette dépendance est spécifiée. Par exemple, laissez y entrer pour Then

Ici, la fonction s'est avérée être spécifiée comme une fonction complexe.

Maintenant que la notion de superposition de fonctions est bien comprise, nous pouvons caractériser avec précision les plus simples de ces classes de fonctions étudiées en analyse : ce sont d'abord les fonctions élémentaires énumérées ci-dessus puis toutes celles qui en sont obtenues. utilisant quatre opérations arithmétiques et superpositions, appliquées successivement un nombre fini de fois. On dit qu'ils s'expriment à travers l'élémentaire dans leur forme définitive ; parfois, ils sont aussi appelés élémentaires.

Par la suite, après avoir maîtrisé un appareil analytique plus complexe (séries infinies, intégrales), nous ferons connaissance avec d'autres fonctions qui jouent également un rôle important dans l'analyse, mais dépassent déjà la classe des fonctions élémentaires.

Soit une fonction f(x 1 , x 2 , ... , x n) et des fonctions

alors nous appellerons la fonction superposition d'une fonction f(x 1 , x 2 , ... , x n) et fonctions .

En d'autres termes : soit F = ( f j ) - un ensemble de fonctions d'algèbre logique, pas nécessairement finies. Une fonction f est appelée superposition de fonctions de l'ensemble F ou fonction sur F si elle est obtenue à partir d'une fonction en remplaçant une ou plusieurs de ses variables par des fonctions de l'ensemble F.

Exemple.

Soit un ensemble de fonctions

F = (f 1 (x 1), f 2 (x 1 , x 2 , x 3), f 3 (x 1 , x 2)).

Alors les superpositions de fonctions de F seront, par exemple, les fonctions :

j 1 (x 2 , x 3) = f 3 (f 1 (x 2), f 1 (x 3));

j 2 (x 1 , x 2) = f 2 (x 1 , f 1 (x 1), f 3 (x 1 , x 2)).

Perfect DNF - superposition de fonctions à partir d'un ensemble

. ð

Définition.

Le système de fonctions s'appelle complet, si l'on utilise les opérations de superposition et de remplacement de variables, n'importe quelle fonction de l'algèbre logique peut être obtenue à partir des fonctions de ce système. ð

Nous disposons déjà d'un certain ensemble de systèmes complets :

;

Parce que ;

Parce que ;

(x+y, xy, 1). ð

Comment déterminer les conditions dans lesquelles le système est complet ? Le concept de classe fermée est étroitement lié au concept d’exhaustivité.

Cours fermés.

L'ensemble (classe) K des fonctions de l'algèbre de la logique est appelé classe fermée, s'il contient toutes les fonctions obtenues à partir de K par opérations de superposition et de changement de variables, et ne contient aucune autre fonction.

Soit K un sous-ensemble de fonctions de P 2 . La fermeture de K est l'ensemble de toutes les fonctions booléennes qui peuvent être représentées à l'aide des opérations de superposition et de changement de variables de fonctions de l'ensemble K. La fermeture d'un ensemble K est notée [K].

En termes de clôture, nous pouvons donner d'autres définitions de clôture et d'exhaustivité (équivalentes aux originales) :

K est une classe fermée si K = [K] ;

K est un système complet si [K] = P 2 .

Exemples.

* (0), (1) - classes fermées.

* Un ensemble de fonctions d'une variable est une classe fermée.

* - classe fermée.

* La classe (1, x+y) n'est pas une classe fermée.

Examinons quelques-unes des classes fermées les plus importantes.

1. T 0- classe de fonctions qui préservent 0.

Notons T 0 la classe de toutes les fonctions de l'algèbre logique f(x 1 , x 2 , ... , x n) préservant la constante 0, c'est-à-dire les fonctions pour lesquelles f(0, ... , 0 ) = 0.

Il est facile de voir qu'il existe des fonctions qui appartiennent à T 0, et des fonctions qui n'appartiennent pas à cette classe :

0, x, xy, xÚy, x+y О T 0 ;

Du fait que Ï T 0 il résulte, par exemple, qu'il ne peut pas être exprimé par disjonction et conjonction.

Puisque le tableau de la fonction f de la classe T 0 contient la valeur 0 dans la première ligne, alors pour les fonctions de T 0, vous pouvez définir des valeurs arbitraires uniquement sur 2 n - 1 ensemble de valeurs variables, c'est-à-dire

,

où est l'ensemble des fonctions qui préservent 0 et dépendent de n variables.

Montrons que T 0 est une classe fermée. Puisque xÎT 0 , alors pour justifier la fermeture il suffit de montrer la fermeture par rapport à l'opération de superposition, puisque l'opération de changement de variables est un cas particulier de superposition avec la fonction x.

Laisser . Il suffit alors de le montrer. Cette dernière découle de la chaîne des égalités

2. T1- classe de fonctions préservant 1.

Notons T 1 la classe de toutes les fonctions de l'algèbre logique f(x 1, x 2, ... , x n) préservant la constante 1, c'est-à-dire les fonctions pour lesquelles f(1, ... , 1 ) = 1.

Il est facile de voir qu'il existe des fonctions qui appartiennent à T 1, et des fonctions qui n'appartiennent pas à cette classe :

1, x, xy, xÚy, xºy О T 1 ;

0, , x+y Ï T 1 .

Du fait que x + y Ï T 0 il résulte, par exemple, que x + y ne peut pas être exprimé en termes de disjonction et de conjonction.

Les résultats sur la classe T 0 sont trivialement transférés à la classe T 1 . Ainsi nous avons :

T 1 - classe fermée ;

.

3.L- classe de fonctions linéaires.

Notons L la classe de toutes les fonctions de l'algèbre logique f(x 1 , x 2 , ... , x n) qui sont linéaires :

Il est facile de voir qu’il existe des fonctions qui appartiennent à L et des fonctions qui n’appartiennent pas à cette classe :

0, 1, x, x+y, x 1 º x 2 = x 1 + x 2 + 1, = x+1 О L ;

Montrons, par exemple, que xÚy Ï L .

Supposons le contraire. Nous chercherons une expression de xÚy sous la forme d'une fonction linéaire à coefficients indéterminés :

Pour x = y = 0 on a a=0,

pour x = 1, y = 0 on a b = 1,

pour x = 0, y = 1 on a g = 1,

mais alors pour x = 1, y = 1 nous avons 1v 1 ¹ 1 + 1, ce qui prouve la non-linéarité de la fonction xy.

La preuve de l’étroitesse de la classe des fonctions linéaires est assez évidente.

Puisqu'une fonction linéaire est déterminée de manière unique en précisant les valeurs n+1 du coefficient a 0 , ... , an , le nombre de fonctions linéaires dans la classe L (n) de fonctions dépendant de n variables est égal à 2 n+1 .

.

4.S- classe de fonctions auto-duales.

La définition de la classe des fonctions auto-duales est basée sur l'utilisation du principe dit de dualité et des fonctions duelles.

La fonction définie par l'égalité s'appelle double à la fonction .

Évidemment, le tableau de la fonction double (avec l'ordre standard des ensembles de valeurs de variables) est obtenu à partir du tableau de la fonction d'origine en inversant (c'est-à-dire en remplaçant 0 par 1 et 1 par 0) la colonne des valeurs de fonction. et le retourner.

C'est facile de voir ça

(x 1 Ú x 2)* = x 1 Ù x 2 ,

(x 1 Ù x 2)* = x 1 Ú x 2 .

Il résulte de la définition que (f*)* = f, c'est-à-dire que la fonction f est duale à f*.

Supposons qu'une fonction soit exprimée en utilisant la superposition à travers d'autres fonctions. La question est de savoir comment construire une formule qui implémente ? Notons par = (x 1, ..., x n) tous les différents symboles variables trouvés dans les ensembles.

Théorème 2.6. Si la fonction j est obtenue par superposition de fonctions f, f 1, f 2, ..., f m, c'est-à-dire

une fonction duale à une superposition est une superposition de fonctions duales.

Preuve.

j*(x 1 ,...,x n) = ` f(`x 1 ,...,`x n) =

Le théorème a été prouvé. ð

Le principe de dualité découle du théorème : si une formule A réalise la fonction f(x 1 , ... , x n), alors la formule obtenue à partir de A en remplaçant les fonctions qu'elle contient par leurs duales réalise la fonction duale f *(x 1 , ... , xn).

Notons S la classe de toutes les fonctions auto-duales de P 2 :

S = (f | f* = f )

Il est facile de voir qu’il existe des fonctions qui appartiennent à S et des fonctions qui n’appartiennent pas à cette classe :

0, 1, xy, xÚy Ï S .

Un exemple moins trivial de fonction auto-duale est la fonction

h(x, y, z) = xy Ú xz Ú ​​​​​​yz ;

En utilisant le théorème sur la fonction dual à la superposition, on a

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h* ; h О S.

Pour une fonction auto-duale, l'identité est valable

ainsi de suite et , que nous appellerons ci-contre, la fonction auto-duale prend des valeurs opposées. Il s'ensuit que la fonction auto-duale est entièrement déterminée par ses valeurs dans la première moitié des lignes du tableau standard. Par conséquent, le nombre de fonctions auto-duales dans la classe S (n) de fonctions dépendant de n variables est égal à :

.

Montrons maintenant que la classe S est fermée. Depuis xÎS , alors pour justifier la fermeture il suffit de montrer la fermeture par rapport à l'opération de superposition, puisque l'opération de changement de variables est un cas particulier de superposition avec la fonction x. Laisser . Il suffit alors de le montrer. Ce dernier s'installe directement :

5.M- classe de fonctions monotones.

Avant de définir le concept de fonction monotone en algèbre logique, il est nécessaire d'introduire une relation d'ordre sur l'ensemble des ensembles de ses variables.

Ils disent que l'ensemble vient avant l'ensemble (ou « pas plus que » ou « inférieur ou égal à »), et utilisez la notation si a i £ b i pour tout i = 1, ... , n. Si et , alors nous dirons que l'ensemble précède strictement l'ensemble (ou « strictement inférieur », ou « inférieur à » l'ensemble), et utiliserons la notation . Les ensembles et sont appelés comparables si , ou . Dans le cas où aucune de ces relations n'est valable, les ensembles et sont appelés incomparables. Par exemple, (0, 1, 0, 1) £ (1, 1, 0, 1), mais les ensembles (0, 1, 1, 0) et (1, 0, 1, 0) sont incomparables. Ainsi, la relation £ (souvent appelée relation de préséance) est un ordre partiel sur l'ensemble B n. Vous trouverez ci-dessous des diagrammes des ensembles partiellement ordonnés B 2, B 3 et B 4.

La relation d’ordre partiel introduite est un concept extrêmement important qui dépasse largement le cadre de notre cours.

Nous avons maintenant la possibilité de définir la notion de fonction monotone.

La fonction d'algèbre logique s'appelle monotone, si pour deux ensembles quelconques et , tel que , l'inégalité est vraie . L'ensemble de toutes les fonctions monotones de l'algèbre logique est noté M, et l'ensemble de toutes les fonctions monotones dépendant de n variables est noté M(n).

Il est facile de voir qu’il existe des fonctions qui appartiennent à M et des fonctions qui n’appartiennent pas à cette classe :

0, 1, x, xy, xÚy О M ;

x+y, x®y, xºy Ï M .

Montrons que la classe des fonctions monotones M est une classe fermée. Depuis xОМ, alors pour justifier la fermeture il suffit de montrer la fermeture par rapport à l'opération de superposition, puisque l'opération de changement de variables est un cas particulier de superposition avec la fonction x.

Laisser . Il suffit alors de le montrer.

Soit des ensembles de variables, respectivement, les fonctions j, f 1 , ... , f m , et l'ensemble des variables de la fonction j est constitué de celles et uniquement de ces variables qui apparaissent dans les fonctions f 1 , ... , f m . Soit et deux ensembles de valeurs de la variable, et . Ces ensembles définissent les ensembles valeurs variables , tel que . En raison de la monotonie des fonctions f 1 , ... , f m

et en raison de la monotonie de la fonction f

De là, nous obtenons

Le nombre de fonctions monotones dépendant de n variables n'est pas connu avec précision. La limite inférieure peut être facilement obtenue :

où - est la partie entière de n/2.

Il s’avère aussi simplement que l’estimation ci-dessus est trop élevée :

Affiner ces estimations est une tâche importante et intéressante de la recherche moderne.

Critère d'exhaustivité

Nous sommes désormais capables de formuler et de prouver un critère de complétude (théorème de Post), qui détermine les conditions nécessaires et suffisantes pour la complétude d'un système de fonctions. Faisons précéder la formulation et la preuve du critère de complétude de plusieurs lemmes nécessaires qui ont un intérêt indépendant.

Lemme 2.7. Lemme sur une fonction non-auto-duale.

Si f(x 1 , ... , x n)Ï S , alors une constante peut en être obtenue en substituant les fonctions x et `x.

Preuve. Depuis fÏS, alors il existe un ensemble de valeurs des variables
=(a 1 ,...,a n) tel que

f(`une 1 ,...,`une n) = f(une 1 ,...,une n)

Remplaçons les arguments dans la fonction f :

x i est remplacé par ,

c'est-à-dire, posons et considérons la fonction

Ainsi, nous avons obtenu une constante (même si on ne sait pas de quelle constante il s'agit : 0 ou 1). ð

Lemme 2.8. Lemme sur la fonction non monotone.

Si la fonction f(x 1 ,...,x n) est non monotone, f(x 1 ,...,x n) Ï M, alors une négation peut en être obtenue en changeant les variables et en remplaçant les constantes 0 et 1.

Preuve. Puisque f(x 1 ,...,x n) Ï M, alors il existe des ensembles de valeurs de ses variables, , , tel que , et pour au moins une valeur i, a i< b i . Выполним следующую замену переменных функции f:

x je serai remplacé par

Après une telle substitution on obtient une fonction d'une variable j(x), pour laquelle on a :

Cela signifie que j(x)=`x. Le lemme est prouvé. ð

Lemme 2.9. Lemme sur la fonction non linéaire.

Si f(x 1 ,...,x n) Ï L , alors à partir de là en substituant les constantes 0, 1 et en utilisant la fonction `x nous pouvons obtenir la fonction x 1 &x 2 .

Preuve. Représentons f comme un DNF (par exemple un DNF parfait) et utilisons les relations :

Exemple. Donnons deux exemples d'application de ces transformations.

Ainsi, une fonction écrite sous forme normale disjonctive, après application des relations indiquées, parenthèses ouvrantes et transformations algébriques simples, devient un polynôme mod 2 (polynôme de Zhegalkin) :

où A 0 est une constante et A i est une conjonction de certaines variables du nombre x 1,..., x n, i = 1, 2, ..., r.

Si chaque conjonction A i est constituée d'une seule variable, alors f est une fonction linéaire, ce qui contredit la condition du lemme.

Par conséquent, dans le polynôme de Zhegalkin pour la fonction f, il existe un terme qui contient au moins deux facteurs. Sans perte de généralité, on peut supposer que parmi ces facteurs il existe des variables x 1 et x 2. Le polynôme peut alors être transformé comme suit :

f = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (x 3 ,..., x n),

où f 1 (x 3 ,..., x n) ¹ 0 (sinon le polynôme n'inclut pas de conjonction contenant la conjonction x 1 x 2).

Soit (a 3 ,...,a n) tel que f 1 (a 3 ,...,a n) = 1. Alors

j(x 1 ,x 2) = f(x 1 ,x 2 , a 3 ,...,a n) = x 1 x 2 +ax 1 +bx 2 +g ,

où a, b, g sont des constantes égales à 0 ou 1.

Utilisons l'opération de négation que nous avons et considérons la fonction y(x 1 ,x 2) obtenue à partir de j(x 1 ,x 2) comme suit :

y(x 1 ,x 2) = j(x 1 +b, x 2 +a)+ab+g.

Il est évident que

y(x 1 ,x 2) =(x 1 +b)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2.

Ainsi,

y(x 1 ,x 2) = x 1 x 2 .

Le lemme est complètement prouvé. ð

Lemme 2.10. Le lemme principal du critère de complétude.

Si la classe F=( f ) des fonctions d'algèbre logique contient des fonctions qui ne préservent pas l'unité, ne préservent pas 0, sont non auto-duales et non monotones :

puis à partir des fonctions de ce système, par opérations de superposition et de remplacement de variables, on peut obtenir les constantes 0, 1 et la fonction.

Preuve. Considérons la fonction. Alors

.

Il existe deux cas possibles de considérations ultérieures, désignés dans la présentation suivante par 1) et 2).

1). La fonction sur l'ensemble des unités prend la valeur 0 :

.

Remplaçons toutes les variables de la fonction par la variable x. Alors la fonction

il y en a, parce que

Et .

Prenons une fonction non-auto-duale. Puisque nous avons déjà obtenu la fonction, alors par le lemme sur une fonction non-auto-duale (lemme 2.7. ) vous pouvez obtenir une constante. La deuxième constante peut être obtenue à partir de la première en utilisant la fonction. Ainsi, dans le premier cas considéré, on obtient des constantes et des négations. . Le deuxième cas, et avec lui le lemme principal du critère de complétude, sont complètement prouvés. ð

Théorème 2.11. Un critère pour l'exhaustivité des systèmes de fonctions dans l'algèbre de la logique (théorème de Post).

Pour que le système de fonctions F = (f i ) soit complet, il faut et suffisant qu'il ne soit entièrement contenu dans aucune des cinq classes fermées T 0, T 1, L, S, M, c'est-à-dire pour chacune des classes T 0 , T 1 , L , S, M dans F comporte au moins une fonction qui n'appartient pas à cette classe.

Nécessité. Soit F un système complet. Supposons que F soit contenu dans l'une des classes indiquées, notons-le par K, c'est-à-dire F Í K. La dernière inclusion est impossible, puisque K est une classe fermée qui n'est pas un système complet.

Adéquation. Supposons que l'ensemble du système de fonctions F = (f i ) ne soit contenu dans aucune des cinq classes fermées T 0 , T 1 , L , S , M . Prenons les fonctions suivantes dans F :

Ensuite, à partir du lemme principal (lemme 2.10 ) à partir d'une fonction qui ne préserve pas 0, d'une fonction qui ne préserve pas 1, de fonctions non auto-duales et non monotones, on peut obtenir les constantes 0, 1 et la fonction de négation :

.

Basé sur le lemme des fonctions non linéaires (lemme 2.9 ) à partir de constantes, de négation et d'une fonction non linéaire on peut obtenir la conjonction :

.

Système de fonction - un système complet selon le théorème sur la possibilité de représenter n'importe quelle fonction de l'algèbre de la logique sous la forme d'une forme normale disjonctive parfaite (notez que la disjonction peut être exprimée par conjonction et négation sous la forme ).

Le théorème est complètement prouvé. ð

Exemples.

1. Montrons que la fonction f(x,y) = x|y forme un système complet. Construisons un tableau des valeurs de la fonction x½y :

X	oui	x|y

f(0,0) = 1, donc x | yÏT 0 .

f(1,1) = 0, donc x | yÏT 1 .

f(0,0) = 1, f(1,1) = 0, donc x | ouais.

f(0,1) = f(1,0) = 1, - sur des ensembles opposés x | y prend les mêmes valeurs, donc x | oui.

Finalement, que signifie la non-linéarité de la fonction ?
X | y.

Sur la base du critère d'exhaustivité, nous pouvons affirmer que f(x,y) = x | y forme un système complet. ð

2. Montrons que le système de fonctions forme un système complet.

Vraiment, .

Ainsi, parmi les fonctions de notre système nous avons trouvé : une fonction qui ne préserve pas 0, une fonction qui ne préserve pas 1, des fonctions non auto-duales, non monotones et non linéaires. Sur la base du critère d'exhaustivité, on peut affirmer que le système de fonctions forme un système complet. ð

Ainsi, nous sommes convaincus que le critère de complétude fournit un moyen constructif et efficace de déterminer la complétude des systèmes de fonctions dans l’algèbre logique.

Formulons maintenant trois corollaires du critère de complétude.

Corollaire 1. Toute classe fermée K de fonctions de l'algèbre logique qui ne coïncide pas avec l'ensemble des fonctions de l'algèbre logique (K¹P 2) est contenue dans au moins une des classes fermées construites.

Définition. La classe fermée K s'appelle pré-complet, si K est incomplet et pour toute fonction fÏ K la classe K È (f) est complète.

De la définition, il s'ensuit que la classe précomplète est fermée.

Corollaire 2. En algèbre logique, il n'existe que cinq classes précomplètes, à savoir : T 0, T 1, L, M, S.

Pour prouver le corollaire, il suffit de vérifier qu'aucune de ces classes n'est contenue dans l'autre, ce que confirme par exemple le tableau suivant des fonctions appartenant à différentes classes :

	T0	T1	L	S	M
	+	-	+	-	+
	-	+	+	-	+
	-	-	+	+	-

Corollaire 3. De tout système complet de fonctions, il est possible de distinguer un sous-système complet ne contenant pas plus de quatre fonctions.

De la preuve du critère d’exhaustivité, il s’ensuit que pas plus de cinq fonctions peuvent être distinguées. De la preuve du lemme principal (Lemme 2.10 ) il s'ensuit que soit n'est pas auto-duel, soit ne préserve pas l'unité et n'est pas monotone. Par conséquent, pas plus de quatre fonctions sont nécessaires.

- (Lat. superpositio, - superposition, de Lat. superpositus - placé sur le dessus) (composition) - opération logico-mathématique. calcul, qui consiste à obtenir de k.l. fonctions f et g données calcul d'une nouvelle fonction g (f) (expression g... ... Encyclopédie philosophique

Le terme superposition (superposition) peut faire référence aux concepts suivants : Composition de superposition de fonctions (fonction complexe) Le principe de superposition est un principe en physique et en mathématiques qui décrit la superposition de processus (par exemple, des ondes) et, par conséquent, ... ... Wikipédia

Composition de fonctions, composer une fonction complexe à partir de deux fonctions... Encyclopédie mathématique

Ce terme a d'autres significations, voir Superposition. Mécanique quantique... Wikipédia

Cet article ou cette section contient une liste de sources ou de références externes, mais les sources des déclarations individuelles restent floues en raison du manque de notes de bas de page... Wikipédia

Dans la théorie des systèmes fonctionnels discrets, une fonction booléenne est une fonction de type, où est un ensemble booléen et n est un entier non négatif, appelé arité ou localité de la fonction. Les éléments 1 (un) et 0 (zéro) sont interprétés standard ... ... Wikipedia

L'un des plus importants pour les fondements des mathématiques et des mathématiques. contiennent des classes logiques de concepts qui servent de clarifications. les concepts d'une fonction arithmétique efficacement calculable et d'un prédicat arithmétique effectivement décidable, et finalement, et... ... Encyclopédie philosophique

Fonction, le calcul des valeurs d'un essaim peut être effectué à l'aide d'une procédure efficace prédéterminée, ou d'un algorithme. Une caractéristique des processus informatiques est que le calcul des quantités requises de problèmes se produit séquentiellement à partir des données initiales... ... Encyclopédie mathématique

Il est nécessaire de transférer le contenu de cet article vers l'article « Différenciation d'une fonction complexe ». Vous pouvez aider le projet en combinant des articles. S'il est nécessaire de discuter de la faisabilité d'une fusion, remplacez ce modèle par le modèle ((pour fusionner)) ... Wikipédia

- (lat. compositio composition, lien, addition, connexion) : Le Wiktionnaire a un article « composition » Art La composition (beaux-arts) est un composant organisateur d'une forme artistique qui donne pro... Wikipédia

Livres

• Mathématiques discrètes. Constructions de base de la théorie des ensembles. Partie VI, A.I. Shirokov. Le manuel constitue la sixième partie de la section « Constructions de base de la théorie des ensembles des mathématiques discrètes ». Pouce. XI considère les notions suivantes : compositions de fonctions (§1) ; les fonctions,...

Les dispositifs logiques discrets à cycle unique (ne contenant pas d'éléments de mémoire) implémentent en sortie un certain ensemble de fonctions d'algèbre logique `F m =(F 1 ,F 2 ,…,Fm), qui à chaque instant dépendent uniquement de l'état des entrées de l'appareil `x n =(X 1 ,X 2 ,…,xn): `Fm = `Fm(`xn). En pratique, de tels dispositifs sont conçus et fabriqués à partir d'éléments indivisibles distincts qui mettent en œuvre un certain ensemble (système) ( F) fonctions élémentaires de l'algèbre en connectant les sorties de certains éléments aux entrées d'autres.

Lors de la conception de dispositifs logiques, les questions suivantes sont pertinentes.

1. Un système de fonctions élémentaires est donné ( F). Quelles sont les fonctions de sortie Fi peut être obtenu en utilisant les fonctions de ( F}?

2. Un ensemble de fonctions booléennes de sortie ( F) (en particulier, égal à l'ensemble des fonctions de l'algèbre de la logique R. 2). Quel devrait être le système initial de fonctions élémentaires ( F), offrant la possibilité d'obtenir en sortie n'importe laquelle des fonctions de l'ensemble ( F}?

Pour apporter une réponse raisonnable à ces questions, les notions de superposition, de fermeture et d'exhaustivité des systèmes de fonctions sont utilisées.

Définition. Considérons un ensemble de connecteurs logiques ( F), correspondant à un système de fonctions ( F} . Superposition sur{F) est toute fonction j qui peut être réalisée par une formule sur ( F}.

En pratique, la superposition peut être représentée comme le résultat de la substitution de fonctions de ( F) comme arguments d'une fonction du même ensemble.

Exemple 1. Considérons un système de fonctions ( F} = {F 1 (X) ='x, f 2 (x,y)= X&oui, f 3 (x,y)=XÚ y). Remplacement dans la fonction F 3 (x,y) au lieu du premier argument X fonction F 1 (X), au lieu du deuxième - F 2 (x,y), on obtient la superposition h(x,y)=F 3 (F 1 (X),F 2 (x,y))=`xÚ X& à. La mise en œuvre physique de la substitution est donnée sur la Fig. 1.18.

Définition. Laisser M-certain ensemble de fonctions d'algèbre logique ( P. 2). L'ensemble de toutes les superpositions sur M appelé court-circuit ensembles M et est noté [ M]. Réception [ M]par l'ensemble d'origine M appelé opération de fermeture. Un tas de M appelé classe fonctionnellement fermée, Si [ M] = M. Sous-ensemble mÍ M appelé système fonctionnellement complet en M, Si [ m] = M.

Fermeture [ M] représente l'ensemble des fonctions pouvant être obtenues à partir de M en appliquant l'opération de superposition, c'est-à-dire toutes les substitutions possibles.

Remarques. 1.Évidemment, tout système de fonctions ( F) est fonctionnellement complet en soi.

2 . Sans perte de généralité, on peut supposer que la fonction d'identité F(X)=x, qui ne modifie pas les valeurs de vérité des variables, fait initialement partie de tout système de fonctions.

Exemple 2. Pour les systèmes de fonctions décrits ci-dessous ( F) procédez comme suit :

1) trouver la fermeture [ F],

2) savoir si le système ( F) classe fermée,

3) trouver des systèmes fonctionnellement complets dans ( F}.

Solution.

JE. ( F}={0} . Lors du remplacement de la fonction ( fº 0) nous le recevons en nous-mêmes, c'est-à-dire aucune nouvelle fonction n'est créée. Cela implique: [ F] = {F). Le système considéré est une classe fonctionnellement fermée. Le système fonctionnellement complet qu'il contient est un et égal au tout ( F}.

II. ( F} = {0,Ø } . Ø de remplacement (Ø X)donne une fonction identique qui n’étend pas formellement le système d’origine. Cependant, en remplaçant Ø (0) nous obtenons une unité identique - une nouvelle fonction qui n'était pas dans le système d'origine : Ø (0)=1 . L'application de toutes les autres substitutions n'entraîne pas l'apparition de nouvelles fonctions, par exemple : ØØ 0 = 0, 0(Ø X)=0.

Ainsi, l'utilisation de l'opération de superposition a permis d'obtenir un ensemble de fonctions plus large que celui d'origine [ F]=(0,Ø ,1). Cela implique une entrée stricte : ( F} Ì [ F]. Système source ( F) n'est pas une classe fonctionnellement fermée. En plus du système lui-même ( F) il n'y a pas d'autres systèmes fonctionnellement complets, car dans le cas de son rétrécissement à partir d'une seule fonction f= 0 ne peut pas être annulé par substitution, et un zéro identique ne peut pas être obtenu à partir de la seule fonction de négation.

III. ( F) = (& ,Ú ,Ø ).La clôture de ce système est l'ensemble des fonctions de l'algèbre de la logique P. 2, puisque la formule de n'importe lequel d'entre eux peut être représentée par DNF ou CNF, qui utilise des fonctions élémentaires ( F) = (& ,Ú ,Ø). Ce fait est une preuve constructive de l'exhaustivité du système de fonctions considéré dans P. 2: [F]=P 2 .

Depuis dans P. 2 contient une infinité d'autres fonctions autres que ( F) = (& ,Ú ,Ø ), alors cela implique une occurrence stricte : ( F}Ì[ F]. Le système considéré n’est pas une classe fonctionnellement fermée.

En plus du système lui-même, les sous-systèmes seront fonctionnellement complets ( F) 1 = (& ,Ø ) et ( F) 2 = (Ú ,Ø ). Cela découle du fait qu'en utilisant les règles de De Morgan, la fonction d'addition logique Ú peut être exprimée par (& , Ø), et la fonction de multiplication logique & par (Ú, Ø) :

(X & à) = Ø (` XÚ` à), (X Ú à) = Ø ( X &`à).

Autres sous-systèmes fonctionnellement complets dans ( F) Non.

Vérification de l'exhaustivité du sous-système fonctionnel ( F) 1 m ( F)dans tout le système ( F)peut être produit en mélangeant ( F) 1 à l'autre, évidemment à compléter en ( F)système.

Incomplétude du sous-système ( F) 1 po ( F)peut être vérifié en prouvant la stricte occurrence de [ F 1 ] М [ F].

Définition. Sous-ensemble mÍ M appelé base fonctionnelle(base)systèmes M, Si [ m] = M, et après en avoir exclu toute fonction, l'ensemble des fonctions restantes n'est pas complet dans M .

Commentaire. Bases du système de fonctions (F) sont tous ses sous-systèmes fonctionnellement complets (F) 1, qui ne peut être réduit sans perte d’exhaustivité dans (F).

Exemple 3. Pour tous les systèmes considérés dans l’exemple 2, trouvez les bases.

Solution.Dans les cas 1 et 2, seuls les systèmes eux-mêmes sont fonctionnels et il est impossible de les affiner. Par conséquent, ce sont aussi des bases.

Dans le cas 3, il y en a deux fonctionnellement complets dans ( F)sous-systèmes ( F) 1 = (&,Ø ) et ( F) 2 =(Ú,Ø ), qui ne peut être réduit sans perte d’exhaustivité. Ils seront les bases du système ( F} = {&,Ú,Ø}.

Définition. Laissez le système ( F) est une classe fermée. Son sous-ensemble ( F) 1 m ( F) sont appelés classe junior en{F), Si ( F) 1 n'est pas complet dans ( F} ([F 1 ] М [ F]), et pour toute fonction j du système ( F), non inclus dans ( F) 1 (jО( F} \ {F) 1) vrai : [ jÈ { F} 1 ] = [F], c'est à dire. en ajoutant jк ( F) 1 le complète en ( F} .

Tâches

1. Vérifier l'étanchéité des ensembles de fonctions :

une) (Ø); b) (1,Ø); c) ((0111); (10));d) ((11101110); (0110));d) ((0001); (00000001); (000000000000000001); … ).

2. Vérifiez l'intégralité des systèmes fonctionnels dans P. 2:

une) (0,Ø); b) ((0101) , (1010) ); V ); d) ((0001) , (1010) ).

3. Trouver la clôture du système de fonctions et sa base :

une) (0, 1, Ø); b) ((1000) , (1010), (0101) ); c) ((0001) , (1110), (10) ); d) ((1010) , (0001), (0111) ).

1.10.2 Fonctions qui préservent les constantes. Classes T 0 et T 1

Définition. Fonction F(`xn) enregistre 0 si F(0,..., 0) = 0. Fonction F(`xn) enregistre 1 si F(1, ... , 1) = 1.

Beaucoup de fonctionnalités n les variables qui stockent 0 et 1 sont notées respectivement, T 0 n Et T 1 n. Tous les ensembles de fonctions d'algèbre logique qui préservent 0 et 1 , dénoter T 0 Et T 1 . Chacun des ensembles T 0 et T 1 est une classe précomplète fermée dans R. 2 .

Des fonctions élémentaires à T 0 et T 1 sont simultanément inclus, par exemple, & et Ú. Appartenance de toute fonction aux classes T 0 , T 1 peut être vérifié par la première et la dernière valeur de son vecteur de valeurs dans la table de vérité ou en remplaçant directement des zéros et des uns dans la formule lors de la spécification analytique de la fonction.

Définition.Dupliquer est une substitution dans laquelle la même variable est substituée dans une fonction au lieu de plusieurs variables indépendantes. Dans ce cas, les valeurs des variables dans des ensembles qui prenaient auparavant des valeurs indépendamment les unes des autres seront toujours les mêmes.

TÂCHES

1.Vérifiez l’appartenance au cours T 0 Et T1 les fonctions:

a) addition généralisée, b) multiplication généralisée, c) constantes, d) xyÚ ouais, d) X® à® xy, e) XÅ à, et)( X 1 Å … Å X n) ® ( oui 1 Å … Å oui m) à n,mÎ N.

2. Prouver la fermeture de chacune des classes T 0 Et T 1 .

3. Prouver que si F(`xn) Ï T 0, puis à partir de là, en dupliquant la substitution, vous pouvez obtenir la constante 1 ou la négation.

4. Prouver que si F(`xn) Ï T 1 , puis à partir de là, en dupliquant la substitution, vous pouvez obtenir la constante 0 ou la négation.

5. Prouver le caractère précomplet de chacune des classes T 0 Et T 1 (par exemple, en réduisant le système augmenté à ( F} = {& ,Ú ,Ø }).

6. Trouvez le pouvoir des cours T 0 n Et T 1 n.

Qu'il y ait un ensemble K, composé d'un nombre fini de fonctions booléennes. Une superposition de fonctions de cet ensemble sont les nouvelles fonctions obtenues en appliquant un nombre fini de deux opérations ;

vous pouvez renommer n'importe quelle variable incluse dans une fonction de K;

au lieu de n'importe quelle variable, vous pouvez mettre une fonction de l'ensemble K ou une superposition préalablement formée.

La superposition est aussi appelée fonction complexe.

Exemple 7. 1. Si on lui donne une fonction X|oui(coup de Schaeffer), alors ses superpositions, en particulier, seront les fonctions suivantes x|x,x|(x|y),x|(y|z) etc.

En fermant ensemble de fonctions de K est appelé l’ensemble de toutes les superpositions. Classe de fonction K appelé fermé, si sa fermeture coïncide avec elle-même.

L'ensemble des fonctions est appelé complet, si sa fermeture coïncide avec toutes les fonctions logiques. En d’autres termes, un ensemble complet est un ensemble de ces fonctions à travers lequel toutes les autres fonctions booléennes peuvent être exprimées.

Un ensemble complet de fonctions non redondantes est appelé une base(« non redondant » signifie que si une fonction est supprimée de l'ensemble, alors cet ensemble ne sera plus complet).

Exemple 7.2. Conjonction, disjonction et négation forment un ensemble complet (nous en avons été convaincus dans la section 5), mais ne constituent pas une base, car cet ensemble est redondant, puisqu'en utilisant les règles de De Morgan on peut supprimer une conjonction ou une disjonction. Toute fonction peut être représentée comme un polynôme de Zhegalkin (Section 6). Il est clair que les fonctions conjonction, addition modulo 2 et les constantes 0 et 1 constituent un ensemble complet, mais ces quatre fonctions ne sont pas non plus une base, puisque 1+1=0, et donc la constante 0 peut être exclue de l'ensemble complet. ensemble (pour construire des polynômes, la constante de Zhegalkin 0 est nécessaire puisque l'expression « 1+1 » n'est pas un polynôme de Zhegalkin).

Il est facile de voir que l'un des moyens de vérifier l'intégralité d'un ensemble À est de vérifier que les fonctions d'un autre ensemble complet sont exprimées à travers des fonctions de cet ensemble (on peut vérifier cela à travers des fonctions de À on peut exprimer conjonction et négation ou disjonction et négation.

Il existe des fonctions telles qu'une de ces fonctions est elle-même une base (il suffit ici de vérifier uniquement l'exhaustivité ; la non-redondance est évidente). De telles fonctions sont appelées fonctions de Scheffer. Ce nom est dû au fait que le trait de Schaeffer constitue une base. Rappelons que le nombre premier de Schaeffer est défini par la table de vérité suivante :

Puisqu'il est évident, c'est-à-dire que la négation est une superposition du trait de Schaeffer, et la disjonction alors , le trait de Schaeffer est lui-même une base. De même, la flèche de Peirce est une fonction de Scheffer (les élèves peuvent le vérifier par eux-mêmes). Pour les fonctions de 3 variables ou plus, il existe de nombreuses fonctions Sheffer (bien sûr, exprimer d'autres fonctions booléennes via une fonction Sheffer d'un grand nombre de variables est difficile, elles sont donc rarement utilisées en technologie).

A noter qu'un dispositif informatique repose le plus souvent sur un ensemble complet de fonctions (souvent sur des bases). Si le dispositif est basé sur la conjonction, la disjonction et la négation, alors le problème de la minimisation du DNF est important pour ces dispositifs ; Si le dispositif est basé sur d’autres fonctions, alors il est utile de pouvoir minimiser algorithmiquement les expressions grâce à ces fonctions.

Passons maintenant à la clarification de l'exhaustivité d'ensembles spécifiques de fonctions. Pour ce faire, nous listons les 5 classes de fonctions les plus importantes :

• T 0 est l'ensemble de toutes ces fonctions logiques qui prennent la valeur 0 sur l'ensemble zéro ( T 0 est la classe de fonction, conservation 0);
• T 1 est l'ensemble de toutes les fonctions logiques qui prennent la valeur 1 sur l'ensemble unitaire ( T 1 est une classe de fonctions, unité de conservation) (notez que le nombre de fonctions de P. les variables appartenant aux classes T 0 et T 1 sont égales à 2 2n-1) ;
• L- Classe linéaire les fonctions, c'est-à-dire les fonctions pour lesquelles le polynôme de Zhegalkin ne contient que les premiers degrés de variables ;
• M- Classe monotone les fonctions. Décrivons la classe de ces fonctions plus en détail. Soit 2 ensembles de P. variables : s1 = (x 1, x 2,..., x n)

s 1 = ( X 1 , X 2 , … , xn) et s 2 = (oui 1 , oui 2, … , ouais p). Nous dirons que l'ensemble s 1 est inférieur à l'ensemble s 2 (s 1 £ s 2 ), si tout x je £ y je .Évidemment, tous les ensembles deP.les variables sont comparables entre elles (par exemple, lorsquen = 2 les ensembles (0,1) et (1,0) ne sont pas comparables entre eux). Fonction deP.les variables sont appeléesmonotone, si sur un ensemble plus petit, cela prend une valeur inférieure ou égale. Bien entendu, ces inégalités ne doivent être testées que sur des ensembles comparables. Il est clair que les ensembles incomparables sont ceux dans lesquels il y a des coordonnées de type (0,1) dans un ensemble et (1,0) dans l'autre aux endroits appropriés (en mathématiques discrètes, les fonctions monotones sont comme « des fonctions monotones croissantes » fonctions », les fonctions « décroissantes monotones » ne sont pas considérées ici).

Exemple. Dans le tableau suivant les fonctions F 1 ,F 2 sont des fonctions monotones, et les fonctions F 3 ,F 4 - Non.

L'ordre naturel des variables est assuré par le fait que si un ensemble est plus petit qu'un autre ensemble, alors il se situe nécessairement dans la table de vérité plus haut ensemble « plus grand ». C'est pourquoi si dans la table de vérité()il y a des zéros en haut,puis les unités,alors cette fonction est définitivement monotone.Cependant des inversions sont possibles, c'est à dire que l'on vient avant quelques zéros, mais la fonction est toujours monotone(dans ce cas, les ensembles correspondant au zéro « supérieur » et au zéro « inférieur » doivent être incomparable; on peut vérifier que la fonction donnée par la table de vérité avec l'ordre naturel de l'ensemble des variables(00010101), est monotone);

Théorème .Classes de fonctions T 0 ,T 1 ,L,M,S fermé.

Cette affirmation découle directement de la définition de ces classes elles-mêmes, ainsi que de la définition de la fermeture.

Dans la théorie des fonctions booléennes, le théorème de Post suivant est très important.

Théorème de Post .Pour qu'un ensemble de fonctions K soit complet, il faut et suffisant qu'il comprenne des fonctions qui n'appartiennent pas à chacune des classes T. 0 ,T 1 ,L,M,S.

Noter que Quoi nécessité ce déclarations évident Donc Comment Si c'est tout les fonctions depuis recrutement À inclus V un depuis répertorié Des classes, Que Et Tous superpositions, UN Moyens, Et court-circuit recrutement inclus serait V ce Classe Et Classe À Pas pourrait être complet.

Adéquation ce déclarations est prouvé assez difficile, C'est pourquoi non montré ici.

De ce théorème découle une manière assez simple de déterminer l'exhaustivité d'un certain ensemble de fonctions. Pour chacune de ces fonctions, l'appartenance aux classes listées ci-dessus est déterminée. Les résultats sont saisis dans ce qu'on appelle Tableau de publication(dans notre exemple, ce tableau est compilé pour 4 fonctions, et le signe « + » indique que la fonction appartient à la classe correspondante, le signe « - » signifie que la fonction n'y est pas incluse).

Selon le théorème de Post, l'ensemble des fonctions sera complet si et seulement s'il y a au moins un moins dans chaque colonne de la table Post. Ainsi, du tableau ci-dessus, il résulte que ces 4 fonctions forment un ensemble complet, mais ces fonctions ne constituent pas une base. A partir de ces fonctions vous pouvez former 2 bases : F 3 ,F 1 Et F 3 ,F 2. Les ensembles complets sont des ensembles contenant une base.

Il résulte directement du tableau de Post que le nombre de fonctions de base ne peut pas être supérieur à 5. Il n'est pas difficile de prouver qu'en fait ce nombre est inférieur ou égal à 4.