수학에서 논리 방정식을 풉니다. 논리 방정식 시스템을 푸는 방법 부울 방정식 시스템

변수를 변경하여 논리 방정식 시스템 풀기

변수 변경 방법은 일부 변수가 특정 표현식의 형태로만 방정식에 포함되고 다른 것은 없는 경우에 사용됩니다. 그런 다음 이 표현식을 새로운 변수로 나타낼 수 있습니다.

실시예 1

다음 조건을 모두 만족하는 논리변수 x1, x2, x3, x4, x5, x6, x7, x8의 값 집합은 몇 개입니까?

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

답은 이 등식 시스템이 충족되는 변수 x1, x2, x3, x4, x5, x6, x7, x8의 모든 다른 값 집합을 나열할 필요가 없습니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

그런 다음 시스템은 단일 방정식으로 작성할 수 있습니다.

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. 각 피연산자가 1로 평가될 때 접속사는 1(참)입니다. 즉, 각각의 의미는 참이어야 하며, 이것은 (1 → 0)을 제외한 모든 값에 대해 참입니다. 저것들. 변수 y1, y2, y3, y4의 값 테이블에서 단위는 0의 왼쪽에 있어서는 안 됩니다.

저것들. 5세트 y1-y4에 대한 조건이 충족됩니다.

왜냐하면 y1 = x1 → x2, 단일 집합 x1, x2: (1, 0)에서 y1 = 0 값이 달성되고 x1, x2: (0,0) , ( 0,1), (1.1). 마찬가지로 y2, y3, y4.

변수 y1에 대한 각 집합(x1,x2)이 변수 y2에 대한 각 집합(x3,x4)과 결합되는 식이므로 변수 x의 집합 수가 곱해집니다.

세트 수를 추가합시다: 1 + 3 + 9 + 27 + 81 = 121.

대답: 121

실시예 2

