Logica propozițională

Logica propozițională (sau enunțiativă ) este un limbaj formal cu o structură sintactică simplă, bazată fundamental pe propoziții elementare (atomi) și pe conectivități logice de tip funcțional adevărat, care returnează valoarea de adevăr a unei propoziții bazată pe valoarea de adevăr conectată. clauze (cunoscute de obicei ca ȘI, SAU, NU ...). Semantica logicii propoziționale definește semnificația simbolurilor și orice propoziție care respectă regulile sintactice ale limbajului, pe baza valorilor de adevăr asociate cu atomii. Având în vedere o interpretare (sau model) a unei propoziții (în general a unui set de propoziții), adică o asociere între propoziții elementare și realități reprezentate, putem genera un set infinit de propoziții cu sens definit asupra acelei realități. Fiecare propoziție se referă, așadar, la unul sau mai multe obiecte ale realității reprezentate (și abstracte, desigur) și vă permite să descrieți sau să raționați despre acel obiect, folosind doar cele două valori „Adevărat” și „Fals”.

Sintaxă

Definiția structurii propoziției (sau sintaxei) logicii propoziționale se bazează pe două componente:

un alfabet de simboluri
un set de secvențe de simboluri (un limbaj ) definit de o gramatică generativă

Alfabet

Alfabetul logicii propoziționale constă din:

Un set numeros de simboluri de propunere: p , q , r , ...
Simbolurile conectivităților logice : ¬ (NU), $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ (ȘI), $\vee$ ${\ displaystyle \ vee}$ $\ vee$ (SAU), → (implicație), ↔ (dublă implicație)
Parantezele: (,) (sunt menite să clarifice limbajul și să evite ambiguitatea)

Formule bine formate

