Semantica

Avem 6 tipuri de simboluri in logica predicatelor:

P di t t Predicate: p, q, r, , p1, q2 etc.

Constante: a, b, c, , z, a1, b4, , ion, mihai, labus etc.

Variabile: x, y, z, x1, y1, z4 etc.

Conective:, , ,,

Paranteze: (, )

Cuantificatori:,

Un termen din logica predicatelor este fie o constanta fie o

variabilavariabila.

O formula atomica din logica predicatelor este un predicat

de aritate n urmat de n termeni intre paranteze si cu virgula

intre ei.

Def.: Formula bine formata (fbf):

Orice formula atomica este o fbf.

DacaA este o fbf atunciA este o fbf.

DacaA si B sunt fbf, atunci (A B) este o fbf.

DacaA si B sunt fbf, atunci (A B) este o fbf.

DacaA si B sunt fbf, atunci (A B) este o fbf., ( )

DacaA si B sunt fbf, atunci (A B) este o fbf.

Def.: Formula bine formata (fbf) continuare:

Daca A este o fbf, x este o variabila, A contine cel putin o aparitie a lui x si

niciun cuantificator de care x sa fie legat, atuncixA este o fbf.

Daca A este o fbf, x este o variabila, A contine cel putin o aparitie a lui x si

niciun cuantificator de care x sa fie legat, atunci xA este o fbf.

O propozitie este o entitate care poate fi fie adevarata, fie falsa.

Def.: O propozitie in logica predicatelor este o fbf din logica

predicatelor care nu contine variabile libere (toate variabilele

sunt legate sau instantiate).g

Def.: Daca A este o fbf c o constanta si x o variabila atunciDef.: Daca A este o fbf, c o constanta si x o variabila, atunci

substitutia A[c|x] este fbf care se obtine prin inlocuirea fiecarei

instante a lui x inA prin cinstante a lui x inA prin c.

In logica predicatelor, precum in orice limbaj logic, exista doua

tipuri de elemente:

Simboluri logice semnificatia lor este specificata in cadrul limbajului.

Ex.: conectivele, cuantificatorii.

Simboluri nonlogice semnificatia lor nu este definita de structura logica

a limbajului. Ex.: predicatele, constantele.

O interpretare da o semnificatie tuturor elementelor nonlogicep g

ale limbajului.

O interpretare in logica predicatelor necesita urmatoarele:

Un univers de definitie (domeniu).

O semnificatie schematica pentru fiecare predicat.

Un obiect care sa fie selectat de fiecare constanta.

Sa luam urmatorul exemplu:

Universul de definitie: personaje de benzi desenate.p j

p(x) x lupta impotriva crimei.

b: Batmanb: Batman.

w: BruceWayne.

Exemplu:

Universul de definitie: personaje de benzi desenate.

p(x) x lupta impotriva crimei.

b: Batman.

w: BruceWayne.

Propozitia p(b) e adevarata in aceasta interpretare, dar nu doarp p( ) p ,

datorita acestei interpretari.

p(b) e adevarata datorita acestei interpretari plus a unor p(b) e adevarata datorita acestei interpretari plus a unor

cunostinte despre benzi desenate.

Exemplu:

Universul (domeniul) de definitie: personaje de benzi desenate.

p(x) x lupta impotriva crimei.

b: Batman.

w: BruceWayne.

Cum este p(w)?p( )

Fiindca Bruce Wayne e identitatea secreta a lui Batman, b = w,

rezulta ca p(w) e adevaratarezulta ca p(w) e adevarata.

Insa, aceasta fiind identitatea secreta, alte personaje nu stiu ca

( ) d t d i ti (b) d tp(w) e adevarata, desi stiu ca p(b) e adevarata.

Dacaamconsideraasignareadevalorideadevarprecumin

logicapropozitiilor,amputeaasignaFsauAfiecareifbf

atomicep(b),p(w)etc.

