logo

이산 수학의 논리적 등가 법칙

X와 Y라는 두 개의 복합 명제가 있다고 가정합니다. 이는 두 명제의 진리표가 해당 열에 동일한 진리값을 포함하는 경우에만 논리적 동등성으로 알려집니다. 기호 = 또는 ⇔의 도움으로 논리적 동등성을 나타낼 수 있습니다. 따라서 X = Y 또는 X ⇔ Y는 이러한 진술의 논리적 동등성이 됩니다.

논리적 동등성 정의의 도움으로 복합문 X와 Y가 논리적 동등성인 경우 이 경우 X ⇔ Y는 동어반복이 되어야 함을 명확하게 했습니다.

논리적 등가의 법칙

이 법칙에서는 'AND'와 'OR' 기호를 사용하여 논리적 등가법칙을 설명하겠습니다. 여기서 AND는 ∧ 기호를 사용하여 표시하고 OR은 ∨ 기호를 사용하여 표시합니다. 논리적 등가의 법칙에는 다음과 같은 다양한 법칙이 있습니다.

멱등법칙:

멱등법칙에서는 단일 명령문만 사용합니다. 이 법칙에 따르면 두 개의 동일한 명령문을 ∧(and) 및 ∨(or) 기호로 결합하면 결과 명령문은 명령문 자체가 됩니다. 복합 진술 P가 있다고 가정합니다. 다음 표기법은 멱등 법칙을 나타내는 데 사용됩니다.

 P ∨ P ? P P ∧ P ? P 

이 법칙의 진리표는 다음과 같습니다.

피 ∨ 피 피 ∧ 피
에프 에프 에프 에프

이 테이블에는 P, P ∨ P 및 P ∧ P 열에 동일한 진리값이 포함되어 있습니다.

따라서 P ∨ P = P 및 P ∧ P = P라고 말할 수 있습니다.

교환법칙:

두 진술은 교환법칙을 보여주기 위해 사용됩니다. 이 법칙에 따르면 두 명제를 ∧(and) 또는 ∨(or) 기호로 결합하면 명제의 위치를 ​​바꿔도 결과는 동일합니다. P와 Q라는 두 개의 진술이 있다고 가정합니다. 진술 P와 Q가 모두 거짓일 때 이 진술의 명제는 거짓이 됩니다. 다른 모든 경우에는 사실입니다. 교환 법칙을 나타내기 위해 다음 표기법이 사용됩니다.

 P ∨ Q ? Q ∨ P P ∧ Q ? Q ∧ P 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

피 ∨ Q Q ∨ 피
에프
에프
에프 에프 에프 에프

이 테이블에는 P ∨ Q 및 Q ∨ P 열에 동일한 진리값이 포함되어 있습니다.

따라서 P∨Q라고 말할 수 있다. Q ∨ 피.

P ∧ Q 를 증명할 수 있는 것과 같습니다. Q ∧ P.

DS에 스택

결합법칙:

세 가지 진술은 결합법칙을 표시하는 데 사용됩니다. 이 법칙에 따르면 ∧(and) 또는 ∨(or) 기호를 사용하여 괄호를 사용하여 세 개의 명령문을 결합하면 괄호의 순서를 변경하더라도 결과 명령문은 동일합니다. 즉, 이 법은 그룹화 또는 연합과 무관합니다. P, Q, R이라는 세 가지 진술이 있다고 가정합니다. P, Q, R이 거짓일 때 이 진술들의 명제는 거짓이 됩니다. 다른 모든 경우에는 사실입니다. 결합법칙을 나타내기 위해 다음 표기법이 사용됩니다.

 P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R P ∧ (Q ∧ R) ? (P ∧ Q) ∧ R 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

아르 자형 피 ∨ Q Q ∨ R (P ∨ Q) ∨ R P ∨ (Q ∨ R)
에프
에프
에프 에프 에프
에프
에프 에프
에프 에프 에프
에프 에프 에프 에프 에프 에프 에프

이 테이블에는 P ∨ (Q ∨ R) 및 (P ∨ Q) ∨ R 열에 동일한 진리값이 포함되어 있습니다.

따라서 P ∨ (Q ∨ R) ? (P ∨ Q) ∨ R.

P ∧ (Q ∧ R) 을 증명할 수 있는 것과 동일합니까? (P ∧ Q) ∧ R

분배법칙:

세 가지 진술은 분배법칙을 보여주기 위해 사용됩니다. 이 법칙에 따르면 ∨(OR) 기호로 된 명제와 ∧(AND) 기호로 결합된 다른 두 명제를 결합하면, 두 명제를 별도로 결합하더라도 결과는 동일합니다. ∨(OR) 기호를 사용하고 결합된 문장을 ∧(AND)로 결합합니다. 세 개의 진술 P, Q, R이 있다고 가정합니다. 다음 표기법은 분배 법칙을 나타내는 데 사용됩니다.

P ∨ (Q ∧ R) ? (P ∨ Q) ∧ (P ∨ R)