다음 조건을 모두 만족하는 불리언 변수 x1, x2, ... x9, y1, y2, ... y9의 다른 값 집합은 몇 개입니까?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬(x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

답으로 필요 없음주어진 등식 시스템이 충족되는 변수 x1, x2, ... x9, y1, y2, ... y9의 모든 다른 값 세트를 나열합니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책:

변수를 변경해 보겠습니다.

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,… ,(x9 ≡ y9) = z9

시스템은 단일 방정식으로 작성할 수 있습니다.

(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)

동등성은 두 피연산자가 동일한 경우에만 참입니다. 이 방정식의 해는 두 세트입니다.

왜냐하면 zi = (xi ≡ yi), 값 zi = 0은 두 세트 (xi,yi): (0,1) 및 (1,0)에 해당하고 값 zi = 1은 두 세트 (xi,yi ): (0,0) 및 (1,1).

그런 다음 첫 번째 집합 z1, z2,…, z9는 29개 집합(x1,y1), (x2,y2),…, (x9,y9)에 해당합니다.

동일한 숫자는 두 번째 집합 z1, z2,…, z9에 해당합니다. 그런 다음 총 2 9 +2 9 = 1024 세트가 있습니다.

대답: 1024

재귀의 시각적 정의에 의한 논리 방정식의 시스템 풀기.

이 방법은 연립방정식이 충분히 단순하고 변수를 추가할 때 집합 수를 늘리는 순서가 분명한 경우에 사용됩니다.

실시예 3

연립방정식에는 몇 개의 다른 해가 있습니까?

¬x9 ∨ x10 = 1,

여기서 x1, x2, ... x10은 부울 변수입니까?

답은 주어진 평등 시스템이 유지되는 모든 다른 값 x1, x2, ... x10 세트를 열거할 필요가 없습니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책:

첫 번째 방정식을 풀자. 피연산자 중 하나 이상이 1인 경우 분리는 1과 같습니다. 즉, 솔루션은 다음과 같습니다.

x1=0의 경우 두 개의 x2 값(0 및 1)이 있고 x1=1의 경우 하나의 x2 값(1)만 있으므로 집합(x1,x2)이 방정식의 해가 됩니다. 단 3세트.

변수 x3을 추가하고 두 번째 방정식을 고려합시다. 첫 번째 것과 유사합니다. 즉, x2=0의 경우 x3(0과 1)의 두 값이 있고 x2=1의 경우 x3(1)의 값이 하나만 있으므로 집합( x2,x3)은 방정식의 해입니다. 총 4세트가 있습니다.

다른 변수를 추가할 때 하나의 집합이 추가되는 것을 쉽게 알 수 있습니다. 저것들. (i+1) 변수의 집합 수에 대한 재귀 공식:

N i +1 = N i + 1. 그런 다음 10개의 변수에 대해 11개의 세트를 얻습니다.

대답: 11

다양한 유형의 논리 방정식 풀이 시스템

실시예 4

다음 조건을 모두 만족하는 불리언 변수 x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 의 서로 다른 값 집합이 몇 개 있습니까?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(Y1 → Y2) ∧ (Y2 → Y3) ∧ (Y3 → Y4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

답으로 필요 없음주어진 등식 시스템이 만족되는 변수 x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 의 모든 다른 값 세트를 나열합니다. .

대답으로 그러한 세트의 수를 표시해야합니다.

해결책:

시스템의 세 방정식은 서로 다른 독립 변수 집합에서 동일합니다.

첫 번째 방정식을 고려하십시오. 접속사는 모든 피연산자가 참(1과 같음)인 경우에만 참(1과 같음)입니다. 의미는 (1,0)을 제외한 모든 집합에서 1입니다. 이것은 첫 번째 방정식의 해가 x1, x2, x3, x4와 같은 집합이 될 것임을 의미하며, 여기서 1은 0(5개 집합)의 왼쪽에 있지 않습니다.

유사하게, 두 번째 및 세 번째 방정식의 해는 정확히 동일한 y1,…,y4 및 z1,…,z4 세트가 됩니다.

이제 시스템의 네 번째 방정식을 분석해 보겠습니다. x 4 ∧ y 4 ∧ z 4 = 0. 해는 변수 중 하나 이상이 0인 모든 집합 x4, y4, z4입니다.

저것들. x4 = 0의 경우 가능한 모든 집합(y4, z4)이 적합하고 x4 = 1의 경우 적어도 하나의 0을 포함하는 집합(y4, z4)이 적합합니다. (0, 0), (0,1) , ( 1, 0).

총 세트 수는 25 + 4*9 = 25 + 36 = 61입니다.

대답: 61

순환 공식을 구성하여 논리 방정식 시스템 풀기

순환식을 구성하는 방법은 집합의 수를 늘리는 순서가 명확하지 않고 볼륨으로 인해 트리를 구축할 수 없는 복잡한 시스템을 해결하는 데 사용됩니다.

실시예 5

다음 조건을 모두 만족하는 불리언 변수 x1, x2, ... x7, y1, y2, ... y7의 다른 값 집합은 몇 개입니까?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

답은 주어진 등식 체계가 성립하는 변수 x1, x2, ..., x7, y1, y2, ..., y7의 모든 다른 값 집합을 나열할 필요가 없습니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책:

시스템의 처음 6개 방정식은 동일하며 변수 집합에서만 다릅니다. 첫 번째 방정식을 고려하십시오. 솔루션은 다음과 같은 변수 집합입니다.

나타내다:

변수 (x1,y1) ~ A 1 의 집합 수 (0,0) ,

변수 (x1,y1) ~ B 1 의 집합 수(0,1) ,

C 1 을 통해 변수(x1,y1)에 대한 세트 수(1,0),

D 1 을 통해 변수(x1,y1)에 대한 집합(1,1)의 수.

변수 (x2,y2) ~ A 2 의 집합 수(0,0) ,

B 2 를 통한 변수(x2,y2)에 대한 세트 수(0,1)

C 2 를 통해 변수(x2,y2)에 대한 집합 수(1,0),

D 2 를 통해 변수(x2,y2)에 대한 세트 수(1,1).

의사 결정 트리에서 우리는 다음을 알 수 있습니다.

A1=0, B1=1, C1=1, D1=1.

변수 (x2,y2)의 튜플 (0,0)은 변수 (x1,y1)의 튜플 (0,1), (1,0) 및 (1,1)에서 얻습니다. 저것들. A 2 \u003d B 1 + C 1 + D 1.

변수 (x2,y2)에 대한 집합 (0,1)은 변수 (x1,y1)에 대한 집합 (0,1), (1,0) 및 (1,1)에서 얻습니다. 저것들. B 2 \u003d B 1 + C 1 + D 1.

비슷하게 주장하면 C 2 \u003d B 1 + C 1 + D 1입니다. D2 = D1.

따라서 재귀 공식을 얻습니다.

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

디 i+1 = A i + B i + C i + D i

테이블을 만들자

마지막 방정식 (x7 ∨ y7) = 1은 x7=0 및 y7=0인 집합을 제외한 모든 집합에서 충족됩니다. 우리 표에서 그러한 집합의 수는 A 7 입니다.

그러면 총 세트 수는 B 7 + C 7 + D 7 = 127+127+1 = 255입니다.

대답: 255

방정식의 사용은 우리 삶에 널리 퍼져 있습니다. 그들은 많은 계산, 구조 건설 및 스포츠에 사용됩니다. 방정식은 고대부터 인간에 의해 사용되었으며 그 이후로 그 사용이 증가했습니다. 수학에는 명제의 논리에 전념하는 특정 작업이 있습니다. 이러한 종류의 방정식을 풀려면 명제 논리의 법칙에 대한 지식, 1 또는 2 변수의 논리 함수의 진리표에 대한 지식, 논리 표현을 변환하는 방법 등의 지식이 있어야 합니다. 또한 논리 연산의 다음 속성을 알아야 합니다: 연결, 분리, 역전, 함축 및 등가.

\ 변수 - \의 모든 논리 함수는 진리표로 지정할 수 있습니다.

몇 가지 논리 방정식을 풀어 보겠습니다.

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

\[X1\]으로 솔루션을 시작하고 이 변수가 취할 수 있는 값(0과 1)을 결정합니다. 그런 다음 위의 각 값을 고려하고 \[X2.\]가 무엇인지 확인합니다. 이 경우 일 수 있습니다

표에서 볼 수 있듯이 논리 방정식에는 11개의 해가 있습니다.

온라인에서 논리 방정식을 풀 수 있는 곳은 어디입니까?

저희 웹사이트 https: // site에서 방정식을 풀 수 있습니다. 무료 온라인 솔버를 사용하면 복잡한 온라인 방정식을 몇 초 만에 풀 수 있습니다. 데이터를 솔버에 입력하기만 하면 됩니다. 또한 비디오 지침을 시청하고 당사 웹사이트에서 방정식을 푸는 방법을 배울 수 있습니다. 질문이 있는 경우 Vkontakte 그룹 http://vk.com/pocketteeacher에서 질문할 수 있습니다. 우리 그룹에 가입하세요. 언제나 기꺼이 도와드리겠습니다.

논리 방정식 시스템을 푸는 방법

Kirgizova E.V., Nemkova A.E.

레소시비르스크 교육학 연구소 -

러시아 시베리아연방대학교 분과

일관되게 생각하고, 결정적으로 논쟁하고, 가설을 세우고, 부정적인 결론을 논박하는 능력은 저절로 생기는 것이 아닙니다. 이 능력은 논리학에 의해 개발됩니다. 논리학은 다른 진술의 참 또는 거짓에 기초하여 일부 진술의 참 또는 거짓을 확립하는 방법을 연구하는 과학입니다.

이 과학의 기초를 마스터하는 것은 논리적 문제를 해결하지 않고는 불가능합니다. 새로운 상황에서 지식을 적용하는 기술의 형성을 확인하는 것은 통과하여 수행됩니다. 특히 이것은 논리적 문제를 해결하는 능력입니다. 시험의 작업 B15는 논리 방정식 시스템을 포함하기 때문에 복잡성이 증가된 작업입니다. 논리 방정식 시스템을 푸는 방법에는 여러 가지가 있습니다. 이것은 하나의 방정식으로의 축소, 진리표의 구성, 분해, 방정식의 순차 해 등입니다.

작업:논리 방정식 시스템을 풉니다.

고려하다 하나의 방정식으로 줄이는 방법 . 이 방법은 우변이 진리값(즉, 1)과 같도록 논리 방정식의 변환을 포함합니다. 이렇게 하려면 논리적 부정 연산을 사용합니다. 그런 다음 방정식에 복잡한 논리 연산이 있는 경우 "AND", "OR", "NOT"와 같은 기본 연산으로 대체합니다. 다음 단계는 논리 연산 "AND"를 사용하여 시스템과 동일한 방정식을 하나로 결합하는 것입니다. 그런 다음 논리 대수의 법칙에 따라 결과 방정식을 변환하고 시스템에 대한 특정 솔루션을 얻어야 합니다.

솔루션 1:첫 번째 방정식의 양변에 반전을 적용합니다.

기본 연산 "OR", "NOT"를 통해 의미를 표현해 보겠습니다.

방정식의 왼쪽은 1이므로 "AND" 연산을 사용하여 원래 시스템과 동일한 하나의 방정식으로 결합할 수 있습니다.

de Morgan의 법칙에 따라 첫 번째 브래킷을 열고 결과를 변환합니다.

결과 방정식에는 하나의 솔루션이 있습니다.답= 0, B=0 및 C=1.

다음 방법은 진리표의 구성 . 논리 값에는 값이 두 개뿐이므로 모든 옵션을 살펴보고 주어진 방정식 시스템이 충족되는 옵션을 찾을 수 있습니다. 즉, 시스템의 모든 방정식에 대해 하나의 공통 진리표를 만들고 원하는 값이 있는 선을 찾습니다.

솔루션 2:시스템에 대한 진리표를 만들어 보겠습니다.

볼드체는 문제의 조건이 충족되는 선입니다. 따라서 A =0 , B =0 및 C =1 입니다.

방법 분해 . 아이디어는 변수 중 하나의 값을 고정하고(0 또는 1로 설정) 방정식을 단순화하는 것입니다. 그런 다음 두 번째 변수의 값을 수정할 수 있습니다.

솔루션 3:허락하다 A = 0이면:

첫 번째 방정식에서 우리는비 =0, 두 번째부터 - С=1. 시스템 솔루션: A = 0 , B = 0 및 C = 1 .

당신은 또한 방법을 사용할 수 있습니다 방정식의 순차 해 , 각 단계에서 고려 중인 집합에 하나의 변수를 추가합니다. 이렇게 하려면 변수가 알파벳 순서로 입력되는 방식으로 방정식을 변환해야 합니다. 다음으로 우리는 결정 트리를 만들고 거기에 변수를 순차적으로 추가합니다.

시스템의 첫 번째 방정식은 A와 B에만 의존하고 두 번째 방정식은 A와 C에 의존합니다. 변수 A는 0과 1의 2가지 값을 가질 수 있습니다.

첫 번째 방정식에서 다음과 같습니다. , 그렇게 할 때 A = 0 B = 0 을 얻고 A = 1 의 경우 B = 1 을 얻습니다. 따라서 첫 번째 방정식에는 변수 A 와 B 에 대한 두 개의 해가 있습니다.

우리는 각 옵션에 대한 C 값을 결정하는 두 번째 방정식을 그립니다. A = 1의 경우 암시가 거짓일 수 없습니다. 즉, 트리의 두 번째 분기에는 솔루션이 없습니다. ~에답= 0 우리는 유일한 해결책을 얻습니다 C= 1 :

따라서 A = 0 , B = 0 및 C = 1 시스템의 솔루션을 얻었습니다.

컴퓨터 과학의 USE에서는 솔루션 자체를 찾지 않고 논리 방정식 시스템의 솔루션 수를 결정하는 것이 매우 자주 필요하며 이에 대한 특정 방법도 있습니다. 논리 방정식 시스템의 솔루션 수를 찾는 주요 방법은 다음과 같습니다. 변수의 변경. 첫째, 논리대수학의 법칙을 바탕으로 각 방정식을 최대한 단순화한 다음 방정식의 복잡한 부분을 새로운 변수로 대체하여 새로운 시스템에 대한 해의 수를 결정하는 것이 필요합니다. 그런 다음 교체품으로 돌아가서 솔루션 수를 결정하십시오.

작업:방정식( A → B ) + (C → D ) = 1? 여기서 A, B, C, D는 부울 변수입니다.

해결책:새로운 변수를 소개하겠습니다. X = A → B 및 Y = C → D . 새로운 변수를 고려하면 방정식은 다음과 같이 쓸 수 있습니다. X + Y = 1.

분리는 (0;1), (1;0) 및 (1;1)의 세 가지 경우에 참인 반면, X와 Y 즉, 세 가지 경우에 참이고 한 가지 경우에 거짓입니다. 따라서 경우(0;1)는 세 가지 가능한 매개변수 조합에 해당합니다. 사례 (1;1) - 원래 방정식의 매개변수에 대한 9가지 가능한 조합에 해당합니다. 따라서 이 방정식의 가능한 해는 3+9=15입니다.

논리 방정식 시스템에 대한 솔루션의 수를 결정하는 다음 방법은 − 이진 트리. 이 방법을 예를 들어 살펴보겠습니다.

작업:논리 방정식 시스템에는 다음과 같은 다양한 솔루션이 있습니다.

주어진 방정식 시스템은 다음 방정식과 같습니다.

( 엑스 1 → 엑스 2 )*( 엑스 2 → 엑스 3 )*…*( xm -1 → xm) = 1.

그런 척 하자엑스 1 참이면 첫 번째 방정식에서 다음을 얻습니다.엑스 2 또한 사실, 두 번째부터 -엑스 3 =1 등 xm= 1. 따라서 집합 (1; 1; …; 1)중 단위는 시스템의 솔루션입니다. 지금 하자엑스 1 =0이면 첫 번째 방정식에서엑스 2 =0 또는 엑스 2 =1.

언제 엑스 2 참이면 다른 변수도 참임을 알 수 있습니다. 즉, 집합 (0; 1; ...; 1)이 시스템의 해입니다. ~에엑스 2 =0 우리는 그것을 얻는다 엑스 3 =0 또는 엑스 3 = 등. 마지막 변수를 계속하면 방정식의 해가 다음과 같은 변수 집합(중 각 솔루션에서 +1 솔루션중 변수 값):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

이 접근 방식은 이진 트리를 구축하여 잘 설명됩니다. 가능한 솔루션의 수는 구성된 트리의 다른 분기 수입니다. 이라는 것을 쉽게 알 수 있다. m+1.

추론 및 의사 결정 트리 구축에 어려움이 있는 경우 다음을 사용하여 솔루션을 찾을 수 있습니다. 진리표, 하나 또는 두 개의 방정식에 대해.

방정식 시스템을 다음과 같은 형식으로 다시 작성합니다.

그리고 하나의 방정식에 대해 별도로 진리표를 만들어 보겠습니다.

두 방정식에 대한 진리표를 만들어 보겠습니다.

다음으로 (0; 0), (0; 1), (1; 1)의 세 가지 경우에 하나의 방정식이 참임을 알 수 있습니다. 두 방정식의 시스템은 네 가지 경우(0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)에서 참입니다. 이 경우 0 이상으로만 구성된 솔루션이 있음이 즉시 분명합니다. 중마지막 위치에서 시작하여 가능한 모든 자리가 채워질 때까지 하나의 단위가 추가되는 솔루션입니다. 일반적인 해가 같은 형태를 갖는다고 가정할 수 있지만, 그러한 접근이 해가 되기 위해서는 가정이 참이라는 증거가 필요하다.

위의 모든 사항을 요약하면 고려된 모든 방법이 보편적인 것은 아니라는 사실에 주목하고 싶습니다. 각 논리 방정식 시스템을 풀 때 솔루션 방법을 선택하는 기준에 따라 해당 기능을 고려해야 합니다.

문학:

1. 논리적 작업 / O.B. 보고몰로프 - 2판. – M.: 바이놈. 지식 연구소, 2006. - 271 p.: ill.

2. Polyakov K.Yu. 논리 방정식의 시스템 / 컴퓨터 과학 교사를 위한 교육 및 조직 신문: 정보학 No. 14, 2011

논리 방정식의 시스템을 푸는 방법

예를 들어, 각 방정식을 단순화한 후 진리표(변수의 수가 너무 많지 않은 경우) 또는 의사 결정 트리를 사용하여 논리 방정식 시스템을 풀 수 있습니다.

1. 변수 변경 방법.

새로운 변수의 도입으로 미지수의 수를 줄여 연립방정식을 단순화할 수 있습니다.새 변수는 서로 독립적이어야 합니다.. 단순화된 시스템을 풀고 나면 다시 원래 변수로 돌아가야 합니다.

특정 예에서 이 방법의 적용을 고려하십시오.

예시.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

해결책:

새로운 변수를 소개하겠습니다. А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(주의! 각각의 변수 x1, x2, ..., x10은 새 변수 A, B, C, D, E 중 하나에만 포함되어야 합니다. 즉, 새 변수는 서로 독립적입니다).

그러면 방정식 시스템은 다음과 같이 보일 것입니다.

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

결과 시스템의 의사 결정 트리를 작성해 보겠습니다.

방정식 A=0을 고려하십시오. (X1≡ X2)=0. 2개의 뿌리가 있습니다.

같은 표에서 방정식 A \u003d 1에도 2개의 근이 있음을 알 수 있습니다. 의사 결정 트리의 루트 수를 정렬해 보겠습니다.

한 분기에 대한 솔루션의 수를 찾으려면 각 수준의 솔루션 수를 곱해야 합니다. 왼쪽 가지는 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32개의 솔루션; 오른쪽 분기에는 32개의 솔루션도 있습니다. 저것들. 전체 시스템에는 32+32=64 솔루션이 있습니다.

답: 64.

2. 추론 방법.

논리 방정식 풀이 시스템의 복잡성은 완전한 의사 결정 트리의 부피에 있습니다. 추론 방법을 사용하면 전체 트리를 완전히 구축할 수 없지만 동시에 얼마나 많은 가지를 가질 것인지 이해할 수 있습니다. 특정 예에서 이 방법을 고려해 보겠습니다.

실시예 1 다음 조건을 모두 만족하는 불리언 변수 x1, x2, x3, x4, x5, y1, y2, y3, y4, y5의 값 집합은 몇 개입니까?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

답은 주어진 등식 시스템이 충족되는 변수 x1, x2, x3, x4, x5, y1, y2, y3, y4, y5의 모든 다른 값 세트를 나열할 필요는 없습니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책 :

첫 번째 및 두 번째 방정식은 세 번째 조건과 관련된 독립 변수를 포함합니다. 첫 번째 및 두 번째 방정식에 대한 의사 결정 트리를 구성해 보겠습니다.

첫 번째 및 두 번째 방정식에서 시스템의 의사 결정 트리를 나타내려면 첫 번째 트리의 각 분기를 변수 트리로 계속해야 합니다.~에 . 이러한 방식으로 구성된 트리에는 36개의 가지가 포함됩니다. 이러한 분기 중 일부는 시스템의 세 번째 방정식을 충족하지 않습니다. 첫 번째 나무에 나무의 가지 수를 기록하십시오."에" , 이는 세 번째 방정식을 충족합니다.

명확히 하자: x1=0에서 세 번째 조건을 충족하려면 y1=1, 즉 트리의 모든 가지가 있어야 합니다."엑스" , 여기서 x1=0은 트리에서 단 하나의 분기로 계속될 수 있습니다."에" . 그리고 나무의 한 가지에만"엑스" (오른쪽) 나무의 모든 가지에 맞음"에". 따라서 전체 시스템의 전체 트리에는 11개의 분기가 포함됩니다. 각 분기는 원래 방정식 시스템에 대한 하나의 솔루션을 나타냅니다. 따라서 전체 시스템에는 11개의 솔루션이 있습니다.

답: 11.

실시예 2 연립방정식에는 몇 개의 다른 해가 있습니까?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1

(X1 ≡ X10) = 0

여기서 x1, x2, …, x10은 부울 변수입니까? 이 평등이 유지되는 다양한 변수 값 집합을 모두 나열할 필요는 없습니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책 : 시스템을 단순화합시다. 첫 번째 방정식의 일부에 대한 진리표를 작성해 보겠습니다.

마지막 열에주의하십시오. 작업 결과와 일치합니다. X1 ≡ X10.

단순화 후 다음을 얻습니다.

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

마지막 방정식을 고려하십시오.(X1 ≡ X10) = 0, 즉 x1은 x10과 같을 수 없습니다. 첫 번째 방정식이 1이 되려면 평등이 유지되어야 합니다.(X1 ≡ X2)=1, 즉 x1은 x2와 일치해야 합니다.

첫 번째 방정식에 대한 의사 결정 트리를 작성해 보겠습니다.

두 번째 방정식을 고려하십시오. x10=1 및 x2=0의 경우 대괄호1과 같아야 합니다(즉, x2는 x3과 같음). x10=0 및 x2=1에서 브래킷(X2 ≡ X10)=0 이므로 대괄호 (X2 ≡ X3) 1과 같아야 합니다(즉, x2는 x3과 같음):

이러한 방식으로 논의하여 모든 방정식에 대한 의사 결정 트리를 구성합니다.

따라서 연립방정식에는 해가 2개뿐입니다.

답: 2.

실시예 3

다음 조건을 모두 만족하는 불리언 변수 x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4의 다른 값 집합이 몇 개 있습니까?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

해결책:

첫 번째 방정식의 의사 결정 트리를 작성해 보겠습니다.

두 번째 방정식을 고려하십시오.

• x1=0일 때 : 두 번째 및 세 번째 괄호는 0이 됩니다. 첫 번째 괄호가 1이 되려면 y1=1, z1=1이어야 합니다(즉, 이 경우 - 1 솔루션).
• x1=1일 때 : 첫 번째 괄호는 0이 됩니다. 초또는 세 번째 괄호는 1과 같아야 합니다. 두 번째 괄호는 y1=0 및 z1=1일 때 1과 같습니다. 세 번째 괄호는 y1=1 및 z1=0에 대해 1과 같습니다(즉, 이 경우 - 2개의 솔루션).

나머지 방정식도 마찬가지입니다. 트리의 각 노드에 대해 얻은 솔루션의 수를 확인합니다.

각 분기에 대한 솔루션의 수를 찾기 위해 각 분기에 대해 얻은 숫자를 별도로 곱합니다(왼쪽에서 오른쪽으로).

1개 가지: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 해

2개의 가지: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2개의 해

세 번째 분기: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 해 4개

4가지: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8개의 해

5개 가지: 2 ⋅ 2 ⋅ 2 ⋅ 2=16개의 해

얻은 숫자를 더해보자: 총 31개의 솔루션.

답: 31.

3. 뿌리 수의 정기적인 증가

일부 시스템에서 다음 방정식의 근 수는 이전 방정식의 근 수에 따라 다릅니다.

실시예 1 다음 조건을 모두 만족하는 불리언 변수 x1, x2, x3, x4, x5, x6, x7, x8, x9, x10의 값 집합은 몇 개입니까?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

단순화 첫 번째 방정식:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). 그러면 시스템은 다음과 같은 형식을 취합니다.

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

등.

다음 방정식은 이전 방정식보다 근이 2개 더 많습니다.

4 방정식에는 12개의 근이 있습니다.

방정식 5에는 14개의 근이 있습니다.

8 방정식에는 20개의 근이 있습니다.

답: 20개의 뿌리.

때때로 뿌리의 수는 피보나치 수의 법칙에 따라 증가합니다.

논리 방정식 시스템을 풀려면 창의적인 접근 방식이 필요합니다.

시립예산교육기관

"중학교 18번"

Bashkortostan 공화국 Salavat시의 도시 지구

논리 방정식 시스템

정보학 시험 과제에서

시험 과제에서 "논리 대수의 기초"섹션은 가장 어렵고 제대로 해결되지 않은 것으로 간주됩니다. 이 주제에 대한 작업을 완료하는 평균 백분율은 가장 낮으며 43.2입니다.

KIM 2018 사양에 따라 이 블록은 복잡성 수준이 다른 4가지 작업을 포함합니다.

작업 23은 난이도가 높기 때문에 완료율이 가장 낮습니다. 훈련된 졸업생(81-100점) 중 49.8%가 과제를 완료했고, 평균적으로 준비된(61-80점)이 13.7%에 대처했으며, 나머지 학생 그룹은 이 과제를 완료하지 못했습니다.

논리 방정식 시스템을 푸는 성공은 논리 법칙에 대한 지식과 시스템을 풀기 위한 방법의 정확한 적용에 달려 있습니다.

매핑 방법으로 논리 방정식 시스템의 솔루션을 고려하십시오.

(23.154 Polyakov K.Yu.) 연립방정식에는 몇 가지 다른 해가 있습니까?

((엑스1  와이1 )  (엑스2  와이2 ))  (엑스1  엑스2 )  (와이1  와이2 ) =1

((엑스2  와이2 )  (엑스3  와이3 ))  (엑스2  엑스3 )  (와이2  와이3 ) =1

((엑스7  와이7 )  (엑스8  와이8 ))  (엑스7  엑스8 )  (와이7  와이8 ) =1

어디 엑스1 , 엑스2 ,…, 엑스8, ~에1 ,와이2 ,…,와이8 - 부울 변수? 이 평등이 유지되는 다양한 변수 값 집합을 모두 나열할 필요는 없습니다. 대답으로 그러한 세트의 수를 표시해야합니다.

해결책. 시스템에 포함된 모든 방정식은 동일한 유형이며 각 방정식에는 4개의 변수가 포함됩니다. x1과 y1을 알면 첫 번째 방정식을 만족하는 x2와 y2의 가능한 모든 값을 찾을 수 있습니다. 비슷한 방식으로 논하면 알려진 x2와 y2에서 두 번째 방정식을 만족하는 x3, y3을 찾을 수 있습니다. 즉, 쌍 (x1, y1)을 알고 쌍 (x2, y2)의 값을 결정하면 쌍 (x3, y3)을 찾을 수 있으며, 이는 차례로 쌍 (x4, y4)으로 이어집니다. 에.

첫 번째 방정식의 모든 해를 구합시다. 이것은 두 가지 방법으로 수행할 수 있습니다. 추론을 통해 진리표를 만들고 논리 법칙을 적용하는 것입니다.

진리표:

진리표를 만드는 것은 힘들고 시간이 비효율적이므로 두 번째 방법인 논리적 추론을 사용합니다. 각 요인이 1인 경우에만 제품은 1입니다.

(엑스1  와이1 )  (엑스2  와이2 ))=1

