Program wykonujący wnioskowanie logiczne

Odpowiedz Nowy wątek
2011-05-31 10:47
0

Natrafiłem na takie zadanko żeby napisać program, który ma wykonywać wnioskowanie dla zadanego typu zdania logicznego w zależności od wczytanego zestawu zmiennych losowych. Wynikiem działania programu ma być plik tekstowy z zawierający opis wnioskowania. Program musi działać poprawnie dla każdej możliwości wczytywanej zmiennej.

No i nie wiem za bardzo o co w takim programie ma chodzić... Co on tak na prawdę ma zrobić :?: Może ktoś ma jakieś pomysły żeby rozwiązać takie zadanie :?:

Pozostało 580 znaków

2011-05-31 11:20
0

Czy te zmienne są wczytane czy losowe (program ma wczytywać czy losować)?
Co oznacza "zadany typ zdania"?
Jak wygląda przykładowe zdanie logiczne?


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2011-05-31 11:26
0

W najprostszej wersji pewnie powinien sprawdzić prawdziwość zdania np. (a && b) || c => (a || c) dla danych wartościowań a, b, c. W wersji rozszerzonej - nieograniczanie się do logiki dwuwartościowej i algebry Boola.


"Robienie w Javie moge porównac do spuszczania wody w kiblu za pomoca wiadra z wodą przyniesioną ze studni zza 7 gór, którą się dodatkowo samemu wykopało łyżeczką do słodzenia herbaty."
Jak nic kandydat do perełek! - _13th_Dragon 2011-05-31 11:48
Chyba Twój komentarz był zbyt pochopny. - ElevenEleven 2011-05-31 23:00

Pozostało 580 znaków

2011-05-31 11:47
0

No ciekawe, bardzo ciekawe !
Czy mógł byś z laski swojej zdefiniować mi operator, np && dla nie dwuwartościowej logiki, może dla przykładu ograniczmy się do trójwartościowej?
Kolejna ciekawostka to logika poza algebrą Boola, może to wyjaśnisz?


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Pokaż pozostałe 4 komentarze
Różne systemy baz danych traktują czasami dowolnie niektóre "wrażliwe" (np. te z nullem) operacje... - ElevenEleven 2011-05-31 22:57
na przykład?... pracowałem z mysql, postresql i mssql, nie znalazłem tam nic niezgodnego z tabelą dostępną pod podanym przeze mnie linkiem, ani też nic co można by nazwać "dowolnym" traktowaniem "wrażliwych" operacji. co to w ogóle znaczy "dowolne"? to są poważne serwery, a nie jakieś zabawki. - ŁF 2011-06-01 00:40
hejhejhej, spokojnie.. 3-wartosciowa to pikuś.. operatory &&/AND oraz ||/OR i inne sa tez zdefiniowane w "wielowartosciowych logikach" dosc dobrze.. np. wg. "prostej" logiki rozmytej, nie pamietam formalnej nazwy, && = MIN, || = MAX, więc: 0.1 && 0.8 == 0.1, 0.8&&0.0 = 0.0, 0.1||0.8 = 0.8, 0.8||0.0 == 0.8. Wyglada logicznie :) ? wszelkie prawidlowosci absolutnego true/false sa zachowane, a dla wartosci "z pomiędzy" zachowane są zachowania "zdroworozsądko-prawdopodobienstwowo'podobne". edti: zrezta.. nie wazne.. doczytalem wątek dalej, dyskusja zjechała już.. - quetzalcoatl 2011-06-01 11:45
ŁF: Nie zajmowałem się szczególnie tą kwestią, ale wiem, że moi znajomi porównywali różne standardowe operacje i otrzymywali różne wyniki w Oracle'u i MsSQL-u (raz jako wynik funkcji był null, raz 0 itp.). Nie zagłębiałem się w temat - bazy mnie specjalnie nie interesują - więc nie jestem w stanie powiedzieć dokładnie, jakie to były różnice i w jakich operacjach, ale wiem, że pewne niewielkie różnice są. - ElevenEleven 2011-06-02 19:57

Pozostało 580 znaków

2011-05-31 12:22
0

Program ma wykonywać wnioskowanie logiczne zapisując do pliku swoje wyniki. To znaczy, że zadane przez siebie zdanie zapisuje symbolami logicznymi, a następnie program ma zapisywać do pliku dokonane przekształcenia. Zakładamy oczywiści, że zdanie nie może być trywialne czyli "idę na spacer kiedy nie pada deszcz" nie jest dobrym zdaniem. Zdanie powinno zakładać przynajmniej 3 zmienne. Zmienne jakie będą brały udział we wnioskowaniu mają być wczytane z jednego pliku, a cały schemat wnioskowania wraz z wynikiem zapisany do innego pliku.

