sekwencja gentzena

0

Witam.

Piszę program przetwarzający zdanie logiczne wg sekwencji gentzena. Poradziłem sobie z rozpoznawaniem poprawności zapisu zdania, teraz kolej na rozłożenie tego na elementy i sprawdzenie czy zdanie jest tautologią.
Nie za bardzo wiem jak się za to zabrać gdyż zdanie jest podawane z klawiatury i nie wiadomo na ile częsci trzeba będzie je podzielić. mOże ktoś ma jakiś pomysł.Wiem że piszę tu ogólnikowo ale jesli ktoś wie o co chodzi to niech się odezwie wtedy ewentualnie podam więcej szczegółów.

POzdr.

0

Kurcze, ktoś się musi zlitować i coś napisać.
Co dokładnei rozumiesz przez sprawdzanie poprawności zdania? Czy chodzi tylko owystępujące znaki, czy też pod wzgledem poprawności językowej.
Jeśli językowej to jaki masz standard, czy możesz narzucić swój własny?
Jakie działania są dozwolone itd.
Najprościej zrobić listę operatorów i wszystko pozostałe traktować jako nazwy o ile nie są podzielone nawiasami.
Napisz kilka przykładów, to coś się podpowie.

0

Witam ponownie.

Rachunek Gentzena stanowi pewną odnianę formalizacji rachunku kwantyfikatorów szczególnie przydatną do automatyzacji procesu dowodzenia twierdze? rachunku kwantyfikatorów.
Rachunek Gentzena wprowadza do rachunku kwantyfika-torów pojęcie sekwencji < S, T > , która jest uporządkowaną parą zbiorów formuł < S, T >, gdzie:

  S = {s1, s2, . . .   ,sn }    i    T = {t1, t2, . . .     ,tm}.

Przez sekwencję < S, T > rozumiemy następującą impli-kację
s1 &s2 & . . . & sn > t1 v t2 v . . . v tm

Sekwencję < S, T > będziemy oznaczali w następujący sposób
s1, s2, . . . ,sn f t1, t2, . . . ,tm

Jeżeli zbiory S i T zawierają wspólny element, to sekwencja < S, T > jest twierdzeniem, a zatem zdaniem zawsze prawdziwym (tautologią)

Oki chodzi więc o to: mamy jakieś zdanie logiczne np. f~ (a v b) =(~a &~b) gdzie
f -znak sekwencji gentzena
~ -negacja
v -alternatywa

-implikacja
& -koniunkcja
= -równoważność
I teraz wg. reguł wnioskowania rachunku Gentzena które brzmią:

Dla negacji
A1: P,~a f Q P f a,Q
A2: P f ~a,Q P,a f Q

Dla koniunkcji
B1: P, a & b fQ P, a, b f Q
B2: P f a & b, Q P f a, Q i P f b, Q

Dla alternatywy
C1: P, a v b f Q P, a f Q i P, b f Q
C2: P fa v b, Q P f a, b, Q

Dla implikacji
D1: P, a >b f Q P,b f Q i P f a, Q
D2: P f a >b, P, a f b, Q

Dla równoważności
E1: P, a =b f Q P, a, b f Q i P f a, b, Q
E2: Pf a = b, Q P, a f b, Q i P, b f a, Q

musimy sprawdzić czy zdanie jest tautologią
np: f ~ (a v b) = (~a &~b)
|
E2
|________________
| |
~ (a v b) f (~a &~b) (~a &~b) f ~ (a v b)
| |
B2 B1
________________________| |
| | ~a,~b f ~(av b)
~(av b) f ~a ~(av b) f ~b |
| | A2
A1 A1 |
| | ~a,~b, a v b f
f a v b,~a f a v b, ~b |
| | A1
C2 C2 |
| | ~b, av b f a
f a, b, ~a f a, b, ~b |
| | A1
A2 A2 |
| | a v b fa, b
a f a, b b fa, b |
C1
__|
| |
a f a, b b f a,b

Chodzi o to że napisałem procedurę sprawdzającą czy wpisane zdanie jest poprawne gramatycznie czyli jest tyle nawiasów co potrzeba czy znaki występujące po sobie są dopuszczalne itp.
A teraz ma mi rozbijać moje zdanie na pomniejsze sprawdzać czy to tautologia

POzdr.

0

Przydałoby się trochę przykładów, ale sugeruję nastepujące kroki:

  1. Skoro znasz znaki dopuszczalne - do tego dodaj nawiasy - i mozesz wyodrebicn zmienne (Literki A, B ABD GORA itp)
  • robisz to następująco - tekst dzielisz na fragmenty pomiędzy występującymi znanymi tobie znakami i deklarujesz je jako zmienne, np. A*(B+CD)dziliesz na kawalki znane i nieznane czyli A|*(|B|+|CD|) Otrzymujesz 3 ciągi neiznanych nieprzedzielonych niczym "obiektów" A, B, CD, oraz cały zestaw znanych tobie znaków *,(),+.
  1. Podzieliłeś tekst na mnóstwo powiazanych ze sobą zmiennych i operatorów, teraz potzrebujesz przekształcić to do jednego formatu. Na podstawie znanej ci arytmetyki mnożysz dzielisz negujesz uwzględnaisz nawiasy. Powinieneś postarać się ustalić jeden najbarziej możliwie rozłożony zapis, np. na sumę iloczynów. Następnei obydwie strony doprowadzić do tego zapisu, i porównać (członami - bo kolejność członów moze być różna) zapisany tekst.
    Przykład - na standardowym wzorze (przejście na sumę iloczynów): A(B+(CD))=AB+ACD, lub A(B+(CD))=AB+AC+AD.
  2. Porównanie członami stron:
    Przykład czy: A*(A+B)+D*(A+B)=(A+D)(B+A)
    No lo lecimy lewa strona: A
    A+AB+DA+DB
    Prawa strona: A
    B+AA+DB+DA
    Jak porównać członami są identyczne, trzeba też pamietać że może zajśc sytuacja 2
    AB=AB+AB
    Krótko mówiąc sporo do implementacji, nie podam szczegółów bo nie jestem w temacie a nie chce mi sie docvzytywać, czy jest rodzielność dodawania względem mnożenia itp, czy jest przemienność działań itp, to już dzialanai musisz sam sobei sprawdzić co można, co nie i co jest czemu równe. W neiktórych sytuacjach A
    B nie jest równe BA (np. macierze), a A(B+C) to nie AB+AC.
    Generalnei pokazałem drogę - nie muszisz zmeinnych nazywać po ichniemu możesz każdemu ciągowi "obcych" znaków dodawac swoją nazwę i jej używać, a
    jedynie rpzy wydruku musisz użyć tych podstawowych.
    Np, jak miałes u góry A,B, CD możesz nazwać je nap1, nap2,nap3 - wewnątrz programu i tak sprawdzać, wówczas :A|(|B|+|CD|) =>nap1(nap2+nap3) o ileż piękniejszy zapis:)

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