(엑스1  엑스2 ) =1

(와이1  와이2 ) =1

첫 번째 방정식을 고려하십시오. 다음은 1과 같으며, 0 0, 0 1, 1 1일 때 (01), (10)에서 (x1 y1)=0일 때 쌍 (엑스2  와이2 ) (00), (01), (10), (11)일 수 있으며 (x1 y1)=1인 경우, 즉 (00) 및 (11) 쌍 (x2 y2)=1은 동일한 값을 취합니다. (00) 및 (11). 이 솔루션에서 두 번째 및 세 번째 방정식이 거짓인 쌍, 즉 x1=1, x2=0, y1=1, y2=0을 제외합니다.

총 쌍 수 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) 논리 방정식 시스템에는 몇 가지 다른 솔루션이 있습니까?

(엑스 1  (엑스 2  와이 2 ))  (와이 1  와이 2 ) = 1

(엑스 2  (엑스 3  와이 3 ))  (와이 2  와이 3 ) = 1

...

( 엑스 6  ( 엑스 7  와이 7 ))  ( 와이 6  와이 7 ) = 1

엑스 7  와이 7 = 1

해결책. 1) 방정식은 같은 유형이므로 추론 방법에 따라 첫 번째 방정식의 가능한 모든 쌍 (x1,y1), (x2,y2)을 찾을 수 있습니다.

