본문으로 이동

항진식

위키백과, 우리 모두의 백과사전.

항진식(恒眞式, 영어: tautology) 또는 항진명제, 토톨로지논리학의 용어로, 어떤 해석(interpretation)에 있어서도 항상 참이 되는 논리식이나 진술을 의미한다. 간단한 예시로 "x가 y와 같거나, x가 y와 같지 않다", "이 공은 녹색이거나 이 공은 녹색이 아니다" 따위를 들 수 있다. 어원은 그리스어에서 '같다'는 의미의 단어인 ταυτο이다.

정의와 예시

[편집]

명제논리에서, 명제변수에 어떤 진릿값이 쓰여도 항상 참인 식을 항진식(tautology)라 한다.

항진식은 무한히 많이 존재할 수 있다. 예컨대 다음과 같은 형태들이 존재한다:

  • ("A이거나 not-A이다"), 배중률. 이 식은 오직 하나의 명제변수 A를 갖는데, 정의에 의해 이 식에 대한 어떤 valuation에서도, A에는 참 또는 거짓을 할당하고 A에는 그 반대의 값을 할당하게 된다.
  • ("만약 AB를 시사한다면, not-B는 not-A를 시사한다, 또한 그 역도 성립한다"), 대우의 법칙.
  • ("만약 not-AB와 그 부정 not-B를 동시에 시사한다면, not-A는 거짓이어야 하며, 그러면 A는 참이어야 한다"), 귀류법(reductio ad absurdum).
  • ("만약 동시에 AB일 수 없다면, not-A이거나 not-B이다. 또한 그 역도 성립한다"), 드모르간의 법칙.
  • ("만약 AB를 시사하고, BC를 시사한다면, AC를 시사하는 것이다"), 삼단논법(연역법).
  • ("만약 적어도 AB 중 하나가 참이면서, 각각이 C를 시사한다면, C는 항상 참이어야 한다"), 논거에 의한 증명(Proof by cases).

최소항진식(minimal tautology)은 더 짧은 항진식으로 대체될 수 없는 항진식을 의미한다.

  • 는 항진식이지만 최소의 것은 아니다. 왜냐하면, 더 짧은 형태인 로 대체될 수 있기 때문이다.

같이 보기

[편집]