Jest dobrze wiadomo, że losowy Preparaty -cnf na n zmiennymi c n klauzule unsatisfiable (tj sprzeczności), z dużym prawdopodobieństwem, na wystarczająco dużej stałej C . Tak więc losowe formuły k- CNN (dla c wystarczająco dużych) stanowią naturalny rozkład w niezadowalających formułach boolowskich (lub podwójnie w tautologiach, tj. Negacjach sprzeczności). Ten rozkład został dokładnie zbadany.
Moje pytanie jest następujące : czy istnieją inne ustalone rozkłady zdań tautologii lub sprzeczności zdań, które można uznać za uchwycenie „przeciętnego przypadku” tautologii lub niezadowalających wzorów? Czy te rozkłady były intensywnie badane?
1
@Iddo Tautologie nie istnieją w „prawdziwym” modelu CNF, ponieważ w przeciwnym razie musiałbyś mieć literał i jego dopełnienie w tej samej klauzuli… Tautologie nie są interesujące do studiowania w CNF.
—
Tayfun Pay
@ Pay, negacja niezadowalającej formuły jest oczywiście tautologią. Dlatego też możemy rozważyć losowe k-CNF jako rozkład między tautologiami (gdy stosunek klauzuli do zmiennej jest wystarczająco duży i gdzie istnieje prawdopodobieństwo o (1), aby k-CNF był zadowalający).
—
Iddo Tzameret
Myślę, że Tayfun ma rację. Powinieneś mówić o tym, że albo formuły CNF są niezadowalające, albo formuły DNF będące tautologiami. W bieżącym pytaniu łączysz oba.
—
Tsuyoshi Ito
To mój ostatni komentarz w tej sprawie: nie wiem, dlaczego nalegasz, aby zachować słowo „tautologie”, co jest wyraźnie błędne, jak wyjaśnił Tayfun. Ale nic mi nie jest, jeśli nie chcesz uwzględniać komentarzy innych osób, aby poprawić brzmienie twojego pytania.
—
Tsuyoshi Ito
Wolę zachować w tytule termin „tautologie”, ponieważ pytam o dystrybucje dotyczące tautologii lub sprzeczności, a pytanie jest odpowiednio sformułowane.
—
Iddo Tzameret,