(엑스1  (엑스2  와이2 ))=1

(와이1  와이2 ) = 1

두 번째 방정식의 해는 쌍 (00), (01), (11)입니다.

첫 번째 방정식의 해를 구합시다. x1=0이면 x2 , y2 - 모두, x1=1이면 x2 , y2는 값 (11)을 취합니다.

(x1 , y1) 과 (x2 , y2) 쌍을 연결해 보겠습니다.

각 단계에서 쌍의 수를 계산하는 표를 만들어 봅시다.

마지막 방정식의 해를 고려하여 엑스 7  와이 7 = 1, 우리는 쌍 (10)을 제거합니다. 총 솔루션 수 찾기 1+7+0+34=42

3)(23.180) 논리 방정식 시스템에는 몇 개의 다른 솔루션이 있습니까?

(엑스1  엑스2 )  (엑스3  엑스4 ) = 1

(엑스3  엑스4 )  (엑스5  엑스6 ) = 1

(엑스5  엑스6 )  (엑스7  엑스8 ) = 1

(엑스7  엑스8 )  (엑스9  엑스10 ) = 1

엑스1  엑스3  엑스5  엑스7  엑스9 = 1

해결책. 1) 방정식은 같은 유형이므로 추론 방법으로 첫 번째 방정식의 가능한 모든 쌍 (x1,x2), (x3,x4)을 찾습니다.

(엑스1  엑스2 )  (엑스3  엑스4 ) = 1

우리는 다음에서 0(1 0)을 주는 쌍을 솔루션에서 제외합니다. 이들은 쌍(01, 00, 11) 및 (10)입니다.

쌍 (x1,x2), (x3,x4) 간의 링크 구성