To są wskazówki, które otrzymałem od prowadzącego... Co prawda nic mi to nie mówi bez konkretnych przykładów, więc czuje się zagubiony w zadaniu - pisanie kodu bez zrozumienia problemu jest głupie :D

Pozostało 580 znaków

2011-05-31 12:41
0

Może chodzi o logikę rozmytą.

Pozostało 580 znaków

2011-05-31 13:17
0

Wpisujesz symbole logiczne. Przykładowe zdanie "idę na spacer kiedy nie pada deszcz" będzie chyba wyglądać tak:
!b->a
gdzie
a=idę na spacer
b=pada deszcz

W wyniku true lub false - nie wiem o jakie inne przekształcenia może chodzić.
Logikę miałem dawno temu i mogłem coś poprzekręcać, jeżeli tak to mnie poprawcie

edytowany 2x, ostatnio: Sarrus, 2011-05-31 13:59

Pozostało 580 znaków

2011-05-31 22:14
0
emilios8 napisał(a)

Może chodzi o logikę rozmytą.

idd, mi też to na zadanie z logiki rozmytej wygląda.

@_13th_Dragon:
zmienna logiczna nie koniecznie musi przyjmować jedną z dwóch wartości
http://pl.wikipedia.org/wiki/Logika_rozmyta


edytowany 1x, ostatnio: byku_guzio, 2011-05-31 22:17
Ta, nawet praktycznie piszę bazę danych opartą na logice rozmytej, powiem szczerze że nic wspólnego z logiką (oprócz nazwy) to nie ma. - _13th_Dragon 2011-05-31 22:56
niedawno pisałem w prawdzie drobną rzecz, ale mimo wszystko opartą jak najbardziej na log. rozmytej i nie mogę się z tym zgodzić. To jest jak najbardziej związane z logiką - logiczne wnioskowanie oparte na konkretnych danych - byku_guzio 2011-05-31 22:58
Używa się owszem jako logiki, zaś w środku - nic wspólnego, tylko operatory zdefiniowane tak aby użytkownik był w stanie pojąć. - _13th_Dragon 2011-05-31 23:01
no tak, rzeczywiście nie ma nic wspólnego z klasyczną logiką, ale po co się ograniczać do poziomu pierwszej klasy liceum ;] Chociaż można powiedzieć, że logika dwuwartościowa jest szczególnym przypadkiem rozmytej - byku_guzio 2011-05-31 23:22
W baaardzo dużym uproszczeniu. - _13th_Dragon 2011-05-31 23:38
tu się zgodzę :) - byku_guzio 2011-06-01 00:48

Pozostało 580 znaków

2011-05-31 22:47
0
_13th_Dragon napisał(a)

No ciekawe, bardzo ciekawe !
Czy mógł byś z laski swojej zdefiniować mi operator, np && dla nie dwuwartościowej logiki, może dla przykładu ograniczmy się do trójwartościowej?
Kolejna ciekawostka to logika poza algebrą Boola, może to wyjaśnisz?

Logiki wielowartościowe, logika rozmyta...
Definicji operatorów jest wiele. Np. w rozmytej (tzn. wartości logiczne są ze zbioru [0;1]) a && b można zdefiniować m.in. jako :

  1. min(a,b) [zwykłe minimum],
  2. a*b [zwykły iloczyn],
  3. (ab)/(a+b-ab) [iloczyn Hamachera],
  4. (ab)/(2-(a+b-ab)) [iloczyn Einsteina],
  5. max(0, a+b-1) [ograniczona różnica],
  6. min(a,b) dla max(a,b)=1, 0 wpp. [iloczyn drastyczny]

W logice trójwartościowej definiuje się najczęściej po 2 operatory "koniunkcji" i "alternatywy" albo zarzuca niektóre twierdzenia logiki dwuwartościowej (z definicji niejako nie zakłada się tertium non datur).

Algebry nieboolowskie: http://en.wikipedia.org/wiki/Heyting_algebra

Wracając do tematu:
Wnioskowaniem w rozumowaniu Twojego prowadzącego może też być "znalezienie odpowiedzi" np. czy zdanie D jest prawdziwe (niech już będzie logika dwuwartościowa, bo niektórzy wyślą mnie na stos), jeśli prawdziwe jest zdanie A oraz reguły A->B, B->C, C->D. Rozumowanie - wg standardowego sposobu z pierwszych wykładów o logice ;)


"Robienie w Javie moge porównac do spuszczania wody w kiblu za pomoca wiadra z wodą przyniesioną ze studni zza 7 gór, którą się dodatkowo samemu wykopało łyżeczką do słodzenia herbaty."
edytowany 4x, ostatnio: ElevenEleven, 2011-05-31 23:06