Arfiechivalentcuainlocuip(b)sip(w)culiteredepropozitii.Arfiechivalentcuainlocuip(b)sip(w)culiteredepropozitii.

Daratunciamignoratoatastructuralogicaapredicatelorsitermenilor.

Inlogicapredicatelor nudamdefinitiiseparatepentrup(b)si Inlogicapredicatelor,nudamdefinitiiseparatepentrup(b)si

p(w),cidamsemnificatiipentrup,b,w.

M i lt f l i i tifi t i Maimult,vremsafolosimsicuantificatori.

Cautamasadaruncomplementaralasignariidevaloride

adevardinlogicapropozitiilorpentruointerpretarea

predicatelorsiconstantelor.

Nusepoateutilizaoasignaredevalorideadevarpentru

aceasta,fiindcaunpredicatnuenicifalsniciadevarat.aceasta,fiindcaunpredicatnuenicifalsniciadevarat.

Inexempluldemaidevreme peadevaratdacaeaplicatlui Inexempluldemaidevreme,peadevaratdacaeaplicatlui

Batman,darnuaresenssaneintrebamdacaeadevaratin

generalgeneral.

Ointerpretareajutainselectareaobiectelorasupracarorapredicatulesteaplicabil.

Interpretandp(x)dreptxluptaimpotrivacrimei,seselecteazaBatman,Superman,Spidermanetc.

Inmodformal,spunemcaaceastaemultimeamembriloruniversuluidedefinitieasupracaruiapredicatulesteaplicabil.

Aceastamultimepoartanumeledeextensia predicatului.p p

Multepredicateaudomeniidedefinitiefoartelargi.

Inexempluldemaisus,nuputemenumeraexhaustivtoti

luptatoriiimpotrivacrimeidinbenziledesenate,cifolosim

limbajulnaturalpentruainterpretapredicatul.limbajulnaturalpentruainterpretapredicatul.

Insainterpretareasinguranuspunecaremembriai

universuluisuntinextensiapredicatului cimaitrebuieuniversuluisuntinextensiapredicatului,cimaitrebuie

cunostintesuplimentaredesprebenzidesenate.

l d l l Ingeneral,extensiaunuipredicatesterezultatulunei

interpretarisialcatorvacunostinte.

Cateodatainsaeposibilsaselistezetoateelementeledinextensiapredicatului.

Samaiadaugampredicatulq(x)xtraiesteinlocuintaWaynelaexempluldemaidevreme.p

Atunciextensialuiqestemultimea:extensia(q)={BruceWayne,Alfredmajordomul,DickGrayson}

Astfel,nutrebuiecunostintedesprebenzidesenatepentruadeterminaca,inaceastainterpretare,q(w)eadevarat BruceWayneeunuldinmembriiluiq.

Inmodsimilar,xq(x)eadevaratinaceastainterpretare:existacelputinunmembrudinuniverscareesteinextensialuiq.

Inschimbxq(x)efals,fiindcanuesteadevaratcatotimembriidinuniverssuntinextensialuiq maisuntsialtepersonajeinbenziledesenatedecatacesteatrei.

Amdefinitsemnificatiaformalaaunuipredicatprinextensiasa.

Cumramaneinsacuconstantelebsiw?

Intelesuluneiconstantedeterminacemembrudinuniverseste

alesdeconstanta.

Individulalesdeconstantasenumestereferentul constantei.

NeputemgandilaliteraconstanteidreptunnumesilareferentNeputemgandilaliteraconstanteidreptunnumesilareferent

dreptlucrulnumit.

Inexemplulnostru bsiwauacelasireferent fiindcasereferala Inexemplulnostru,bsiwauacelasireferent,fiindcasereferala

acelasipersonaj.

Unmodel inlogicapredicatelorestestructuraformala

determinatade:

ununivers,

oextensiepentrufiecarepredicat oextensiepentrufiecarepredicat

