Download - 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
-
7/28/2019 Logica_computationala_2012_1013
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
-
7/28/2019 Logica_computationala_2012_1013
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.
-
7/28/2019 Logica_computationala_2012_1013
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
-
7/28/2019 Logica_computationala_2012_1013
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.
-
7/28/2019 Logica_computationala_2012_1013
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/28/2019 Logica_computationala_2012_1013
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.
-
7/28/2019 Logica_computationala_2012_1013
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.