Bom dia amigos...

[Pablo Honey 0]

Bom dia Amigos, estou com um trabalho de Algoritmo para entregar na proxima quinta feira, e sinceramente estou desesperado, ele consiste no seguinte.

 

O problema da satisfabilidade SAT é um problema de logica que envolve expressões booleanas. Pode Ser definido da seguinte forma:

 

Dado: Um expressão booleana B na sua forma normal Conjuntiva (FNC).

Objetivo: Verificar se B é satisfativel, ou seja, verificar se existe uma atribuição de valores as variaveis da expressão de tal modo que a expressão seja avaliada verdadeira.

 

Uma expressão é FNC quando for uma conjução de clausulas.

 

Voce deverá escrever um programa capaz de receber uma expressão boolena de, no maximo 5 valores, na forma FNC imprimir se a mesma é ou não satisfativel.

 

 

Alguem poderia dar uma explicação como eu poderia usar um polinomio para resolver tal questão, pois inicialmente eu pensei em fazer varias comparações, mas ai percebi que não seria possivel ja que a expressão vai ser o usuario que vai definir então não tem como. Então peço ajuda se alguem já resolveu tal problema ou sabe resolver, puder me ajudar, não quero que resolva o problema que possa me explicar como chegar na solução correta. Desde já eu agradeço.

 

Muito obrigado...

[Kandrade 7]

Tem o algoritmo DPLL

 

http://pt.wikipedia.org/wiki/Algoritmo_DPLL

 

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[Pablo Honey 0]

Tem o algoritmo DPLL

 

http://pt.wikipedia.org/wiki/Algoritmo_DPLL

 

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

Kandrade pelo amor de Deus :rolleyes: , eu nem sei como usar esse algoritmo DPLL - Estou no primeiro periodo de Sistemas de Informação e a professora passa um trabalho desse. Por exemplo para resolver esse tipo de algoritmo a pessoa tem que ter uma noção de equação booleana coisa que nunca vimos http://forum.imasters.com.br/public/style_emoticons/default/upset.gif - Se você puder dar uns toques eu te agradeço pelo resto do curso de Sistemas kkkk... É desespero mesmo, estou levando pau em Algoritmo e a professora não ajuda... Obrigado

[Kandrade 7]

Isso é matéria de lógica matemática, pra falar a verdade faz tanto tempo que quase não lembro de nada.

 

Bom o que posso te falar é:

 

são características de uma expressão na FNC:

 

- Aceita os conectivos lógicos: v "ou", ^ "e", -> "implica"

 

Vou montar a tabela verdade das expressões:

A v B

A "ou" B

 

A B S

0 0 0

0 1 1

1 0 1

1 1 1

 

A ^ B

A "e" B

 

A B S

0 0 0

0 1 0

1 0 0

1 1 1

 

A -> B

A "implica em" B

 

A B S

0 0 1

0 1 1

1 0 0

1 1 1

 

Creio que não são só essas regras, tem mais algumas.

Recomendo procurar algum material de :

lógica de programação

Leia também sobre a FNC.

 

Pelo enunciado do trabalho, voce não precisa se preocupar se a expressão B está na FNC.

A entrada deve ser uma expressão FNC.

 

O que pode ser feito:

 

- Separar o que é conectivo lógico de uma proposição.

- Montar a tabela verdade da expressão.

- Verificar se possui alguma solução "verdadeira"

[Pantoja 5]

nossa Rooney que treco complicado esse viu!

 

 

o USER que vai por as cinco variaveis booleanas para se "cruzar" e no fim você tem que dizer se é satisfatível?

 

 

uauHUAAUHAU

 

 

boa sorte meu amigo. PelamordeDEUS! que prof é essa hein. Mas imagino o pq desse programa.. ela ta testando os alunos.. vendo até onde são capazes de chegar...

 

 

Mas se você cair dentro você consegue com certeza. É dificil mas nao impossivel.

 

 

Abraços