Sciaga z logiki

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

(pq)(~q~p) – prawo transpozycji

(p ▲q r) (p(qr)) – prawo eks/importacji

Prawa łączności:

((p ▲q) ▲r) (p ▲(q ▲ r)

((p ▼q) ▼r) (p ▼(q ▼r))

((p)r) (p (qr))

Prawa przemienności:

(p ▲q) (q ▲p) ; (p ▼q) (q ▼p)

(pq) (qp)

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)

(pq) (pq) ▲(qp)

(pq) (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 $\frac{A1,An}{B}$ 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: (pq i qr) --> pr]; odrywania (modus ponens): (p i pq)--> q]; odrzucania (modus tollens): (pq i ~q)--> ~p]; dylematu: (p▼q i pr i qr)--> 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: (pq i qp)--> pq]; 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 AB 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 (AB); 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 (AB) (/\x A /\x B); ekstensjonalności: T7 /\x (AB) (/\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: Jeżeli A1,An T(lpr) B, przy czym reguła generalizacji nie jest stosowana do zmiennych wolnych w A, to A1,An T(lpr) A-->B oraz w nowym dowodzie reguła generalizacji jest stosowana do tych samych zmiennych co w poprzednim dowodzie. ARYTMETYKA PEANO (teoria pierwszego rzędu): język: ^2, +^2, *^2, S^1,0; s-symbol następnika s(n)=n+1; aksjomaty arytmetyczne: R1 x=x zwrotność; R2 x=y -->y=x symetria; R3 x=y --> (y=z-->x=z) przechodniość; R4 x=y -->S(x)=S(y); x1=y1 i x2=y2 --> x1+x2=y1+y2; x1=y1 i x2=y2 --> x1*x2=y1*y2; aksjomaty pozalogiczne teorii P: aksjomaty następnika: P1 ~S(x)=0; P2 S(x)=S(y)-->x=y; aksjomaty dodawania: P3 x+0=x; P4 x+S(y)=S(x+y); aksjomaty mnożenia P5 x*0=0; P6 x*s(y)=x*y+x; aksjomaty indukcji matematycznej: P7 A[x/0] i /\x(A-->A[x/S(x)])-->/\x A; A(0) i /\x (A(x)-->A(S(x))-->/\x A(x); n z kreską=S(S(S(0))) n razy; 0=0; 1=S(0); 2=S(S(0)); TEORIA MNOGOŚCI: pojęcia pierwotne: zbiór X Y, należenie aeX, równość. Antynomia Russella 1901: zbiór nie jest swoim elementem, zbiór A nie należy do zbioru A; Tworzymy zbiór R={X: Xe/X}. /\x(YeR<-->Ye/Y), Y/R, (ReR)<-->(Re/R) – sprzeczność; Aksjomaty Zermela (istnienia zbiorów 1908): a. ekstensjonalności (jeżeli 2 zbiory posiadają dokładnie takie same elementy to są one równe): /\z(zeX <-->zeY) --> x=y; {x: xeR i x>0}={xeR i x^3>0}; a. zbioru pustego (istnieje zbiór, który nie ma żadnych elementów): \/x /\y ye/X; a. inkluzji (zawieranie się zbiorów): AcB – A zawiera się w B (A jest podzbiorem B) <--> (xeA -->xeB); A zawiera się w B wtw gdy każdy element A jest elementem B. Własności inkluzji: AcA (zwrotność), AcB i BcA -->A=B (antysymetria), AcB i BcC --> AcC (przechodniość), /\A o/cA; aksjomat pary: dla wszelkich przedmiotów a i b istnieje zbiór, którego jedynymi elementami są a i b: /\a /\b \/x \/y (yeX <-->y=a lub y=b); /\y(ye{a,b} <--> y=a lub y=b); Zbiór {a,b} nazywamy parą nieuporządkowaną elementów a i b; Wartość nie zależy od kolejności argumentów; aksjomat sumy: Dla wszelkich zbiorów A i B istnieje zbiór, którego elementami są wszystkie elementy zbioru A i wszystkie elementy zbioru B: /\A /\B \/x \/y (yeX <->yeA lub yeB); AuB={x: xeA lub xeB}; aksjomat zbioru potęgowego: Dla każdego zbioru A istnieje zbiór wszystkich podzbiorów zbioru A: /\A \/x \/y (YeX<->YcA); P(A)={Y:YcA} – zbiór potęgowy zbioru A, 2^A; yeP(A)<-->YcA; Jeżeli zbiór A ma n elementów to zbiór P(A) ma 2^n elementów; P(o/)={o/}, P({a,b})={o/,{a},{b},{a,b}}; aksjomat wyróżniania: dla każdego zbioru A istnieje zbiór wszystkich elementów zbioru A, które spełniają warunek W(x); /\A \/x \/y (YeX<-> yeA i w(x)); {x: xeA i W(x)}; Nie istnieje zbiór wszystkich zbiorów; klasa {x: W(x)} – każdy zbiór jest klasą ale nie każda klasa jest zbiorem; ALGEBRA ZBIORÓW: suma AuB={x: xeA lub xeB}; iloczyn AnB={x: xeA i xeB}; różnica A\B={x: xeA i xe/B}; różnica symetryczna: A-:-B=(A\B)u(B\A); prawa algebry zbiorów: przemienności: AuB=BuA; AnB=BnA; de Morgana: A\(BuC)=(A\B)n(A\C); A\(BnC)=(A\B)u(A\C); (A\B)\C=A\(BuC); A\(B\C)=(A\B)u(AnC); (AuB)\C=(A\C)u(B\C); prawa dla u i n w związku z c: AcAuB; BcAuB; AcC i BcC -->(AuB)cC; prawo monotoniczności: A1cA2 i B1cB2 -->A1uB1 c A2uB2 i A1nB1 c A2nB2; działania dopełnienia: U- zbiór ustalony (uniwersum); A’=U\A; A’={xeU: xe/A}; A’ – dopełnienie zbioru A (do uniwersum); o/’=U; U’=o/; A’’=A; (AuB)’=A’nB’; (AnB)’=A’uB’; AcB-->B’cA’; Aksjomaty algebry BOOLE’A: B1 AuB=BuA; B1’ AnB=BnA; B2 (AuB)uC=Au(BuC); B2’ (AnB)nC=An(BnC); B3 An(BuC)=(AnB)u(AnC); B3’ Au(BnC)=(AuB)n(AuC); B4 Auo/=A; B4’ AnU=A; B5 AuA’=U; B5’ AnA’=o/; Zdanie W’ nazywamy dualnym do zdania W jeżeli powstaje ze zdania W poprzez konsekwentne zastąpienie wszystkich sum zbiorów poprzez iloczyny (i odwrotnie) oraz o/ przez uniwersum (i odwrotnie). Zasada dualności: jeżeli W jest twierdzeniem wyprowadzalnym z aksjomatów Boole’a to zdanie dualne do W (W’) też jest takim twierdzeniem. prawo idempotentności dla U: 1) AuA=A; 2) AnA=A; 3) AuU=U; 4) Ano/=o/; 5 i 6 – prawa pochłaniania; 5) Au(AnB)=A; 6) An(AuB)=A; AuB=B<-->AnB=A; AcB i BcA --> A=B; różnica: A\B=AnB’; (AuB)\C=(A\C)u(B\C); Para uporządkowana: (x,y)={{x},{x,y}}; (x,y) para uporządkowana; x – poprzednik, y – następnik; Pary uporządkowane są równe wtw gdy ich poprzedniki i następniki są równe (lemat o parach up); (a,b)=(c,d)<-> a=c i b=d; iloczyn (produkt) kartezjański: AxB={(x,y): xeA i yeB)}; AxB - iloczyn kartezjański zbiorów A i B; Na ogół AxB=/BxA; Jeżeli A ma n elementów i B ma m elementów to AxB ma m*n elementów; prawa: Axo/=o/xA=o/; (AuB)xC=(AxC)u(BxC); (AnB)xC=(AxC)n(BxC); (A\B)xC=(AxC)\(BxC); Ax(BuC)=(AxB)u(AxC); Ax(BnC)=(AxB)n(AxC); Ax(B\C)=(AxB)\(AxC); potęga kartezjańska: A^n+1=AnxA; An=Ax...xA (n razy); Relacją w produkcie A1xAn nazywamy dowolny zbiór RcA1xAn. Takie relacje nazywamy relacjami n-argumentowymi. Zwykle są to relacje dwuargumentowe RcAxB zwane relacjami. Relacje jednoargumentowe są to dowolne zbiory. Relacje dwuargumentowe składają się z par uporządkowanych. Dziedzina: DR={xeA: \/yeB (x,y)eR}; przeciwdziedzina: DR*={yeB: \/xeA (x,y)eR}; relacja odwrotna: R^-1={(y,x):(x,y)eR}; DR^-1=DR*; D*R-1=DR; złożenie relacji: SoR={(x,y): \/z ((x,z)eR i (z,y)eS)}; (SoR)^-1=R^-1 o S^-1; (ToS)oR=To(SoR); (RuS)oT=(RoT)u(SoT); To(RuS)=(ToR)u(ToS);

