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ę – pJeden 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 → qKpq 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)
...
Goll_