집 구성

논리 방정식 시스템. 논리. 논리 기능. 방정식 풀기

서비스의 목적. 온라인 계산기는 다음을 위해 설계되었습니다. 논리식에 대한 진리표 구성.
진리표 – 입력 변수와 해당 출력 값의 가능한 모든 조합을 포함하는 테이블입니다.
진리표에는 2n개의 행이 포함되어 있습니다. 여기서 n은 입력 변수의 수이고 n+m은 열입니다. 여기서 m은 출력 변수입니다.

지침. 키보드로 입력할 때 다음 규칙을 사용하십시오.

예를 들어 논리식 abc+ab~c+a~bc는 다음과 같이 입력해야 합니다. a*b*c+a*b=c+a=b*c
논리도 형식으로 데이터를 입력하려면 이 서비스를 이용하세요.

논리 함수 입력 규칙

v(접합, OR) 기호 대신 + 기호를 사용합니다.
논리 함수 앞에 함수 지정을 지정할 필요가 없습니다. 예를 들어 F(x,y)=(x|y)=(x^y) 대신 (x|y)=(x^y) 를 입력하면 됩니다.
최대 금액변수는 10과 같습니다.

컴퓨터 논리 회로의 설계 및 분석은 수학의 특수 분야인 논리 대수학을 사용하여 수행됩니다. 논리 대수학에서는 "NOT"(부정), "AND"(접속), "OR"(접합)의 세 가지 주요 논리 함수를 구분할 수 있습니다.
논리 장치를 생성하려면 기존 입력 변수에 대한 각 출력 변수의 종속성을 결정해야 하며, 이러한 종속성을 전환 함수 또는 논리 대수 함수라고 합니다.
논리 대수 함수는 2n개의 값이 모두 주어지면 완전히 정의된 함수라고 합니다. 여기서 n은 출력 변수의 수입니다.
모든 값이 정의되지 않은 경우 해당 함수를 부분 정의라고 합니다.
장치의 상태가 논리 대수 함수를 사용하여 설명되면 장치를 논리 장치라고 합니다.
다음 방법은 논리 대수 함수를 나타내는 데 사용됩니다.
대수적 형태에서는 논리 요소를 사용하여 논리 장치의 회로를 구축할 수 있습니다.

그림 1 - 논리 장치 다이어그램

논리 대수학의 모든 연산이 정의됩니다. 진리표가치. 진리표는 연산 결과를 결정합니다. 누구나 가능하다 x 원래 진술의 논리값. 연산 적용 결과를 반영하는 옵션의 수는 논리식의 명령문 수에 따라 달라집니다. 논리 표현식의 명령문 수가 N이면 가능한 인수 값의 조합이 2N개이므로 진리표에는 2N개의 행이 포함됩니다.

NOT 연산 - 논리적 부정(반전)

단순하거나 복잡한 논리 표현식일 수 있는 단일 인수에는 논리 연산이 적용되지 않습니다. 작업 결과는 다음이 아닙니다.

원래 표현식이 참이면 부정 결과는 거짓이 됩니다.
원래 표현식이 거짓이면 부정 결과는 참이 됩니다.

부정 연산에는 다음 규칙이 허용되지 않습니다.
A가 아님, Ā, A가 아님, ¬A, !A
부정 연산의 결과는 다음 진리표에 의해 결정되지 않습니다.

ㅏ	A가 아니다
0	1
1	0

부정 연산의 결과는 원래 문장이 거짓일 때 참이고 그 반대도 마찬가지입니다.

OR 연산 - 논리적 덧셈(접합, 합집합)

논리 OR 연산은 단순하거나 복잡한 논리 표현식일 수 있는 두 명령문을 결합하는 기능을 수행합니다. 논리 연산의 시작점이 되는 명령문을 인수라고 합니다. OR 연산의 결과는 원래 표현식 중 하나 이상이 참인 경우에만 참이 되는 표현식입니다.
사용된 명칭: A 또는 B, A V B, A 또는 B, A||B.
OR 연산의 결과는 다음 진리표에 의해 결정됩니다.
OR 연산의 결과는 A가 참이거나, B가 참이거나, A와 B가 모두 참이면 참이고, 인수 A와 B가 거짓이면 거짓이 됩니다.

연산 AND - 논리 곱셈(접속)

논리 연산 AND는 단순하거나 복잡한 논리 표현식일 수 있는 두 명령문(인수)의 교차 기능을 수행합니다. AND 연산의 결과는 두 원래 표현식이 모두 참인 경우에만 참이 되는 표현식입니다.
사용된 명칭: A 및 B, A Λ B, A & B, A 및 B.
AND 연산의 결과는 다음 진리표에 의해 결정됩니다.

ㅏ	비	A와 B
0	0	0
0	1	0
1	0	0
1	1	1

AND 연산의 결과는 진술 A와 B가 모두 참인 경우에만 참이고, 다른 모든 경우에는 거짓입니다.

"IF-THEN" 작업 - 논리적 결과(함축)

이 연산은 두 개의 간단한 논리 표현식을 연결하는데, 첫 번째는 조건이고 두 번째는 이 조건의 결과입니다.
사용된 명칭:
A이면 B이고; A에는 B가 수반됩니다. A이면 B이고; A→B.
진리표:

ㅏ	비	A → B
0	0	1
0	1	1
1	0	0
1	1	1

전제 A가 참이고 결론 B(결과)가 거짓인 경우에만 암시 연산의 결과가 거짓입니다.

“A if and only if B” 연산(동등성, 동등성)

사용지정 : A ← B, A ~ B
진리표:

ㅏ	비	A ← B
0	0	1
0	1	0
1	0	0
1	1	1

“덧셈 모듈로 2” 연산(XOR, 배타적 또는 엄격한 분리)

사용된 표기법: A XOR B, A ⊕ B.
진리표:

ㅏ	비	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

동등성 연산의 결과는 A와 B가 동시에 참이거나 거짓인 경우에만 참입니다.

논리 연산의 우선순위

괄호 안의 작업
반전
접속사 (&)
분리(V), 배타적 OR(XOR), 모듈로 합계 2
함의 (→)
등가(←)

완전 분리 정규형

완전 분리 정규형 공식(SDNF)는 기본 접속사의 분리이며 다음과 같은 속성을 갖는 등가 공식입니다.

공식의 각 논리항에는 함수 F(x 1,x 2,...xn)에 포함된 모든 변수가 포함됩니다.
공식의 모든 논리적 용어는 다릅니다.
단일 논리 용어에는 변수와 그 부정이 포함되어 있지 않습니다.
수식의 논리 용어에는 동일한 변수가 두 번 포함되지 않습니다.

SDNF는 진리표를 사용하거나 동등한 변환을 사용하여 얻을 수 있습니다.
각 기능에 대해 SDNF와 SCNF는 순열까지 고유하게 정의됩니다.

