logica_computationala_2012_1013

7/28/2019 Logica_computationala_2012_1013

1/8

Logic computaional

http://cs.ubbcluj.ro/~lupea/LOGICA/Romana

Obiective

Scopul acestui curs este prezentarea bazelor logice ale informaticii: logica propoziiilor i

logica predicatelor, metode de demonstrarea teoremelor n aceste sisteme logice, algebre

i funcii booleene. Se face legtura cu aplicaii ale logicii n informatic: programarea

logic, circuite secveniale i combinaionale. Sunt de asemenea introduse noiuni de

codificarea i reprezentarea informaiei n calculator.

Competene utilizarea bazelor de numeraie i cunoaterea reprezentrilor interne ale

numerelor;

modelarea raionamentului uman, obinuit, cotidian i a celui matematic folosind

logica propoziiilor i logica predicatelor;

cunoaterea bazelor teoretice ale circuitelor logice.

Metode

prelegeri ce conin aspecte teoretice i exemple;

seminarii care constau n exerciii pentru aprofundarea teoriei i prezentri

individuale ale studenilor a unor probleme existente ntr-o baz de probleme propuse

(M. Lupea, A. Mihis, 2011).

Program (Pascal,C,C++,Java) care contine implementarea algoritmilor de conversii i

operaii n diferite sisteme de numeraie.

Coninut

I Sisteme de numeraie i reprezentare intern a numerelor

II Logicile clasice: logica propoziiilor i logica predicatelor de ordinul I

III Algebre booleene, funcii booleene i circuite logice


2/8

I Sisteme de numeraie i reprezentarea intern a numerelor

====> noiunile utilizate la disciplina:Arhitectura calculatoarelor

Sisteme de numeraie

1. Definiii, reprezentare i operaii (algoritmi de comparare, adunare, nmulire,

mprire) cu numere ntr-o baz dat.

2. Conversiile numerelor ntregi i raionale ntre baze de numeraie folosind metodele:

calculul n baza surs, calculul n baza destinaie, utilizarea unei baze intermediare.

3. Exemple pentru bazele particulare: 2,3,4,6,8,10,16.

Reprezentarea intern a numerelor

1. Reprezentarea numerelor ntregi fr semn, operaii, noiunea de depire, algoritmi

de nmulire i mprire. Exemple.

2. Reprezentarea numerelor ntregi cu semn folosind codurile: direct, invers i

complementar, operaii, depire. Exemple.

3. Reprezentarea numerelor subunitare cu semn, codurile: direct, invers, complementar.

4. Reprezentarea numerelor reale: virgul fix, virgula mobil (cu mantisa subunitar,

cu mantisa supraunitar). Exemple.

Bibliografie

1) F. Boian:Bazele Matematice ale Calculatoarelor, Editura Presa Universitara Clujeana,

2002.

2) M. Cocan, B. Pop: Bazele matematice ale sistemelor de calcul (capitol 1), Editura

Albastra, Cluj-Napoca, 2001.3) A. Vancea, F. Boian, D.Bufnea, A.Gog, A.Darabant, A.Sabau: Arhitectura

calculatoarelor. Limbajul de asamblare 80x86, (capitol 1), Editura Risoprint,

Cluj-Napoca, 2005.

II Logici clasice: logica propoziiilor i logica predicatelor de ordinul I


3/8

Logica propoziiilor i logica predicatelor prezentate algebric i ca sisteme

deductive (perspectiv computaional). Metode de demonstrare a teoremelor utilizate

pentru a decide dac o formul (conjectura) este consecin logic a unei mulimi de

formule (axiome si ipoteze).

Scop: Formalizarea raionamentului uman i a celui matematic folosind aceste logici

clasice.

===> noiuni utilizate la disciplinele: Programare logic, Inteligen Artificial, Sisteme

de demonstrare automat.

Aplicaii ale domeniului demonstrarea automat

Matematic : EQP- algebre Booleene, OTTER- algebra, Geometry Expert-

geometrie Euclidian.

Informatic

Limbaje naturale, vedere artificial, ageni inteligeni;

Generare si verificarea produseor soft: KIDS(Kestrel Institute- algoritmi de

planificare,), AMPHION (NASA- programe pentru ghidarea sateliilor),