Expresiile „sintactic corecte” ale logicii propoziționale (cele care ar trebui să reprezinte propoziții cu semnificație într-un mod lipsit de ambiguitate) se numesc f ormule b en f ormate, pe scurt fbf (adesea în literatură găsim și wff , din engleza „formule bine formate” ") și sunt definite utilizând următoarea definiție recursivă :

un simbol de propunere este un wff
dacă A este un wff, așa este și ¬ A
dacă A și B sunt wffs, atunci sunt și ele ( A $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ B ), ( A $\vee$ ${\ displaystyle \ vee}$ $\ vee$ B ), ( A → B ) și ( A ↔ B )
nimic altceva nu este un wff

Exemple de formule bine formate sunt :

p (din regula 1)
¬ p (din regula 2 aplicată la wff-ul anterior)
( pag $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ ¬ p ) (din regula 3 aplicată celor două WFF-uri anterioare)
(( pag $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ ¬ p ) $\vee$ ${\ displaystyle \ vee}$ $\ vee$ ¬ p ) (din regula 3 aplicată celor două WFF-uri anterioare)

Regulile de mai sus definesc limbajul logicii propoziționale printr-o gramatică generativă .

Gramatica logicii propoziționale scrise în BNF este următoarea:

f: = L | NU f | (f1 ȘI f2) | (f1 SAU f2) | (f1 -> f2) | (f1 <-> f2)

Semantică

Formulele logicii propoziționale pot fi asociate cu valorile adevărului prin intermediul unei funcții de evaluare :

O funcție de evaluare se numește o funcție care merge de la mulțimea L a formulelor bine formate din mulțimea { V , F } (adevărat, fals)

v : L → { V , F }

astfel încât pentru fiecare pereche de wffs x și y să se îndeplinească următoarele condiții:

v (¬ x ) = V dacă v ( x ) = F

v (¬ x ) = F dacă v ( x ) = V

v ( x

\wedge

{\ displaystyle \ wedge}

\ wedge

y ) = V dacă și numai dacă v ( x ) = V și v ( y ) = V

v ( x

\vee

{\ displaystyle \ vee}

\ vee

y ) = V dacă și numai dacă v ( x ) = V sau v ( y ) = V

v ( x → y ) = V dacă și numai dacă v ( x ) = F sau v ( y ) = V

v ( x ↔ y ) = V dacă și numai dacă v ( x ) = v ( y )

Aceste condiții reflectă semnificația care trebuie atribuită simbolurilor asociate conectivităților logice și pot fi rezumate prin intermediul următorului tabel de adevăr :

$P.$ ${\ displaystyle P}$ $P.$	$Î$ ${\ displaystyle Q}$ $Î$	$\neg$ ${\ displaystyle \ neg}$ $\ neg$ $Î$ ${\ displaystyle Q}$ $Î$	$P.$ ${\ displaystyle P}$ $P.$ $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ $Î$ ${\ displaystyle Q}$ $Î$	$P.$ ${\ displaystyle P}$ $P.$ $\vee$ ${\ displaystyle \ vee}$ $\ vee$ $Î$ ${\ displaystyle Q}$ $Î$	$P.$ ${\ displaystyle P}$ $P.$ ↔ $Î$ ${\ displaystyle Q}$ $Î$	$P.$ ${\ displaystyle P}$ $P.$ → $Î$ ${\ displaystyle Q}$ $Î$
F.	F.	V.	F.	F.	V.	V.
F.	V.	F.	F.	V.	F.	V.
V.	F.	V.	F.	V.	F.	F.
V.	V.	F.	V.	V.	V.	V.

Se arată că o evaluare este identificată în mod unic prin valorile pe care și le asumă asupra simbolurilor propozițiilor: valorile formulelor mai complexe în care apar simbolurile operatorilor logici pot fi deduse pornind de la condițiile stabilite mai sus care definesc o evaluare.

Satisfacție, tautologii și contradicții

Următoarele definiții sunt importante:

Se spune o formulă A bine formată

satisfăcător dacă există o evaluare v astfel încât v ( A ) = V ,
contradicție dacă nu este satisfăcătoare,
tautologie dacă pentru fiecare evaluare v avem v ( A ) = V ,

Un exemplu banal de formulă satisfăcătoare este p , un exemplu de formulă contradictorie este ( p $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ ¬ p ), un exemplu de tautologie este ( p $\vee$ ${\ displaystyle \ vee}$ $\ vee$ ¬ p ).

Problema stabilirii dacă o formulă este satisfăcătoare - cunoscută și sub numele de problema de satisfacție booleană - este o problemă decisivă : poate fi rezolvată luând în considerare toate combinațiile posibile de evaluări pe simboluri propoziționale și calculând valoarea de adevăr corespunzătoare a formulei compuse prin exploatarea proprietățile funcției de evaluare. Teorema Cook-Levin afirmă că această problemă aparține clasei de probleme NP-complete .

Definiția satisfacției poate fi extinsă la seturi (posibil infinite) de formule bine formate:

Se spune că un set de wffs S este satisfăcător dacă există o evaluare v care atribuie valoarea V tuturor formulelor lui S.

Teorema compactității stabilește că un set de wffs S este satisfăcător dacă și numai dacă fiecare dintre subsetul său finit este satisfăcător.

Cu alți termeni este posibil să se dea următoarele definiții. O formulă A bine formată este:

satisfăcător dacă există o interpretare I a lui A în care A este adevărat; în acest caz I se numește modelul lui A.

falsificabil dacă există o interpretare I astfel încât A este falsă; I se numește contramodelul lui A.

valabil dacă A este adevărat în orice interpretare.

Bibliografie

Dirk van Dalen, Logică propozițională , în Logică și structură , Berlin, Springer, 2013, ISBN 978-3-540-20879-2 .
Sergio Galvan, Logica predicatelor , EDUCatt, Milano, 2004.

Elemente conexe

linkuri externe

Logică propozițională , în Dicționar de filosofie , Institutul Enciclopediei Italiene , 2009.
( EN ) Logică propozițională / Logică propozițională (altă versiune) , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Controlul autorității	GND ( DE ) 4136098-9

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică