맨위로가기

항진식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

항진식은 명제 변수에 어떤 진릿값을 대입해도 항상 참이 되는 명제 논리의 식을 의미한다. 이는 고대 그리스 시대부터 사용된 용어로, 1800년대 이후 논리학에서 특정 유형의 명제 공식을 지칭하는 데 사용되었다. 항진식은 무한히 많으며, 배중률, 대우의 법칙, 귀류법, 드 모르간의 법칙, 삼단논법 등이 그 예시이다. 항진식 여부를 판단하는 것은 진리표를 활용하거나 대수적 식 변형을 통해 확인할 수 있으며, 연역 시스템을 통해서도 증명할 수 있다. 항진식은 항진적 함축, 대입 규칙, 의미론적 완전성 및 안정성과 관련이 있으며, 부울 만족 문제와도 연관된다. 일계 논리에서는 논리적 타당성과 항진 명제를 구분하며, 비고전 논리에서는 항진식의 정의가 달라질 수 있다.

더 읽어볼만한 페이지

  • 명제 - 모순
    모순은 논리학, 철학, 과학 등 다양한 분야에서 사용되는 개념으로, 서로 상반되는 두 가지 주장이나 사실이 동시에 존재하는 상태를 의미하며, 특히 헤겔과 마르크스의 변증법적 유물론에서 사물의 내재적 대립으로서 역사 발전의 원동력으로 간주된다.
  • 명제 - 동어 반복
    동어반복은 같은 의미의 단어나 구절을 반복하는 표현 기법으로, 강조, 역설, 말장난 등의 효과를 위해 여러 분야에서 사용되지만, 불필요한 반복은 의미 전달을 방해할 수 있으므로 신중한 사용이 요구된다.
  • 논리식 - 추론 규칙
    추론 규칙은 전제가 참일 때 결론이 필연적으로 참임을 보이는 논리적 도출 과정을 형식적으로 표현한 규칙으로, 다양한 유형이 존재하며 명제 논리와 술어 논리에서 기본적인 추론을 수행하는 데 사용되고, 형식 체계의 핵심 요소이다.
  • 논리식 - 정리
    정리는 논리학과 수학에서 공리를 바탕으로 증명된 참인 명제로서, "만약 A이면 B이다" 형태의 가정적 조건문으로 표현되며, 수학 외 다양한 분야에서도 사용되지만 수학에서의 엄밀한 증명과는 차이가 있다.
  • 명제 논리 - 모순
    모순은 논리학, 철학, 과학 등 다양한 분야에서 사용되는 개념으로, 서로 상반되는 두 가지 주장이나 사실이 동시에 존재하는 상태를 의미하며, 특히 헤겔과 마르크스의 변증법적 유물론에서 사물의 내재적 대립으로서 역사 발전의 원동력으로 간주된다.
  • 명제 논리 - 추론 규칙
    추론 규칙은 전제가 참일 때 결론이 필연적으로 참임을 보이는 논리적 도출 과정을 형식적으로 표현한 규칙으로, 다양한 유형이 존재하며 명제 논리와 술어 논리에서 기본적인 추론을 수행하는 데 사용되고, 형식 체계의 핵심 요소이다.
항진식

2. 역사

고대 그리스인들은 같은 것을 두 번 말함으로써 참이라고 주장되는 진술을 설명하기 위해 "항진식"이라는 단어를 사용했는데, 이는 여전히 비난조의 의미로 수사적 항진식에 사용된다.[3] 1800년에서 1940년 사이에 이 단어는 논리에서 새로운 의미를 얻었으며, 현재는 수학적 논리에서 특정 유형의 명제 공식을 나타내는 데 사용되며, 원래 가졌던 비난조의 함축은 없다.

1800년, 이마누엘 칸트는 그의 저서 ''논리''에서 다음과 같이 썼다.

