논리는 수학적 주장을 정확하게 표현하고, 그 주장이 언제 참인지 판단하기 위한 언어이다. 가장 기본적인 Propositional Logic은 문장 전체를 하나의 참·거짓 단위로 다루고, Predicate Logic은 문장 안의 대상과 성질까지 표현한다.

명제와 진릿값

명제(proposition)는 참인지 거짓인지 분명하게 판정할 수 있는 문장이다. 예를 들어 “2는 짝수이다”는 참인 명제이고, “9는 소수이다”는 거짓인 명제이다.

반면 다음 표현은 그 자체만으로 명제가 아니다.

  • “이 수는 크다”처럼 기준이 불분명한 문장
  • “문을 닫아라”와 같은 명령문
  • 처럼 변수의 값이 정해지지 않은 문장

마지막 식은 변수의 값이나 범위가 주어질 때 명제가 된다. 이처럼 변수에 따라 참과 거짓이 달라지는 표현을 뒤에서 Predicate로 다룬다.

논리 연산자

명제를 , 라고 할 때 자주 사용하는 논리 연산자는 다음과 같다.

  • : 가 아니다. Negation
  • : 이고 이다. Conjunction
  • : 이거나 이다. Disjunction
  • : 둘 중 정확히 하나만 참이다. Exclusive OR

논리합 는 보통 inclusive OR이다. 즉 두 명제가 모두 참인 경우도 참에 포함한다. XOR는 두 명제의 진릿값이 다를 때만 참이다.

진리표와 논리적 동치

복합 명제의 모든 경우를 나열한 표를 진리표(truth table)라고 한다. 두 논리식의 마지막 열이 모든 행에서 같으면 두 식은 논리적으로 동치이다.

대표적인 동치 법칙은 다음과 같다.

분배법칙과 흡수법칙도 식을 간소화할 때 자주 사용한다.

진리표에서 논리식 만들기

진리표의 출력이 참인 행마다 그 행을 정확히 나타내는 논리곱을 만들고, 이들을 논리합으로 연결하면 원하는 식을 얻는다. 예를 들어 의 진릿값이 인 행은

로 표현한다. 참인 행을 모두 더한 표현을 Disjunctive Normal Form, DNF라고 한다. 반대로 거짓인 행을 이용해 논리합들을 논리곱으로 연결하면 Conjunctive Normal Form, CNF를 얻을 수 있다.

항상 참인 식을 tautology, 항상 거짓인 식을 contradiction이라고 한다.

조건명제

조건명제 는 “이면 이다”라는 뜻이다. 를 가정 또는 전건, 를 결론 또는 후건이라고 한다.

조건명제는 전건이 참인데 후건이 거짓인 경우에만 거짓이다. 전건이 거짓이면 조건을 어긴 반례가 제시되지 않았으므로 논리적으로 참으로 정의한다. 이를 vacuous truth라고 부른다.

조건명제는 다음 식과 동치이다.

또한 원래 명제와 대우는 동치이다.

쌍조건명제 는 두 방향의 조건이 모두 성립한다는 뜻이다.

Predicate와 Domain

Predicate는 변수에 따라 참과 거짓이 달라지는 문장이다. 예를 들어

은 의 값이 정해지기 전에는 명제가 아니다. 변수의 허용 범위를 domain이라고 한다. Domain이 정수일 때 는 참이고 는 거짓이다.

Predicate가 참이 되는 원소를 모으면 Truth Set을 얻는다.

Quantifier

Predicate를 명제로 바꾸는 대표적인 방법이 Quantifier를 붙이는 것이다.

  • : 모든 에 대해 가 참이다.
  • : 어떤 가 존재하여 가 참이다.
  • : 를 만족하는 가 정확히 하나 존재한다.

Quantifier의 부정은 다음처럼 바뀐다.

“모든 사람이 어떤 책을 좋아한다”와 “모든 사람이 좋아하는 책이 하나 존재한다”는 다르다. Quantifier의 순서는 의미를 바꾼다.

첫 식에서는 사람마다 다른 책을 선택할 수 있지만, 두 번째 식에서는 모든 사람이 공통으로 좋아하는 한 책이 있어야 한다.

정리

Propositional Logic은 명제를 참·거짓 단위로 결합하고, Predicate Logic은 대상과 성질을 변수와 Quantifier로 표현한다. 진리표는 논리식의 동치 여부를 직접 확인하는 도구이며, 조건명제와 Quantifier의 부정은 증명과 수학적 문장 해석에서 특히 중요하다.

연습 문제

  1. 가 와 동치임을 보인다.
  2. “정수 중 가장 작은 양의 정수가 존재한다”를 Predicate와 Quantifier로 표현한다.
  3. 를 부정 기호가 Predicate 앞에만 남도록 바꾼다.

풀이

1번

조건명제를 논리합으로 바꾸면

따라서 두 식은 논리적으로 동치이다.

2번

Domain을 양의 정수로 제한하면 가장 작은 원소가 존재한다는 문장은

로 표현할 수 있다. 실제로 이 조건을 만족한다.

3번

Quantifier의 부정 법칙을 바깥쪽부터 차례로 적용한다.