KIV (Karlsruhe Institute-: verificare soft- supervizarea cursului de neutroni

ntr-un reactor nuclear, transferul in siguran a comenzilor ntr-un vehiculspaial), PVS (NASA- verificarea soft-ului care coordoneaz zborurile

spaiale).

Verificare hard: sistemul ACL2 (verific corectitudinea codului pentru

mprirea n virgul mobil la microprocesorul AMD5K86), ANALYTICA

(verific circuitul de mprire care implementeaz standardul IEEE),

sistemul HOL (Bell Laboratories)

Domenii poten iale : biologie, stiine sociale, medicin, comer.

Logica propoziiilor

Propoziiile logice sunt modele ale afirmaiilor propoziionale din limbajul natural

i ele pot s fie adevrate saufalse.


4/8

P: Este soare. Q: Afar este cald. R: Merg la piscin.

S:Dac este soare ieste cald afar atuncimerg la piscin.

S: RQP

Demonstrarea teoremelor:

Din formulele P,Q,S (ipoteze) putem deduce (infera) R (concluzia)?

1. Sintaxa logicii propoziiilor: conective, formule.

2. Semantica: interpretarea unei formule, model, formul consistent (realizabil),

formul inconsistent (contradictorie), tautologie, relaia de consecin logic.

Tabela de adevr a unei formule.

3. Echivalene logice (legi): DeMorgan, absorbia, comutativitatea, asociativitatea,

distributivitatea, idempotena.

4. Clauze i forme normale: conjunctiv (FNC) i disjunctiv (FND), algoritmul de

transformare a unei formule n FNC i FND.

5. Sistemul formal (axiomatic, deductiv) al logicii propoziionale, deducie, teorem.

6. Teorema de deducie i consecinele sale.

7. Teorema de corectitudine i completitudine a logicii propoziiilor. Proprieti ale

logicii propoziiilor: necontradicia, coerena i decidabilitatea.

8. Metoda tabelelor semantice metod semantica prin respingere.

9. Metoda rezoluiei i rafinrile sale n logica propoziiilor.

Logica predicatelor de ordinul I

Axiomele care definesc numerele naturale:

a1. Orice numr natural are un unic successor imediat.

