Bu Informatică - set 3

Cât de multe soluții diferite face sistemul de ecuații

(X1 ˅ x2) ((x1 x2) → x3) = 1
(X2 ˅ x3) ((x2 x3) → x4) = 1
(X3 ˅ x4) ((x3 x4) → x5) = 1
(X4 ˅ x5) ((x4 x5) → x6) = 1
(X5 ˅ x6) ((x5 x6) → x7) = 1
(X6 ˅ x7) ((x6 x7) → x8) = 1
(˅ x8 X7) = 1

în cazul în care x1, x2, ..., X8 - variabile logice? Ca răspuns, nu este necesar pentru a enumera toate diferitele seturi de variabile pentru care deține această egalitate. Ca răspuns, trebuie să specificați numărul de seturi.

Rezolvăm sistemul folosind șiruri de biți. șir de biți - un set de unu și zero pentru x1 variabilă. x8, în care sistemul va fi adevărat.

Lanțuri sunt construite în conformitate cu anumite reguli care pot fi derivate din sistem. Luați în considerare prima ecuație:

(X1 ˅ x2) ((x1 x2) → x3) = 1

Pentru expresia adevărului (x1 ˅ x2) trebuie să fie neapărat adevărat, adică în ecuația nu poate fi două zerouri consecutive.

În plus, expresia ((x1 x2) → x3) trebuie să fie adevărat. Fals, ar fi cazul dacă x1 și x2 este egal cu 1, și x3 - 0. Asta este, după două unități consecutive nu poate fi zero.

Fiecare următoarea ecuație este legată de cea anterioară:

(X1 ˅ x2) ((x1 x2) → x3) = 1
(X2 ˅ x3) ((x2 x3) → x4) = 1

Există două reguli pe care le-am luat, nu numai că se aplică la fiecare ecuație, dar, de asemenea, la întregul lanț.

Primul șir evident pentru un set de x - toate unitățile:

Luați în considerare lanț, care poate fi doar un singur zero. Conform regulii nu poate fi zero după două unități:

Luați în considerare lanțuri cu două zerouri. Prin regula dublei zero nu poate fi aproape de:

Construirea restul lanțului:

Se pare că există acest sistem pentru 9 soluții diferite.