FUNKCJE: Relację R nazywamy funkcją jeżeli spełnia warunek prawostronnej jednoznaczności /\(x,y1,y2) ((x,y1)eR i (x,y2)eR --> y1=y2); Relacja R przyporządkowuje każdemu x conajwyżej jeden y a każdemu xeD – dokładnie jeden y; Mówimy, że f jest funkcją ze zbioru A w zbiór B jeżeli: f jest funkcją, Df=A, D*f c B; f: A-->B jeżeli D*f=B to mówimy, że f jest funkcją ze zbioru A na zbiór B; funkcję nazywamy różnowartościową (wzajemnie jednoznaczną 1-1) jeżeli: /\(x1,x2eDf) (f(x1)=f(x2) --> x1=x2) lub /\(x1,x2eDf) (x1=/x2 --> f(x1)=/f(x2)); /\x1,x2,y ((x1,y)ef i (x2,y)ef -->x1=x1) – warunek lewostronnej jednoznaczności; Funkcje różnowartościowe są to relacje, które spełniają jednocześnie warunek prawostronnej i lewostronnej jednoznaczności; Relację f^(-1) nazywamy relacją odwrotną do funkcji f; Relacja odwrotna do funkcji f jest funkcją wtw gdy f jest funkcją różnowartościową; złożenie funkcji: /\(xeD(gof) (gof)(x)=g(f(x)); f: A-->(1-1)B iniekcja; f:A-->(na)B suriekcja; f: A-->(na 1-1)B bijekcja; Jeżeli f i g są funkcjami to gof też jest funkcją; D(gof)c Df; D*(gof) c D*g; Jeżeli f i g są funkcjami różnowartościowymi to gof jest też funkcją różnowartościową. Jeżeli f: A-->B i g: B-->C to gof: A-->C; D(gof)c A; D*(gof) c C; Jeżeli f: A-->(

na)B i g: B-->(na)C to (gof):A-->(na)C; złożenie suriekcji jest suriekcja; złożenie bijekcji jest bijekcją; funkcja odwrotna do bijekcji jest bijekcją; OBRAZY I PRZECIWOBRAZY: f:X-->Y; dla AcX: f[A]={y: \/x(xeA i f(x)=y)} – obraz zbioru A dany przez funkcję F; dla BcY: f^-1[B]={xeX: f(x)eB} – przeciwobraz zbioru B dany przez funkcję f; f=x^2 i A=-1<x<-1; f[A]=0<x<1; f^-1[A]=-1<x<1=A; prawa: f[A1uA2]=f[A1]uf[A2]; f^-1[A1uA2]=f^-1[A1]uf^-1[A2]; f[A1nA2]=f[A1]nf[A2]; f^-1[A1nA2]=f^-1[A1]nf^-1[A2]; f^-1[B’]=(f^-1[B])’; Relację RcA^2 nazywamy relacją na zbiorze A; (x,y)eR<--> xRy – x jest w relacji R z y; Własności złożenia relacji: (RoS)oT=Ro(SoT); (RoS)^-1=S^-1 o R^-1; xRoSy <-> \/z(xSz i zRy); Własności relacji: zwrotność /\(xeA) xRx; symetryczność /\(x,yeA) (xRy --> yRx); przechodniosc /\(x,y,z) (xRy i yRz) --> xRz; słaba antysymetryczność /\(x,yeA) xRy i yRx --> x=y; przeciwzwrotność /\(xeA) ~xRx; przeciwsym. /\(x,y) (xRy --> ~yRx); spójność /\(x,y) xRy lub yRx; ostra spójność: /\(x,yeA) xRy lub yRx lub y=x; Relacje równoważności: Relację RcA^2 nazywamy relacją równoważności na zbiorze A jeżeli jest zwrotna, symetryczna i przechodnia. xRy<-->|x|=|y|; Klasa abstrakcji: R – relacja równoważności na zbiorze A. Dla xeA zbiór [x]R = {y:xRy} nazywamy klasą abstrakcji relacji R wyznaczoną przez element x; |x|=|y|, ogólnie dla x=0 [0]R={0}, [x]R={-x,x}; własności: 1 /\xeA xe[x]R; 2 /\x,yeA (xRy-->[x]R=[y]R); 3 /\x,yeA (~(xRy) -->[x]R i [y]R = o/); Rodzinę wszystkich klas abstrakcji relacji równoważności R na zbiorze A oznaczamy symbolem A/R i nazywamy zbiorem ilorazowym zb. A wyznaczonym przez relację R; A/R={[x]R: xeA}; Rodzinę niepustych podzbiorów zb. A nazywamy podziałem zbioru A, jeżeli każdy element zbioru A należy do dokładnie jednego zbioru tej rodziny; Zasada abstrakcji (tw. o relacjach równoważności): Jeżeli R jest relacją równoważności na zb. A to zbiór A/R jest podziałem zbioru A. Każdy podział P zbioru A wyznacza relację równoważności na zbiorze A: xRy<-->/\AeP (xeA i yeA); Relacje porządkujące: Relację RcA^2 nazywamy relacją (częściowo) porządkującą, jeżeli jest zwrotna, słabo antysymetryczna i przechodnia; Relację porządkującą i spójną nazywamy relacją liniowo porządkującą; Parę (A,R) taką, że R jest relacją porządkującą nazywamy zbiorem uporządkowanym. Parę (A,R) taką że R jest relacją liniowo porządkującą nazywamy zbiorem liniowo uporządkowanym; (N,<), (Z,<), (R,<); Elementy x i y e A nazywamy elementami porównywalnymi jeżeli xRy lub yRx; Zbiór jest liniowo uporządkowany wtw gdy każde dwa elementy są porównywalne; Niech YcA; el. największy w zb. Y: element aeY jeżeli /\(yeY) yRa; el. najmniejszy: element aeY jeżeli /\(yeY) aRy; el. maksymalny: element aeY jeżeli /\yeY (aRy-->a=y); el. minimalny: element aeY jeżeli /\(yeY) (yRa-->a=y); Jeżeli w zbiorze istnieje element najmniejszy (największy) to jest on jedynym elementem minimalnym (maksymalnym); Element największy (najmniejszy) może być jedynie jeden w danym zbiorze. Ograniczenie górne: Niech (A,R) – częściowy porządek YcA. Element aeA nazywamy ograniczeniem górnym zb. Y jeżeli /\(yeY) yRa; ograniczenie dolne: element aeA nazywamy ograniczeniem dolnym zb. Y jeżeli /\(yeY) aRy; Fakty: element najmniejszy (największy) o ile istnieje, jest tylko jeden. Element największy (najmniejszy) jest maksymalny (minimalny); Elementy minimalne, maksymalne, największe, najmniejsze będziemy nazywać elementami wyróżnionymi; Funkcja fi jest izomorfizmem (podobieństwem) tych częściowych porządków wtw gdy spełnione są: fi jest bijekcją; /\(x,yeA) (xRa y<-->fi(x)Rb fi(y); Jeżeli fi jest izomorfizmem częściowych porządków to fi^-1 też jest izomorfizmem; Złożenie izomorfizmów częściowych porządków też jest izomorfizmem; Izomorfizm częściowych porządków zachowuje i odbija elementy wyróżnione; Obcięcie relacji Ra do zbioru B będziemy oznaczać tym samym symbolem i (B,Ra) też jest zbiorem częściowo uporządkowanym; Zbiór B jest łańcuchem w (A, Ra) wtw gdy /\(x,yeB) (xRa y lub yRa x); Kresy dolne i górne: niech (A, Ra) – częściowy porządek, BcA, a0eA; Element ao jest w (A, Ra) kresem dolnym zbioru B wtw gdy: /\(xeB) a0 Ra x; jeśli deA oraz /\(xeB) dRa x to dRa a0; piszemy wtedy a0=inf(B); Element ao jest w (A, Ra) kresem górnym zbioru B wtw gdy spełnione są: /\(xeb) xRa a0; jeśli deA i /\(xeB) xRa d to a0 Ra d. Piszemy wtedy ao=sup(B); fakt: a=inf D <--> fi(a)=inf fi(D); a=sup(D) <--> fi(a)=sup fi(D); Krata: zbiór (A, Ra) jest kratą wtw gdy dla dowolnych elementów (a,b)eA istnieją inf{a,b} oraz sup{a,b};

Minimalizacja sieci logicznej: zaznaczamy 2^n sąsiadujących pól i redukujemy tą zmienna dla której mamy raz jej negację i raz bez negacji (reszta bez zmian). A=1 – apn, A=0 – kpn (na odwrót) Metoda tablic analitycznych: każda gałąź reprezentuje koniunkcję formuł na niej występujących. Tablica reprezentuje alternatywę formuł reprezentujących gałęzie. Formuła A jest tautologią wtw gdy każda gałąź zawiera formułę i jej negację (gałąź zamknięta)

Funkcja zdaniowa: wyrażenie W(x) w którym występuje zmienna xi które staje się zdaniem prawdziwym lub fałszywym gdy zamiast zmiennej x podstawimy nazwę dowolnego elementu dziedziny D (przestrzeni) nazywamy funkcję zdaniową jednej zmienne x, której zakresem zmienności jest przestrzeń D.

Relacje częściowego porządku. Mówimy, że relacja r w zbiorze X jest relacją częściowego porządku, jeśli jest zwrotna, przechodnia i antysymetryczna. Parę (A, R), gdzie A jest zbiorem, a R relacją częściowo porządkującą na zbiorze A, nazywamy zbiorem częściowo uporządkowanym.Relację R na zbiorze A nazywamy liniowo porządkującą, jeżeli jest: Zwrotna,Przachodnia,Spójna . Parę (A, R), gdzie A jest zbiorem, a R relacją liniowo porządkującą na zbiorze A, nazywamy zbiorem liniowo uporządkowanym.