Probleme Logica Propozitii Rom

9.1. Probleme din logica propoziţiilor

Problema 9.1.1.

Folosind metoda tabelelor de adevăr verificaţi:

1. asociativitatea conectivei „ ”: ;

2. dacă se poate aplica o lege a lui De’Morgan pentru conectiva „ ”: ;

3. asociativitatea conectivei „ ”: ;

4. dacă se poate aplica o lege a lui De’Morgan pentru conectiva „ ”:

;

5. dacă are loc proprietatea de absorbţie: ;

6. distributivitatea conectivei „ ” faţă de conectiva „ ”:;

7. distributivitatea conectivei „ ” faţă de conectiva „ ”:

;

8. dacă are loc proprietatea de absorbţie: .

Problema 9.1.2.Utilizând metoda tabelelor de adevăr decideţi tipul (consistentă, inconsistentă, tautologie, contingentă) formulei A:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .Dacă formula A este contingentă, scrieţi toate modelele lui A, sau anti-modelele sale, dacă sunt mai puţine decât modelele.

Problema 9.1.3.Demonstraţi că au loc următoarele relaţii de consecinţă logică:

1. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

folosind metoda tabelelor de adevăr.

Problema 9.1.4.Demonstraţi că formulele următoare sunt tautologii utilizând metoda tabelelor de adevăr.

1. legea permutării premiselor: ;

2. semidistributivitatea la stânga a conectivei „ ” faţă de „ ”:

;


;

4. regula silogismului: ;


;

6. legea separării premiselor: ;

7. legea reunirii premiselor: ;

8. teorema de tăiere: .

Problema 9.1.5.Demonstraţi că mulţimile următoare sunt mulţimi adecvate de conective, adică toate celelalte conective propoziţionale pot fi exprimate folosind elementele unei astfel de mulţimi (vezi subcapitolul 1.3, definirea conectivelor).1. { , }; 2. { , }; 3. {, }; 4. {};5. {}; 6. {, }; 7. {, }; 8. {, };

Problema 9.1.6.Aduceţi la FNC (forma normală conjunctivă) şi FND (forma normală disjunctivă):1. legea separării premiselor: ;2. semidistributivitatea la stânga a disjuncţiei faţă de implicaţie:

;

3. legea permutării premiselor: ;4. semidistributivitatea la stânga a implicaţiei faţă de conjuncţie:

;

5. regula silogismului: ;

16. axioma a doua a calculului propoziţional: ;

17. teorema de tăiere: ;

18. legea reunirii premiselor: .

Folosind una din aceste forme normale, demonstraţi că această lege sau proprietate este o formulă validă în calculul propoziţional.

Problema 9.1.7.Utilizând forma normală adecvată (FNC sau FND) demonstraţi:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.8.Utilizând forma normală adecvată scrieţi toate modelele formulelor:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.9.Demonstraţi că următoarele formule sunt inconsistente folosind forma normală adecvată:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

Problema 9.1.10.Să se demonstreze următoarele proprietăţi ale relaţiei de consecinţă logică, unde R, S FP şi U,V,Z FP.1. monotonia: dacă R |=U şi R S atunci S |=U;2. eliminarea: dacă S |=Vi, iI şi S{Vi|iI }|= U atunci S |=U;3. tranzitivitatea: dacă S |=U şi {U}|=V atunci S |=V;4. conjuncţia în concluzii (“şi” la dreapta):

dacă S |= U şi S |= V atunci S |= UV;5. disjuncţia în premise (“sau” la stânga):

dacă S{U} |= Z şi S{V} |= Z atunci S{UV}|=Z;6. demonstraţia pe cazuri:

dacă S{U} |= V şi S{U } |= V atunci S |= V.

Problema 9.1.11. Folosind definiţia deducţiei să se demonstreze că au loc deducţiile:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.12.Folosind teorema de deducţie şi inversa sa demonstraţi:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.13.Folosind teorema de deducţie şi inversa sa demonstraţi:



;



;

5. a doua axiomă a logicii propoziţionale: ;



;

8. .

Problema 9.1.14. Folosind metoda tabelelor semantice decideţi tipul formulei A. Dacă A este consistentă, scrieţi toate modelele sale: 1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.15.Demonstraţi că formula A este tautologie folosind metoda tabelelor semantice:



3. distributivitatea la stânga a conectivei „ ” faţă de „ ”:

;



6. ;

7. distributivitatea la stânga a conectivei „ ” faţă de „ ”: ;

8. .

Problema 9.1.16.Folosind metoda tabelelor semantice demonstraţi că au loc relaţiile de consecinţă logică:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.17.Folosind calculul secvenţelor verificaţi dacă secvenţele următoare sunt adevărate:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.18.Utilizând calculul secvenţelor verificaţi validitatea formulei A:



3. legea reunirii şi a separării premiselor: ;


;




8. axioma A3 a calculului propoziţional: .

Problema 9.1.19. Folosind calculul secvenţelor verificaţi dacă au loc relaţiile:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.20. Demonstraţi nevaliditatea formulelor următoare folosind calculul anti-secvenţelor. Furnizaţi un anti-model al formulei.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.21. Utilizând calculul anti-secvenţelor arătaţi că nu au loc deducţiile următoare. Furnizaţi un anti-model al deducţiei.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.22.Folosind rezoluţia generală demonstraţi că formulele următoare sunt tautologii:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.23.Demonstraţi inconsistenţa următoarelor mulţimi de clauze folosind rezoluţia blocării. Alegeţi două indexări diferite pentru literalii din clauze.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.24.Construiţi o respingere liniară din mulţimea de clauze S. Există respingeri input şi unit din S?

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.25.Utilizând strategia mulţimii suport demonstraţi că au loc următoarele deducţii:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Problema 9.1.26.

Demonstraţi legea silogismului: utilizând:1. o metodă sintactică; 2. o metodă semantică;3. o metodă directă; 4. o metodă prin respingere;5. o metodă semantică şi directă; 6. o metodă sintactică şi directă;7. o metodă semantică şi prin respingere;8. o metodă sintactică şi prin respingere.

Probleme Logica Propozitii Rom

Documents

Transcript of Probleme Logica Propozitii Rom