Anda diberi satu set pernyataan logika. Tantangan Anda adalah menghapus yang bertentangan dengan yang lain, tetapi dengan cara yang optimal (yaitu menghapus jumlah pernyataan minimal).

Tantangan

Anda akan menulis program atau fungsi yang mengambil sebagai input daftar pernyataan, menghilangkan jumlah minimal pernyataan sehingga ada solusi dan output sisanya.

Logika

Pernyataan terdiri dari variabel A-Z dan operator di antara mereka.

Ada 5 operator : -(tidak), v(atau), ^(dan), ->(jika) dan <->(iff).

Meja kebenaran:

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

Operator - operator ini dapat digabungkan bersama dengan tanda kurung ():

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

Sistem logika terdiri dari 1 pernyataan atau lebih .

Sebuah solusi untuk sistem logika adalah suatu keadaan dimana semua pernyataan yang bersamaan benar.

Contoh sistem logika:

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

Satu-satunya solusi adalah A = 1, B = 0.

A^B
-(B<->A)

Yang ini tidak punya solusi ; tanpa kombinasi Adan Bkedua pernyataan itu benar.

Memasukkan

Anda akan menerima serangkaian pernyataan sebagai masukan. Ini dapat diambil melalui STDIN atau argumen fungsi, diformat sebagai larik (dalam format yang mudah) atau string yang dipisahkan baris atau dipisahkan oleh spasi.

Pernyataan tersebut akan dalam bentuk berikut (di hampir 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" / "^" / "->" / "<->"

Pernyataan contoh:

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

Keluaran

Anda harus mengembalikan seperangkat pernyataan yang dikurangi (mungkin), dalam bentuk persis seperti yang Anda terima. Sekali lagi, daftar dapat diformat sebagai array string atau string yang dipisahkan oleh baris atau spasi.

Aturan

• Anda harus selalu menghapus jumlah minimal pernyataan. Jika ada beberapa solusi yang mungkin, keluarkan salah satunya.
• Anda dapat mengasumsikan bahwa input selalu mengandung setidaknya 1 pernyataan dan tidak ada pernyataan yang diulang dalam input.
• Anda tidak boleh berasumsi bahwa output selalu berisi pernyataan. (lihat contoh)
• Menggunakan celah standar bertentangan dengan jawaban Anda yang valid, dan salah satunya harus dihapus.
• Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.

Contohnya

Memasukkan:

A^(-A)

Keluaran:

(nothing)

Memasukkan:

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

Keluaran:

A^B A<->B

Memasukkan:

["AvB","A^B"]

Keluaran:

["AvB","A^B"]

Ruby, 299 298 283 279 byte

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

• Mengharapkan sederetan ekspresi.
• Jika Anda akan menjalankannya, tetapkan $ VERBOSE = nil dari dalam ruby ​​sehingga Anda tidak mendapatkan banyak peringatan tentang mendefinisikan ulang konstanta.
• Perhatikan bahwa ia sebenarnya menetapkan variabel "v" juga tetapi itu tidak membuat perbedaan.
• Menggunakan nilai kebenaran karena mereka sudah memiliki semua operator yang diperlukan, kecuali implikasinya. Sayangnya Ruby tidak memiliki kelas boolean sehingga kita harus men-patch objek untuk mendapatkan implikasi :)
• Bisa membuatnya lebih pendek jika kita hanya menyetel SEMUA variabel huruf besar, tetapi kemudian akan membutuhkan banyak waktu untuk menjalankannya. Mungkin harus memiliki peringatan dalam pertanyaan tentang itu.

Tidak Terkumpul:

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 byte

Tidak terlalu bermain golf sekarang, tetapi saya pikir saya akan mendapatkan bola dengan jawaban. Coba di sini , g()adalah fungsi utamanya.

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)