: 분석적 판단의 개념의 동일성은 '명시적'(explicita) 또는 '비명시적'(implicita)일 수 있다. 전자의 경우 분석적 명제는 '항진적'이다.de

여기서 ''분석적 명제''는 관련된 용어만으로 참이 되는 자연어의 진술인 분석적 진리를 의미한다.

1884년, 고틀로프 프레게는 그의 저서 ''Grundlagen''에서 진리가 논리를 사용하여 파생될 수 있다면 정확히 분석적이라고 제안했다. 그러나 그는 분석적 진리(즉, 용어의 의미에만 기반한 진리)와 항진식(즉, 내용이 없는 진술) 사이의 구분을 유지했다.

1921년, 루트비히 비트겐슈타인은 그의 ''논리-철학 논고''에서 논리적 추론에 의해 추론될 수 있는 진술은 항진적(의미가 없음)일 뿐만 아니라 분석적 진리라고 제안했다. 앙리 푸앵카레는 1905년 ''과학과 가설''에서 이와 유사한 언급을 했다. 비록 버트런드 러셀은 처음에는 비트겐슈타인과 푸앵카레의 이러한 발언에 반대하며, 수학적 진리가 항진적이지 않을 뿐만 아니라 종합적 진리라고 주장했지만, 나중에는 1918년에 이를 지지하는 발언을 했다.

: 논리의 명제인 모든 것은 어떤 의미에서든 항진식과 같아야 한다. 논리적 명제에 속하지만 다른 명제에는 속하지 않는, 내가 정의할 수 없는 특별한 품질을 가져야 한다.영어

여기서 ''논리적 명제''는 논리 법칙을 사용하여 증명할 수 있는 명제를 의미한다.

20세기 초 많은 논리학자들은 명제 논리의 공식이든 일차 논리의 공식이든, 보편적으로 유효한 모든 공식에 대해 '항진식'이라는 용어를 사용했다. 이러한 광범위한 의미에서 항진식은 모든 해석에서 참이거나 모순의 부정과 논리적으로 동일한 공식이다. 타르스키와 괴델은 이 용법을 따랐으며, 이는 루이스와 랭포드의 교과서와 같은 교과서에 나타난다.[3] 이러한 용어의 광범위한 사용은 오늘날 덜 일반적이지만, 일부 교과서는 이를 계속 사용하고 있다.[4] [5]

현대 교과서는 '항진식'의 사용을 명제 논리의 유효한 문장 또는 대입을 통해 명제 항진식으로 축소될 수 있는 술어 논리의 유효한 문장으로 더 일반적으로 제한한다.[6] [7]

3. 정의 및 예시

명제논리에서 명제변수에 어떤 진릿값을 대입해도 항상 참이 되는 식을 '''항진식'''(tautology)이라고 한다.

항진식은 무한히 많이 존재할 수 있다. 예를 들면 다음과 같다.


  • (A \lor \lnot A) (''A''이거나 not-''A''이다영어): 배중률을 나타낸다. 이 식은 명제변수 ''A'' 하나만을 가지며, 정의에 따라 ''A''에는 참 또는 거짓이 할당되고 \lnot''A''에는 그 반대의 값이 할당된다. 예를 들어 "고양이는 검거나 고양이는 검지 않다"와 같이 표현할 수 있다.
  • (A \to B) \Leftrightarrow (\lnot B \to \lnot A) (만약 ''A''가 ''B''를 시사한다면, not-''B''는 not-''A''를 시사한다, 또한 그 역도 성립한다영어): 대우 법칙을 나타낸다. 예를 들어 "묶여 있으면 책이고, 책이 아니면 묶여 있지 않다"와 그 반대이다.
  • ((\lnot A \to B) \land (\lnot A \to \lnot B)) \to A (만약 not-''A''가 ''B''와 그 부정 not-''B''를 동시에 시사한다면, not-''A''는 거짓이어야 하며, 그러면 ''A''는 참이어야 한다영어): 귀류법을 나타낸다. 예를 들어 "묶여 있지 않으면 책이라는 것을 알고, 묶여 있지 않으면 책이 아니라는 것도 알고 있으므로 묶여 있다"와 같이 표현할 수 있다.
  • \lnot(A \land B) \Leftrightarrow (\lnot A \lor \lnot B) (만약 동시에 ''A''와 ''B''일 수 없다면, not-''A''이거나 not-''B''이다. 또한 그 역도 성립한다영어): 드모르간의 법칙을 나타낸다. 예를 들어 "책이 아니고 묶여 있지 않으면, 책이 아니거나 묶여 있지 않다는 것을 확신할 수 있다"와 그 반대이다.
  • ((A \to B) \land (B \to C)) \to (A \to C) (만약 ''A''가 ''B''를 시사하고, ''B''가 ''C''를 시사한다면, ''A''가 ''C''를 시사하는 것이다영어): 삼단논법을 나타낸다. 예를 들어 "묶여 있으면 책이고, 책이면 책꽂이에 있으므로 묶여 있으면 책꽂이에 있다"와 같이 표현할 수 있다.
  • ((A \lor B) \land (A \to C) \land (B \to C)) \to C (만약 적어도 ''A''와 ''B'' 중 하나가 참이면서, 각각이 ''C''를 시사한다면, ''C''는 항상 참이어야 한다영어): 경우별 증명을 나타낸다. 예를 들어 "묶인 것과 책은 책꽂이에 있습니다. 책이거나 파란색이면 책꽂이에 있습니다"와 같이 표현할 수 있다.


고대 그리스인들은 같은 말을 두 번 반복함으로써 참이라고 주장되는 진술을 설명하기 위해 "항진식"이라는 단어를 사용했는데, 이는 여전히 비난조의 의미로 수사적 항진식에 사용된다. 1800년에서 1940년 사이에 이 단어는 논리학에서 새로운 의미를 얻었으며, 현재는 수학적 논리에서 특정 유형의 명제 공식을 나타내는 데 사용되며, 원래 가졌던 비난조의 함축은 없다.

명제 논리에서 명제를 기호화한 것이 논리식인데, 논리식을 구성하는 가장 단순한 문에 해당하는 요소식의 진위값에 관계없이 항상 참(항진)이 되는 논리식이 존재하며, 이들을 토톨로지 혹은 항진식이라고 부른다.[3] 참 또는 거짓이 될 수 있는 논리식은 정합식(consistent well-formed formula|links=no영어), 항상 거짓이 되는 논리식은 항위식 또는 모순식(contradictory well-formed formula|links=no영어)이라고 한다.

주요 항진식으로는 동일률, 배중률, 모순율, 이중 부정의 법칙, 멱등율, 교환율, 결합율, 분배율, 흡수율, 드 모르간의 법칙, 대우율, 선언적 삼단 논법, 전건 긍정식, 추이율, 도입율, 축소율, 확대율 등이 있다.[3]

3. 1. 최소 항진명제

명제논리에서 최소 항진 명제는 더 짧은 항진 명제의 예가 아닌 항진 명제를 의미한다.

예를 들어,

  • (A ∨ B) → (A ∨ B)는 항진 명제이지만, C → C의 예시이기 때문에 최소 항진 명제는 아니다.

4. 항진명제 확인

어떤 식이 항진식인지 확인하는 것은 명제 논리의 기본이다. 명제 논리에서 항진명제를 확인하는 방법은 다음과 같다.[2]


  • 모든 가능한 평가(진리값 할당)에 대해 식이 항상 참인지 확인한다.
  • 진리표를 작성하여 모든 경우의 수를 확인하는 것이 일반적이다.
  • 대수적 식 변형을 통해 항진식임을 보일 수도 있다.
  • 연역 시스템을 통해 항진식을 증명할 수 있다.


