Logika Stosowana.pdf

(302 KB) Pobierz
AppLogic.dvi
LOGIKASTOSOWANA
Wykład fakultatywny
kierunek: Matematyka,
Semestr letni, 2001–2002
NguyenHungSon,MarcinSzczuka
InstytutMatematykiUW
Warszawa,ul.Banacha2
szczuka@mimuw.edu.pl
Spistreści
1 Rachunekzdań 5
1.1 Językrachunkuzdań . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Semantykadwuwartościowa ................... 6
1.3 Syntaktyka ............................ 8
1.4 Twierdzenieopełności...................... 9
1.5 Twierdzenieozwartości ..................... 11
2 LogikaModalna 13
2.1 Wstęp............................... 13
2.2 Językilogikimodalnej...................... 13
2.3 StrukturalnaSemantyka..................... 15
2.3.1 Podstawowarelacjaspełnialności . . . . . . . . . . . . 15
2.3.2 Przykład.......................... 16
2.3.3 Trzyrelacjespełnialności................. 18
2.4 Relacjekonsekwencjisematycznej................ 20
2.5 Podstawowysystemdowodzenia . . . . . . . . . . . . . . . . . 22
2.5.1 Przykład.......................... 23
2.5.2 Innesystemyformalne.................. 23
2.5.3 Poprawnośćsystemudowodzenia ............ 25
2.6 Pełnośćlogikmodalnych..................... 27
2.6.1 Twierdzenieigłówneścieżkidowodu . . . . . . . . . . 27
2.6.2 Konstrukcjamodelukanonicznego . . . . . . . . . . . . 28
2.6.3 Dowódtwierdzenia25(opełnościlogikimodalnej). . . 30
2.7 PełnośćwsensieKripkego.................... 30
2.8 Roztrzygalność.......................... 32
3
4
SPISTREŚCI
3 Zbioryilogikirozmyte 35
3.1 Rachunekzbiorówrozmytych .................. 35
3.1.1 Relacjerozmyte...................... 38
3.2 Logiczneoperatoryrozmyte................... 39
3.3 Logikapossybilistyczna . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Prawdziwościowalogikarozmyta................. 46
Rozdział1
Rachunekzdań
1.1 Językrachunkuzdań
Językrachunkuzdańskładasięznastępującychelementów:
1. Symbole :
•
Nieskończonyzbiórzmiennychzdaniowych VAR =
{
p,q,r,...
}
•
4wyróżnionesymbole:
¬
,
∨
, ( , ).
2. Regułyskładania: Podajemydefinicjęrekurencyjnąpojęcia” popraw-
niezdefiniowanychformułzdaniowych ”lubkrótko formułzdaniowych
•
Zmienne zdaniowe ze zbioru VAR =
{
p,q,r,...
}
są formułami
zdaniowymi.
φ teżjestformułązdaniową
• Jeśli φ i ψ są formułami zdaniowymi, to ( φ ∨ ψ ) jest formułą
zdaniową.
Jeśli φ jestformułązdaniowąto
¬
Zbiórwszystkichformułoznaczamyprzez FORM .Symbole ¬ i ∨ nazywa-
my spójnikamilogicznymi (lub operatoramilogicznymi ).Intuicyjnie,nawiasy
są wprowadzone po to, aby określić kolejność działania, dlatego mogą one
być usunięte z języka. W celu uproszczenia opisów oraz ułatwienia pisania
formuł,wprowadzamydojęzykadodatkowestałe
,
⊥
orazoperatory
∧
,
⇒
,
5
•
6
ROZDZIAŁ1. RACHUNEKZDAŃ
⇔
,któresądefinowanenastępująco:
φ
∧
ψ = def ¬
(
¬
φ
∨¬
ψ )
φ
⇒
ψ = def ¬
φ
∨
ψ
φ
⇔
φ )
= def p ∨¬ p dlapewnejzmiennej p ∈ VAR
⊥
ψ = def (
¬
φ
∨
ψ )
∧
(
¬
ψ
∨
= def p
∧¬
p dlapewnejzmiennej p
∈
VAR
Znaczenia operatorów logicznych i stałych (które mogą być traktowane
jakooperatory0-argumentowe)sąpodanewnastępnymrozdziale.
1.2 Semantykadwuwartościowa
.Utożsamiamy0zwartościąlogiczną FAŁSZ ,
a1– PRAWDA .Wówczasoperatorylogicznesąskojarzonezodpowiednimi
funkcjami na
B
=
{
0 , 1
}
B
.Spójnik
¬
jest skojarzony z funkcją
¬
:
B→B
taką, że
¬
( x )=1
−
x . Dwuczłonowe spójniki logiczne są skojarzone z funkcjami
postaci
∗
:
B×B→B
gdzie
∗
oznaczadowolnyoperatorzezbioru
{∨
,
∧
,
→
,
⇔}
.Funkcjetesąde-
finiowaneprzeznastępnątabelkę(truthtable):
xyx
∨
yx
∧
yx
→
yx
⇔
y
00 0 0 1 1
01 1 0 1 0
10 1 0 0 0
11 1 1 1 1
możnatraktowaćjakspójniki ...lub... , ...i... oraz
jeśli...to... wjęzykunaturalnym.Nazywamyjeodpowiednio: alternatywą ,
koniunkcją , implikacją . Wprowadźmy formalną definicję semantyki formuł
zdaniowych:
Intuicyjnie,
∨
,
∧
,
→
Definicja1. Wartościowaniemnazywamykażdąfunkcję
v : VAR
→B
Rozpatrujemyzbiór
729887809.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin