Proposisjonell logikk

Den proposisjonelle (eller enunciative ) logikken er et formelt språk med en enkel syntaktisk struktur , grunnleggende basert på elementære proposisjoner (atomer) og på logiske forbindelser av en sann-funksjonell type, som returnerer sannhetsverdien til en proposisjon basert på sannhetsverdien relatert. klausuler (vanligvis kjent som AND, OR, NOT ...). Semantikken _av proposisjonell logikk definerer betydningen av symboler og enhver proposisjon som respekterer språkets syntaktiske regler, basert på sannhetsverdiene assosiert med atomer. Gitt en tolkning (eller modell) av en proposisjon (generelt av et sett av proposisjoner), det vil si en assosiasjon mellom elementære proposisjoner og representerte realiteter, kan vi generere et uendelig sett med proposisjoner med definert mening angående den virkeligheten. Hver proposisjon refererer derfor til ett eller flere objekter i den representerte virkeligheten (også abstrakt, selvfølgelig) og lar deg beskrive eller resonnere om det objektet, ved å bruke bare de to verdiene "True" og "False".

Syntaks

Definisjonen av setningsstrukturen (eller syntaksen) av proposisjonell logikk er basert på to komponenter:

et alfabet av symboler
et sett med sekvenser av symboler (et språk ) definert av en generativ grammatikk

Alfabet

Alfabetet til proposisjonell logikk består av:

Et tellbart sett med forslagssymboler: p , q , r , ...
Symbolene for de logiske forbindelsene : (IKKE), (OG), (ELLER), (implikasjon), (dobbel implikasjon) $\ neg$ $\ kile$ $\vee$ ${\ displaystyle \ implies}$ ${\ displaystyle \ iff}$
Klammerne: (,) (er mest ment for å gjøre språket klarere og unngå tvetydighet)

Velformede formler

De "syntaktisk korrekte" uttrykkene for proposisjonell logikk (de som skal representere setninger med mening på en entydig måte) kalles f ormule b en f ormate, kort fbf (ofte i litteraturen finner vi også wff , fra de engelske "well-formed formulas" "), og er definert ved hjelp av følgende rekursive definisjon :

et forslagssymbol er en wff
hvis A er en wff er det også ¬ A
hvis A og B er wffs, så er det ( A B ), ( A B ), ( A → B ) og ( A ↔ B ) $\ kile$ $\vee$
ingenting annet er en wff

Eksempler på velformede formler er :

p (fra regel 1)
¬ p (fra regel 2 brukt på forrige wff)
( p ¬ p ) (fra regel 3 brukt på de to forrige wffene) $\ kile$
(( p ¬ p ) ¬ p ) (fra regel 3 brukt på de to forrige wffene) $\ kile$ $\vee$

Reglene ovenfor definerer språket for proposisjonell logikk gjennom en generativ grammatikk .

Grammatikken for proposisjonell logikk skrevet i BNF er som følger:

f: = L | IKKE f | (f1 OG f2) | (f1 ELLER f2) | (f1 -> f2) | (f1 <-> f2)

Semantikk

Formlene for proposisjonell logikk kan assosieres med sannhetsverdier ved hjelp av en evalueringsfunksjon :

En evalueringsfunksjon er en funksjon som går fra settet L av velformede formler i settet { V , F } (sant, usant)

v : L → { V , F }

slik at for hvert par wffs x og y gjelder følgende betingelser:

v (¬ x ) = V hvis v ( x ) = F v (¬ x ) = F hvis v ( x ) = V v ( x y ) = V hvis og bare hvis v ( x ) = V og v ( y ) = V

\ kile

v ( x y ) = V hvis og bare hvis v ( x ) = V eller v ( y ) = V

\vee

v ( x → y ) = V hvis og bare hvis v ( x ) = F eller v ( y ) = V v ( x ↔ y ) = V hvis og bare hvis v ( x ) = v ( y )

Disse forholdene gjenspeiler betydningen som skal tilskrives symbolene knyttet til de logiske forbindelsene og kan oppsummeres ved hjelp av følgende sannhetstabell :

$P.$	$Q$	$\ neg$ $Q$	$P.$ $\ kile$ $Q$	$P.$ $\vee$ $Q$	$P.$ ↔ $Q$	$P.$ → $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.

Det er vist at en evaluering er entydig identifisert av verdiene den antar på symbolene til proposisjoner: verdiene på de mer komplekse formlene der symboler for logiske operatorer vises, kan utledes fra betingelsene ovenfor som definerer en evaluering .

Tilfredsstillelse, tautologier og motsetninger

Følgende definisjoner er viktige:

En velformet formel A sies

tilfredsstillende hvis det er en evaluering v slik at v ( A ) = V ,
selvmotsigelse hvis den ikke er tilfredsstillende,
tautologi hvis vi for hver evaluering v har v ( A ) = V ,

Et trivielt eksempel på en tilfredsstillende formel er p , et eksempel på en motstridende formel er ( p ¬ p ), et eksempel på tautologi er ( p ¬ p ). $\ kile$ $\vee$

Problemet med å fastslå om en formel er tilfredsstillende - også kjent som det boolske tilfredshetsproblemet - er et problem som kan avgjøres : det kan løses ved å vurdere alle mulige kombinasjoner av evalueringer på proposisjonelle symboler og beregne den tilsvarende sannhetsverdien til den sammensatte formelen ved å utnytte egenskapene til evalueringsfunksjonen. Cook-Levin-teoremet sier at dette problemet tilhører klassen av NP-komplette problemer .

Definisjonen av tilfredsstillelse kan utvides til (muligens uendelige) sett med velformede formler:

Et sett med wffs S sies å være tilfredsstillende hvis det er en evaluering v som tildeler verdi V til alle formlene til S.

Kompaktitetsteoremet fastslår at et sett med wffs S er tilfredsstillbar hvis og bare hvis hver av dens endelige delmengde er tilfredsstilt.

Med andre termer er det mulig å gi følgende definisjoner. En velformet formel A er:

tilfredsstillende hvis det eksisterer en tolkning I av A der A er sann; i dette tilfellet kalles jeg modell av A.

falsifiserbar hvis det er en tolkning I slik at A er falsk; Jeg kalles motmodellen til A.

gyldig hvis A er sann i hver tolkning.

Bibliografi

Dirk van Dalen, Propositional Logic , in Logic and Structure , Berlin, Springer, 2013, ISBN 978-3-540-20879-2 .
Sergio Galvan, Logic of predicates , EDUCatt, Milano, 2004.

Relaterte elementer

Eksterne lenker

proposisjonell, kalkulus , i Dictionary of Philosophy , Institute of the Italian Encyclopedia , 2009.

( EN ) Proposisjonell logikk / Proposisjonell logikk (annen versjon) , i Encyclopedia Britannica , Encyclopædia Britannica, Inc.