명제 변수가 ''n''개 존재할 경우 2''n''가지 경우를 조사하면 된다. 예를 들어 \alpha \to (\beta \to \alpha)가 항진식인지 확인하기 위해 다음과 같이 대수적 식 변형을 이용할 수 있다.

:\alpha \to (\beta \to \alpha) = \neg \alpha \vee (\neg \beta \vee \alpha) = (\alpha \vee \neg \alpha) \vee \neg \beta = \top \vee \neg \beta = \top

4. 1. 진리표

명제 논리에서 식의 진리값을 판단하는 방법 중 하나는 진리표를 사용하는 것이다. 진리표는 명제 변수에 가능한 모든 진리값 할당에 대해 식의 진리값을 보여주는 표이다.[2]

예를 들어, 다음 수식을 고려해 보자.

: ((A \land B) \to C) \Leftrightarrow (A \to (B \to C)).

명제 변수 ''A'', ''B'', ''C''에 대해 가능한 8가지 진리값 할당은 다음 표의 처음 세 열에 나타나 있다. 나머지 열은 위 수식의 부분 수식의 진리값을 보여주며, 마지막 열은 각 평가에서 원래 수식의 진리값을 보여준다.

ABCA \land B(A \land B) \to CB \to CA \to (B \to C)((A \land B) \to C) \Leftrightarrow (A \to (B \to C))
TTTTTTTT
TTFTFFFT
TFTFTTTT
TFFFTTTT
FTTFTTTT
FTFFTFTT
FFTFTTTT
FFFFTTTT



마지막 열의 각 행이 ''T''를 표시하므로, 이 문장은 항진식임을 알 수 있다.[2]

일반적으로, 수식에 ''n''개의 변수가 나타나면 해당 수식에 대해 2''n''개의 서로 다른 평가가 존재한다. 따라서 해당 수식이 항진식인지 여부를 판단하는 것은 유한하고 기계적인 작업이며, 각 가능한 평가에서 수식의 진리값을 평가하여 모든 평가가 수식을 참으로 만드는지 확인하면 된다.

다른 예로, \alpha \to (\beta \to \alpha)의 경우 다음 4가지 경우를 조사하여 항진식임을 확인할 수 있다.

\alpha\beta\beta\to\alpha\alpha \to (\beta \to \alpha)
TTTT
TFTT
FTFT
FFTT


4. 2. 대수적 식 변형

대수적인 식 변형을 통해 항진식인지 확인할 수 있다.

:\alpha \to (\beta \to \alpha) = \neg \alpha \vee (\neg \beta \vee \alpha) = (\alpha \vee \neg \alpha) \vee \neg \beta = \top \vee \neg \beta = \top

4. 3. 연역 시스템

명제 논리에 대한 연역 시스템(증명 시스템)은 1차 논리에 사용되는 추론 시스템의 단순화된 변형으로 정의할 수 있다(Kleene 1967, Sec 1.9 참조).[2] 적절한 추론 시스템에서 항진식의 증명은 완전한 진리표보다 훨씬 짧을 수 있다. ''n''개의 명제 변수가 있는 수식은 2''n''개의 행이 있는 진리표가 필요하며, ''n''이 증가함에 따라 빠르게 실현 불가능해진다. 배중률이 가정되지 않아 진리표 방법을 사용할 수 없는 직관 논리와 같은 경우에도 증명 시스템이 필요하다.

5. 항진적 함축

수식 ''R''은 ''R''을 참으로 만드는 모든 평가가 ''S''를 참으로 만들 경우, ''S''를 '''항진적으로 함축'''한다고 한다. 이 상황은 R \models S로 표기한다. 이는 수식 R \to S가 항진식인 것과 같다.[1]