siunreferentpentrufiecareconstanta.

d Saconsideramurmatoareainterpretare: Universul:EchipelespanioledinChampionsLeaguein20092010.

h(x):xesteoechipadinorasulMadrid.

f:Galacticii.

d f b l Dacanustimnimicdesprefotbal,nuputemspunecarepropozitiiinlogicapredicatelorsuntadevarateinaceastainterpretare.

Estepropozitiah(f)adevaratasaufalsa?DepindecaredintreechipelespanioledinChampionsLeague20092010estesupranumitaGalacticii.

Careestemodelulcarecorespundeacesteiinterpretari?

EraupatruechipeinChampionsLeague20092010:RealMadrid,

AtleticoMadrid,BarcelonasiSevilla.

DintreacesteaBarcelonasiSevillanusuntdinMadrid.

Asadaravemmodelul:Asadaravemmodelul:

UniversulU={RealMadrid,AtleticoMadrid,Barcelona,Sevilla}

extensia(h)={RealMadrid AtleticoMadrid} extensia(h)={RealMadrid,AtleticoMadrid}

referent(f)={RealMadrid}

A it b i ti i i d f tb l t l Acumnumaitrebuiesastimnimicdesprefotbalpentruaevalua

dacaopropozitiecareilincludepehefalsasauadevaratain

acestmodel.

UniversulU={RealMadrid,AtleticoMadrid,Barcelona,Sevilla} extensia(h)={RealMadrid,AtleticoMadrid} referent(f)={RealMadrid} h(f)eadevarat,fiindcareferentulluif,adicaRealMadrid,estein

extensialuih. Atatxh(x)catsixh(x)suntadevarate,fiindca existacelputinunelementdinUcareesteinextensialuih

siexistacelputinunelementdinUcareNUesteinextensialuih

Astfel,modelulcaptureazatoatasemnificatiaformalaainterpretarii.

Saconsideramurmatoareainterpretare:

U:numerelenaturalemaimarica0simaimicidecat1o.

e(x):xepar.

n(x):xestenegativ.( ) g

l(x,y):xestemaimicdecaty.

t(x y z):xinmultitcuyesteegalcuzt(x,y,z): xinmultitcuyesteegalcuz .

Careestemodelulcaresepotrivesteacesteiinterpretari?

U={1 2 3 4 5 6 7 8 9} U={1,2,3,4,5,6,7,8,9}.

Extensiapredicatelore saun estesubmultimealuiUpentrucare

f dfiecareesteadevarat.

Saconsideramurmatoareainterpretare:

U:numerelenaturalemaimarica0simaimicidecat1o.

e(x):xepar.

n(x):xestenegativ.( ) g

l(x,y):xestemaimicdecaty.

t(x y z):xinmultitcuyesteegalcuzt(x,y,z): xinmultitcuyesteegalcuz .

extensia(e)={2 4 6 8} alegemelementeleparedinU extensia(e)={2,4,6,8} alegemelementeleparedinU.

extensia(n)= nuexistanumerenegativeinU.

e(x):xepar.n(x):xestenegativ.l( ) i i d l(x,y):xestemaimicdecaty.t(x,y,z):xinmultitcuyesteegalcuz.

U:numerelenaturalemaimarica0simaimicidecat1o.

Parecaextensialuil: Artrebuisailcontinape1,fiindca1emaimicdecattoatecelelaltenumere

Artrebuisailcontinasipe2,fiindca2emaimicdecattoatecelelaltemaiputin1.

OricemembrudinUinafarade9emaimicdecatunaltmembrudinU.

Amputeadeciscrieextensia(l)={1,2,3,4,5,6,7,8}?

Continuare:

Amputeadeciscrieextensia(l)={1,2,3,4,5,6,7,8}?

Insaintromultime,ordineaelementelornuconteaza.

Deciextensia(l)={8,7,6,5,4,3,2,1}.( ) { , 7, , 5, 4, 3, , }

