Informatyka studia dzienne - WMI, WMID, UAM, Uniwersytet im. Adama Mickiewicza w Poznaniu

Informatyka studia dzienne - WMI, WMID, UAM, Uniwersytet im. Adama Mickiewicza w Poznaniu

11:R-LOG-1/071126/0

4 responses on "11:R-LOG-1/071126/0" »

11:R-LOG-1/071126/0

4 responses on "11:R-LOG-1/071126/0" »

Dodaj komentarz

Zbiór teorii na kolokwium z logiki (gr. 11) - 26.11.2007

Zbiór teorii na kolokwium z logiki (gr. 11) - 26.11.2007

Podgląd komentarza:

Kalendarz

Kategorie

RSS

Recent Posts

Recent Comments

Meta

Posted by M in Ćwiczenia - gr. 11,... | 11.24.2007 - 21:27

- wersja 2.0
- nie ma jeszcze tego co mieliśmy skserować od drugiej grupy…

______________________________________________________________________

SPÓJNIKI		negacja	koniunkcja	alternatywa	implikacja	równoważność
$p$	$q$	$\neg p$	$p \wedge q$	$p \vee q$	$p \Rightarrow q$	$p \Leftrightarrow q$
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

Notacja Łukasiewicza (notacja polska)		N	K	A	C	E

______________________________________________________________________

Zmienne zdaniowe - zb. zmiennych zd. $Var _{RZ}$

Alfabet języka rachunku zdań:
zmienne zdaniowe, stałe logiczne (spójniki) i nawiasy

Wyrażenie nad alfabetem j. r. zd.
- składa się z co najmniej dwóch symboli alfabetu j. r. zd.

Formuła - zbiór formuł: $For _{RZ}$
- poprawne wyrażenie nad alfabetem j. r. zd.

Podformuła formuły A - sub (A)
dana formuła A i wszystkie formuły z których się ona składa aż do gołych zmiennych zdaniowych

______________________________________________________________________

Zastępowanie zmiennych zdaniowych
- jak się zastępuje zmienne zdaniowe każdy wie

Kłamstwo - niezgodność z tym co uważamy za prawdę

______________________________________________________________________

Spójniki i ich interpretacja logiczna (przykłady):
A oraz B - $A \wedge B$
A o ile B - $B \Rightarrow A$
A a B - $A \wedge B$
A choć B - $A \wedge B$ (i przeciwstawiające)

Funkcje prawdziwościowe w zapisie matematycznym z +, -, *
$f_\neg (A) = 1-f(A)$
$f_\wedge (A,B) = f(A) \cdot f(B)$
$f_\vee (A,B)= f(A)+f(B) -f(A)\cdot f(B)$
$f_\rightarrow (A,B) = 1 - f(A)\cdot(1 - f(B))$
$f_\leftrightarrow (A,B) = 1 -f(A)\cdot (1-f(B)) -(1 - f(A))\cdot f(B) -$

______________________________________________________________________

Wartościowanie
- ciąg wartości logicznych odpowiadających ciągowi zmiennych
- wartościowanie nr. n - rozpisać n binarnie i pierwsze bity to wartościowanie

Tautologia - formuła prawdziwa dla każdego wartościowania
Kontrtautologia - formuła fałszywa dla każdego wartościowania
Formuła spełnialna - istnieje takie wartościowanie, dla którego formuła jest prawdziwa
Nietautologia - istnieje takie wartościowanie, dla którego formuła jest fałszywa

______________________________________________________________________

Sposoby sprawdzania tautologiczności formuł:

tabelkowa (siłowa)
- robimy tabelkę i sprawdzamy prawdziwość formuły dla każdego wartościowania
(skrócona) metoda zero-jedynkowa
- zakładamy, że cała formuła jest fałszywa i zgodnie z tym założeniem wyznaczamy wartości logiczne kolejnych podformuł, aż dojdziemy do sprzeczności, co oznacza, że nie istnieje takie wartościowani, dla którego formuła jest fałszywa
- przydatne szczególnie przy implikacjach
metoda dedukcji analitycznej (drzewko)
- wypisujemy tyko formuły prawdziwe (w razie potrzeby zanegować fałszywą)
- zakładamy, że nasza formuła jest fałszywa (korzeń) i wypisujemy logiczne następstwa tego założenia (rozbijamy formułę aż do zmiennych zdaniowych) - tak rosną gałęzie drzewa; kiedy jakaś gałąź jest wewnętrznie sprzeczna (od korzenia do końca gałęzi), to zaznaczamy na jej końcu X i mówimy, że jest zamknięta; gdy wszystkie gałęzie się zamkną, to niemożliwe jest aby nasza wyjściowa formuła była nieprawdą (zanegowaliśmy ją), więc musi być tautologią

