8/17/2019 Curs 4-II Bazele Logice 3-Algoritm Forme Normale

1/4

Curs 4 A.I. – Forme normale conjunctive şi disjunctive

FORME NORMALE ŞI CONSECINŢE LOGICE

Logica matematică = logica simbolică în care afirmaţiile !e care le vom numi !ro!o"iţii# sunt notatecu literele alfabetului.

Logica propoziţiilor = un limbaj formal care conţine un alfabet$ reguli de sinta%ă$ a%iome şi o regulăde deducţie. studia"ă legăturile dintre !ro!o"iţii. (!Aceată propoziţie ete "ală#$#.

%ropoziţii = atom = afirmaţii cărora li se ataşea"ă o valoare de adevăr.

Logica im&olică = utili"ea"ă simboluri !entru re!re"entarea elementelor universului !roblemei şi ao!eraţiilor asu!ra acestora.

Operaţii logice:

 

• ordinea efectuării o!eraţiilor logice& ' ) * +, -. /-.

Calc0l propoziţio1al2

atom = !ro!o"iţie cu valoare de adevăr  formulă = !ro!o"iţie com!usă

Form0lă &i1e "ormată sau &i1e "orm0lată - 3"" #& se construieşte du!ă următoarele reguli&

'(. )n atom este o formulă.

'*. +acă F este o formulă$ atunci ,F este formulă bine formată.

'-. +acă F şi sunt formule$ atunci & Fv$ F/$ F01$ F201 sunt bine formate.'4. 3rice f.b.f. se obţine !rin a!licarea regulilor '($'*$'-.

• 3 formulă bine formată !oate fi&

4i501cţia e6cl0i*ă

p 7 p*7

8 8 98 9 89 8 89 9 9

4i501cţia

p 7 p*7

8 8 88 9 89 8 89 9 9

Ec:i*ale1ţa

p 7 p 7

8 8 8

8 9 99 8 99 9 8

1

8/17/2019 Curs 4-II Bazele Logice 3-Algoritm Forme Normale

2/4

Curs 4 A.I. – Forme normale conjunctive şi disjunctive

A5I+6 I7A5I+6

8otdeauna adevărată. 7u totdeauna adevărată. 8otdeauna falsă. 7u totdeauna falsă.

C379I98:786 I7C379I98:786

 

FORME NORMALE

4e"i1iţie& Echivalenţa se notea"ă F=#& F şi sunt ec;ivalente atunci cv'# / ,v>v'#

0 fnd& / ,># v , / ,># v / >#.

Algoritm ;e tra1"ormare a 01ei "orm0le &i1e "ormate 01'#019 ... 9v,v>#/9v,v,'#

2

8/17/2019 Curs 4-II Bazele Logice 3-Algoritm Forme Normale

3/4

Curs 4 A.I. – Forme normale conjunctive şi disjunctive

Consecinţe logice:

4e"i1i ţ ie2 +acă F($..$Fn$ sunt f.b.f.$ şi dacă !entru orice inter!retare I !entru care F(/F*/.../Fn esteadevărată$ atunci este adevărată atunci se s!une că este o co1eci1ţă logică a lui F($...$Fn$ iar F($...$ Fn sunt a6iome !entru .

=eorema82  este o consecinţă logică a lui F ($..$Fn  dacă şi numai dacă  formula F(/.../Fn01 estevalidă.

=eorema>& este o consecinţă logică a lui F($..$Fn dacă şi numai dacă formula F(/.../Fn / , esteinconsistentă.

roblema(& Fie F(& 01>  F*& ,>  & ,

9ă se demonstre"e că& este o consecinţă logică a lui F( şi F*.

Indicaţie& +in 8( =1 F(/F*01 0 validă sau din 8* =1 F(/F*/, 0 inconsistentă.

roblema*&

9e dau&

= arlamentul refu"ă să acţione"e.

> = reva s0a terminat.' = +irectorul firmei demisionea"ă.9 = reva continuă de mai mult de un an.

 F( & +acă !arlamentul refu"ă să acţione"e atunci directorul firmai demisionea"ă şi greva continuă maimult de un an.

F* & arlamentul refu"ă să acţione"e.

F- & reva nu s0a terminat.

9e cere&

i# să se trans!ună în formule F($ F* şi F-ii# să se demonstre"e că F- este o consecinţă logică a lui F( / F* / F-.

=ema 8

9ă se construiască o !roblemă în stilul !roblemei *$ să se trans!ună a!oi în formule şi să se re"olve.

:% de re"v cu tabele. 8ema voastra este sa demonstrati cu ajutorul teoremelor.

9e cunosc&

 7 = se formea"ă numărul8 = telefonul sună

5 = linie ocu!ată

3

8/17/2019 Curs 4-II Bazele Logice 3-Algoritm Forme Normale

4/4

Curs 4 A.I. – Forme normale conjunctive şi disjunctive

A = abonatul răs!unde

? = linie ocu!ată !e tim!ul convorbirii.

F( & 9e formea"ă numărul$ telefonul sună sau linie ocu!ată.

F* & 8elefonul sună$ abonatul răs!unde$ linia este ocu!ată !e tim!ul convorbirii.

F-  & +acă linia nu e ocu!ată telefonul sună.  F( F* F-

= L A M N N?= N?=∨L =?A =?A?M

 L   L?=

( B ( ( B ( ( ( ( ( (

( ( B B ( ( ( B ( B (

B B ( ( ( B B ( ( ( B

B ( B B B ( ( ( B B (

4