[이산수학] 명제 (proposition)

명제(proposition)란?

명제 (proposition or statement): 어떤 사고를 나타내는 문장 중 참이나 거짓을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 식.

• 명제는 통상 영문 소문자 $p, q, r ...$ 등으로 표기합니다.
• 명제가 참 또는 거짓 값을 가질 때 그 값을 명제의 진리값(truth value)이라 하며, 참($T$; true), 거짓($F$; false)으로 각각 표시합니다.
• $T$/$F$의 2 가지 진리값만 가지므로 이진 논리라고도 합니다.

 

단순 명제 (simple proposition)

단순 명제 (simple proposition): 하나의 문장이나 식으로 구성되어 있는 명제

• 단순 명제들을 연결시켜 주는 역할을 하는 연결자($∨$, $∧$, ~)들을 논리 연산자(logical operation)라고 합니다.
• 단순 명제의 진리값은 그 명제가 참이냐 거짓이냐에 따라 $T$또는 $F$를 표시합니다.

 

합성 명제 (composition proposition)

합성 명제 (composition proposition): 여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제

• 합성 명제의 진리값은 그 명제를 구성하는 단순 명제의 진리값과 논리 연산자의 특성에 따라 값이 정해집니다.
• 단순 명제에 비해 합성 명제의 진리값은 복잡한 경우가 많으므로, 진리표(truth table)를 사용하여 단계적으로 연산함으로써 원하는 합성 명제의 진리값을 편리하게 구할 수 있습니다.
• 진리표 작성하는 방법: 단순 명제들이 가질 수 있는 모든 경우의 진리값을 표시 → 복합 명제 연산. $n$개의 단순 명제가 있을 때 진리값의 경우의 수는 $2^n$개입니다.
• 논리 기호 등을 여러 번 사용하여 합성 명제를 구성할 경우 합성 명제 $P$의 부분 명제 $p, q, r, ...$ 등을 변수(variables)라 합니다.

 

항진 명제 (tautology)

항진 명제 (tautology): 합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 진리값이 항상 참(T)의 값을 가질 때 그 명제를 항진 명제라 한다.

• $p$가 단순 명제일 때, $p ∨ ($~$p)$의 진리값은 항상 참이므로 항진 명제입니다.

 

모순 명제 (contradiction)

모순 명제 (contradiction): 합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 진리값이 항상 거짓(F)의 값을 가질 때 그 명제를 모순 명제라 한다.

• $p$가 단순 명제일 때, $p ∧ ($~$p)$의 진리값은 항상 거짓이므로 모순 명제입니다.