Информатика бу - да 3

Колко различни решения прави системата уравнения

(X1 ˅ х2) ((х1 х2) → х 3) = 1
(X2 ˅ х 3) ((х2 x3) → x4) = 1
(Х 3 ˅ x4) ((x3 x4) → х5) = 1
(Х4 ˅ х5) ((Х4 Х5) → x6) = 1
(Х5 ˅ x6) ((х5 x6) → х7) = 1
(X6 ˅ х7) ((x6 х7) → х8) = 1
(X7 ˅ х8) = 1

където x1, x2, ..., x8 - логически променливи? В отговор на това, че не е необходимо да се изброят всички различните набори от променливи, за които притежава това равенство. В отговор на това, което трябва да се уточни броят на масивите.

Ние решаваме системата, използвайки битови низове. Bit низ - набор от единици и нули за променлив x1. x8, в който системата ще бъде вярно.

Вериги са конструирани в съответствие с определени правила, които могат да бъдат получени от системата. Помислете за първото уравнение:

(X1 ˅ х2) ((х1 х2) → х 3) = 1

За изразяване на истината (x1 ˅ x2), трябва задължително да е вярно, това е, в уравнението не може да бъде на две последователни нули.

В допълнение, експресията ((х1 х2) → х 3) трябва да бъде вярно. False, би бил случаят, ако x1 и x2 е равно на 1, и x3 - 0. Това означава, че след две последователни единици не може да бъде нула.

Всяка следваща уравнение е свързано с предишното:

(X1 ˅ х2) ((х1 х2) → х 3) = 1
(X2 ˅ х 3) ((х2 x3) → x4) = 1

Има две правила, които взехме, не само, приложими за всяка уравнение, но и за цялата верига.

Първата очевидна низ за набор от х е - всички звена:

Помислете за верига, която може да бъде само една нула. Според правилото не може да бъде нула след две единици:

Помислете вериги с две нули. По правилото за двойна нула не може да бъде в близост до:

Построяване на останалата част от веригата:

Оказва се, че съществува тази система в продължение на 9 различни решения.