Teoria programării logice #1

Logica propozițiilor este un limbaj. Ca orice limbaj, el despune de:

• Alfabet – simboluri
• Sintaxă – gramatica
• Semantică – sensul

Alfabet.

P – Ion studiază logica.

Q – Ion studiază informatica.

R – Ion va fi bun specialist.

¬ – Nu

˄ – Și

˅ – sau

⊃ – dacă, atunci

≡  – Echivalență

( ), { }, [ ].

Sintaxa.

Bazis: Fie p și q, le vom numi formule.

Pas inductiv: dacă p și q sunt formule, atunci negația p^q, p˅q, p⊃q, p≡q, tot sunt formule. Aplicând o dată sau de mai multe ori pasul inductiv, obținem diverse modele a lumei reale. {[(p^q)⊃r] ≡ (p˅r)}≡¬q.

Prezentarea grafică a formulei logice propozițiilor (ex: {[(p^q)⊃r] ≡ (p˅r)}≡¬q):

Formule elementare și compuse:

Elementare – sunt acelea care nu mai pot fi discompuse(cele puse la bazis).

Compuse – sunt celea la care au fost aplicate o dată sau mai multe ori pasul inductiv.

Semantică:

Metode de interpretare a sensului logice a propozițiilor:

1. Tabeluri de adevăr
2. Algoritmică

Lectură: N. Pelin, элем. логическ. программировании, edit. Nestor 2000

Aspecte de interpretare:

1. Model a unei formule logice – În calitate de model a unei formule legice, noi, vom considera formula concretă care este interpretată ca adevăr. Presupunem: (p˅q) unde p – adevăr și q – adevăr, dacă q – F, atunci această formulă nu este model iterpretabil.
2. Formule executabile – sunt cele formule care cel puțin o dată pot fi interpretate ca model.
3. Formule neexecutabile – sunt cele care nu dispun de model.
4. Tautologie – o formulă poate fi numită tautologie în cazul când ea este interpretată ca adevăr, indiferent de semnificația a literelor existente în formulă (ex: p˅¬p).
5. Disjunct – este disjuncția mulțimei de litere (ex: p˅¬r, p˅¬r˅q˅s, p, [ ]- vid, unicul care nu poate fi executabil.)

Pilonii a programării în logică:

1. Disjunctul vid.
2. Principii de rezoluție (Rezolvant)
3. Strategie de căutare

Forma conjuctiv normală – reprezintă conjuncția mulțimei de dijuncți.

Teoremă: Orice formulă a logicei propozițiilor poate fi retransformată în formă conjutciv normală.

Algoritm de retransformare a formulei logice în formă conjuctiv normală:

1. Ne eliberăm de echivalență
2. Ne eliberăm de implicație
3. Folosind legile lui Demorgan, introducem negația în paranteze (formule de echivalență)
4. Folosind legea de Involuție, ne eliberăm de negație dublă
5. Folosind legile asociative, distributive și comutative aducem formula logică a propozițiilor, aducem la forma conjuctiv normală.

Principul de rezoluție:

A fost elaborat de Robinson în 1985, esența căruia este următoarea:

Fie, avem doi disjuncți, (p˅q) și (r˅¬q)

(p˅q) ^ (p˅r) ^ (¬q ˅¬r) ^¬p

S = { p˅q , p˅r, ¬q ˅¬r, ¬p }

1. p˅q
2. p˅r
3. ¬q ˅¬r
4. ¬p
5. q – rezolventa din 1 și 4
6. p˅¬r – rezolventa 1 și 3
7. r – 2 și 3
8. p˅¬q 2 și 3

Strategii de căutare:

1. Metoda de căutare a soluțiilor în adâncime –
2. Metoda de căutare în lățime – se folosește în cazul când știm ceva despre probleme de acest fel. Având statistica de probabilitate. Este mai efectivă ca prima, dar nu garantează
   

Disjuncții lui Horn.

Definiție: Disjuncții lui Horn sunt cei disjuncți care nu despun de mai mult de una literă pozitivă.

Cazuri disjun.țiilor lui Horn

1. Când dispunem de una literă pozitivă și nici una literă negativă (q)
2. Când dispunem de una literă pozitivă și una sau mai multe negative (p˅¬r˅¬q) (Variante pentru reguli)
3. Când dispunem de una sau mai multe litere negative și nici una pozitivă.

 

Lucrul cu ferestrele.

clearwindow

makewindow(x1,x2,…,x8) parametri

x1 – numarul ferestrei

x2,x3 – culoarea la text și la chenar

x4 – denumirea ferestrei la mijlocul ferestrei

x5,x6 – coltul de sus a monitorului x5 in jos și x6 la dreapta. Punctul de incepere

x7,x8 – înălțimea și lungimea (maxim 25×80)

 

makewindow(1,7,7,”Meniu:”,5,20,15,40),

shiftwindow(X)

gotowindow(X)

removewindow

Lucru cu bază de date dinamice.

Faptele scrise în textul programului, formează împreună, așa zise bază de date statică. Adică baze de date care nu se schimbă în procesul de executare a programului, dar deseori avem necesitatea să formăm așa zisă baza de date dinamice. Bază de date care se modifică bază în procesul de executare a programului.

Formarea și modificarea bazei de date dinamice se face prin intermediul urmatoarelor predicate predefinite.

asserta(studiaza_bd(Nume,Obiect),

assertz( – // – ),

retract(studiaza_bd(ion,_)),

 

save(”al_meu_bd.pro”)

consult(”al_meu_bd.pro”)

 

f(11):- studiaza(Nume,Obiect),

asserta(studiaza_bd(Nume,Obiect)),

fail.

F(12):- save(”al_meu_bd.pro”).

f(13):-  existfile(”al_meu_bd.pro”).

Elaborăm o funcție care ne va permite să introducem un nou rând in db de la tastă.