17.02.2010.doc

Logika formalna

Temat I: Klasyczny rachunek zdań:

Def 1. (Słownik) Następujące znaki tworzą słownik KRZ:

p1, p2, p3... - zmienne zdaniowe

~, /\, v, →, ↔ - spójniki

), ( - nawiasy

Def. 2 (Wyrażenie) Wyrażeniem j. KRZ jest każdy skończony ciąg znaków ze słownika języka KRZ.

Wyrażenia poprawnie zbudowane („sensowne”) języka KRZ nazywamy formułami (zdaniowymi).

Def. 2 (Formuła)

1.     Każda zmienna zdaniowa jest formułą KRZ.

2.     Jeżeli A, B są formułami języka KRZ, to wyrażenia:
~(A), (A)/\(B), (A)v(B)...

3.     Nie ma innych formuł j. KRZ poza zmiennymi zdaniowaymi i takimi formułami, które powstają dzięki zastosowaniu reguły 2.

Notacja:

(1)  Dla uproszczenia, zamiast p1 będziemy pisać po prostu p, zamiast p2 – q.

(2)  Pojedynczej zmiennej nie bierzemy w nawiasy. Nie dodaje się nawiasu, gdy umieszcza się znak negacji przed formułą już poprzedzoną znakiem negacji: tj. zamiast ~(~(A)) pisze się ~~A. Nie dodaje się nowego nawiasu, dodając nowy człon konunkcji (alternatywy) do formuły będącej koniunkcją (alternatywą): tj.

pisze się  (A)/\(B)/\(C) zamiast ((A) /\ (B) /\(C)) itp.

(3)  Spójnik ~ wiąże najsilniej. Spójniki /\ i v wiążą silniej niż spójniki → i ↔

np. zamiast: (~(p) /\ q) → (r\/~(s)) wolno pisać ~p /\ q → r v ~s.

Notacja: For = zbiór wszystkich formuł języka KRZ:

Napis „A e For” będziemy czytać: A jest

Def. 3 (Podformuła). Dowolną część formuły A, która sama jest formułą nazywamy podformułą formuły A. Do podformuł formuły A zaliczamy też samo A.

Przykład: Podformułami formuły p → ~(q /\ ~r) są:

p, q, r, ~r, q /\ ~r... itd.

Graf formuł = Drzewo synktatyczne.

Formuły języka KRZ są schematami zdań jakiegoś języka etnicznego. Każda formuła jest schematem nieskończonej klasy zdań. Aby zbudować schemat zdania:

Jeżeli wypowiedziałeś alternatywę, to o ile jeden jej składnik nie jest fałszywy, to wypowiedziałeś zdanie prawdziwe.

Postępujemy następująco:

·         zdania proste zastępujemy zmiennymi zdaniowymi:

Wypowiedziałeś alternatywę – p
Jeden jej

Dygresja: Nawiasy w zapisie formuł nie są konieczne. Można je w ogóle wyeliminować.

Za J. Łukasiewiczem używa się następujących symboli:

N zamiast ~

C zamiast →

K zamiast /\

A zamiast v

E zamiast ↔

tak więc piszemy:
Np zamiast ~p

Cpq zamiast p → q
Kpq zamiast p /\ q

Apq zamiast p v q

Epq zamiast p ↔ q

Przykłady:

Formule:                                                                      odpowiada

p v ~p                                                                                    ApNp;

~(p /\ ~p)                                                                      NKpNp;

p → (~p → q)                                                                      CpCNpq;

[(p → q) /\ ~q] → ~p                                          CKCpqNqNp

[p /\ (q v r)] ↔ [(p /\ q) v (p /\ r)]                           

Niech 1 i 0 będą wartościami logicznymi oznaczającymi odpowiednio Prawdę i Fałsz.

Def. 4 (Funkcja prawdziwościowa) Pod pojęciem n-argumentowej funckji prawdziwościowej

(n >= 1) rozumiemy funkcję n zmiennych przebiegających zbiór {0,1} i o wartościach należących do zbioru {1,0}

A zatem, funkcje prawdziwościowe przyporządkowują n-wyrazowym ciągom wartości logicznych wartości logiczne. Następujące funkcje prawdziwościowe charakteryzują własności semantyczne spójników: ~, /\, v, → i ↔ .

Funkcja parzystości: 2n = m;

Def. 5.

f~(1) = 0, f~(0) = 1;

f/\(1,1) = 1, f/\ (1,0) = 0, itp.

fv(1,1) = 1,

f →(1,1) = 1,

f ↔ (1,1) = 1,

Procesowi przypisywana zdaniom języka naturalnego wartości logicznych odpowiada pojęcie funkcji wartościowania formuł.

Def. 6 (Funkcja wartościowania). Wartościowaniem w KRZ nazywamy każdą funkcję v ze zbioru formuł języka KRZ w zbiór wartości logicznych {0,1} taką, że dla dowolnych formuł A, B zachodzi:

Jeżeli v(A), v(B), to v(~A), v(A/\B), V(AvB), v(A → B), v(A ↔ B)

              1              1                0                  1                     1                            1                   1

              1              0                0                  0                     1                            1                   0

              0              1                1                  0                     1                            1                   0

              0              0                1                  0                     0                            1                   1

Notacja: v(A) = wartość logiczną formuły A przy wartościowaniu v.

Związek między zdefiniowanymi wyżej funkcjami prawdziwościowymi a funkcją wartościowania jest następujący:

Wniosek 1.

(1)  v(~A) = f~(v(A));

(2)  v(A/\B) = f/\(v(A), v(B));

(3)  v(AvB) = fv(v(A), v(B));

(4)  v(A → B) = f → (v(A), v(B));

(5)  v(A ↔ B) = f ↔ (v(A), v(B));

Wniosek 2.

2.1 Wartość formuły jest jednoznacznie zdeterminowana wartościami jej podformuł.

2.2 Znając wartości podformuł można wyliczyć wartość całej formuły.

2.3 Z punktu widzenia wartościowania formuł wyróżniamy ich 3 rodzaje:
a) formuły, które dla każdego wartościowania przyjmują wartość 1: nazywamy je tautologiami: są to schematy zdań wyłącznie prawdziwych;
b) formuły, które dla każdego wartościowania przyjmują wartość 0: nazywamy je kontrtautologiami: są to schmeaty zdań wyłącznie fałszywych;

c) formuły, które dla pewnych wartościowań przyjmują wartość 1, a dla innych wartość 0.

Aby obliczyć wartość jakiejś formuły A przy danym wartościowaniu, nie trzeba znać wartości wszystkich zmiennych przy tym wartościowaniu. Wystarczy znać wartości logiczne przyporządkowane przez dane wartościowanie zmiennym występującym w analizowanej formule A. Jest tak dlatego, że zachodzi następujące twierdzenie:

Twierdzenie 1. Niech A będzie dowolną formułą, zaś v i v' wartościowaniami takimi, że:

(*) dla dowolnej zmiennej zdaniowej z występującej w A, v(z) = v'(z).

Wówczas: v(A) = v'(A)

...