Matematik/Diskret matematik/Logik/Satslogik

Satslogik

Grundläggande satslogiska konnektiv

Inom satslogiken hanterar man (kombinationer av) påståenden eller teser och varje påstående kan vara antingen sant eller falskt. Alltså måste påståendet vara av en typ som kan vara sant eller falskt. Det måste innehålla ett påstående om en egenskap hos detta, t.ex vad nåt är, har , blir, eller gör. Giltiga påståenden är t.ex: 2 x 2 = 4 , Det regnar, Jag sover, 1 + 1 = 73 (ett falskt påstående men fullt giltigt). Däremot är inte 3*7 giltigt då det inte innehåller något påstående om talet. x / 5 = 11 är giltigt men x måste tilldelas att värde för att kunna avgöras om det är sant eller falskt. I stället för att skriva hela satserna brukar man använda A, B, C osv.

negation

För att negera ett påstående så används icke-symbolen ¬ A.

disjunktion

Satsen A eller B kallas disjunktion och betecknas A ∨ B.

konjunktion

Satsen A och B kallas konjunktion och skrivs A ∧ B.

implikation

A leder till B kallas implikation och skrivs A → B.

ekvivalens

Om både A → B och B → A är sanna så kallas det ekvivalens och skrivs A ↔ B. Det är alltså samma sak som A → B ∧ B → A

Med kombinationer av dessa kan man dela upp ett påstående i dess atomära satser. Satsen "Om jag jobbar med lön och inte blir lurad eller rånad så tjänar jag pengar" kan skrivas:

• (jag jobbar ∧ jag får lön ∧ ¬(blir lurad ∨ blir rånad)) → jag tjänar pengar.

Om detta är det enda sättet att tjäna pengar gäller implikationen åt bägge håll och är alltså en ekvivalens

• (jag jobbar ∧ jag får lön ∧ ¬(blir lurad ∨ blir rånad)) ↔ jag tjänar pengar.

Sanningsvärden

Sanningsvärdet av en sammansatt (molekylär) sats bestäms av sanningsvärderna på dom ingående atomära satserna.

För att se möjliga sanningsvärden gör man en sanningsvärdestabell där de ingående atomära sats prövas med alla möjliga kombinationer av sant/falskt.

negationen ¬ A har alltid motsatt sanningsvärde som A, om A är sann så är ¬ A falsk.

Negation ( ¬ )   sann om A är falsk falsk om A är sann   A   B   ¬ A  s s f s f f f s s f f s

Disjunktion ( ∨ )   sann om någon av A och B är sann   A   B   A ∨ B  s s s s f s f s s f f f

Konjunktion ( ∧ )   sann om både A och B är sanna   A   B   A ∧ B  s s s s f f f s f f f f

Implikation ( → )   sann om A & B är sanna eller A är falsk   A   B   A → B  s s s s f f f s s f f s

Ekvivalens ( ↔ )   sann om A & B har lika sanningsvärde   A   B   A ↔ B  s s s s f f f s f f f s

Tautologi

Tautologi
(A → B) ∨ A har alltid samma sanningsvärde
A	B	(A → B) ∨  A
s	s	s    s    s
s	f	f    s    s
f	s	s    s    f
f	f	s    s    f

• En sammansatt sats som alltid är sann sägs vara satslogiskt sann (tautologi).
• En sammansatt sats som alltid är falsk sägs vara satslogiskt falsk (kontradiktorisk).

Satslogisk ekvivalens

Två satser A och B som är satslogiska följder av varandra (A↔B) är satslogiskt ekvivalenta. Dom har samma sanningsvärdestabell. T.ex: ¬(A ∧ B)  <=>  ¬A ∨ ¬B

Satslogisk ekvivalens ( <=> )
Två satser med samma sanningsvärden
A	B	¬  (A ∧ B)  <=>  ¬A ∨ ¬B
s	s	f  s      f f f
s	f	s  f      f s s
f	s	s  f      s s f
f	f	s  f      s s s

Följande satslogiska ekvivaleser är bra att kunna:

Dubbel negation

• ¬¬A<=>A

Kommutativa lagarna

• A∧B<=>B∧A
• A∨B<=>B∨A
• A↔B<=>B↔A

Kommutativa lagarna I   sats 1 & 2 har lika sanningsvärde   A   B   A∧B<=>B∧A  s s s  s  s s f f  f  f f s f  f  f f f f  f  f

Kommutativa lagarna II   sats 1 & 2 har lika sanningsvärde   A   B   A∨B<=>B∨A  s s s  s  s s f s  s  s f s s  s  s f f f  f  f

Kommutativa lagarna III   sats 1 & 2 har lika sanningsvärde   A   B   A↔B<=>B↔A  s s s  s  s s f f  f  f f s f  f  f f f s  s  s

de Morgans lagar

• ¬(A∧B)<=>¬A∨¬B
• ¬(A∨B)<=>¬A∧¬B

Kontraposistion

• A→B<=>¬B→¬A

Associativa lagarna

• A∧(B∧C)<=>(A∧B)∧C
• A∨(B∨C)<=>(A∨B)∨C;

Distrubativa lagarna

• A∧(B∨C)<=>(A∧B)∨(A∧C)
• A∨(B∧C)<=>(A∨B)∧(A∨C)

regler för →

• A→B<=>¬A∨B

regler för ↔

• A↔B<=>(A→B)∧(B→A)