Wartościowaniem zbioru zmiennych {p1, pn} nazywamy dowolne przyporządkowanie wartości logicznych tym zmiennym. Można określić 2^n wartościowań. Tautologia: formuła A jest prawem (tautologią) KRZ jeżeli dla każdego wartościowania zbioru zmiennych V(A), formuła A jest prawdziwa tzn. A=1. Schemat zdaniowy, który przy każdym wartościowaniu przyjmuje wartość logiczną 1;
p ▼~p – prawo wyłączonego środka
~(p ▲~p) – prawo sprzeczności
~~p óp – prawo podwójnej negacji
(pàq)ó(~qà~p) – prawo transpozycji
(p ▲q àr) ó(pà(qàr)) – prawo eks/importacji
Prawa łączności:
((p ▲q) ▲r) ó(p ▲(q ▲ r)
((p ▼q) ▼r) ó(p ▼(q ▼r))
((pó)ór) ó (pó (qór))
Prawa przemienności:
(p ▲q) ó (q ▲p) ; (p ▼q) ó(q ▼p)
(póq) ó(qóp)
Prawa rozdzielczości:
(p ▲ (q ▼ r) ó ((p ▲ q) ▼ (p ▲ r))
(p ▼ (q ▲ r) ó ((p ▼ q) ▲ (p ▼ r))
Prawa idempotentności:
(p ▲ p) ó p; (p ▼ p) ó p
Prawa de Morgana:
~(p ▲ q) ó (~p ▼~q) ; ~(p ▼ q) ó (~p ▲~q)
Prawa definiowania:
(p à q) ó (~p ▼q)
(póq) ó(pàq) ▲(qàp)
(póq) ó(p ▲q) ▼(~p ▲~q)
p ▲q ó ~(~p ▼~q)
p ▼q ó ~(~p ▲~q)
metody: zero-jedynkowa (tabelka), nie-wprost (zakładamy, że nie jest tautologią lewa=1 prawa=0); Wynikanie logiczne: Schemat B wynika ze schematu A1,An w rachunku zdań, jeżeli formuła A1 i An --> B jest tautologią KRZ. Jeżeli nie istnieje wartościowanie dla którego A1,An przyjmują wartość 1 a B 0, wtedy schemat wnioskowania A1, An --> B jest poprawny; Wnioskowaniem nazywamy dowolny zbiór zdań A1, An, B w którym wyróżniamy zdanie B i nazywamy wnioskiem a zdania A1, An nazywamy przesłankami tego rozumowania; Schemat wnioskowania A1,AnB jest niezawodny (jest logiczną regułą wnioskowania) jeżeli wniosek B wynika logicznie z przesłanek A1, An. Rozumowanie jest dedukcyjne jeżeli jego schemat jest niezawodny. Logiczne reguły wnioskowania: sylogizmu warunkowego: (pàq i qàr) --> pàr]; odrywania (modus ponens): (p i pàq)--> q]; odrzucania (modus tollens): (pàq i ~q)--> ~p]; dylematu: (p▼q i pàr i qàr)--> r]; opuszczania koniunkcji: (p ▲q)-->p lub (p ▲q)-->q]; wprowadzania koniunkcji: (p i q)-->p ▲q]; wprowadzania alternatywy: a-->(a ▼b) lub b-->(a ▼b)]; wprowadzania równoważności: (pàq i qàp)--> póq]; eliminacji alternatywy: (p ▼q i p-->r i q-->r)-->r];
Twierdzenie o podstawianiu: jeżeli A jest tautologią i w A za zmienne zdaniowe podstawimy pewne schematy zdaniowe, to formuła w wyniku też jest tautologią. Jeżeli w poprawnym schemacie wnioskowania podstawimy schematy zdaniowe to też otrzymamy poprawny schemat wnioskowania. Formuły A i B są logicznie równoważne jeżeli dla każdego wartościowania zmiennych występujących w A i B wartości logiczne tych formuł są jednakowe. Formuły A i B są logicznie równoważne wtw gdy formuła AóB jest tautologią KRZ. A<≡>B – A i B są logicznie równoważne. Jeżeli A<≡>B to jeżeli C’ powstaje z C przez zastąpienie niektórych wystąpień formuły A przez B to C<≡>C’. Formuła A jest postaci koniunkcyjnej (alternatywnej) normalnej jeżeli jest postaci A = L1▲▼Ln gdzie L1=Bi1 gdzie Bi1 to zmienna zdaniowa lub jej negacja. Dla każdej formuły A istnieje równoważna logicznie formuła postaci apn i kpn. Aksjomatyczny system rachunku zdań: aksjomaty implikacji: A1 p-->(q-->p); A2 [p-->(q-->r]-->[(p-->q)-->(p-->r)]; aksjomat negacji A3 (~q-->~p)-->(p-->q); aksjomaty koniunkcji A4 p i q -->p; A5 p i q -->q; A6 (p-->q)-->[(p-->r)-->(p-->q i r)]; aksjomaty alternatywy A7 p-->p lub q; A8 q--> p lub q; A9 (p-->r)-->[(q-->r)-->(p lub q -->r)]; aksjomaty równoważności A10 (p<-->q)-->(p-->q); A11 (p<-->q)-->(q-->p); A12 (p-->q)-->[(q-->p)-->(p<-->q)]; Dowodem formalnym systemu nazywamy ciąg formuł, gdzie każda formuła jest aksjomatem systemu lub wnioskiem z przesłanek formuł na mocy jednej z reguł dowodzenia systemu. Ostatnia formuła w ciągu jest formułą dowodzoną. Formuły które mają dowód w systemie – tezy. A1, An t B – B posiada dowód w systemie, A1, An – założenia, B – teza. Jeżeli A1,An t B to taki schemat wnioskowania (A1,An)-->B nazywamy wtórną regułą dowodzenia. Do założeń nie można nic podstawiać.
Logika pierwszego rzędu: zdania, nazwy (pojedyncze przedmioty), wyrażenia relacyjne (w połączeniu z nawami tworzą zdania > =), wyr. funkcyjne (w połączeniu z nazwami tworzą bardziej złożone nazwy +, *). Formy zdaniowe: wyrażenia zawierające zmienne, które stają się zdaniami, jeżeli wszystkie zmienne zastąpimy stałymi odpowiednich kategorii (x<y). Język LPR: zmienne przedmiotowe x,y,z; stałe logiczne -->, i lub; symbole pomocnicze . , ; symbole pozalogiczne, symbole redakcyjne, symbole funkcyjne, stałe przedmiotowe; Termy: termami języka pierwszego rzędu nazywamy wyrażenia zdefiniowane przez warunki: każda zmienna i stała przedmiotowa jest termem, jeżeli f jest symbolem funkcyjnym o arności (liczbie argumentów) równej n oraz wyrażenia t1,tn są termami to f(t1,tn) jest termem. Przykład: f(x,y), g(a,b), f(g(x),h(g)); Formuły atomowe: wyrażenia postaci R(t1,tn) gdzie R jest n-argumentowym symbolem relacyjnym a wyrażenia t1,tn są termami; R(a,b,c), Q(f(x),y,g(z’)), P(f(a,b),g(x,y))’; Formuły: formułami LPR nazywamy wyrażenia wyznaczone przez warunki: każda formuła atomowa jest formułą; jeżeli A i B są formułami to wyrażenia postaci ~A, A i B, A lub B, A to B są formułami; jeżeli A jest formułą a x zmienną przedmiotową to wyrażenia postaci /\xeA, \/xeA też są formułami: R(a,b,c), P(x,y) --> Q(f(a),x), /\x P(x) --> \/y Q(y); Podformuła formuły: każda formuła wchodząca w skład formuły A; formuła: /\y (x<y --> x+1<y+1) podformuły: x<y -->x+1<y+1; x<y; x+1<y+1; Wystąpienie zmiennej w formule A nazywamy związanym jeżeli znajduje się wewnątrz pewnej podformuły A postaci /\x B lub \/x B. Pozostałe wystąpienia x w A nazywamy wolnymi. Zmienną nazywamy wolną w formule A jeżeli A zawiera przynajmniej jedno wolne wystąpienie zmiennej x. Zdaniem nazywamy formułę bez zmiennych wolnych. Mówimy że wystąpiła kolizja przy podstawieniu A[x/t] jeżeli pewne wolne wystąpienie x w A leży wewnątrz podformuły /\y B lub \/y B takiej, że y występuje w t. Interpretacja języka polega na ustaleniu zbioru niepustego zwanego dziedziną oraz nadaniu znaczenia symbolom pozalogicznym języka (symbolom relacyjnym przypisującym relację określoną na dziedzinie o tej samej arności, symbolom funkcyjnym przypisującym działania określone na dziedzinie tej samej arności, stałym przedmiotowym przypisujemy elementy dziedziny). Kwantyfikatory ograniczone: ogólny ▲x:a B ó ▲x (AàB); szczegółowy ▼x:a B ó ▼x (A▲B).
PRAWA LPR: prawem logiki pierwszego rzędu nazywamy formułę która jest prawdziwa dla wszystkich interpretacji danego języka i wszystkich wartości zmiennych wolnych.
rozdzielczości kwantyfikatorów: T1 /\x (A ▲B) ó /\x A ▲/\x B; Niepełne prawa rozdzielczości: T2 /\x A ▼/\x B à /\x(A ▼B); T2’ \/x (A ▲B) à \/x A ▲\/x B; przestawiania kwatyfikatorów: T3 /\x /\y Aó /\y /\x A; Nieepełne prawo przestawiania: T4 \/x /\y A à /\y \/x A; Prawa de Morgana: T5 ~/\x A ó \/x ~A; T5’ ~\/x A ó /\x ~A; rozdzielania kwatyfikatorów przy implikacji: T6 /\x (AàB) à (/\x A à /\x B); ekstensjonalności: T7 /\x (AóB) à (/\x A ó /\x B); zmiany zmiennych związanych: /\xA <--> /\y A[x/y];
Aksjomaty logiczne: wszystkie formuły logiczne prawdziwe na gruncie KRZ. Przyjmujemy te aksjomaty dla wszystkich formuł zmiennych. Zał: nie ma kolizji zmiennych przy podstawianiu. L1 /\x A --> A[x/t]; L1’ A[x/t] --> \/x A; L2 /\x(A-->B)-->(/\x A --> /\x B); L2’ \/x(A-->B)-->(\/x A --> \/x B); Zał: x nie jest wolne w A; L3 A--> /\xA; L3’ \/xA--> A; T(lpr) A – A jest tezą tego systemu, A posiada dowód; A1,An T(lpr) A – A posiada dowód, przy założeniach A1,An; Każda logiczna reguła wnioskowania KRZ jest wtórną regułą systemu LPR. Reguły wtórne: R. generalizacji: A-->/\x A; R. wprowadzania k. ogólnego /\: (A-->B)-->(/\x A --> /\x B); R. wprowadzania k. szczegółowego: (A-->B)-->(\/x A-->\/x B); Reguła dołączania /\: (A--> B)-->(A--> /\x B); Reguła dołączania \/: (A-->B)--> (\/x A-->B); Twierdzenie o dedukcji:...
RezidentRnR