Tabel de adevar in C

Salut ! Trebuie sa realizez un program in C care sa-mi genereze tabelul de adevar pentru orice propozitie logica introdusa de utilizator.
Input : p && q -> !r
Output :
p q r ((p ∧ q) → ¬r)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

Fac programare de cateva luni si nu stiu cum as putea implementa acest program destul de simplu.
Nu vreau codul propriu zis ci doar niste sfaturi / etape pe care sa le urmez ca sa-mi duc task-ul la bun sfarsit.
Va multumesc mult :smiley:

Ai un and logic, iar apoi rezultatul il treci printr-un not
cel putin daca inteleg bine tabelul

1 Like

Programul trebuie sa functioneze pentru orice propozitie. Mai sus am dat doar un exemplu.

In ce context ai problema asta? Parsarea e o problema mai avansata, nu neaparat abordabila de cineva abia la inceput. Ai alte constrangeri la expresia de input care ar putea sa simplifice problema?

1 Like

expresiile logice pot fi simplificate utilizand prop algebrei boolene !

Pur si simplu mi s-a cerut sa creez acest program care sa genereze tabel de adevar pentru absolut orice propozitie.

Am gasit aceste link-uri. Sper sa te ajute

https://cboard.cprogramming.com/c-programming/167911-its-assignment-c-program-generate-truth-table-n-input-logic-gates.html

http://www.dreamincode.net/forums/topic/172368-truth-table/http://www.dreamincode.net/forums/topic/172368-truth-table/

Vezi ca trebuie sa tii cont si de precedneta operatorilor.
http://en.cppreference.com/w/c/language/operator_precedence

De asemenea ia in considerare anumite propietati ale algebrei boolene.
Ca la matematica ai comutativitate si asociativitate.

https://www.electronics-tutorials.ws/boolean/bool_6.html

1 Like

OK, fair enough. Sfatul meu e sa vorbesti cu persoana care ti-a cerut asta si sa mai slefuiasca putin definitia problemei si sa mai reduca din scope. Vad ca ai descris mai sus programul ca fiind “destul de simplu”, dar e departe de adevar. E un program relativ complicat. Nu-i mare, dar se foloseste de niste tehnici care nu fac parte din toolkit-ul standard al unui programator - parsare si compilatoare pe deo-parte, enumerare combinatorica si ceva algebra Booleana pe cealalta parte.

Ca si idee trebuie sa rezolvi trei subprobleme:

  • sa parsezi textul formulei intr-o structura cu care poti sa operezi pe calculator. Trebuie sa formezi din text un AST al formulei. Primele 5 capitole din The Dragon Book ar trebui sa acopere domeniul. Poate asta sa fie mai digerabila. Dar in principiu e mult material pana sa poti sa faci ceva pe care sa-l intelegi. Desi gramatica pentru expresii de genul asta e destul de simpla, si poti sa generezi un lexer/parstor de mana relativ direct.
  • Un by-product al parsarii este setul de variabile cu care operezi - p,q,a,b etc. Asta formeaza environmentul de executie al expresiei. Pornind de la AST-ul ala si o asociere gen p=1,q=0,a=0,b=1, vrei sa vezi ce valoare ar avea formula. E un procedeu relativ mecanic asta din fericire.
  • Ultimul pas este sa generezi toate variantele de asocieri - toate 2^n, pentru fiecare sa evaluezi cu prodecura de mai sus, si sa produci astfel tabelul. Daca ai mai putin de 64 de variabile (si o sa ai - chiar si pentru 32 programul risca sa nu termine intr-un an), un truc e sa numeri de la 0 la 1<<n - 1. Ai o reprezentare mult mai compacta a asocierii si nu trebuie sa faci tot backtrackingul complex.

Cam atatea ar fi idei. Sper sa ajute la gasirea solutiei.

3 Likes

Pas 1. Studierea limbajului C.
Pas 2. Shit, this is boring like fuck. Better go out now
Pas 3. Studierea limbajului C.
Pas 4. Chinuiala, incerci sa scrii codul dar nu merge.
Pas 5. Shit, this is still boring like fuck. Better go out now
Pas 6. Chinuiala, incerci sa scrii codul dar nu merge.
Pas 7. Go to Pas 3

Sorry man, developer’s life is shit, I know.

2 Likes

Multumesc mult de tot , am reusit sa fac programul si merge :smiley: , dupa ore de studiu i-am dat de cap.

6 Likes

Ma bucur ! :smiley:
Felicitari !

1 Like

De cartea mentionata de tine am mai auzit. Este recomandata la cursul de compilatoare de la ACS - UPB.

Legat de compilatoare stiu ca mai este si ceva numit yacc sau flex(doar am auzit de ele).

Concret, care a fost partea cea mai grea?

Mi-a fost greu sa fac programul sa genereze tabel pentru propozitiile compuse, am luat meticulos toate cazurile in parte si mi-am facut alte functii incluzand multe switchuri. Alta bataie de cap am avut cand le-am pus in functia main , dar mi-am facut o schema logica si-am scos-o la cap intr-un final.

1 Like

lex si yacc. flex si bison sunt inlocuitorii ceva mai buni. Eu am avut ocazia sa le folosesc de cateva ori :slight_smile:

Evaluarea unei formule ca mai sus se face foarte usor, partea plictisitoare e automatizata.

2 Likes