완전접합정규형

완전 결합 정규형 공식(SCNF)이것은 기본 분리의 결합이고 속성을 만족하는 것과 동등한 공식입니다.

모든 기본 분리에는 함수 F(x 1 ,x 2 ,...xn)에 포함된 모든 변수가 포함됩니다.
모든 기본 분리는 다릅니다.
각 기본 분리에는 변수가 한 번씩 포함됩니다.
단일 기본 분리에는 변수와 그 부정이 포함되지 않습니다.

컴퓨터 과학 시험 섹션 A와 B의 일부 문제를 해결하는 방법

수업 #3. 논리. 논리 기능. 방정식 풀기

다수의 통합 상태 시험 문제가 명제 논리에 전념합니다. 대부분의 문제를 해결하려면 명제 논리의 기본 법칙, 하나 및 두 변수의 논리 기능에 대한 진리표에 대한 지식을 아는 것으로 충분합니다. 나는 명제 논리의 기본 법칙을 제시할 것이다.

분리와 결합의 교환성:
a ˅ b ñ b ˅ a
a^b ñ b^a
분리와 결합에 관한 분배 법칙:
a ˅ (b^с) zzo (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ל (a ^ b) ˅ (a ^ c)
부정의 부정:
¬(¬a) ña
일관성:
a ^ ¬a EMA 거짓
독점 3번째:
a ˅ ¬а ñ 사실
드 모건의 법칙:
¬(a ˅ b) ñ ¬a ˄ ¬b
¬(a ˄ b) ñ ¬a ˅ ¬b
단순화:
a ˄ a ñ a
a ˅ a ñ a
a ˄ 사실 ñ a
a ˄ 거짓 = 거짓
흡수:
a ˄ (a ˅ b) ñ a
a ˅ (a ˄ b) ñ a
암시의 대체
a → b ‚ ¬a ˅ b
신원 대체
a 량 b 량(a ˄ b) ˅ (¬a ˄ ¬b)

논리 함수 표현

n 변수의 모든 논리 함수 - F(x 1, x 2, ... x n)는 진리표로 지정될 수 있습니다. 이러한 테이블에는 2n개의 변수 세트가 포함되어 있으며 각 세트에 대한 함수 값이 지정됩니다. 이 방법은 변수의 수가 상대적으로 적을 때 유용합니다. 이미 n > 5인 경우 표현이 잘 보이지 않게 됩니다.

또 다른 방법은 알려진 매우 간단한 함수를 사용하여 일부 공식으로 함수를 정의하는 것입니다. 함수 f i만 포함하는 공식으로 논리 함수를 표현할 수 있는 경우 함수 시스템(f 1, f 2, ... f k)을 완전이라고 합니다.

기능(¬, ˄, ˅) 시스템이 완성되었습니다. 법칙 9와 10은 부정, 접속, 분리를 통해 암시와 정체성이 어떻게 표현되는지 보여주는 예입니다.

실제로 부정과 결합 또는 부정과 분리라는 두 가지 기능의 시스템도 완성되었습니다. De Morgan의 법칙은 부정과 분리를 통해 결합을 표현하고 그에 따라 부정과 결합을 통해 분리를 표현할 수 있도록 하는 아이디어를 따릅니다.

(a ˅ b) ñ ¬(¬a ˄ ¬b)
(a ˄ b) ñ ¬(¬a ˅ ¬b)

역설적이게도 단 하나의 기능으로 구성된 시스템이 완성됩니다. Peirce 화살표라고 불리는 anticonjunction과 antidisjunction과 빈 시스템을 나타내는 Schaeffer 스트로크라는 두 가지 이진 함수가 있습니다.

프로그래밍 언어의 기본 기능에는 일반적으로 동일성, 부정, 연결 및 분리가 포함됩니다. 국가고시 문제에서는 이러한 기능과 함께 함축적인 의미도 발견되는 경우가 많습니다.

논리 함수와 관련된 몇 가지 간단한 문제를 살펴보겠습니다.

문제 15:

진리표의 일부가 제공됩니다. 주어진 세 가지 기능 중 이 조각에 해당하는 기능은 무엇입니까?

× 1	X 2	X 3	X 4	에프
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

(X 1 → X 2) ˄ ¬ X 3 ˅ X 4
(¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

기능 번호 3.

문제를 해결하려면 기본 기능의 진리표를 알아야 하고 작업의 우선순위를 기억해야 합니다. 연결(논리적 곱셈)이 분리(논리적 덧셈)보다 우선순위가 높고 먼저 실행된다는 점을 상기시켜 드리겠습니다. 계산 중에 세 번째 세트의 숫자 1과 2가 있는 함수는 값 1을 가지며 이러한 이유로 조각에 해당하지 않는다는 것을 쉽게 알 수 있습니다.

문제 16:

주어진 숫자 중 조건을 만족하는 숫자는 무엇입니까?

(가장 중요한 숫자부터 내림차순) → (숫자 - 짝수) ˄ (낮은 숫자 - 짝수) ˄ (높은 숫자 - 홀수)

그러한 숫자가 여러 개인 경우 가장 큰 숫자를 표시하십시오.

13579
97531
24678
15386

조건은 숫자 4에 의해 충족됩니다.

처음 두 숫자는 가장 낮은 숫자가 홀수이므로 조건을 만족하지 않습니다. 조건의 결합은 접속 조건 중 하나가 거짓인 경우 거짓입니다. 세 번째 숫자의 경우 가장 높은 숫자에 대한 조건이 충족되지 않습니다. 네 번째 숫자의 경우 숫자의 낮은 자리와 높은 자리에 부과된 조건이 충족됩니다. 접속사의 첫 번째 항도 참입니다. 왜냐하면 전제가 거짓이면 암시가 참이기 때문입니다.

문제 17: 두 명의 증인이 다음과 같이 증언했습니다.

첫 번째 증인: A가 유죄라면 B는 더욱 유죄이고 C는 무죄입니다.

두 번째 증인: 두 사람이 유죄입니다. 그리고 나머지 한 명은 확실히 유죄이고 유죄인데 정확히 누구인지는 말할 수 없습니다.

증언을 통해 A, B, C의 유죄에 대해 어떤 결론을 내릴 수 있습니까?

답: 증언에 따르면 A와 B는 유죄이고 C는 무죄입니다.

해결책: 물론 대답은 다음을 기반으로 주어질 수 있습니다. 상식. 하지만 이것이 어떻게 엄격하고 공식적으로 이루어질 수 있는지 살펴보겠습니다.

가장 먼저 할 일은 진술을 공식화하는 것입니다. 세 가지 논리 변수 A, B, C를 소개하겠습니다. 각 변수는 해당 용의자가 유죄인 경우 참(1) 값을 갖습니다. 그런 다음 첫 번째 증인의 증언은 다음 공식으로 제공됩니다.

A → (B ˄ ¬C)

두 번째 증인의 증언은 다음과 같은 공식으로 표현됩니다.

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

두 증인의 증언은 모두 사실로 간주되며 해당 공식의 결합을 나타냅니다.

이러한 판독값에 대한 진리표를 작성해 보겠습니다.

ㅏ	비	씨	F 1	F 2	에프 1 ˄ 에프 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

요약 증거는 단 한 가지 경우에만 사실이므로 A와 B는 유죄이고 C는 무죄라는 명확한 답변으로 이어집니다.

이 표를 분석하면 두 번째 증인의 증언이 더 많은 정보를 제공한다는 결론이 나옵니다. 그의 간증의 진실성에서 단 두 가지 사실이 나옵니다. 가능한 옵션- A와 B가 유죄이고 C가 무죄이거나, A와 C가 유죄이고 B가 무죄입니다. 첫 번째 증인의 증언은 그다지 유익하지 않습니다. 5가지가 있습니다. 다양한 옵션, 그의 증언에 해당합니다. 두 증인의 증언은 함께 피의자의 유죄에 대한 명확한 답변을 제공합니다.

논리 방정식 및 방정식 시스템

F(x 1, x 2, …x n)을 n 변수의 논리 함수로 설정합니다. 논리 방정식은 다음과 같습니다.

F(x1, x2, …xn) = C,

상수 C는 1 또는 0의 값을 갖습니다.

논리 방정식은 0에서 2n개의 서로 다른 해를 가질 수 있습니다. C가 1이면 해는 함수 F가 참(1) 값을 취하는 진리표의 모든 변수 집합입니다. 나머지 세트는 C가 0인 방정식의 해입니다. 항상 다음 형식의 방정식만 고려할 수 있습니다.

F(x1, x2, …xn) = 1

실제로 방정식을 다음과 같이 가정해 보겠습니다.

F(x1, x2, …xn) = 0

이 경우, 우리는 동등한 방정식으로 갈 수 있습니다:

¬F(x 1 , x 2 , …x n) = 1

k개의 논리 방정식 시스템을 고려해보세요.

F1(x1, x2, …xn) = 1

F 2 (x1, x2, …xn) = 1

Fk(x1, x2, …xn) = 1

시스템의 해는 시스템의 모든 방정식을 만족시키는 변수의 집합입니다. 논리 함수의 관점에서, 논리 방정식 시스템에 대한 해를 얻으려면 논리 함수 Ф가 참인 집합을 찾아야 하며, 이는 원래 함수 F의 결합을 나타냅니다.

Ф = F 1 ˄ F 2 ˄ … F k

변수의 수가 작은 경우(예: 5개 미만) 함수 Ф에 대한 진리표를 구성하는 것이 어렵지 않습니다. 이를 통해 시스템에 몇 개의 해가 있고 해를 제공하는 집합이 무엇인지 말할 수 있습니다.

논리 방정식 시스템에 대한 해를 찾는 일부 USE 문제에서는 변수 수가 10에 도달합니다. 그러면 진리표를 구성하는 것이 거의 불가능한 작업이 됩니다. 문제를 해결하려면 다른 접근 방식이 필요합니다. 임의의 연립방정식의 경우 이러한 문제를 해결하는 일반적인 방법은 열거형 외에는 없습니다.

시험에 제시된 문제에서 해결책은 일반적으로 방정식 시스템의 세부 사항을 고려하는 데 기반을 둡니다. 거듭 말씀드리지만, 변수 세트에 대한 모든 옵션을 시도하는 것 외에는 문제를 해결할 수 있는 일반적인 방법이 없습니다. 솔루션은 시스템의 특성을 기반으로 구축되어야 합니다. 알려진 논리 법칙을 사용하여 방정식 시스템의 예비 단순화를 수행하는 것이 유용한 경우가 많습니다. 이 문제를 해결하는 또 다른 유용한 기술은 다음과 같습니다. 우리는 모든 집합에 관심이 있는 것이 아니라 함수 Ф의 값이 1인 집합에만 관심이 있습니다. 완전한 진리표를 작성하는 대신 이진 의사결정 트리와 유사한 유사어를 작성할 것입니다. 이 트리의 각 분기는 하나의 솔루션에 해당하며 함수 Ф의 값이 1인 집합을 지정합니다. 의사결정 트리의 분기 수는 방정식 시스템에 대한 솔루션 수와 일치합니다.

몇 가지 문제의 예를 사용하여 이진 의사결정 트리가 무엇인지, 어떻게 구축되는지 설명하겠습니다.

문제 18

두 방정식의 시스템을 만족하는 논리 변수 x1, x2, x3, x4, x5, y1, y2, y3, y4, y5의 서로 다른 값 집합은 몇 개입니까?

답변: 시스템에는 36가지의 서로 다른 솔루션이 있습니다.

해결책: 연립방정식에는 두 개의 방정식이 포함됩니다. 5개의 변수(x 1, x 2, ...x 5)에 따라 첫 번째 방정식의 해 개수를 찾아보겠습니다. 첫 번째 방정식은 5개 방정식의 시스템으로 간주될 수 있습니다. 표시된 대로 방정식 시스템은 실제로 논리 함수의 결합을 나타냅니다. 반대의 경우도 마찬가지입니다. 조건의 결합은 방정식 시스템으로 간주될 수 있습니다.

첫 번째 방정식으로 간주될 수 있는 접속사의 첫 번째 항인 의미(x1→ x2)에 대한 결정 트리를 구축해 보겠습니다. 이 트리의 그래픽 표현은 다음과 같습니다.

트리는 숫자에 따라 두 가지 레벨로 구성됩니다. 방정식 변수. 첫 번째 수준에서는 첫 번째 변수 X 1 을 설명합니다. 이 레벨의 두 분기는 이 변수의 가능한 값인 1과 0을 반영합니다. 두 번째 레벨에서 트리 분기는 방정식이 참인 변수 X 2의 가능한 값만 반영합니다. 방정식은 의미를 지정하므로 X 1의 값이 1인 분기에는 해당 분기의 X 2에 값 1이 있어야 합니다. X 1의 값이 0인 분기는 X 2 값을 갖는 두 개의 분기를 생성합니다. 0과 1과 같음 구성된 트리는 X 1 → X 2의 의미가 값 1을 취하는 세 가지 해를 정의합니다. 각 분기에서 해당 변수 값 세트가 작성되어 방정식에 대한 해를 제공합니다.

이러한 집합은 다음과 같습니다: ((1, 1), (0, 1), (0, 0))

다음 방정식, 즉 X 2 → X 3 의 의미를 추가하여 의사결정 트리를 계속 구축해 보겠습니다. 우리 방정식 시스템의 특수성은 시스템의 각각의 새로운 방정식이 이전 방정식의 변수 하나를 사용하여 하나의 새로운 변수를 추가한다는 것입니다. 변수 X 2는 이미 트리에 값을 가지고 있으므로 변수 X 2의 값이 1인 모든 분기에서 변수 X 3도 값 1을 갖게 됩니다. 이러한 분기의 경우 트리 구성 다음 레벨로 계속 진행되지만 새로운 가지가 나타나지 않습니다. 변수 X 2의 값이 0인 단일 분기는 변수 X 3이 값 0과 1을 받는 두 개의 분기로 분기됩니다. 따라서 새 방정식을 추가할 때마다 세부 사항이 주어지면 하나의 솔루션이 추가됩니다. 원래의 첫 번째 방정식:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
6가지 솔루션이 있습니다. 이 방정식의 전체 의사결정 트리는 다음과 같습니다.

우리 시스템의 두 번째 방정식은 첫 번째 방정식과 유사합니다.

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

유일한 차이점은 방정식이 Y 변수를 사용한다는 것입니다. 이 방정식에도 6개의 해가 있습니다. 변수 X i에 대한 모든 해는 변수 Y j에 대한 모든 해와 결합될 수 있으므로, 총 수 36개의 솔루션이 있습니다.

구성된 의사결정 트리는 (분기 수에 따른) 솔루션 수뿐만 아니라 트리의 각 분기에 작성된 솔루션 자체도 제공합니다.

문제 19

아래 나열된 모든 조건을 만족하는 논리 변수 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

이 작업은 이전 작업을 수정한 것입니다. 차이점은 변수 X와 Y를 연결하는 또 다른 방정식이 추가된다는 것입니다.

방정식 X 1 → Y 1에서 X 1이 값 1을 가질 때(이러한 해가 하나 존재함) Y 1도 값 1을 갖습니다. 따라서 X 1과 Y 1이 값을 갖는 집합이 하나 있습니다. 1. X 1이 0과 같을 때 Y 1은 0과 1 모두 임의의 값을 가질 수 있습니다. 따라서 X 1이 0인 각 집합과 5개의 이러한 집합이 있는 것은 Y 변수가 있는 6개의 집합 모두에 해당합니다. 따라서 총 솔루션 수는 31개입니다.

문제 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

해결책: 기본 동등성을 기억하여 방정식을 다음과 같이 작성합니다.

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

의미의 순환 사슬은 변수가 동일하다는 것을 의미하므로 방정식은 다음 방정식과 동일합니다.

X 1 ‚ X 2 ‚ X 3 ‚ X 4 ‚ X 5 = 1

이 방정식에는 모든 X i가 1 또는 0일 때 두 가지 해가 있습니다.

문제 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

해결책: 문제 20에서와 마찬가지로 순환적 함의에서 항등식으로 이동하여 방정식을 다음 형식으로 다시 작성합니다.

(X 1 → X 2) ˄ (X 2 ‚ X 3 ‚ X 4) ˄ (X 4 → X 5) = 1

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

문제 22

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

((X 1 지구X 2) ˄ (X 3 지구X 4)) ˅(¬(X 1 지구X 2) ˄ ¬(X 3 지구X 4)) = 0

((X 3 지구X 4) ˄ (X 5 지구X 6)) ˅(¬(X 3 지구X 4) ˄ ¬(X 5 지구X 6)) = 0

((X 5 지구X 6) ˄ (X 7 ДX 8)) ˅(¬(X 5 지구X 6) ˄ ¬(X 7 ДX 8)) = 0

((X 7 ДX 8) ˄ (X 9 ∨X 10)) ˅(¬(X 7 ДX 8) ˄ ¬(X 9 ∨X 10)) = 0

답: 64

해결 방법: 다음과 같은 변수 변경을 도입하여 10개 변수에서 5개 변수로 이동해 보겠습니다.

Y1=(X1=X2); Y2=(X3=X4); Y 3 = (X 5 ñ X 6); Y4=(X7=X8); Y 5 = (X 9 ‚ X 10);

그러면 첫 번째 방정식은 다음과 같은 형식을 취합니다.

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

방정식은 다음과 같이 작성하여 단순화할 수 있습니다.

(Y 1 ‚ Y 2) = 0

전통적인 형식으로 이동하여 다음 형식으로 단순화한 후 시스템을 작성합니다.

¬(Y 1 ñ Y 2) = 1

¬(Y 2 ñ Y 3) = 1

¬(Y 3 ‚ Y 4) = 1

¬(Y 4 ñ Y 5) = 1

이 시스템의 의사결정 트리는 간단하며 변수 값이 교대로 나타나는 두 가지 분기로 구성됩니다.

원래 X 변수로 돌아가서, Y 변수의 각 값에 대해 X 변수에 2개의 값이 있으므로 Y 변수의 각 솔루션은 X 변수에 25개의 솔루션을 생성합니다. 두 가지 분기는 2 * 2를 생성합니다. 솔루션이 5개이므로 총 솔루션 수는 64개입니다.

보시다시피 방정식 시스템을 푸는 각 문제에는 고유한 접근 방식이 필요합니다. 일반적인 기술은 등가 변환을 수행하여 방정식을 단순화하는 것입니다. 일반적인 기술은 의사결정 트리를 구성하는 것입니다. 사용된 접근 방식은 가능한 변수 값의 모든 집합이 구성되지 않고 함수가 값 1(true)을 취하는 집합만 구성된다는 특징을 지닌 진리표 구성을 부분적으로 연상시킵니다. 제안된 문제에서는 완전한 결정 트리를 구축할 필요가 없는 경우가 많습니다. 예를 들어 문제 18에서와 같이 이미 초기 단계에서 각 후속 수준에서 새 분기의 모양 패턴을 설정할 수 있기 때문입니다. .

일반적으로 논리 방정식 시스템의 해를 찾는 문제는 좋은 수학적 연습입니다.

문제를 수동으로 해결하기 어려운 경우 방정식 및 방정식 시스템을 해결하기 위한 적절한 프로그램을 작성하여 컴퓨터에 솔루션을 맡길 수 있습니다.

그러한 프로그램을 작성하는 것은 어렵지 않습니다. 이러한 프로그램은 통합 상태 시험에서 제공되는 모든 작업에 쉽게 대처할 수 있습니다.

이상하게도 논리 방정식 시스템의 해를 찾는 작업은 컴퓨터에게는 어렵고 컴퓨터에는 한계가 있다는 것이 밝혀졌습니다. 컴퓨터는 변수 수가 20-30개인 문제에 아주 쉽게 대처할 수 있지만 더 큰 크기의 문제에 대해서는 오랫동안 생각하기 시작할 것입니다. 사실 집합 수를 지정하는 함수 2n은 n이 증가함에 따라 빠르게 증가하는 지수 함수입니다. 너무 빨라서 일반 개인용 컴퓨터로는 하루에 40개의 변수가 있는 작업을 처리할 수 없습니다.

논리 방정식을 풀기 위한 C# 언어 프로그램

논리 방정식을 풀기 위한 프로그램을 작성하는 것은 통합 상태 시험 테스트 문제에 대한 자신의 솔루션의 정확성을 확인하는 데 사용할 수 있기 때문에 여러 가지 이유로 유용합니다. 또 다른 이유는 이러한 프로그램이 통합 상태 시험의 카테고리 C 작업 요구 사항을 충족하는 프로그래밍 작업의 훌륭한 예이기 때문입니다.

프로그램 구축 아이디어는 간단합니다. 가능한 모든 변수 값 세트에 대한 완전한 검색을 기반으로합니다. 주어진 논리 방정식 또는 방정식 시스템에 대해 변수의 수 n이 알려져 있으므로 정렬해야 하는 세트의 수도 2n개로 알려져 있습니다. C# 언어의 기본 기능인 부정, 분리, 결합 및 항등식을 사용하면 주어진 변수 세트에 대해 논리 방정식 또는 방정식 시스템에 해당하는 논리 함수의 값을 계산하는 프로그램을 작성하는 것이 어렵지 않습니다. .

이러한 프로그램에서는 루프 본문에서 세트 수를 사용하여 세트 수를 기반으로 루프를 구축하고 세트 자체를 형성하고 이 세트의 함수 값을 계산해야 합니다. 값이 1이면 집합은 방정식에 대한 해를 제공합니다.

프로그램을 구현할 때 발생하는 유일한 어려움은 설정된 숫자를 기반으로 변수 값의 집합 자체를 생성하는 작업과 관련됩니다. 이 문제의 장점은 겉보기에 어려워 보이는 이 작업이 실제로는 이미 여러 번 발생한 간단한 문제로 귀결된다는 것입니다. 실제로, 0과 1로 구성된 숫자 i에 해당하는 변수 값 세트가 숫자 i의 이진 표현을 나타낸다는 것을 이해하는 것만으로도 충분합니다. 그래서 어려운 일집합 번호로 변수 값 집합을 얻는 것은 숫자를 이진법으로 변환하는 잘 알려진 문제로 귀결됩니다.

문제를 해결하는 C#의 함수는 다음과 같습니다.

///

/// 솔루션 수를 계산하는 프로그램

/// 논리 방정식(방정식 시스템)

///

/// 논리 함수 - 메소드,

/// DF 대리인이 서명을 지정함

///

/// 변수의 수

/// 솔루션 수

static int SolveEquations(DF fun, int n)

부울 세트 = 새로운 bool[n];

int m = (int)Math.Pow(2, n); //세트 수

int p = 0, q = 0, k = 0;

//세트 수로 검색 완료

for (int i = 0; i< m; i++)

//다음 세트의 형성 - 세트,

//숫자 i의 이진 표현으로 지정됨

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//세트의 함수 값을 계산합니다.

프로그램을 이해하기 위해서는 프로그램 아이디어에 대한 설명과 본문에 나오는 설명이 충분했으면 좋겠습니다. 나는 주어진 함수의 제목에 대해서만 설명하는 데 중점을 둘 것이다. SolveEquations 함수에는 두 개의 입력 매개변수가 있습니다. fun 매개변수는 풀려는 방정식 또는 방정식 시스템에 해당하는 논리 함수를 지정합니다. n 매개변수는 재미있는 변수의 수를 지정합니다. 결과적으로 SolveEquations 함수는 논리 함수의 해 수, 즉 함수가 true로 평가되는 집합의 수를 반환합니다.

일부 함수 F(x)에 산술, 문자열 또는 논리 유형의 변수인 입력 매개변수 x가 있는 경우 학생들에게 흔히 발생합니다. 우리의 경우에는 더 많은 것을 사용합니다. 강력한 디자인. SolveEquations 함수는 고차 함수, 즉 F(f) 유형의 함수를 참조하며, 해당 매개변수는 단순 변수일 뿐만 아니라 함수일 수도 있습니다.

SolveEquations 함수에 매개변수로 전달될 수 있는 함수 클래스는 다음과 같이 지정됩니다.

위임 bool DF(bool vars);

이 클래스는 vars 배열에 의해 지정된 논리 변수 값 세트를 매개변수로 전달하는 모든 함수를 소유합니다. 결과는 이 세트의 함수 값을 나타내는 부울 값입니다.

마지막으로 SolveEquations 함수를 사용하여 여러 논리 방정식 시스템을 푸는 프로그램이 있습니다. SolveEquations 함수는 아래 ProgramCommon 클래스의 일부입니다.

수업 프로그램공통

위임 bool DF(bool vars);

정적 무효 Main(문자열 인수)

Console.WriteLine("그리고 함수 - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("이 함수에는 51개의 솔루션이 있습니다. - " +

SolveEquations(Fun51, 5));

Console.WriteLine("이 함수에는 53개의 솔루션이 있습니다. - " +

SolveEquations(Fun53, 10));

정적 bool FunAnd(bool vars)

반환 변수 && vars;

정적 bool Fun51(부울 변수)

f = f && (!vars || vars);

정적 bool Fun53(부울 변수)

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

이 프로그램의 솔루션 결과는 다음과 같습니다.

독립적인 작업을 위한 10가지 작업

세 가지 기능 중 동일한 기능은 무엇입니까?
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
주어진 진리표의 일부는 다음과 같습니다.

× 1	X 2	X 3	X 4	에프
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

이 조각은 세 가지 기능 중 어느 기능에 해당합니까?

(X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
심사위원은 3명으로 구성됩니다. 배심원 위원장이 최소한 한 명의 배심원 구성원의 지지를 받아 투표하면 결정이 내려집니다. 그렇지 않으면 결정이 내려지지 않습니다. 의사결정 프로세스를 공식화하는 논리적 기능을 구성합니다.
동전을 4번 던져 앞면이 3번 나오면 X가 Y를 이깁니다. X의 보수를 설명하는 논리 함수를 정의합니다.
문장의 단어는 1부터 시작하여 번호가 매겨집니다. 다음 규칙이 충족되면 문장이 올바르게 구성된 것으로 간주됩니다.
1. 짝수 단어가 모음으로 끝나면 다음 단어도 모음으로 시작해야 합니다.
2. 홀수 단어가 자음으로 끝나는 경우 다음 단어가 있으면 자음으로 시작하고 모음으로 끝나야 합니다.
  다음 중 올바르게 구성된 문장은 무엇입니까?
3. 엄마는 마샤를 비누로 씻었습니다.
4. 리더는 언제나 모델이다.
5. 진실은 좋지만 행복은 더 좋습니다.
방정식에는 몇 개의 해가 있습니까?
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
방정식에 대한 모든 해를 나열합니다.
(a → b) → c = 0
다음 연립방정식에는 몇 개의 해가 있습니까?
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1
방정식에는 몇 개의 해가 있습니까?
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

문제에 대한 답변:

함수 b와 c는 동일합니다.
조각은 함수 b에 해당합니다.
심사위원장이 결정에 "찬성" 투표할 때 논리 변수 P의 값을 1로 설정합니다. 변수 M 1 과 M 2 는 심사위원들의 의견을 나타냅니다. 긍정적인 결정을 지정하는 논리 함수는 다음과 같이 작성할 수 있습니다.
P ˄ (M 1 ˅ M 2)
논리 변수 Pi가 다음과 같을 때 값 1을 취하도록 합니다. i 번째 던지기동전은 앞면이 나옵니다. 보수 X를 지정하는 논리 함수는 다음과 같이 작성할 수 있습니다.
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
문장 ㄴ.
방정식에는 3가지 해가 있습니다: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

이 자료에는 컴퓨터 과학 통합 상태 시험의 작업 B15(2015년 23호)에서 논리 방정식 및 논리 방정식 시스템을 해결하는 방법을 제시하는 프레젠테이션이 포함되어 있습니다. 이 과제는 통합고시 과제 중 가장 어려운 과제 중 하나로 알려져 있다. 프레젠테이션은 전문 수업에서 "논리"라는 주제에 대한 수업을 할 때뿐만 아니라 통합 상태 시험을 준비할 때 유용할 수 있습니다.

다운로드:

시사:

프레젠테이션 미리보기를 사용하려면 Google 계정을 만들고 로그인하세요: https://accounts.google.com

슬라이드 캡션:

작업 B15(논리 방정식 시스템) 솔루션 Vishnevskaya M.P., MAOU "Gymnasium No. 3" 2013년 11월 18일, Saratov

Task B15는 컴퓨터 공학 통합 상태 시험에서 가장 어려운 문제 중 하나입니다!!! 다음 기술이 테스트됩니다. 논리 변수가 포함된 표현식을 변환합니다. 주어진 논리 변수 세트가 참인 논리 변수 값 세트를 자연어로 설명합니다. 주어진 조건을 만족하는 이진 집합의 수를 셉니다. 가장 어려운 이유는... 이를 수행하는 방법에 대한 공식적인 규칙은 없으며 추측이 필요합니다.

없이는 할 수 없는 것!

기호 결합: A /\ B , A  B , AB , A &B, A 및 B 분리: A \ / B , A + B , A | B , A 또는 B 부정: ‚ A , A, not A 등가: A  B, A  B, A  B 배타적 “또는”: A  B , A xor B

변수 대체 방법 아래 나열된 모든 조건을 만족하는 논리 변수 x1, x2, ..., x9, x10의 값 집합이 몇 개나 존재합니까? ((x1 ‚ x2) \/ (x3 ‚ x4)) /\ (¬(x1 ‚ x2) \/ ¬(x3 ‚ x4)) = 1 ((x3 ‚ x4) \\ (x5 ‚ x6)) /\ (¬(x3 ‚ x4) \\/ ¬(x5 DF x6)) = 1 ((x5 ‚ x6 ) \/ (x7 ‚ x8)) /\ (¬(x5 ‚ x7) \/ ¬(x7 ‚ x8)) = 1 ((x7 ‚ x8) \/ (x9 ė x10)) /\ (¬(x7 ė x8) \/ ¬(x9 ė x10)) = 1 대답은 다음과 같은 모든 다른 집합 x1, x2, …, x9, x10을 나열할 필요는 없습니다. 이 평등 시스템이 유지됩니다. 답변으로 해당 세트의 수를 표시해야 합니다(데모 버전 2012).

풀이 단계 1. 변수를 변경하여 단순화 t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 단순화 후: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 방정식 중 하나를 고려하십시오: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 분명히 변수 중 하나가 0이고 다른 하나가 1인 경우에만 =1입니다. .접합과 분리를 통한 XOR 연산을 공식으로 표현해보자: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ל t2) =1 ¬(t1 Ā t2) =1 ¬( t2 ‚ t3) =1 ¬(t3 ‚ t4) =1 ¬(t4 ‚ t5) =1

2 단계. 시스템 분석 ¬(t1 ė t2) =1 ¬(t2 ė t3) =1 ¬(t3 ė t4) =1 ¬(t4 t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .에게. tk = x2k-1 Д x2k (t1 = x1  x2 ,….), tk의 각 값은 x2k-1 및 x2k 값의 두 쌍에 해당합니다. 예를 들어 tk =0은 두 쌍에 해당합니다. - (0 ,1) 및 (1, 0) 및 tk =1 – (0,0) 및 (1,1) 쌍.

3단계. 솔루션 수를 계산합니다. 각 t에는 2개의 해가 있고, t의 수는 5입니다. 따라서. 변수 t에 대해 2 5 = 32개의 해가 있습니다. 그러나 각 t에 대해 한 쌍의 해 x가 대응됩니다. 즉, 원래 시스템에는 2*32 = 64개의 솔루션이 있습니다. 답: 64

해의 일부를 제거하는 방법 아래 나열된 모든 조건을 충족하는 논리 변수 x1, x2, ..., x5, y1,y2,..., y5의 값 세트가 몇 개나 존재합니까? (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. 대답은 이 등식 시스템이 유지되는 모든 다른 집합 x1, x2, ..., x5, y 1 , y2, ... , y5를 나열할 필요가 없습니다. 답은 그러한 세트의 수를 나타내야 합니다.

해결책. 1 단계. 순차적 솔루션방정식 x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 첫 번째 방정식은 1과 같은 여러 함축 연산의 결합입니다. 즉, 각각의 의미는 사실입니다. 이 의미는 1  0인 한 가지 경우에만 거짓이고, 다른 모든 경우(0  0, 0  1, 1  1)에서는 연산이 1을 반환합니다. 이를 표 형식으로 작성해 보겠습니다.

1 단계. 방정식 T.o의 순차적 해법 x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111)에 대해 6개 세트의 솔루션을 얻었습니다. 비슷하게 추론하면 y1, y2, y3, y4, y5에 대해 동일한 솔루션 세트가 있다는 결론에 도달합니다. 왜냐하면 이 방정식은 독립적입니다. 즉, 공통 변수가 없으면 이 방정식 시스템의 해(세 번째 방정식을 고려하지 않음)는 6 * 6 = 36개의 "X'와 'Y' 쌍이 됩니다. 세 번째 방정식을 생각해 보세요: y5→ x5 =1 해는 쌍입니다: 0 0 0 1 1 1 쌍은 해가 아닙니다: 1 0

얻은 해를 비교해 보겠습니다. y5 =1, x5=0은 적합하지 않습니다. 그러한 쌍이 5개 있습니다. 시스템에 대한 솔루션 수: 36-5= 31. 답변: 31개의 조합론이 필요했습니다!!!

동적 프로그래밍 방법 논리 방정식 x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1에는 몇 가지 다른 해가 있습니까? 여기서 x 1, x 2, …, x 6은 논리 변수입니다. 대답은 이러한 동등성이 유지되는 다양한 변수 값 세트를 모두 나열할 필요는 없습니다. 답변으로 해당 세트의 수량을 표시해야 합니다.

솔루션 Step1. 조건 분석 방정식의 왼쪽에는 함축 연산이 순차적으로 작성되어 있으며 우선 순위는 동일합니다. 다시 작성해 보겠습니다. ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! 각 후속 변수는 이전 변수가 아니라 이전 의미의 결과에 따라 달라집니다!

2 단계. 패턴 공개 첫 번째 의미인 X 1 → X 2를 고려해 보겠습니다. 진리표: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 하나의 0에서 2 단위를 얻었고 1에서 우리는 하나의 0과 하나의 1을 얻었습니다. 0은 하나와 1은 세 개뿐입니다. 이것이 첫 번째 작업의 결과입니다.

2 단계. 패턴 공개 첫 번째 연산의 결과에 x 3을 연결하면 다음을 얻습니다. F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 2개의 0 – 2개의 1에서 각 1(3개가 있음)에서 하나의 0과 하나의 1(3+3)

3단계. 공식 T.o 도출 변수가 i개인 방정식에 대해 0의 개수 N i와 1의 개수 E i를 계산하는 공식을 만들 수 있습니다.

4단계. 표 채우기 위 공식을 사용하여 0과 1의 수를 계산하면서 i = 6에 대해 왼쪽에서 오른쪽으로 표를 채워 보겠습니다. 표는 이전 열에서 다음 열이 어떻게 구성되는지 보여줍니다. 변수 수 1 2 3 4 5 6 0의 수 N i 1 1 3 5 11 21 일의 수 E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 정답: 43

논리식의 단순화를 이용한 방법 방정식에 ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 여기서 J, K, L, M, N은 논리 변수입니까? 대답은 이러한 동등성이 유지되는 J, K, L, M 및 N의 다양한 값 세트를 모두 나열할 필요는 없습니다. 답변으로 해당 세트의 수를 표시해야 합니다.

해법 J → K = ¬ J  K 변수의 변화를 도입해 봅시다: J → K=A, M  N  L =B 변화를 고려하여 방정식을 다시 작성해 봅시다: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. 당연히 A와 B의 동일한 값에 대해 A  B 6. 마지막 의미 M → J =1 이는 다음과 같은 경우에 가능합니다: M= J=0 M=0, J=1 M=J=1

솔루션 때문에 A  B, 그러면 M=J=0일 때 1 + K=0이 됩니다. 해결책이 없습니다. M=0, J=1일 때 0 + K=0, K=0을 얻고 N과 L은 임의이며 4개의 해: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

풀이 10. M=J=1일 때 0+K=1 *N * L 또는 K=N*L을 얻습니다. 4개의 해: 11. 총 4+4=8개의 해가 있습니다 답: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

정보 출처: O.B. 보고몰로바, D.Yu. Usenkov. B15: 새로운 작업과 새로운 솔루션 // 정보학, No. 6, 2012, p. 35 – 39. K.Yu. 폴리아코프. 논리 방정식 // 정보학, No. 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [전자 자료]. http://kpolyakov.narod.ru/school/ege.htm, [전자 자료].

n 변수의 논리 함수라고 하자. 논리 방정식은 다음과 같습니다.

상수 C는 1 또는 0의 값을 갖습니다.

논리 방정식은 0부터 다양한 해를 가질 수 있습니다. C가 1이면 해는 함수 F가 참(1) 값을 취하는 진리표의 모든 변수 집합입니다. 나머지 세트는 C가 0인 방정식의 해입니다. 항상 다음 형식의 방정식만 고려할 수 있습니다.

실제로 방정식을 다음과 같이 가정해 보겠습니다.

이 경우, 우리는 동등한 방정식으로 갈 수 있습니다:

k개의 논리 방정식 시스템을 고려해보세요.

시스템의 해는 시스템의 모든 방정식을 만족시키는 변수의 집합입니다. 논리 함수 측면에서 논리 방정식 시스템에 대한 해를 얻으려면 논리 함수 Ф가 참인 집합을 찾아야 하며, 이는 원래 함수의 결합을 나타냅니다.

변수의 수가 작은 경우(예: 5개 미만) 함수에 대한 진리표를 구성하는 것이 어렵지 않습니다. 이를 통해 시스템에 몇 개의 솔루션이 있고 솔루션을 제공하는 세트가 무엇인지 말할 수 있습니다.

시험에 제시된 문제에서 해결책은 일반적으로 방정식 시스템의 세부 사항을 고려하는 데 기반을 둡니다. 거듭 말씀드리지만, 변수 세트에 대한 모든 옵션을 시도하는 것 외에는 문제를 해결할 수 있는 일반적인 방법이 없습니다. 솔루션은 시스템의 특성을 기반으로 구축되어야 합니다. 알려진 논리 법칙을 사용하여 방정식 시스템의 예비 단순화를 수행하는 것이 유용한 경우가 많습니다. 이 문제를 해결하는 또 다른 유용한 기술은 다음과 같습니다. 우리는 모든 집합에 관심이 있는 것이 아니라 함수의 값이 1인 집합에만 관심이 있습니다. 완전한 진리표를 작성하는 대신 그 아날로그인 이진 의사결정 트리를 구축할 것입니다. 이 트리의 각 분기는 하나의 솔루션에 해당하며 함수의 값이 1인 집합을 지정합니다. 의사결정 트리의 분기 수는 방정식 시스템에 대한 솔루션 수와 일치합니다.

몇 가지 문제의 예를 사용하여 이진 의사결정 트리가 무엇인지, 어떻게 구축되는지 설명하겠습니다.

문제 18

두 방정식의 시스템을 만족하는 논리 변수 x1, x2, x3, x4, x5, y1, y2, y3, y4, y5의 서로 다른 값 집합은 몇 개입니까?

답변: 시스템에는 36가지의 서로 다른 솔루션이 있습니다.

해결책: 연립방정식에는 두 개의 방정식이 포함됩니다. 5개의 변수에 따라 첫 번째 방정식의 해 개수를 찾아보겠습니다. 첫 번째 방정식은 5개 방정식의 시스템으로 간주될 수 있습니다. 표시된 대로 방정식 시스템은 실제로 논리 함수의 결합을 나타냅니다. 반대의 진술도 마찬가지입니다. 조건의 결합은 방정식 시스템으로 간주될 수 있습니다.

첫 번째 방정식으로 간주될 수 있는 접속사의 첫 번째 항인 함축()에 대한 결정 트리를 구축해 보겠습니다. 이 트리를 그래픽으로 표현하면 다음과 같습니다.

트리는 방정식의 변수 수에 따라 두 가지 수준으로 구성됩니다. 첫 번째 수준은 첫 번째 변수를 설명합니다. 이 레벨의 두 분기는 이 변수의 가능한 값인 1과 0을 반영합니다. 두 번째 레벨에서 트리의 분기는 방정식이 true로 평가되는 변수의 가능한 값만 반영합니다. 방정식은 의미를 지정하므로 값이 1인 분기에는 이 분기에 값 1이 있어야 합니다. 값이 0인 분기는 0과 1과 동일한 값을 가진 두 개의 분기를 생성합니다. 트리는 세 가지 솔루션을 지정하며 그 중 의미는 값 1을 취합니다. 각 분기에서 해당 변수 값 세트가 작성되어 방정식에 대한 솔루션을 제공합니다.

이러한 집합은 다음과 같습니다: ((1, 1), (0, 1), (0, 0))

다음 방정식, 다음 의미를 추가하여 의사결정 트리를 계속 구축해 보겠습니다. 우리 방정식 시스템의 특수성은 시스템의 각각의 새로운 방정식이 이전 방정식의 변수 하나를 사용하여 하나의 새로운 변수를 추가한다는 것입니다. 변수는 이미 트리에 값을 가지고 있으므로 변수의 값이 1인 모든 분기에서 변수의 값도 1이 됩니다. 이러한 분기의 경우 트리 구성은 다음 단계로 계속됩니다. 하지만 새로운 가지가 나타나지 않습니다. 변수의 값이 0인 단일 분기는 변수가 0과 1의 값을 받는 두 개의 분기로 분기됩니다. 따라서 특정성을 고려하여 새 방정식을 추가할 때마다 하나의 솔루션이 추가됩니다. 원래의 첫 번째 방정식:

6가지 솔루션이 있습니다. 이 방정식의 전체 의사결정 트리는 다음과 같습니다.

우리 시스템의 두 번째 방정식은 첫 번째 방정식과 유사합니다.

유일한 차이점은 방정식이 Y 변수를 사용한다는 것입니다. 이 방정식에도 6개의 해가 있습니다. 각 변수해는 각 변수해와 결합될 수 있으므로 총 솔루션 개수는 36개이다.

구성된 의사결정 트리는 (분기 수에 따른) 솔루션 수뿐만 아니라 트리의 각 분기에 작성된 솔루션 자체도 제공합니다.

문제 19

아래 나열된 모든 조건을 만족하는 논리 변수 x1, x2, x3, x4, x5, y1, y2, y3, y4, y5의 값 집합은 몇 개입니까?

이 작업은 이전 작업을 수정한 것입니다. 차이점은 변수 X와 Y를 연결하는 또 다른 방정식이 추가된다는 것입니다.

값이 1일 때(그러한 솔루션이 하나 존재함) 값은 1이라는 방정식을 따릅니다. 따라서 값이 1인 하나의 세트가 있습니다. 0과 같을 때, 0과 1 모두 임의의 값을 갖습니다. 따라서 가 있는 각 세트는 0과 같고 5개의 세트가 있으며 변수 Y가 있는 6개의 세트 모두에 해당합니다. 따라서 총 솔루션 수는 31개입니다.

문제 20

해결책: 기본 동등성을 기억하여 방정식을 다음과 같이 작성합니다.

의미의 순환 사슬은 변수가 동일하다는 것을 의미하므로 방정식은 다음 방정식과 동일합니다.

이 방정식은 모두 1 또는 0일 때 두 가지 해를 갖습니다.

문제 21

방정식에는 몇 개의 해가 있습니까?

해결책: 문제 20에서와 마찬가지로 순환적 함의에서 항등식으로 이동하여 방정식을 다음 형식으로 다시 작성합니다.

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

문제 22

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

수업 주제: 논리 방정식 풀기

교육적인 - 논리 방정식을 푸는 방법을 연구하고, 논리 방정식을 푸는 기술을 개발하고, 진리표를 사용하여 논리 표현을 구성합니다.

발달 - 학생들의 인지적 관심 발달을 위한 조건을 조성하고, 기억력, 주의력, 주의력 발달을 촉진합니다. 논리적 사고;

교육적인 : 다른 사람의 의견을 경청하는 능력을 키우고,최종 결과를 달성하기 위한 의지와 인내를 키우는 것입니다.

수업 유형: 결합 레슨

장비: 컴퓨터, 멀티미디어 프로젝터, 프레젠테이션 6.

수업 중에는

기본 지식의 반복 및 업데이트. 시험 숙제(10 분)

이전 수업에서 우리는 논리 대수학의 기본 법칙을 익히고 이러한 법칙을 사용하여 논리 표현을 단순화하는 방법을 배웠습니다.

논리식을 단순화하는 방법에 대한 숙제를 확인해 봅시다:

1. 다음 중 논리적 조건을 만족하는 단어는 무엇입니까?

(첫 글자 자음→두 번째 글자 자음)٨ (마지막 모음 → 끝에서 두 번째 모음)? 그러한 단어가 여러 개인 경우 가장 작은 단어를 표시하십시오.

1) 안나 2) 마리아 3) 올레그 4) 스테판