Scriereanunespunenimicdesprecaremembrisuntmaimicidecatalti

membri.

Solutia: Trebuiesaaratamca1emaimicdecat8darsicanuavemsisituatia

inversa.

Extensialuilvatrebuisafiealcatuitadinperechiordonatedenumere.

extensia(l)={,,,,,,,,,,,,,,,,,,,

Continuare: t(x,y,z):xinmultitcuyesteegalcuz.

Extensialuitvacontinetripleteordonatedenumeredetipul,fiindca2*4=8.

Ingeneral,extensiaunuipredicatdearitaten esteomultimeatuturorntuplurilorordonateastfelincat a1,a2,,an suntmembriaiuniversului

sipredicatulaplicatluia1,a2,,an esteadevaratinaceastaordine.

FieAsiBdouapropozitiiinlogicapredicatelor.AB(BsededucedinA)dacanuexistaniciunmodelincareAsafieadevaratsiBfals. AinseamnacaAesteadevaratinoricemodel.

Definitii: Otautologie inlogicapredicateloresteopropozitieAcareesteadevaratain

oricemodel,A.

Ocontradictie inlogicapredicateloresteopropozitieAcareestefalsainoricemodel,A.

Opropozitieestecontingenta inlogicapredicatelordacasinumaidacanut i i t t l i i i t di tiesteniciotautologieniciocontradictie.

Definitii: UnrationamentincareCsededucedinP1,P2,estevalid inlogica

predicatelordacasinumaidacanuexistaniciunmodelincaretoatepremiselesafieadevaratesiconcluziafalsa,{P1,P2,}C.

l f l l d l d l Altfel,estenevalid inlogicapredicatelor.

DouapropozitiiAsiBsuntlogicechivalenteinlogicapredicatelordacasinumaidacaatatABcatsiBAnumaidacaatatABcatsiBA.

Multimea{A1,A2,A3,}esteconsistenta inlogicapredicatelordacasinumaidacaexistacelputinunmodelincaretoatepropozitiilesuntnumaidacaexistacelputinunmodelincaretoatepropozitiilesuntadevarate.

Multimeaesteinconsistenta dacasinumaidacanuexistaunastfeldemodel.

Saaratamcaxp(x x) q(d)nuesteotautologie Saaratamcaxp(x,x) q(d)nuesteotautologie. Trebuiesaaratamasadarcapropozitianuesteadevaratainorice

d l d i t f l i t it d lmodel,decicaestefalsaintrunanumitmodel. Dacaevidentiemunmodelincarepropozitiasafiefalsa,atunciam

d t t t t t l idemonstratcanuestetautologie. Pentrucaxp(x,x) q(d)safiefalsa,xp(x,x)trebuiesafie

d i (d)f ladevaratasiq(d)falsa. Vremcaxp(x,x)safieadevarata,inseamnacafiecaremembrual

funiversuluitrebuiesaformezeperechecuelinsusiinextensialuip. q(d)trebuiesafiefals,decireferentulluid nutrebuiesaseaflein

extensialuiq.

Vremcaxp(x x)safieadevarata inseamnacafiecaremembru Vremcaxp(x,x)safieadevarata,inseamnacafiecaremembrualuniversuluitrebuiesaformezeperechecuelinsusiinextensial iluip. SaconsideramU={Paris}

extensia(p)={}

q(d)trebuiesafiefals,decireferentulluid nutrebuiesaseafleint i l iextensialuiq.

extensia(q)=

referent(d)=Paris esingurulmembrudinU

Avemastfelunmodelpartial nuamdefinitsialtepredicatesau id l constante,cidoarcelenecesare.

Inacestmodel,propozitiadataestefalsa.

Carearputeafisemnificatiapredicatelorsiaconstantelorin Carearputeafisemnificatiapredicatelorsiaconstantelorinlimbajnatural?

U {P i } U={Paris}

extensia(p)={}

i ( ) extensia(q)=

referent(d)=Paris

M d l l ti l t d i tf ld i t t i Modelulpartialarputeacorespundeuneiastfeldeinterpretari: U={Paris}

( ) i i i p(x,y):xesteinaceeasitaracasiy

q(x):xafostfondatinsec.XX

d O lL i il d:OrasulLuminilor

Saaratamcaxp(x,x) q(d)nuesteocontradictie. Trebuiesaspecificamunmodelincarefiexp(x,x)estefals,fie

q(d)eadevaratsixp(x,x)estetotadevarat. Unastfeldemodelpartialarfi: U={Paris}

extensia(p)={}

extensia(q)={Paris}

referent(d)=Paris Fiindcaxp(x,x) q(d)nuestenicitautologie,nicicontradictieinseamnaca

estecontingenta.I l t t iti t ti t t b i Ingeneral,pentruaaratacaopropozitieestecontingenta,vatrebuisaspecificamdouamodele:unulincaresafieadevaratasiunulincaresafiefalsa.

Saaratamcaxs(x)sixs(x)nusuntlogicechivalente Saaratamcaxs(x)sixs(x)nusuntlogicechivalente. Trebuiesaconstruimunmodelincareceledouapropozitiisaaiba

valoridiferitedeadevarvaloridiferitedeadevar. Dedataaceasta,nevatrebuiununiverscucelputindoimembri. Dacaamaveaunsingurmembru,celedouaaraveaaceeasivaloareDacaamaveaunsingurmembru,celedouaaraveaaceeasivaloare

deadevar. Ilputemfacepexs(x)adevaratincluzandcevadinuniversinp p

extensialuis,iarpexs(x)falsomitandcevadinuniversinextensialuis. U={Paris,Londra}

extensia(s)={Paris}

Acestmodelpartialaratacaceledouapropozitiinusuntlogicechivalente.

(r(c) k1(c)) t(c)

Sarevedemunrationamentdesprecareamspuscaesteinvalid

t(c) k2(c)

Sarevedemunrationamentdesprecareamspuscaesteinvalid. Pentruaaratacaesteinvalid,trebuieconstruitunmodelincare

i l fi d t i l i f lpremiselesafieadevaratesiconcluziafalsa. U={Mihai}

h extensia(t)={Mihai}

extensia(k1)={Mihai}

i (k ) extensia(k2)=

extensia(r)={Mihai}

f ( ) Mih i referent(c)=Mihai

Inmodsimilar,putemaratacaomultimedepropozitiiestei t t t i d d li t t itiil tconsistenta,construindunmodelincaretoatepropozitiilesunt

adevarate.

Pentruaaratacaopropozitienuesteotautologie construimun Pentruaaratacaopropozitienuesteotautologie,construimunmodelincarepropozitiaefalsa.C t i iti t t l i ? Cumarataminsacaopropozitieeotautologie?

Existaoinfinitatedemodele,nuputemsaleprecizampetoate,t d iti d t i d llaratandcapropozitiaeadevarataincadrullor.

Putemluainsa,spreexemplu,propozitiar(a,a) r(a,a)sisa l i i i i laratamcaesteotautologieprintrunrationamentsimplu.

Existadouafeluridemodele: celeincareeinextensialuir

siceleincarenueste.

d f l d d l

r(a, a) r(a, a)

Existadouafeluridemodele: celeincareeinextensialuiR

siceleincarenueste.

Inconsecinta: Inprimulcaz,r(a,a)eadevaratsi,dintabeluldeadevarpentru,r(a,a)

r(a,a)eadevarat.

I ld il ( ) f l i di b l ld d ( ) ( Inaldoileacaz,r(a,a)efalssi,dintabeluldeadevarpentru,r(a,a) r(a,a)eadevarat.

Dinmomentcepropozitiaeadevaratainoricaredinceledouatipuriposibile Dinmomentcepropozitiaeadevaratainoricaredinceledouatipuriposibiledemodel,inseamnacaeotautologie.

Cutoateacestea,rationamentulestefacutintrunmetalimbajsiCutoateacestea,rationamentulestefacutintr unmetalimbajsinuinlogicapredicatelor.

Consideramoaltatautologieevidenta:x(r(x,x) r(x,x))

Amputeafitentatisarationamastfel:p

r(x,x) r(x,x)eadevaratainoricemodel,decisix(r(x,x) r(x,x))trebuie

fi d tsafieadevarata.

Darr(x,x) r(x,x)nueadevaratainoricemodel!

Eanureprezintaopropozitie,decinupoatefiniciadevarata,nicifalsa!

Pentruaconsiderasiformuleleatomicecarenusuntpropozitii,p p ,

vomdefiniconceptuldesatisfiabilitate.

I t b DA NUIntrebare DA NU

EsteAotautologie? Arata caAeste adevarata inorice model.

Construieste unmodelincareAe falsa.

EsteAocontradictie? Arata caAeste falsa inoricemodel.

Construieste unmodelincareAe adevarata.

EsteAcontingenta? Construieste doua modele Arata cafieAeotautologie EsteAcontingenta? Construieste doua modele,unul incareAeste adevarata sialtul incareeste falsa.

Arata cafieAeotautologie,fieocontradictie.

SuntAsi Bechivalente? Arata caAsi Bauaceeasi Construieste unmodelincareSuntAsi Bechivalente? Arata caAsi Bauaceeasivaloare deadevar inoricemodel.

Construieste unmodelincareAsi Bauvalori diferite deadevar.

EstemultimeaAconsistenta? Construieste unmodelincare Arata capropozitiile nupotfiEstemultimeaAconsistenta? Construieste unmodelincaretoate propozitiile dinAsuntadevarate.

Arata capropozitiile nupotfitoate adevarate inoricemodel.

Estedeductia lui CdinP Arata cainorice modelincare ConstruiesteunmodelincareEstedeductia lui CdinPvalida?

Arata cainorice modelincarePeadevarata,Cesteadevarata.

ConstruiesteunmodelincareP eadevaratasiCfalsa.

b l l b d l Cumseinterpreteazaovariabilalibera,deexempluxinp(x)? Vomintroduceoasignaredevariabile ofunctiecarerealizeaza

potrivireaintrefiecarevariabilasiunmembrualuniversuluiU. Def.1:Oformulap(x)estesatisfiabilaintrunmodelMdeo

asignaredevariabilea dacasinumaidacaa(x),obiectulpecareailasigneazaluix,esteinextensialuip(x)inM.

Candesteacumxp(x)satisfiabil? Nuesuficientcap(x)esatisfiabilinMpentrua: Aceastainseamnacaa(x)einextensie(p).

xp(x)necesitacafiecaremembrualluiUsafieinextensie(p).

f f b l l f b l Def.2:Pentrufiecaremembruo aluniversuluiU sifiecarevariabilax,fiea[x|o]asignareadevariabilecareatribuieo luix,darrespectaincelelaltecazuridefinitialuia.

Formal:

Def.3:xp(x)esatisfiabilintrunmodelMdeoasignaredevariabilea dacasinumaidaca,pentrufiecareobiecto dinuniversulUalluiM,p(x)esatisfiabilainMprina[x|o].

f f f d l f l Def.4:Definimofuncties intrunmodelMastfelincat,pentruoricefbfAsiasignaredevariabilea,s(A,a)=1dacaAesatisfiabilinMdea;altfels(A,a)=0.

1.DacaAesteofbfatomicadeformap(t1,,tn)sioi esteobiectulselectatdeti,atunci

Pentrufiecaretermenti: Dacati esteoconstanta,atuncioi =referent(ti).

Dacati esteovariabila,atuncioi =a(ti).

fbf 2.DacaAesteB,cuBfbf,atunci:

3.DacaAesteBC,pentruBsiCfbf,atunci:

4.DacaAesteBC,pentruBsiCfbf,atunci:

5.DacaAesteBC,pentruBsiCfbf,atunci:

fbf 6.DacaAesteBC,pentruBsiCfbf,atunci:

7.DacaAestexB,pentruBfbfsivariabilax,atunci:

8.DacaAestexB,pentruBfbfsivariabilax,atunci:

d l Saconsideramopropozitiesimplaprecumxp(x): Dinpunctul7deladefinitiasatisfiabilitatii,propozitiaesatisfiabiladaca

[ | ] i f ( )i M fi di Ua[x|o]satisfacep(x)inMpentrufiecareo dinU.

Dinpunctul1,aceastaseintampladacafiecareo seaflainextensialuip.

F t l ( ) ti fi bil d i d d i Faptulcaxp(x)esatisfiabilsaunudepindedeasignareaparticularadevariabilea.D t iti ti fi bil t i t d t Dacaaceastapropozitieesatisfiabila,atuncieaesteadevarata.

Astfelformalizamfaptulcaxp(x)eadevaratadacatoatel l di U i i l ielementeledinUsuntinextensialuip.

d l f d l d l d Asadar,incazulfiecareipropozitiidinlogicapredicatelor,dinmotivulcatoatevariabilelesuntlegate,aceastaestesatisfiabilasaunuindiferentdedetaliileasignariidevariabile.

Def.5:OpropozitieAesteadevarata inMdacasinumaidacavreoasignaredevariabilesatisfacepeAinM;altfel,AestefalsainM.

Savedemacumcumputemfolosinotiuniledesatisfiabilitatesiadevarpentruarealizaunrationamentundesuntimplicateoinfinitatedemodele.

Demonstrati ca x(r(x x) r(x x)) este o tautologieDemonstrati ca x(r(x, x) r(x, x)) este o tautologie.

SaconsideramunmodelarbitrarMsiunmembruo arbitrardinU.

Dacaseaflainextensialuir,atuncir(x,x)estesatisfiabildeasignarea

devariabilecareilatribuiepeo luix (punctul1dindef.4).

Dinmomentceconsecintaluir(x,x) r(x,x)estesatisfiabila,implicatiaestesatisfiabila(punctul5).

Dacanuseaflainextensialuir,atuncir(x,x)nuestesatisfiabilde

i d i bil il ib i l i ( l )asignareadevariabilecareilatribuiepeo luix (punctul1).

Dinmomentceconditialuir(x,x) r(x,x)estenesatisfiabila,implicatiaestesatisfiabila(punctul5)satisfiabila(punctul5).

Demonstrati ca x(r(x x) r(x x)) este o tautologieDemonstrati ca x(r(x, x) r(x, x)) este o tautologie.

r(x,x) r(x,x)estesatisfiabilapentrufiecaremembrudinU,decix(r(x,x)

r(x,x))estesatisfiabiladeoriceasignaredevariabile(punctul7).

Decix(r(x,x) r(x,x))esteadevaratainM(def.adevarului),pentruoriceU

siextensiealuir,decieadevaratainoricemodel,fiindasadarotautologie.siextensiealuir,decieadevaratainoricemodel,fiindasadarotautologie.

Demonstrati ca xh(x) se deduce din x(h(x) j(x)).

d d l b h SaconsideramunmodelarbitrarMincarepremisax(h(x) j(x))esteadevarata(vezitabel). Conjunctiah(x) j(x)esatisfiabilaindiferentdeasignareapentrux,asadar

asaestesih(x)(punctul3dindef.4).

h( ) f b l d d b l ( l ) Decixh(x)estesatisfiabiladeoriceasignaredevariabile(punctul7)siadevaratainM(def.adevarului).

Mfiindarbitrarales rezultacaxh(x)esteadevaratainoricemodelincare Mfiindarbitrarales,rezultacaxh(x)esteadevaratainoricemodelincarex(h(x) j(x))eadevarata.

Decix(h(x) j(x))xh(x) Decix(h(x) j(x))xh(x).

Chiarsipentruargumentesimple,rationamentulecomplicat.

Pentruacontracaraacestaspect vomstudiaincursulurmatorsistemeledePentruacontracaraacestaspect,vomstudiaincursulurmatorsistemelededemonstratie.

1.Determinatidacafiecarepropozitieesteadevaratasaufalsainmodeluldat:

U={Cristi,Alin}

Extensia(p) {Cristi Alin} Extensia(p)={Cristi,Alin}

Extensia(q)={Alin}

Extensia(r)=( )

Referent(c)=Cristi

1. q(c)2. p(c) r(c)3. r(c) (p(c) q(c))4 xp(x)4. xp(x)5. xq(x)6. x(p(x) q(x))7. xq(x)xp(x)

2. Determinatidacafiecarepropozitieesteadevaratasaufalsainmodeluldat:

U={Cristi,Mihai,Ionut}

h extensia(p)={Cristi,Mihai,Ionut}

extensia(q)={Cristi,Mihai}

extensia(r)={ } extensia(r)={,,}

referent(c)=Ionut

1. x(r(x,c) r(c,x))2. x(p(x) q(x))3. x(r(x,c) q(x))4 x(q(x) (p(x) q(x)))4. x(q(x) (p(x) q(x)))5. xyr(x,y)6. xy(r(x,y) r(y,x))

3.Determinatidacafiecarepropozitieesteadevaratasaufalsainmodeluldat: U={Tiberiu,Cristina,Edi}

extensia(p)={Tiberiu Cristina Edi} extensia(p)={Tiberiu,Cristina,Edi}

extensia(q)={Cristina}

extensia(r)={Tiberiu,Edi}

referent(c)=Cristina

referent(e)=Edi

1. q(c)q2. q(e)3. r(c) r(e)4 r(c) p(c)4. r(c) p(c)5. x(p(x) q(x))6. xq(x) xr(x)

( ( ) ( ))7. x(q(x) r(x))8. xy(p(x) q(y))

4.Scrietimodelulcarecorespundelaurmatoareainterpretare:

U numerenaturaledela10la13 U:numerenaturaledela10la13

p(x):xesteimpar

q(x):desprexsespunecapoartaghinion

r(x,y):xesteurmatorulnumardupay

s(x):xestemaimicdecat9

t(x):xesteunnumarformatdindouacifre

5.Arataticafiecaredinurmatoareleestecontingent:

p(a) p(b)

x(t(x,c))

p(c) xp(x)

x(p(x)yq(y)) x(p(x)yq(y))

6.Arataticaurmatoareleperechidepropozitiinusuntlogic

echivalente:

p(a),q(a)

xp(x),p(x)

xr(x x) xr(x x) xr(x,x),xr(x,x)

xp(x)q(x),x(p(x)q(x))

xyr(x,y),xyr(x,y)

7.Arataticaurmatoarelemultimidepropozitiisunt

iconsistente:

{p(a),q(a),r(a),s(a)}

{p(c,c),p(c,a),p(a,c),p(a,a)}

{p(a) p(b),p(a)xp(x)}p( ) p( ), p( ) p( )

{x(q(x) p(x)),xr(x),x[(p(x) q(x)) r(x)]}

8.Construitimodelepentruaaratacaurmatoarelerationamentesuntnevalide:

x(p(x) q(x))x(p(x) q(x))

xq(x)x(p(x) r(x))

q(x) r(x)p(a)

p(b) q(a b)xq(x b)p(b)

p(c)

q(a,b)xq(x,b)

xq(x,b)

xp(x) q(b,b)