Program wykonujący wnioskowanie logiczne

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 :?:

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?

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.

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?

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

0

Może chodzi o logikę rozmytą.

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

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

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 ;)

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 :)

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