Proposisjonslogikk

Proposisjonslogikk er et formelt system i logikk som studerer proposisjoner og deres sammensetning ved hjelp av logiske forbindelser. En proposisjon er en påstand som enten er sann eller usann. I proposisjonslogikk arbeides det med proposisjonale variabler som ofte betegnes med bokstaver som p, q og r.

En formell uttrykks syntaks består av variablene og logiske forbindelser. De vanligste forbindelsene er negasjon (¬), konjunksjon (∧), disjunksjon (∨), implikasjon (→) og ekvivalens (↔). Sammen setter man parenteser for å angi struktur og fortelle i hvilken rekkefølge operasjonene skal utføres. En gyldig eller veldefinert form innebærer riktig bruk av disse symbolene og konnektivene.

Semantisk tildeles hver variabel en sannhetsverdi gjennom en valens som mapper p, q og r til sann eller usann. Verdien av en sammensatt formel bestemmes deretter av sannhetsreglene: ¬φ er sann hvis φ er usann; φ ∧ ψ er sann hvis både φ og ψ er sanne; φ ∨ ψ er sann hvis minst en av dem er sann; φ → ψ er usann bare hvis φ er sann og ψ er usann; φ ↔ ψ er sann hvis φ og ψ har samme sannhetsverdi. En formel er en tautologi hvis den er sann under alle valenser, og den er satisfierbar hvis den er sann under minst én valens.

Bevismessig brukes regler som modus ponens: fra p og p → q kan man inferere q. Andre regler benyttes i naturlig deduksjon og i Hilbert-systemer. Proposisjonslogikk er decidable og kompletterbar; den er også grunnlaget for normale former som CNF og DNF, som er sentrale i datavitenskapelige metoder som SAT-løsere. Proposisjonslogikk står i kontrast til førsteordenslogikk, som innfører kvantifikatorer og dermed større uttrykkskraft og kompleksitet.