______________________________________________________________________

Równoważność semantyczna formuł A~B
A i B są równoważne semantycznie, gdy dla każdego wartościowania $\vec a$
zachodzi $A[\vec a]=B[\vec a]$

Lemat
$A \sim B$ wgdy $A \leftrightarrow B$

Wynikanie semantyczne X A
- A wynika ze zbioru formuł X

Dowodliwość X A
- formuła A jest dowodliwa w oparciu ozb. aksjomatów i formuły ze zb. X

Teza KRZ A
- formuła A jest dowodliwa w oparciu o sam zbiór aksjomatów

-2 systemy aksjomatyczne są równoważne, gdy ich zbiory tez są takie same

Twierdzenie o pełności dla rachunku zdań
- zb. tez RZ = zb. tautologii

Dowód formuły A w oparciu o zb. formuł X - ciąg formuł, taki że:
- ostatnia jest dowodzoną formułą A
- każda jest albo przesłanką ze zb. X, albo aksjomatem, albo wynika z dwóch wcześniejszych

______________________________________________________________________

Aksjomaty rachunku zdań - każda formuła powstała przez podstawienie do A1 - A12 dowolnych formuł

Aksjomaty implikacji:
(A1.) $p \rightarrow (q \rightarrow p)$ - prawo poprzednika
(A2.) $(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow q) \rightarrow (p \rightarrow r))$ - prawo Fregego
(A3.) $( \neg q \rightarrow \neg p) \rightarrow (p \rightarrow q)$ - prawo transpozycji

Aksjomaty koniunkcji:
(A4.) $p \wedge q \rightarrow p$
(A5.) $p \wedge q \rightarrow q$
(A6.) $(p \rightarrow q) \rightarrow ((p \rightarrow r) \rightarrow (p \rightarrow q \wedge r))$ - prawo mnożenia następników

Aksjomaty alternatywy:
(A7.) $p \rightarrow p \vee q$
(A8.) $q \rightarrow p \vee q$
(A9.) $( p \rightarrow r) \rightarrow ((q \rightarrow r) \rightarrow (p \vee q \rightarrow r))$

Aksjomaty równoważności:
(A10.) $(p \leftrightarrow q) \rightarrow ( p \rightarrow q)$
(A11.) $(p \leftrightarrow q) \rightarrow ( q \rightarrow p )$
(A12.) $( p \rightarrow q) \rightarrow (( q \rightarrow p ) \rightarrow ( p \leftrightarrow q))$

Reguły wtórne w KRZ - sposób przechodzenia od formuł do formuł

Reguła odrywania (Modus Ponens)
$\frac{A, A \rightarrow B}{B}$

Reguła sylogizmu hipotetycznego
$\frac{A \rightarrow B, B\rightarrow C}{A \rightarrow C}$

Reguła komutacji poprzedników
$\frac{A \rightarrow (B \rightarrow C)}{B \rightarrow (A \rightarrow C)}$

Twierdzenie o podstawianiu
Jeżeli dana formuła jest tautologią, to formuła powstała przez zastąpienie jej zmiennych innymi formułami, również jest tautologią

Twierdzenie o dedukcji
X,A B wgdy X A $\rightarrow$ B
- czyli poprzednik dowodzonej formuły można przenieść do przesłanek, co ułatwia zazwyczaj dowodzenie

______________________________________________________________________

System binarny, a system dziesiątkowy