existena: ))(,())(( xsuccesoryegalyx

unicitate: )),())(,())(,()()()(( zyegalxsuccessorzegalxsuccesoryegalzyx


5/8

a2. Numrul natural 0 nu este succesorul imediat al nici unui alt numr

natural. ))(,0()( xsuccesoregalx

a3. Orice numar natural cu exceptia lui 0 are un unic predecesor imediat.

existena: )))(,(),0()()(( xpredecesoryegalxegalyx

unicitatea:

)),())(,())(,()()()(( zyegalxpredecesorzegalxpredecesoryegalzyx

Funcii: predecesorsuccesor, ; Predicate: egal

1. Sintaxa logicii predicatelor: conective, cuantificatori, termeni, atomi, formule,

literali, clauze.

2. Sistemul formal (axiomatic, deductiv) asociat logicii predicatelor.

3. Semantica logicii predicatelor: interpretare, model, formul valid, formul

consistent, formul contradictorie, consecina logic.

4. Forme normale ale formulelor predicative: forma normal prenex, forma

normal Skolem - algoritmi.

5. Teorema de corectitudine i completitudine. Proprietile logicii predicatelor:

necontradicia, coerena, semi-decidabilitatea.

6. Metoda tabelelor semantice reguli specifice cuantificatorilor.

7. Univers Herbrand, interpretare Herbrand, teorema lui Herbrand. Demonstrareaprin respingere pe baza teoremei lui Herbrand.

8. Substituii i unificatori ai termenilor i atomilor. Algoritmul de obinere al celui

mai general unificator a doi atomi.

9. Metoda rezoluiei i rafinrile sale n logica predicatelor.

Bibliografie

1. M. Ben-Ari:Mathematical Logic for Computer Science, Ed. Springer, 2001.

2. W. Bibel:Automated theorem proving, View Verlag, 1987.

3. C.L. Chang, R.C.T. Lee: Symbolic Logic and Mechanical Theorem Proving,

Academic Press 1973.


6/8

4. M. Clarke:Logic for Computer Science, Ed. Eddison-Wesley 1990.

5. J.P. Delahaye: Outils logiques pour l'intelligence artificielle, Ed Eyrolls, 1986.

6. M. Fitting: First-order logic and Automated Theorem Proving, Ed. Springer

Verlag, 1990.

7. Mihaela Malita, Mircea Malita: Bazele Inteligentei Artificiale, Vol.I, Logici

propozitionale, Ed. Tehnica, Bucuresti, 1987.

8. M. Lupea, A. Mihi: Logici clasice i circuite logice. Teorie i exemple,

Editura Albastra, editia II - 2009, editia III-2011.

9. L.C. Paulson:Logic and Proof, Univ. Cambridge, 2000, curs on-line.

10.M. Possega:Deduction Systems, Inst. of Informatics, 2002, curs on-line .

11.(ed) A.Thayse: From standard logic to Logic Programming, Ed. J.Wiley,

vol1(1989), vol2(1989), vol3(1990).

12.D.Tatar: Bazele matematice ale calculatoarelor, edition 1999- bibliotec.

13.D.Tatar: Inteligenta artificiala: demonstrare automata de teoreme si NLP,

Editura Microinformatica, 2001 bibliotec.

III Algebre booleene, funcii booleene, circuite logice.

1. Algebre booleene: definiii, proprieti, principiul dualitii.

2. Funcii booleene, formele canonice echivalente.

3. Simplificarea funciilor booleene

definiii: monoame maximale, monoame centrale, factorizare;

metoda diagramelor Veitch-Karnaugh pentru funcii cu 2-3 variabile;

metoda analitic a lui Mc.Quine

4. Circuite logice

definiii, reprezentarea circuitelor poart de baz (and, or, not) i a

circuitelor poart derivate (xor, nand, nor);

exemple de circuite logice.


7/8

Bibliografie

1) M. Cocan, B. Pop:Bazele matematice ale sistemelor de calcul(capitol 2), Editura

Albastra, Cluj-Napoca, 2001.

2) M. Lupea, A. Mihi:Logici clasice i circuite logice. Teorie i exemple, Editura

Albastra, editia II-2009, editia III-2011.

3) D.Tatar:Bazele matematice ale calculatoarelor, ediia 1999 -biblioteca.

Evaluarea ponderi n nota final

1. 15%- Lucrare scris (seminar 5 o or ) cu subiecte din prima parte:

cunoaterea operaiilor n diferite baze de numeraie i conversii ntre baze de

numeraie

cunoaterea reprezentrilor interne ale numerelor ntregi i reale

!! Prezena la lucrarea scris este obligatorie.

2. 60% -Lucrare scris (curs 14 2 ore) cu 3 subiecte (teorie i probleme) din materia

cursurilor 3-13: logica propoziional

logica predicativ

algebre booleene, funcii booleene, circuite logice

3. 20%- Activitate seminarii:

rspunsuri neanunate + prezentri individuale de probleme dintr-o baz de

probleme ( M. Lupea, A. Mihis , 2009, 2011).4. 10%- Tem opional (poate crete nota final), la alegere dintre:

Program (Pascal,C,C++,Java,...) care conine implementarea algoritmilor de

conversii i operaii n diferite sisteme de numeraie, predat n sptmna

3-7 decembrie 2012.


8/8

Modelarea si rezolvarea unui set de probleme de raionament din viaa cotidian i

din domeniul matematic, folosind metodele studiate de demonstrare automat n

logicile clasice. Setul de probleme va conine att probleme propuse spre

rezolvare studentilor, ct i probleme care vor fi enunate i rezolvate de ctre

studeni. Tem predat n sptmna 7-11 ianuarie 2013.

Pentru promovare:

-prezena la cel puin 75% din cursuri (10 cursuri).

- prezena la cel puin 75% din seminarii (11 seminarii).

- notele de la lucrrile scrise i cea de la seminar trebuie s fie cel puin 5.

Detalii organizatorice, gestionarea situaiilor excepionale

Sunt valabile regulamentele oficiale ale universitii n legtur cu prezena

studenilor la activitile didactice, cazurile de copiat i plagiat.

logica_computationala_2012_1013

Documents