예를 들어, ''S''가 A \land (B \lor \lnot B)라고 하자. 그러면 ''S''는 항진식이 아닌데, ''A''를 거짓으로 만드는 모든 평가는 ''S''를 거짓으로 만들기 때문이다. 하지만 ''A''를 참으로 만드는 모든 평가는 ''S''를 참으로 만들 것이다. 왜냐하면 B \lor \lnot B는 항진식이기 때문이다. ''R''이 수식 A \land C라고 하자. 그러면 R \models S인데, ''R''을 만족하는 모든 평가는 ''A''를 참으로 만들 것이고, 따라서 ''S''를 참으로 만들기 때문이다.[1]

정의에 따르면, 수식 ''R''이 모순이면 ''R''은 모든 수식을 항진적으로 함축하는데, ''R''을 참으로 만드는 진리 평가는 없으며, 따라서 항진적 함축의 정의가 자명하게 충족되기 때문이다. 마찬가지로, ''S''가 항진식이라면 ''S''는 모든 수식에 의해 항진적으로 함축된다.[1]

6. 대입 규칙

일반적인 절차인 '''대입 규칙'''은 주어진 항진명제로부터 추가적인 항진명제를 구성할 수 있게 해준다. 만약 S가 항진명제이고, S에 있는 각 명제변수 A에 대해 고정된 문장 S_A가 선택되었다고 가정하자. 그러면 S의 각 변수 A를 해당 문장 S_A로 대체하여 얻은 문장 또한 항진명제이다.

예를 들어, S가 다음과 같은 항진명제라고 하자:

:(A \land B) \lor \lnot A \lor \lnot B.

S_A를 C \lor D로 하고 S_B를 C \to E로 하자.

대입 규칙에 의해 다음 문장:

:((C \lor D) \land (C \to E)) \lor \lnot (C \lor D) \lor \lnot (C \to E)

역시 항진명제이다.

7. 의미론적 완전성과 안정성

공리적 체계는 모든 타당 명제가 정리(공리에서 도출 가능)이면 완전하다고 한다. 공리적 체계는 모든 정리가 타당 명제이면 안정하다고 한다.

8. 효율적인 검증과 부울 만족 문제

명제 변수가 많은 문장이 항진식인지 여부를 결정하는 실용적인 알고리즘을 구성하는 문제는 자동 정리 증명 분야의 현대 연구 분야이다.

위에 설명된 진리표 방법은 증명된 방식이며, 항진식의 진리표는 마지막 열이 ''T''로 끝나고, 항진식이 아닌 문장의 진리표는 마지막 열이 ''F''인 행을 포함하며, 해당 행에 해당하는 값은 테스트 중인 문장을 만족시키지 않는 값이다. 항진식을 검증하는 이 방법은 효율적인 절차이며, 이는 무제한의 계산 자원이 주어지면 항상 문장이 항진식인지 기계적으로 결정하는 데 사용할 수 있음을 의미한다. 특히, 고정된 유한 또는 가산 알파벳에 대한 항진식 집합은 결정 가능한 집합이다.

그러나 효율적인 절차로서 진리표는 확인해야 하는 값의 수가 2''k''로 증가한다는 사실에 의해 제약되며, 여기서 ''k''는 공식의 변수 수이다. 계산 길이의 이러한 지수적 증가는 현재의 컴퓨팅 하드웨어로는 실행 가능한 기간 내에 알고리즘을 실행할 수 없으므로 수천 개의 명제 변수가 있는 공식에 대해 진리표 방법을 쓸모없게 만든다.

공식을 참으로 만드는 값이 있는지 여부를 결정하는 문제는 부울 만족 문제이다. 문장 ''S''가 항진식임을 검증하는 것은 \lnot S를 만족하는 값이 없음을 검증하는 것과 동일하므로 항진식을 검사하는 문제는 이 문제와 동일하다. 부울 만족 문제는 NP-완전이고, 결과적으로 항진식은 co-NP-완전이다. (모든 NP-완전 문제와 동등하게) 일부 알고리즘이 특수한 종류의 공식에서 잘 수행되거나 많은 인스턴스에서 빠르게 종료되지만, 다항 시간 알고리즘이 만족성 문제를 해결할 수 없다고 널리 알려져 있다.[8]