P ∧ (Q ∨ R) ? (P ∧ Q) ∨ (P ∧ R)

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

아르 자형 Q ∧ R P∨(Q ∧R) 피 ∨ Q P ∨ R (P ∨ Q) ∧ (P ∨ R)
에프 에프
에프 에프
에프 에프 에프
에프
에프 에프 에프 에프 에프 에프
에프 에프 에프 에프 에프 에프
에프 에프 에프 에프 에프 에프 에프 에프

이 테이블에는 P ∨ (Q ∧ R) 및 (P ∨ Q) ∧ (P ∨ R) 열에 동일한 진리값이 포함되어 있습니다.

따라서 P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)이라고 말할 수 있습니다.

P ∧ (Q ∨ R) 을 증명할 수 있는 것과 동일합니까? (P ∧ Q) ∨ (P ∧ R)

신원법:

단일 진술은 동일성 법칙을 표시하는 데 사용됩니다. 이 법칙에 따르면, 진술과 참값을 ∨(또는) 기호와 결합하면 참값이 생성됩니다. 명령문과 False 값을 ∧(and) 기호와 결합하면 명령문 자체가 생성됩니다. 마찬가지로 반대 기호를 사용하여 이 작업을 수행합니다. 즉, 진술과 True 값을 기호 ∧(and)와 결합하면 진술 자체가 생성되고, 진술과 False 값을 기호 ∨(or)와 결합하면 진술 자체가 생성됩니다. 잘못된 값. 참 값 T와 거짓 값 F인 복합 명제 P가 있다고 가정합니다. 항등법칙을 나타내기 위해 다음 표기법이 사용됩니다.

 P ∨ T ? T and P ∨ F ? P P ∧ T ? P and P ∧ F ? F 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

에프 피 ∨ 티 P ∨ F
에프
에프 에프 에프

이 테이블은 P ∨ T 및 T 열에 동일한 진리값을 포함합니다. 따라서 P ∨ T = T라고 말할 수 있습니다. 마찬가지로 이 테이블은 P ∨ F 및 P 열에도 동일한 진리값을 포함합니다. P ∨ F = P라고 말할 수 있습니다.

P ∧ T 를 증명할 수 있는 것과 동일합니까? P와 P ∧ F ? 에프

보완법:

단일문은 보수 법칙에 사용됩니다. 이 법칙에 따르면, ∨(or) 기호를 사용하여 보수문과 진술을 결합하면 True 값이 생성되고, 이러한 진술을 ∧(and) 기호와 결합하면 False 값이 생성됩니다. 값. 참값을 부정하면 거짓값이 생성되고, 거짓값을 부정하면 참값이 생성됩니다.

보수 법칙을 나타내기 위해 다음 표기법이 사용됩니다.

 P ∨ ¬P ? T and P ∧ ¬P ? F ¬T ? F and ¬F ? T 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

¬P ¬T 에프 ¬F 피 ∨ ¬P 피 ∧ ¬P
에프 에프 에프 에프
에프 에프 에프 에프

이 테이블은 P ∨ ¬P 및 T 열에 동일한 진리값을 포함합니다. 따라서 P ∨ ¬P = T라고 말할 수 있습니다. 마찬가지로 이 테이블은 P ∧ ¬P 및 T 열에도 동일한 진리값을 포함합니다. F. 따라서 P ∧ ¬P = F라고 말할 수 있습니다.

이 테이블은 ¬T 및 F 열에 동일한 진리값을 포함합니다. 따라서 ¬T = F라고 말할 수 있습니다. 마찬가지로 이 테이블은 ¬F 및 T 열에 동일한 진리값을 포함합니다. 따라서 다음과 같이 말할 수 있습니다. ¬F = T.

이중 부정 법칙 또는 진화 법칙

이중 부정의 법칙을 나타내기 위해 단일 진술이 사용됩니다. 이 법칙에 따르면, 부정 명제를 부정하면 결과 명제는 명제 자체가 됩니다. 명제 P와 부정 명제 ¬P가 있다고 가정합니다. 다음 표기법은 이중 부정 법칙을 나타내는 데 사용됩니다.

 ¬(¬P) ? P 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

아날로그 통신
¬P ¬(¬P)
에프
에프 에프

이 테이블에는 ¬(¬P) 및 P 열에 동일한 진리값이 포함되어 있습니다. 따라서 ¬(¬P) = P라고 말할 수 있습니다.

모건의 법칙에서:

두 진술은 De Morgan의 법칙을 보여주기 위해 사용됩니다. 이 법칙에 따르면 두 명제를 ∧(AND) 기호로 결합한 다음 이 결합된 명제에 대해 부정을 수행하면 두 명제의 부정을 ∨( 기호로 별도로 결합하더라도 결과 명제는 동일합니다. 또는). P와 Q라는 두 개의 복합 진술이 있다고 가정합니다. 다음 표기법은 De Morgan의 법칙을 나타내는 데 사용됩니다.

 ¬(P ∧ Q) ? ¬P ∨ ¬Q ¬(P ∨ Q) ? ¬P ∧ ¬Q 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