Pozostało 580 znaków

2011-06-01 12:12
0

nie jestem w tej kwestii zbytnim specem, ale solvery/testery często "sprowadza się" do iteracyjnego:

  • wzięcia kolejnego wyrażenia podanego jako warunek/ograniczenie
  • upraszczania pozostalych zdan/wyrażen wobec wiedzy w nim zawartej
  • proby uzupełniania faktów na podstawie zmienionej bazy faktow i ograniczen (np. a<b i b<e, wiec fakt pochodny to a<e)
  • ew. proby znalezienia przykladu lub kontr-przykladu na danym etapie
    de facto, kazdy z tych kroczkow stanowi niezly problem sam w sobie, silnie zalezny od charakteru i typu zdan..

IMHO, na poczatek zainteresuj się programami/jezykami takimi jak Prolog czy Z3 - razem z nimi bardzo czesto przychodza artykuly, a nawet ksiażki, opisujące jak za tego typu problemu zabrać. Prolog moze wygladac prosto, ale pokaze, jak manioulujac postacia wyrazen logicznych mozesz w "szybki" sposob oceniac czy ze soba nie kolidują.

Niestety, w zaleznosci od DOKŁADNEGO opisu problemu, Twoj sposob rozwiazywania drastycznie się zmienia. Np. majac problem - to:

A) zestaw zdań logiki Boole'a z małą liczba zmiennych - mozesz "pojechac" bruteforce'm i sprawdzic wszytkie kombinacje przypisan true-false do zmiennych
B) dużą liczbą zmiennych - masz bardzo duzy NP-trudny problem, idz do publikacji zwiazanych z "checking for logic/boolean satisfiability", bo wyników nieoptymalizowanego algorytmu sprawdzacza mozesz banalnie po prostu nie dożyć
C) zestaw ograniczen a < b, c >= d itp, gdzie a/b/c/d to liczby i zmienne lub proste wyrazenia liniowe - problem rozwiazuje sie budujac i obcinajac "wielokaty wypukle", w impementacji sprowadza sie to do 1 tabelki i kilku petel
D) zestaw ograniczen a < b, c >= d itp, gdzie a/b/c/d to wyrazenia matematyczne "dowolnej" postaci - masz spory problem, poniewaz analiza funkcji nie jest prosta - po to sa kombajny w stylu mathcad czy mathematica. Jezeli znasz pewne "gwarantowane" cechy wyrazen (monotoniczne? wielomianowe? itp...), mozna to wykorzystac do znaczengo przyspieszenia/uproszczenia wstepnego zagadnienia ale i tak nie jest latwo, a dochodzi jeszcez do tego problem, czy Twoj checker ma byc "matematyczny" cyz "programistyczny".. tzn. czy ma operowac na liczbach rzeczywistych, czy "dziurawych" n-bitowych skonczonych reprezentacjach.. po przeanalizowaniu funkcji wspolnie lub osobno, stajesz przed problemem podobnym do (C), ale masz juz niekoniecznie wypukłe wielokąty, co jest bardziej trudne/czasochlonne
E) czy odpowiedz ma byc absolutna, czy z okreslonym % prawdopodobienstwa błędu? - jesli to drugie, mozesz monte-carlo'wac, co niby upraszcza, ale wprowadza Cie w problem pokrycia przestrzeni i "dobrego rozkladu" strzałów..
F) ..
...

mam nadzieje ze rozumiesz rozdzwięk pomiędzy klasami problemow które się pojawiają.. rodzaj logiki która rządzi zdaniami które dostarczasz, ma niemniejszy wpływ na konstrukcję rozwiązania niż takie "detale" jak wyżej. jezeli chcesz, aby ktos sensownie cokolwiek Ci powiedział, musisz scisle okreslic, co masz do analizy, podrzucic wszystkie ograniczenia ulatwiajace/utrudniajace jakie znasz w ramach "rzeczy do analizy", oraz jakiego wyniku masz w odpowiedzi dostarczyc.

sformułowania "zdanie logiczne", "zmienna losowa", "opis wnioskowania", czy "każda możliwość wczytywanej zmiennej" to znacząco za mało, aby w ogóle zgadnąć przed jakiej klasy problemem się stawiasz, chocby dlatego, że do "zdan logicznych" na upartego zaliczysz także "F jest jednoargumentowe => calka z F(x) ma być większa od e^x", a w kontekscie pisania solvera dla pakietu takich zdan erm.. "życzę powodzenia" i szczesliwego zakonczenia habilitacji/profesury :)


no to pojechałem z nieobecnością.. chwila przerwy i prawie rok przeleciał
edytowany 3x, ostatnio: quetzalcoatl, 2011-06-01 12:24

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0