Logica computationala

Logica computationala

Obiective

Scopul acestui curs este prezentarea bazelor logice ale informaticii: logica propozitiilor si logica predicatelor, metode de demonstrarea teoremelor in aceste sisteme logice, algebre si functii booleene. Se face legatura cu aplicatii ale logicii in informatica: programarea logica, circuite secventiale si combinationale. Sunt de asemenea introduse notiuni de codificarea si reprezentarea informatiei in calculator.

Competente

• utilizarea bazelor de numeratie si cunoasterea reprezentarilor interne ale numerelor;
• modelarea rationamentului uman, obisnuit, cotidian si a celui matematic folosind logica propozitiilor si logica predicatelor;
• cunoasterea bazelor teoretice ale circuitelor logice.

Metode

prelegeri ce contin aspecte teoretice si exemple;

seminarii care constau in exercitii pentru aprofundarea teoriei si prezentari individuale ale studentilor a unor probleme existente intr-o baza de probleme propuse (M. Lupea, A. Mihis, 2011).

Program (Pascal,C,C++,Java) care contine implementarea algoritmilor de conversii si operatii in diferite sisteme de numeratie.

Continut

I    Sisteme de numeratie si reprezentare interna a numerelor

II    Logicile clasice: logica propozitiilor si logica predicatelor de ordinul I

III Algebre booleene, functii booleene si circuite logice

I Sisteme de numeratie si reprezentarea interna a numerelor

= => notiunile utilizate la disciplina: Arhitectura calculatoarelor

Sisteme de numeratie

Definitii, reprezentare si operatii (algoritmi de comparare, adunare, inmultire, impartire) cu numere intr-o baza data.

Conversiile numerelor intregi si rationale intre baze de numeratie folosind metodele: calculul in baza sursa, calculul in baza destinatie, utilizarea unei baze intermediare.

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

Reprezentarea interna a numerelor

Reprezentarea numerelor intregi fara semn, operatii, notiunea de depasire, algoritmi de inmultire si impartire. Exemple.

Reprezentarea numerelor intregi cu semn folosind codurile: direct, invers si complementar, operatii, depasire. Exemple.

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

Reprezentarea numerelor reale: virgula fixa, virgula mobila (cu mantisa subunitara, cu mantisa supraunitara). Exemple.

Bibliografie

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

M. Cocan, B. Pop: Bazele matematice ale sistemelor de calcul (capitol 1), Editura Albastra, Cluj-Napoca, 2001.

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 propozitiilor si logica predicatelor de ordinul I

Logica propozitiilor si logica predicatelor prezentate algebric si ca sisteme deductive (perspectiva computationala). Metode de demonstrare a teoremelor utilizate pentru a decide daca o formula (conjectura) este consecinta logica a unei multimi de formule (axiome si ipoteze).

Scop: Formalizarea rationamentului uman si a celui matematic folosind aceste logici clasice.

= > notiuni utilizate la disciplinele: Programare logica, Inteligenta Artificiala, Sisteme de demonstrare automata.

Aplicatii ale domeniului "demonstrarea automata"

• Matematica: EQP- algebre Booleene, OTTER- algebra, Geometry Expert- geometrie Euclidiana.
• Informatica

v    Limbaje naturale, vedere artificiala, agenti inteligenti;

Document online: Saracia in societatea romaneasca Referat: Sociologie economica rurala - intrebari

v    Generare si verificarea produseor soft: KIDS(Kestrel Institute- algoritmi de planificare,), AMPHION (NASA- programe pentru ghidarea satelitilor), KIV (Karlsruhe Institute-: verificare soft- supervizarea cursului de neutroni intr-un reactor nuclear, transferul in siguranta a comenzilor intr-un vehicul spatial), PVS (NASA- verificarea soft-ului care coordoneaza zborurile spatiale).

v    Verificare hard: sistemul ACL2 (verifica corectitudinea codului pentru impartirea in virgula mobila la microprocesorul AMD5K86), ANALYTICA (verifica circuitul de impartire care implementeaza standardul IEEE), sistemul HOL (Bell Laboratories)

• Domenii potentiale: biologie, stiinte sociale, medicina, comert.

Logica propozitiilor

Propozitiile logice sunt modele ale afirmatiilor propozitionale din limbajul natural si ele pot sa fie adevarate sau false.

P: Este soare.                      Q: Afara este cald. R: Merg la piscina. 

S: Daca este soare si este cald afara atunci merg la piscina.

S:

"Demonstrarea teoremelor":

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

Sintaxa logicii propozitiilor: conective, formule.

Semantica: interpretarea unei formule, model, formula consistenta (realizabila), formula inconsistenta (contradictorie), tautologie, relatia de consecinta logica. Tabela de adevar a unei formule.

Echivalente logice (legi): DeMorgan, absorbtia, comutativitatea, asociativitatea, distributivitatea, idempotenta.