¬P ¬Q 피 ∧ Q ¬(P ∧ Q) ¬ P ∨ ¬Q
에프 에프 에프 에프
에프 에프 에프
에프 에프 에프
에프 에프 에프

이 테이블에는 ¬(P ∧ Q) 및 ¬ P ∨ ¬Q 열에 동일한 진리값이 포함되어 있습니다. 따라서 ¬(P ∧ Q) = ¬ P ∨ ¬Q라고 말할 수 있습니다.

¬(P ∨ Q) 를 증명할 수 있는 것과 동일합니까? ¬P ∧ ¬Q

흡수 법칙:

두 진술은 흡수법칙을 보여주기 위해 사용됩니다. 이 법칙에 따르면, ∨(OR) 기호로 명제 P를 동일한 명제 P와 ∧(AND) 기호와 결합된 다른 명제 Q와 결합하면 결과 명제는 첫 번째 명제 P가 됩니다. 기호를 교환하면 동일한 결과가 생성됩니다. P와 Q라는 두 개의 복합 진술이 있다고 가정합니다. 다음 표기법은 흡수 법칙을 나타내는 데 사용됩니다.

 P ∨ (P ∧ Q) ? P P ∧ (P ∨ Q) ? P 

이러한 표기법에 대한 진리표는 다음과 같이 설명됩니다.

피 ∧ Q 피 ∨ Q P ∨ (P ∧ Q) P ∧ (P ∨ Q)
에프 에프
에프 에프 에프 에프
에프 에프 에프 에프 에프 에프

이 표에는 P ∨ (P ∧ Q) 및 P 열에 동일한 진리값이 포함되어 있습니다. 따라서 P ∨ (P ∧ Q) ? 피.

마찬가지로 이 테이블에는 P ∧ (P ∨ Q) 및 P 열에도 동일한 진리값이 포함되어 있습니다. 따라서 P ∧ (P ∨ Q) ? 피.

논리적 동등성의 예

논리적 동등성의 다양한 예가 있습니다. 그 중 일부는 다음과 같이 설명됩니다.

예시 1: 이 예에서는 다음과 같이 설명되는 명령문의 동등성 속성을 설정합니다.

피 → q ? ¬p ∨ q

해결책:

우리는 다음과 같이 설명되는 진리표를 사용하여 이를 증명할 것입니다.

¬p 피 → q ¬p ∨ q
에프
에프 에프 에프 에프
에프
에프 에프

이 테이블에는 p → q 및 ¬p ∨ q 열에 동일한 진리값이 포함되어 있습니다. 따라서 우리는 p → q라고 말할 수 있습니다. ¬p ∨ q.

예 2: 이 예에서는 다음과 같이 설명되는 명령문의 동등성 속성을 설정합니다.

P ⇔ Q ? ( P → Q ) ∧ ( Q → P )

해결책:

피 → Q Q → 피 P ⇔ Q ( P → Q ) ∧ ( Q → P )
에프 에프 에프 에프
에프 에프 에프 에프
에프 에프

이 테이블에는 P ← Q 및 (P → Q) ∧ (Q → P) 열에 동일한 진리값이 포함되어 있습니다. 따라서 P ⇔ Q라고 말할 수 있습니다. (P → Q) ∧ (Q → P).

예시 3: 이 예에서는 동등한 속성을 사용하여 다음 진술을 증명할 것입니다.

피 ← q ? ( p ∧ q ) ∨ ( ¬ p ∧ ¬q )

해결책:

이를 증명하기 위해 위에서 설명한 법칙 중 일부를 사용하고 이 법칙에서 다음을 얻습니다.

피 ← q ? (¬p ∨ q) ∧ (¬q ∨ p) ..........(1)

이제 위 방정식에서 교환법칙을 사용하여 다음을 얻습니다.

? (p ∨ q) ∧ (p ∨ ¬q)

이제 이 방정식에서 분배 법칙을 사용하여 다음을 얻습니다.

? (¬ p ∧ (p ∨ ¬q)) ∨ (q ∧ (p ∨ ¬q))

이제 우리는 이 방정식에 분배법칙을 사용하여 다음을 얻습니다.

? (p ∧ p) ∨ (p ∧ ¬q) ∨ (q ∧ p) ∨ (q ∧ ¬q)

이제 이 방정식에 보수법칙을 사용하여 다음을 얻습니다.

? F ∨ (¬p ∧ ¬q) ∨ (q ∧ p) ∨ F

이제 우리는 항등법칙을 사용하여 다음을 얻습니다.

? (¬ p ∧ ¬ q) ∨ (q ∧ p)

이제 이 방정식에서 교환법칙을 사용하여 다음을 얻습니다.

? (p ∧ q) ∨ (¬ p ¬q)

마지막으로 방정식 (1)은 다음과 같습니다.

피 ← q ? (p ∧ q) ∨ (¬ p ¬q)

마지막으로 식 (1)은 p ⇔ q 가 된다고 말할 수 있다. (p ∧ q) ∨ (¬ p ∧ ¬q)