Vous recevez un ensemble d'instructions logiques. Votre défi consiste à supprimer celles qui contredisent les autres, mais de la manière optimale (c'est-à-dire en supprimant un nombre minimal de déclarations).

Défi

Vous allez écrire un programme ou une fonction qui prend en entrée une liste d'instructions, supprime le nombre minimal d'instructions de sorte qu'il existe une solution et génère le reste.

Logique

Les instructions se composent de variables A-Z et d' opérateurs entre elles.

Il existe 5 opérateurs : -(pas), v(ou), ^(et), ->(si) et <->(ssi).

Table de vérité:

A | B | -A | AvB | A^B | A->B | A<->B
0 | 0 |  1 |  0  |  0  |   1  |   1
0 | 1 |  1 |  1  |  0  |   1  |   0
1 | 0 |  0 |  1  |  0  |   0  |   0
1 | 1 |  0 |  1  |  1  |   1  |   1

Ces opérateurs peuvent être combinés avec des parenthèses ():

A | B | -(AvB) | Av(-A) | A^(-A) | (AvB)->(-B)
0 | 0 |    1   |    1   |    0   |      1
0 | 1 |    0   |    1   |    0   |      0
1 | 0 |    0   |    1   |    0   |      1
1 | 1 |    0   |    1   |    0   |      0

Les systèmes logiques se composent d'une ou plusieurs instructions .

Une solution au système logique est un état où toutes les déclarations sont simultanément vraies.

Exemples de systèmes logiques:

AvB
-(A<->B)
(AvB)->(-B)

La seule solution est A = 1, B = 0.

A^B
-(B<->A)

Celui-ci n'a pas de solution ; sans combinaison de Aet les Bdeux affirmations sont vraies.

Contribution

Vous recevrez un ensemble de relevés en entrée. Cela peut être pris via STDIN ou des arguments de fonction, formatés comme un tableau (dans un format pratique) ou une chaîne séparée par des sauts de ligne ou des espaces.

Les relevés seront de la forme suivante (en quasi- ABNF ):

statement        = variable / operation
operation        = not-operation / binary-operation
not-operation    = "-" operand
binary-operation = operand binary-operator operand
operand          = variable / "(" operation ")"
variable         = "A"-"Z"
binary-operator  = "v" / "^" / "->" / "<->"

Exemples d'instructions:

A
Av(-B)
(A<->(Q^C))v((-B)vH)

Production

Vous devez renvoyer l'ensemble (éventuellement) réduit de relevés, sous la forme exacte que vous les avez reçue. Encore une fois, la liste peut être formatée sous la forme d'un tableau de chaînes ou d'une chaîne séparée par des sauts de ligne ou des espaces.

Règles

• Vous devez toujours supprimer le nombre minimal d'instructions. S'il existe plusieurs solutions possibles, sortez l'une d'entre elles.
• Vous pouvez supposer que l'entrée contient toujours au moins 1 instruction et qu'aucune instruction n'est répétée dans l'entrée.
• Vous ne pouvez pas supposer que la sortie contient toujours une instruction. (voir exemples)
• L'utilisation de failles standard contredit la validité de votre réponse et l'une d'entre elles doit être supprimée.
• Il s'agit de code-golf , donc la réponse la plus courte en octets l'emporte.

Exemples

Contribution:

A^(-A)

Production:

(nothing)

Contribution:

A^B A<->(-B) A<->B

Production:

A^B A<->B

Contribution:

["AvB","A^B"]

Production:

["AvB","A^B"]

Rubis, 299 298 283 279 octets

class Object;def * o;!self|o;end;def s;w=join.gsub(/\W/,"").chars.uniq;n=w.size;(0..2**n).any?{|i|n.times{|j|eval(w[j]+"=#{i[j]>0}")};all?{|e|eval([%w[<-> ==],%w[-> *],%w[- !],%w[^ &],%w[v |]].inject(e){|x,i|x.gsub(*i)})}}?self:combination(size-1).map(&:s).max_by(&:size);end;end

• Attend un tableau d'expressions.
• Si vous allez l'exécuter, définissez $ VERBOSE = nil à l'intérieur de ruby ​​afin de ne pas recevoir beaucoup d'avertissements concernant la redéfinition des constantes.
• Notez qu'il définit également la variable "v" mais cela ne fait aucune différence.
• Utilise les valeurs de vérité car elles ont déjà tous les opérateurs requis, sauf implication. Malheureusement, Ruby n'a pas de classe booléenne, nous devons donc patcher un objet pour obtenir une implication :)
• Pourrait le raccourcir si nous définissons TOUTES les variables majuscules, mais cela prendrait énormément de temps à s'exécuter. Devrait probablement avoir une mise en garde dans la question à ce sujet.

Non golfé:

class Object
  def * o 
    !self|o
  end 
end

def sat? exs 
  #exs: an array of expressions
  s=[%w[<-> ==], %w[-> *], "-!", "^&", %w[v ||]]

  w=exs.join.gsub(/\W/,"").chars.uniq #variable names
  n=w.size
  if (0...2**n).any? {|i|
    n.times do |vi|
      eval("#{w[vi]}=#{i[vi]==1}")
    end 
    exs.all?{|ex|eval(s.inject(ex){|x,i|x.gsub(i[0],i[1])})}
  }
    exs
  else
    exs.combination(exs.size-1).map{|sm|sat?(sm)}.max_by(&:size)
  end
end

Python 3, 431 octets

Pas très golfé en ce moment, mais je pense que je pourrais lancer la balle avec une réponse. Essayez-le ici , g()c'est la fonction principale.

import re,itertools as H
def g(i):
 y=re.sub(r'\W','',''.join(set(i)).upper());l=i.split()
 def e(s):
  def f(a):
   for v,w in a:exec(v+'='+w)
   return eval(re.sub('[^A-Z()]+',lambda x:{'v':' or ','^':'*','<->':'==','->':'<=','-':'not '}[x.group()],s))
  return[c for c in H.product("01",repeat=len(y))if f(zip(y,c))]
 for n in range(len(l),-1,-1):
  for q in H.combinations(l,n):
   if e('('+')^('.join(q)+')'):return' '.join(q)