Clauze si forme normale: conjunctiva (FNC) si disjunctiva (FND), algoritmul de transformare a unei formule in FNC si FND.

Sistemul formal (axiomatic, deductiv) al logicii propozitionale, deductie, teorema.

Teorema de deductie si consecintele sale.

Teorema de corectitudine si completitudine a logicii propozitiilor. Proprietati ale logicii propozitiilor: necontradictia, coerenta si decidabilitatea.

Metoda tabelelor semantice - metoda semantica prin respingere.

Metoda rezolutiei si rafinarile sale in logica propozitiilor.

Logica predicatelor de ordinul I

Axiomele care definesc numerele naturale:

a1. Orice numar natural are un unic successor imediat.

existenta:

unicitate:

a2. Numarul natural 0 nu este succesorul imediat al nici unui alt numar

natural.

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

existenta:

unicitatea:            

Functii:; Predicate:

Sintaxa logicii predicatelor: conective, cuantificatori, termeni, atomi, formule, literali, clauze.

Sistemul formal (axiomatic, deductiv) asociat logicii predicatelor.

Semantica logicii predicatelor: interpretare, model, formula valida, formula consistenta, formula contradictorie, consecinta logica.

Forme normale ale formulelor predicative: forma normala prenexa, forma normala Skolem - algoritmi.

Teorema de corectitudine si completitudine. Proprietatile logicii predicatelor: necontradictia, coerenta, semi-decidabilitatea.

Metoda tabelelor semantice - reguli  specifice cuantificatorilor.

Univers Herbrand, interpretare Herbrand, teorema lui Herbrand. Demonstrarea prin respingere pe baza teoremei lui Herbrand.

Substitutii si unificatori ai termenilor si atomilor. Algoritmul de obtinere al celui mai general unificator a doi atomi.

Metoda rezolutiei si rafinarile sale in 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.
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. Mihis: Logici clasice si circuite logice. Teorie si 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- biblioteca.
13. D.Tatar: Inteligenta artificiala: demonstrare automata de teoreme si NLP, Editura Microinformatica, 2001 - biblioteca.

III    Algebre booleene, functii booleene, circuite logice.

Algebre booleene: definitii, proprietati, principiul dualitatii.

Functii booleene, formele canonice echivalente.

Simplificarea functiilor booleene

definitii: monoame maximale, monoame centrale, factorizare;

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

metoda analitica a lui Mc.Quine

4. Circuite logice

definitii, reprezentarea circuitelor poarta de baza ("and", "or", "not") si a circuitelor poarta derivate ("xor", "nand", "nor");

exemple de circuite logice.

Bibliografie

M. Cocan, B. Pop: Bazele matematice ale sistemelor de calcul (capitol 2), Editura Albastra, Cluj-Napoca, 2001.

M. Lupea, A. Mihis: Logici clasice si circuite logice. Teorie si exemple,  Editura Albastra, editia II-2009, editia III-2011.

D.Tatar: Bazele matematice ale calculatoarelor, editia 1999 -biblioteca.

Evaluarea - ponderi in nota finala

15%- Lucrare scrisa (seminar 5 -o ora ) cu subiecte din prima parte:

cunoasterea operatiilor in diferite baze de numeratie si conversii intre baze de numeratie

cunoasterea reprezentarilor interne ale numerelor intregi si reale

!! Prezenta la lucrarea scrisa este obligatorie.

60% -Lucrare scrisa (curs 14 - 2 ore) cu 3 subiecte (teorie si probleme) din materia cursurilor 3-13:

• logica propozitionala
• logica predicativa
• algebre booleene, functii booleene, circuite logice

20%- Activitate seminarii:

raspunsuri neanuntate + prezentari individuale de probleme dintr-o baza de probleme ( M. Lupea, A. Mihis , 2009, 2011).

4. 10% Tema optionala (poate creste nota finala), la alegere dintre:

Program (Pascal,C,C++,Java,) care contine implementarea algoritmilor de conversii si operatii in diferite sisteme de numeratie, predat in saptamana             3-7 decembrie 2012.

Modelarea si rezolvarea unui set de probleme de rationament din viata cotidiana si din domeniul matematic, folosind metodele studiate de demonstrare automata in logicile clasice. Setul de probleme va contine atat probleme propuse spre rezolvare studentilor, cat si probleme care vor fi enuntate si rezolvate de catre studenti. Tema predata in saptamana 7-11 ianuarie 2013.

Pentru promovare:

- prezenta la cel putin 75% din cursuri (10 cursuri).

prezenta la cel putin 75% din seminarii (11 seminarii).

- notele de la lucrarile scrise si cea de la seminar trebuie sa fie cel putin 5.

Detalii organizatorice, gestionarea situatiilor exceptionale

Sunt valabile regulamentele oficiale ale universitatii in legatura cu prezenta studentilor la activitatile didactice, cazurile de copiat si plagiat.