11011001 (II) =
= 1 $\cdot 2^7$ + 1 $\cdot 2^6$ +0 $\cdot 2^5$ + 1 $\cdot 2^4$ + 1 $\cdot 2^3$ + 0 $\cdot 2^2$ + 0 $\cdot 2^1$ +1 $\cdot 2^0$ =
=1 $\cdot$ 128+ 1 $\cdot$ 64+0 $\cdot$ 32+ 1 $\cdot$ 16+ 1 $\cdot$ 8+ 0 $\cdot$ 4+ 0 $\cdot$ 2+1 $\cdot$ 1=
=128+64+16+8+1=217 (X)

Funkcje boole’owskie

Dla
n - argumentów
mamy:
$2^n$ możliwych wartościowań
$2^{(2^n)}$ funkcji wartościujących

$f^{liczba \ argumentow}_{numer \ wartosciowania}$

Przykładowa funkcja wartościująca (jeden wers z tabelki wszystkich funkcji)

Wartościowania n=2 argumentów	11	10	01	00
$f^2_{11}$	1	0	1	1	1011 (II) = 11 (X)

Wybrane funkcje wartościujące

$f_\neg = f^1_1$

$f_\vee = f^2_{14}$

$f_\wedge = f^2_8$

$f_\rightarrow = f^2_{11}$

$f_\leftrightarrow = f^2_9$

$\mathbb{B}$ - zb. wszystkich funkcji boole’owskich

$\mathbb{B}_n$ - zb. wszystkich funkcji boole’owskich n argumentowych

Funkcja podstawowo definiowalna ze zb. funkcji X
- można funkcję przedstawić jako wyrażenie zbudowane z funkcji ze zb. X i zmiennych

Zupełny zbiór funkcji X
- każdą funkcję boole’owską można przedstawić jako wyrażenie zbudowane z funkcji z tego zupełnego zbioru funkcji X
- zbiór składający się z funkcji koniunkcji/alternatywy oraz negacji jest zupełny

______________________________________________________________________

Podane definicje nie mają charakteru formalnego, a jedynie intuicyjny, bardziej przydatny (mam nadzieję) do nauki. Zachęcam do sprawdzenia wszystkiego w swoich notatkach, tudzież w innych dziełach pisanych.

No i musicie jeszcze nabrać w tym wszystkim praktyki…

Życzę bardzo dużo szczęścia
M

______________________________________________________________________

Błędy, pytania, uwagi zgłaszaj na
m@wmid.amu.edu.pl
(w temacie podaj sygnaturę strony)

Wydrukuj ten post

kachaj7
Posted on 17/02/2008

Poprawka koła
We wtorek jest poprawka i niestety nie pamiętam do końca co było. O to co pamiętam
1 kolokwium
a) notacja bez nawiasowa
b) tablica analityczna
c) udowodnić formule (za pomocą dedukcji?)
d)(…)
e)(…)
2 kolokwium
a) dowód A\B\C=Au(BnC) nie do końca pamiętam
b) udowodnić tezę
c) siatka
d)(…)
e)(…)
Tylko tyle pamiętam :(.

admin
Posted on 17/02/2008

no niestety, nie bardzo, też starałem sobie przypomnieć pytania z 2 koła
wiem że co do tego zadania z siatki to była też oczywiście binarka i minimalna postać apn
+jeszcze formalizacja zdań (Jan jest filozofem - fil(x) )

BTW jesteś PEWIEN że ta poprawka jest we wtorek? wydawało mi się że jest 21 lutego czyli w czwartek!
czy to poprawka dla wszystkich?

kachaj
Posted on 17/02/2008

Grupa 12 ma we wtorek:
Wiadomość przeznaczona jest dla grupy studentów: PODSTAWY LOGIKI I TEORII MNOGOŚCI Grupa: 12 Prowadzący/a: JACEK MARCINIEC
Odpowiedzi na tę wiadomość należy kierować na adres: jacmar@amu.edu.pl
——————————————
Szanowni Państwo,
Kolokwium poprawkowe odbędzie się 19 lutego (wtorek), o godzinie 13:00, w auli C.

admin
Posted on 20/02/2008

no fakt, grupa dr Kandulskiego kiedy indziej,
tzn w czwartek 21 lutego o 17.15 w A2-14

Kanał RSS dla tego wpisu.

TrackBack URL

« października