9. 술어 논리에서의 항진명제

명제 논리의 항진식을 취하고 각 명제 변수를 일계 공식으로 균일하게 대체하여 얻을 수 있는 문장이 술어 논리에서의 항진 명제이다. 예를 들어 A \lor \lnot A가 명제 논리의 항진 명제이므로, (\forall x ( x = x)) \lor (\lnot \forall x (x = x))는 일계 논리에서의 항진 명제이다.[3] 단항 관계 기호 ''R'',''S'',''T''를 가진 일계 언어에서 다음 문장은 항진 명제이다.

:(((\exists x Rx) \land \lnot (\exists x Sx)) \to \forall x Tx) \Leftrightarrow ((\exists x Rx) \to ((\lnot \exists x Sx) \to \forall x Tx)).

이것은 명제 논리 항진 명제 ((A \land B) \to C) \Leftrightarrow (A \to (B \to C))에서 A를 \exists x Rx로, B를 \lnot \exists x Sx로, C를 \forall x Tx로 대체하여 얻어진다.

명제 논리와 다르게 모든 논리적 타당성이 일계 논리에서의 항진 명제는 아니다. 예를 들어

:(\forall x Rx) \to \lnot \exists x \lnot Rx

는 어떤 일계 해석에서도 참이지만, 명제 논리의 항진 명제가 아닌 명제 문장 A \to B에 해당한다.

술어 논리에서는 항진 명제를 직접 다루지 않지만, 유사한 개념으로 논리식의 타당성을 생각할 수 있다. 논리식이 모든 해석에서 참일 때, 이 논리식은 타당하며 타당식이 된다. 적어도 하나의 해석으로 논리식이 참이 될 때는 충족 가능하며, 충족 가능식이 된다. 모든 해석에서 논리식이 거짓일 때는 충족 불가능하며, 모순식이 된다.[10]

10. 비고전 논리에서의 항진명제

20세기 초, 많은 논리학자들은 명제 논리의 공식이든 일차 논리의 공식이든, 보편적으로 유효한 모든 공식에 대해 '항진식'이라는 용어를 사용했다. 이러한 광범위한 의미에서 항진식은 모든 해석에서 참이거나 모순의 부정과 논리적으로 동일한 공식이다.[3] 이러한 용어의 광범위한 사용은 오늘날 덜 일반적이지만, 일부 교과서는 이를 계속 사용하고 있다.[4] [5]

현대 교과서는 '항진식'의 사용을 명제 논리의 유효한 문장 또는 대입을 통해 명제 항진식으로 축소될 수 있는 술어 논리의 유효한 문장으로 더 일반적으로 제한한다.[6] [7] 주어진 공식이 항진식인지 여부는 사용 중인 논리의 형식 체계에 따라 달라진다. 예를 들어, 다음 공식은 고전 논리의 항진식이지만, 직관 논리의 항진식은 아니다.

:\neg \neg A \to A

11. 정규 형식

명제논리에서 사용되는 정규 형식은 다음과 같다.


  • 대수적 정규 형식
  • 결합 정규 형식
  • 선언 정규 형식


