Comment montrer ?u p(u)? Soit p(u) une fonction propositionnelle
Ce sont vraiment deux fonctions propositionnelles sur l'univers du discours (pq
Que sont et que peuvent etre les fonctions propositionnelles de
FONCTIONS PROPOSITIONNELLES DE. RUSSELL? «I! y a juste un point ou j'ai rencontre une di/ficulte. Vous dites qu'une fonction egalement peut jouer le role
notions-de-logique-cours-1-1.pdf
I) LES PROPOSITIONS ; LES FONCTIONS PROPOSITIONNELLES Si on lie la variable d'une fonction propositionnelle par le quantificateur universel on obtient ...
Eléments de logique
13 juil. 2018 C'est une fonction propositionnelle définie sur N. 1.9 Quantificateurs vous savez que quel que soit le nombre réel x
Chapitre 2 Dé nition de la logique propositionnelle
Définition de fonctions par récurrence peut être une variable propositionnelle ... Une méthode pour définir une fonction : par une expression.
Cours logique - Mémo n?1 Logique propositionnelle
p o`u p est une variable propositionnelle sont des formules. de ses sous-formules est donné par la fonction sf(A) définie inductivement comme.
= n < ?. Considérons U
13 oct. 2015 Si G(u1u2) une autre fonction propositionnelle avec univers du discours sur U × U. Alors RF = RG si et seulement si F et G sont logiquement ...
4.2. Tableau de vérité. Nous présentons ces définitions en forme de
Une fonction p : U ? {propositions logiques} qui associe à chaque u ? U la proposition logique p(u) s'appelle fonction propositionnelle avec U comme
4. Quantificateurs (encore) 4.1. Beaucoup de quantificateurs sont
Similairement pour ?. Proposition 4.1. Soit p(u) une fonction propositionnelle avec univers de discours un en- semble U et q une proposition logique
Logique propositionnelle
Logique propositionnelle. 6/25. 3 Sémantique : évaluation des formules. Définir une sémantique sur les formules c'est définir une fonction d'évaluation.
Cours de logique propositionnelle
fonction vdé?nie sur tout Fqui véri?e les conditions suivantes (B) vétend v: pour toute variable propositionnelle p2P v(p) = v(p); (I) la négation s’interprète par la négation logique : si Fest de la forme :G alors v(F) = 1 ssi v(G) = 0; (I) ^s’interprète comme le et logique :
LES PRINCIPES DE LOGIQUE
1-3-FONCTION PROPOSITIONNELLE 1-3-1-DEFINITION On appelle fonction propositionnelle tout énoncé contenant des variables appartenant à un ensemble E et la fonction propositionnelle devient une proposition si on remplace les variables par des valeurs déterminées de E 1-3-2-EXEMPLE P(x) : x2 d10 P(1) est vraie car 12-1=0 d0 P(2) est fausse car
Cahiers pour l’Analyse (An electronic edition)
Cahiers pour l’Analyse (An electronic edition)
Searches related to fonction propositionnelle PDF
0 1 Proposition-Fonction Propositionnelle D e nition 0 1 1 Une proposition logique est un enonc e form ee d’un assemblage de symboles et de mots portant sur des objets math ematiques a laquelle on peut clairement attribuer la valeur vraie ou la valeur faux On note P une proposition Par d e nition P satisfait les 3 principes suivants :
Quelle est la logique propositionnelle ?
La logique propositionnelle est décidable :r il existe une procédure effective qui pour toute formule Aen entréer s'arrête et retourne `oui' si Aest valide, et `non' sinon. Un exemple de procédure de décision est lar méthode des tables de vérité. Une méthode plus efficace est la r méthode de balayage.
Quelle est la fonction de la proposition principale?
Elle occupe donc la fonction decomplément circonstanciel. Exemple :Quandtu auras fini, tupourrasvenir m’aider. CC La proposition principale Elle peut presque toujours être déplacée ou supprimée.
Comment construire une formule propositionnelle ?
Une formule propositionnelle est construite à partir de propositions simples, telles que « cinq est supérieur à trois », ou de variables propositionnelles telles que P et Q, en utilisant des connecteurs logiques tels que NON, ET, OU et IMPLIQUE ; par exemple : ( P ET NON Q) IMPLIQUE ( P OU Q ).
Comment définir une relation fonctionnelle?
Relation fonctionnelle. Article détaillé : fonction (mathématiques). Lorsque, pour tout élément x de E, x n’est en relation qu’avec 0 ou 1 élément y de F, on dit que la relation est fonctionnelle. C’est une façon élémentaire de définir la notion de fonction.
Logique propositionnelle
1/25Lyc´ee Louis-le-Grand
Ann´ee 2003-2004Logique propositionnelle
option informatiqueLogique propositionnelle
2/251 Sommaire
-formules de la logique propositionnelle ; -s´emantique : l"´evaluation des formules ; -tautologies, formules satisfiables, contradictions ; -tables de v´erit´e ; -fonctions bool´eennes ; -´equivalence des formules ; -formes normales conjonctives et disjonctives.Logique propositionnelle
3/252 Formules de la logique propositionnelle
Les formules propositionnelles sont d´efinies `a l"aide deconstantes,variables etconnecteurs. Les constantes sontVetF; les variables forment un ensemble d´enombrable, et on les d´esignera ici par des lettres romaines :p,q, ; on dispose d"un connecteur unaire¬, et de quatre connecteurs binaires :?,?,?et?. L"ensemble des formules se d´efinit alors r´ecursivement : ◦toute constante est une formule ; ◦toute variable est une formule ; ◦sieest une formule et si?est un connecteur unaire,(?e)est une formule ; ◦sieetfsont des formules et si?est un connecteur binaire,(e?f)est une formule. Comme d"habitude les r`egles de priorit´e entre op´erateurs permettent d"´eviter l"accumulation des parenth`eses : p?q?r?p?rest (((p?q)?r)?(p?r)).Logique propositionnelle
4/25Le nombre de connecteurs n"est pas limit´e, certains introduisent leou
exclusif, ou lenand(la n´egation de la conjonction). On en reparlera plus tard. On ne revient pas non plus sur la repr´esentation par des arbres des formules de la logique propositionnelle.Logique propositionnelle
5/25On pourra utiliser le typage suivant en Caml :
type formule = V | F | Variable of string | Neg of formule | Ou of formule list | Et of formule list | Implique of formule * formule| Equivalent of formule * formule ;;On notera qu"on a anticip´e sur l"associativit´e de?et de?, qui s"´eclaircira
quand on parlera de s´emantique.Logique propositionnelle
6/253 S´emantique : ´evaluation des formules
D´efinir une s´emantique sur les formules, c"est d´efinir une fonction d"´evaluation qui leur associe, pour chaque contexte, unevaleur de v´erit´e. Plus pr´ecis´ement, on d´esigne parBl"ensemble des valeurs de v´erit´e, que nous noterons ici{0,1}; parFl"ensemble des formules propositionnelles et parVl"ensemble (d´enombrable) des variables.Uncontexteμest une application deVdansB.
L"´evaluation d"une formulef? Fdans un contexteμse note[μ]f, c"est un ´el´ement deB. On pourra noterevalμ:f?[μ]fla fonction d"´evaluation dans le contexteμ.Logique propositionnelle
7/25eval
μse d´efinit r´ecursivement de la fac¸on suivante : ?[μ]V= 1et[μ]F= 0; ?pour toute variablep,[μ]p=μ(p); ?sieest une formule,[μ](¬e) = 1-[μ]e=ε¬([μ]e); ?sieetfsont des formules : [μ](e?f) =ε?([μ]e,[μ]f) = ([μ]e)×([μ]f) [μ](e?f) =ε?([μ]e,[μ]f) = max([μ]e,[μ]f) [μ](e?f) =ε?([μ]e,[μ]f) [μ](e?f) =ε?([μ]e,[μ]f) Pour tout connecteur binairec, on fournit la fonctionεc:B × B ? B. En particulier :ε?(0,0) =ε?(0,1) =ε?(1,1) = 1etε?(1,0) = 0; ?(0,0) =ε?(1,1) = 1etε?(1,0) =ε?(0,1) = 0.Logique propositionnelle
8/254 Vocabulaire
Une formule logiqueeest
◦unetautologiesi pour tout contexteμon a[μ]e= 1; ◦unecontradictionsi pour tout contexteμon a[μ]e= 0; ◦satisfiables"il existe au moins un contexteμpour lequel[μ]e= 1. On n"a pas encore vraiment moyen de les distinguer...Logique propositionnelle
9/255 Tables de v´erit´e
Par induction structurelle sur les formules on peut facilement montrer leTh´eor`eme Soiteune formule logique. L"ensembleV(e)des variables qui y figurent est un ensemble fini. Siμ1etμ2sont deux contextes qui co¨ıncident surV(e),alors[μ1]e= [μ2]e.Autrement dit il suffit de connaˆıtre les valeurs des contextes sur les variables
qui apparaissent effectivement dans la formule, ce qui est assez ´evident, non? C"est ainsi que pour tester si une formuleetelle quen=|V(e)|est une tautologie, il faudra tester les2npossibilit´es qui correspondent aux valeurs d"un contexte sur les variables.Logique propositionnelle
10/25Dresser la table de v´erit´e dee, c"est dresser un tableau `a2nlignes et (au
moins)n+1colonnes. Lesnpremi`eres colonnes contiennent les valeurs des variables qui apparaissent danse, et la derni`ere la valeur dee, chaque ligne correspondant `a un contexte diff´erent. En pratique, on ajoute souvent des colonnes pour les valeurs des sous- expressions de l"expression consid´er´ee. On lit sur la derni`ere colonne sieest une tautologie, une contradiction, ou bien satisfiable. Cet algorithme pour d´ecider si une formule est une tautologie est enO(2n). On ne connaˆıt pas de meilleur algorithme. On ne sait pas s"il en existe.Logique propositionnelle
11/25Voici par exemple la table de v´erit´e de(p?q)?(¬p?r):pqr(p?q)?(¬p?r)0000
0011 01000111
1000
1010
1101
1111
Logique propositionnelle
12/256 Fonctions bool´eennes
Unefonction bool´eenne`apvariables est simplement une application deBp dansB. Sieest une formule et sin=|V|, on peut lui associer une fonction bool´eenne denvariables, not´eeεe: chaquen-uplet de bool´eens d´efinit un contexte (on peut affecter n"importe quelle valeur aux variables qui ne figurent pas danse) dans lequel on ´evalue l"expressione.RemarqueRemarquons queε(p?q)=ε?, et de mˆemeε(p?q)=ε?
pour tout connecteur binaire?etε(¬p)=ε¬.En fait, toute fonction bool´eenne admet ce type de repr´esentation.
Logique propositionnelle
13/25L"id´ee est la suivante : soit?:Bn? Bune fonction bool´eenne, et nommons
p1,p2,...,pnles variables.
On dresse la table des valeurs de?: c"est un tableau `a2nlignes. On cherche `a construire une formule, o`u n"interviennent que les variablespi, dont ce tableau soit la table de v´erit´e. On a le choix entre deux approches : on regarde les lignes pour lesquelles le r´esultat vaut 1, et on ditil faut et il suffit que l"on soit dans l"un ou l"autre de ces cas. Ou bien, on regarde les lignes pour lesquelles le r´esultat vaut 0, et on ditil faut et il suffit que l"on ne soit dans aucun de ces cas.Logique propositionnelle
14/25Utilisons par exemple la premi`ere approche, et notons1?l"ensemble des
n-uplets de bool´eens sur lesquels?vaut 1. Autrement dit :1?=?-1({1}).Sipest une variable, notonsp0=¬petp1=p.
Avec ces notations on dispose duTh´eor`eme
La fonction?est repr´esent´ee par la formulefsuivante, c"est-`a-dire que f=?avec : f=? (b1,b2,...,bn)?1?? n? i=1p bii? .La d´emonstration est laiss´ee au lecteur attentif et...courageux.Logique propositionnelle
15/25En utilisant la deuxi`eme approche, on obtiendrait ´evidemment le th´eor`eme
dual :Th´eor`eme La fonction?est repr´esent´ee par la formulegsuivante, c"est-`a-dire que g=?avec : g=? (b1,b2,...,bn)?0?? n? i=1p1-bii?
.On a bien sˆur not´e0?=?-1({0})l"ensemble desn-uplets de variables o`u s"annule?. L`a encore la d´emonstration se ferait en v´erifiant que la table de v´erit´e deg co¨ıncide avec le tableau de valeurs de?.Logique propositionnelle
16/257
´Equivalence des formules
Deux formuleseetfsont dites ´equivalentes, et on notee≡f, si pour tout contexteμon a[μ]e= [μ]f. Pour v´erifier algorithmiquement cette ´equivalence, on utilise le th´eor`eme suivantTh´eor`eme Deux formuleseetfsont ´equivalentes si et seulement si la formulee?f est une tautologie.C"est une cons´equence assez imm´ediate de ce queε?(x,y) = 1si et seulement six=y.Logique propositionnelle
17/25On v´erifie ais´ement les r´esultats suivants, pour deux variablespetq
quelconques :¬(p?q)≡ ¬p? ¬q¬(p?q)≡ ¬p? ¬q
p?q≡ ¬p?q p?q≡ ¬q? ¬p p?q≡(p?q)?(q?p) p?q≡(p?q)?(¬p? ¬q) On aimerait en d´eduire les mˆemes r´esultats quandpetqd´esignent non seulement des variables mais mˆeme des sous-formules...Logique propositionnelle
18/25Substitution dans une formule
Soitfune formule,p1,p2,...,pkdes variablesdeux `a deux distinctes, et e1,e2,...,ekdes formules quelconques.
On d´efinit inductivement la formule obtenue par substitution dansfdeei`a chaquepi, qu"on note{e1/p1,e2/p2,...,ek/pk}fde la fac¸on suivante : ◦ {e1/p1,...,ek/pk}V=Vet{e1/p1,...,ek/pk}F=F; ◦sipest une variable, {e1/p1,...,ek/pk}p=?ei,sip=pi; p,sipn"est aucune des variablesp1,...,pk; ◦ {e1/p1,...,ek/pk}(¬f) =¬({e1/p1,...,ek/pk}f); ◦pour tout connecteur binaire?, {e1/p1,...,ek/pk}(e?f) = ({e1/p1,...,ek/pk}e)?({e1/p1,...,ek/pk}f).Logique propositionnelle
19/25On d´emontre alors par induction structurelle le
Th´eor`eme
Soitp1,p2,...,pkdes variables deux `a deux distinctes,fune formule quelconque, et enfinμun contexte quelconque. On dispose alors de[μ]({e1/p1,e2/p2,...,ek/pk}f) = [μ?]f, o`uμ?est le contexte d´efini parμ?(p) =μ(p)sipn"est pas une des variablespi, et ?(pi) = [μ]eipour1?i?k.Logique propositionnelle
20/25On est maintenant en mesure de d´emontrer un nouveau th´eor`eme qui permet
de g´en´eraliser au cas des sous-formules les ´equivalences de formules d´ej`a vues plus haut.Th´eor`eme Soitp1,p2,...,pkdes variables deux `a deux distinctes,fetgdeux formule quelconques, et enfine1,e2,ekdes formules quelconques.On suppose quef≡g.
Alors :{e1/p1,e2/p2,...,ek/pk}f≡ {e1/p1,e2/p2,...,ek/pk}g.En effet, pour tout contexteμ: [μ]({e1/p1,...,ek/pk}f) = [μ?]f= [μ?]g= [μ]({e1/p1,...,ek/pk}g).Logique propositionnelle
21/258 Formes normales conjonctives, disjonctives
Unlitt´eralest ou bien une variable, ou bien la n´egation d"une variable. Donc une formule du genrepou¬p. Notons au passage que la n´egation d"un litt´eral est ´equivalente `a un litt´eral. Uneclauseest une disjonction de litt´eraux, c"est-`a-dire une formule du genre1? ··· ??ro`u chaque?iest un litt´eral.
Uneforme normale conjonctiveest une conjonction de clauses, c"est-`a-dire une formule du genrec1? ··· ?cko`u chaquecjest une clause. Uneforme normale disjonctiveest une disjonction d"une conjonction de litt´eraux.Logique propositionnelle
22/25Nous voulons montrer que toute formule est ´equivalent `a une forme normale
conjonctive (resp.disjonctive).´Enonc¸ons rapidement quelques lemmes.LemmeToute n´egation d"un litt´eral est ´equivalente `a un litt´eral.
LemmeLa n´egation d"une disjonction (resp.d"une conjonction) de litt´eraux est ´equivalente `a une conjonction (resp.une disjonction) de litt´eraux.LemmeLa n´egation d"une disjonction de conjonctions (resp. d"une conjonction de disjonctions) de litt´eraux est´equivalente `a une conjonction de disjonctions (resp.une disjonction de conjonctions) de litt´eraux.Logique propositionnelle
23/25Nous sommes en mesure de d´emontrer par induction structurelle le
Th´eor`eme
Toute formulefest ´equivalente `a une forme normale conjonctivef×et `a une forme normale disjonctivef+.On peut se contenter des connecteurs binaires?et?, comme il a ´et´e prouv´e plus haut. Le cas des constantes est facile :V+=V×=p? ¬p,F+=F×= p? ¬p.Le cas des variables aussi :p+=p×=p.
Le cas de la n´egation tout autant, grˆace aux lemmes pr´ec´edents. Reste le cas d"une formulee=f?goue=f?g, pour laquelle on connaˆıt d´ej`af+,f×,g+,g×.Logique propositionnelle
24/25On dispose ´evidemment de(f?g)+=f+?g+et de(f?g)×=
f×?g×.
Consid´erons maintenant(f?g)×. On dispose def×=? if iet g ig i, o`u lesfiet lesgisont des disjonctions de litt´eraux.Maisf?g≡f×?g×= (?
if i)?(? jg j)≡? i,j(fi?gj)o`u on reconnaˆıt une conjonction de disjonctions de litt´eraux.De mˆemef?g≡f+?g+= (?
if ?i)?(? jg ?j)≡? i,j(f?i?g?j)o`u on reconnaˆıt une disjonction de conjonctions de litt´eraux.Logique propositionnelle
25/25Utilisation des tables de v´erit´e
Le lecteur attentif aura remarqu´e que les th´eor`emes que nous avons ´enonc´es pour la repr´esentation des fonctions bool´eennes par des formules, faisaient intervenir des formes normales conjonctives ou disjonctives : associant `a une formuleela fonction bool´eenneεe, et appliquant les th´eor`emes en question, on en d´eduit de nouvelles formules, sous formes normales, qui seront ´equivalentes `ae. C"est, en pratique, la m´ethode la plus naturelle et la plus rapide pour obtenir une forme normale (qu"elle soit disjonctive ou conjonctive) d"une formule propositionnelle.quotesdbs_dbs19.pdfusesText_25[PDF] fonction proportionnelle
[PDF] formule chimique des ions
[PDF] liste des molécules chimiques
[PDF] formule chimique brute
[PDF] tableau des grandeurs physiques
[PDF] patron d'un cube
[PDF] propriétés des fluides pdf
[PDF] les fluides pdf
[PDF] propriétés physiques des liquides
[PDF] fluide définition simple
[PDF] caractéristiques des fluides
[PDF] exemple de fluide
[PDF] propriété des fluides exercice
[PDF] propriété du carré