다음 표기법을 소개하겠습니다.

A – 첫 글자 자음

B – 두 번째 글자 자음

S – 마지막 글자 모음

D – 끝에서 두 번째 모음 문자

표현을 해보자:

테이블을 만들어 봅시다:

2. 어떤 논리 표현식이 표현식과 동일한지 나타냅니다.

원래 표현식과 제안된 옵션의 기록을 단순화해 보겠습니다.

3. 표현식 F의 진리표 일부가 주어지면:

F와 일치하는 표현식은 무엇입니까?

지정된 인수 값에 대해 이러한 표현식의 값을 결정해 보겠습니다.

수업 주제 소개, 새로운 자료 발표 (30 분)

우리는 논리의 기초를 계속 공부하고 있으며 오늘 수업의 주제는 "논리 방정식 풀기"입니다. 이 주제를 공부한 후에는 논리 방정식을 푸는 기본 방법을 배우고 논리 대수학 언어를 사용하여 이러한 방정식을 푸는 기술과 진리표를 사용하여 논리 표현식을 구성하는 능력을 습득하게 됩니다.

1. 논리 방정식 풀기

(¬K M) → (¬L 중 아니오) =0

답을 변수 K, L, M, N의 값(순서대로) 4개의 문자열로 작성하세요. 따라서 예를 들어 1101행은 K=1, L=1, M=0, N=1이라는 사실에 해당합니다.

해결책:

표현을 바꿔보자(¬K  M) → (¬L  중  N)

두 항이 모두 거짓인 경우 표현식은 거짓입니다. 두 번째 항은 M =0, N =0, L =1인 경우 0과 같습니다. 첫 번째 항에서는 M = 0이므로 K = 0이고,
.