명제 변수에 어떤 진릿값을 대입해도 항상 참이 되는 식을 항진식이라고 한다. 항진식은 무한히 많이 존재할 수 있으며, 예시는 다음과 같다.

  • (A \lor \lnot A) (배중률): "''A''이거나 not-''A''이다"라는 의미로, 명제 변수 ''A''에 참 또는 거짓을 할당하면, \lnot''A''에는 그 반대의 값이 할당된다. 예: "고양이는 검거나 고양이는 검지 않다".
  • (A \to B) \Leftrightarrow (\lnot B \to \lnot A) (대우): "'A'가 'B'를 시사하면, not-'B'는 not-'A'를 시사한다. 또한 그 역도 성립한다"라는 의미이다. 예: "묶여 있으면 책이고, 책이 아니면 묶여 있지 않다".
  • ((\lnot A \to B) \land (\lnot A \to \lnot B)) \to A (귀류법): "not-'A'가 'B'와 그 부정 not-'B'를 동시에 시사하면, not-'A'는 거짓이어야 하며, 그러면 'A'는 참이어야 한다"라는 의미이다. 예: "묶여 있지 않으면 책이라는 것을 알고, 묶여 있지 않으면 책이 아니라는 것도 알고 있으므로 묶여 있다".
  • \lnot(A \land B) \Leftrightarrow (\lnot A \lor \lnot B) (드 모르간의 법칙): "'A'와 'B'가 동시에 참일 수 없다면, not-'A'이거나 not-'B'이다. 또한 그 역도 성립한다"라는 의미이다. 예: "책이 아니고 묶여 있지 않으면, 책이 아니거나 묶여 있지 않다는 것을 확신할 수 있다".
  • ((A \to B) \land (B \to C)) \to (A \to C) (삼단논법): "'A'가 'B'를 시사하고, 'B'가 'C'를 시사한다면, 'A'가 'C'를 시사한다"라는 의미이다. 예: "묶여 있으면 책이고, 책이면 책꽂이에 있으므로 묶여 있으면 책꽂이에 있다".
  • ((A \lor B) \land (A \to C) \land (B \to C)) \to C (논거에 의한 증명): "'A'와 'B' 중 적어도 하나가 참이면서, 각각이 'C'를 시사한다면, 'C'는 항상 참이어야 한다"라는 의미이다. 예: "묶인 것과 책은 책꽂이에 있다. 책이거나 파란색이면 책꽂이에 있다".


최소항진식은 더 짧은 항진식으로 대체될 수 없는 항진식을 의미한다. 예를 들어 (A \lor B) \to (A \lor B)는 항진식이지만, C \to C로 대체 가능하므로 최소항진식이 아니다.

고전 논리에서 항진식은 다음과 같다.[1]

  • \neg(\alpha\wedge\neg\alpha)
  • \alpha\vee\neg\alpha
  • (\alpha\to \beta)\Leftrightarrow(\neg \beta\to \neg \alpha)
  • \neg\neg\alpha\Leftrightarrow\alpha
  • \neg(\alpha\wedge \beta)\Leftrightarrow(\neg \alpha\vee\neg \beta)
  • ((\alpha\to \beta)\wedge(\beta\to \gamma))\to(\alpha\to \gamma)


주요 항진식에는 동일률, 배중률, 모순율, 이중 부정의 법칙, 멱등율, 교환율, 결합율, 분배율, 흡수율, 드 모르간의 법칙, 대우율, 선언적 삼단 논법, 전건 긍정식, 추이율, 도입율, Exportation (logic)|이출률(移出律)영어, 축소율, 확대율, Constructive dilemma|구성적 양도 논법영어 등이 있다.[2]

12. 관련 논리 주제

명제 논리, 배중률, 대우, 귀류법, 드모르간의 법칙, 삼단논법, 진리표, 자동 정리 증명, 부울 만족 문제, NP-완전, co-NP-완전

참조

[1] 웹사이트 Tautology https://mathworld.wo[...] 2020-08-14
[2] 웹사이트 tautology {{!}} Definition & Facts https://www.britanni[...] 2020-08-14
[3] 서적 Symbolic Logic Dover 1959
[4] 서적 A First Course in Logic Oxford University Press 2004
[5] 서적 A Concise Introduction to Mathematical Logic Springer 2010
[6] 서적 Mathematical Introduction to Logic Academic Press 2001
[7] 서적 Fundamentals of Mathematical Logic Springer 2010
[8] 문서 See [[SAT solver]] for references.
[9] 간행물 New Members http://dx.doi.org/10[...] 2002-01
[10] 웹사이트 記号論理学 https://www.sist.ac.[...] 2020-09-09


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com