명제 논리 (命題論理, 영어 : propositional logic )는 내부 구조가 없는 명제 에 논리합 이나 부정 따위의 논리 연산 을 가하여 구성한 명제들을 다루는 논리 체계이다.[1] :30, Chapter 3
집합 I {\displaystyle I} 가 주어졌다고 하자. 그렇다면, I {\displaystyle I} 에 대한 명제 논리의 언어 L I {\displaystyle {\mathcal {L}}_{I}} 는 다음과 같은 기호들로 구성된다.
각 i ∈ I {\displaystyle i\in I} 에 대하여, 원자 명제 (原子命題, 영어 : atomic proposition ) p i {\displaystyle {\mathsf {p}}_{i}}
부정 (否定, 영어 : negation ) ¬ {\displaystyle \lnot } 과 실질적 함의 (實質的含意, 영어 : material implication ) ⟹ {\displaystyle \Longrightarrow }
명제 논리의 논리식 (論理式, 영어 : (well-formed) formula )은 다음 문법을 따르는 명제 논리 기호들의 문자열이다.
모든 원자 명제는 논리식이다.
논리식 P {\displaystyle P} , Q {\displaystyle Q} 에 대하여, ¬ P {\displaystyle \lnot P} 와 P ⟹ Q {\displaystyle P\Longrightarrow Q} 는 논리식이다. 주어진 논리 체계의 문장 (文章, 영어 : sentence )은 자유 변수 를 갖지 않는 논리식으로 정의된다. 명제 논리의 논리식은 변수 를 포함하지 않으므로 모든 논리식은 문장이다.
공리와 추론 규칙
편집
명제 논리의 추론 규칙 과 공리 기본꼴 들은 (임의의 논리식을 나타내는 기호 P {\displaystyle P} , Q {\displaystyle Q} , R {\displaystyle R} 를 사용하여) 다음과 같이 나타낼 수 있다.
추론 규칙
(전건 긍정의 형식 )P , P ⟹ Q Q {\displaystyle {\begin{matrix}P,\;P\Longrightarrow Q\\\hline Q\end{matrix}}}
공리 기본꼴
P ⟹ ( Q ⟹ P ) {\displaystyle P\Longrightarrow (Q\Longrightarrow P)}
( P ⟹ ( Q ⟹ R ) ) ⟹ ( ( P ⟹ Q ) ⟹ ( P ⟹ R ) ) {\displaystyle (P\Longrightarrow (Q\Longrightarrow R))\Longrightarrow ((P\Longrightarrow Q)\Longrightarrow (P\Longrightarrow R))}
( ¬ P ⟹ ¬ Q ) ⟹ ( Q ⟹ P ) {\displaystyle (\lnot P\Longrightarrow \lnot Q)\Longrightarrow (Q\Longrightarrow P)} 공리와 추론 규칙 (부정과 논리합을 사용할 경우)
편집
명제 논리는 또 다른 함수적 완전 집합 { ¬ , ∨ } {\displaystyle \{\lnot ,\lor \}} 을 사용하여 전개할 수 있으며, 이 경우 명제 논리의 추론 규칙과 공리 기본꼴들은 (임의의 논리식을 나타내는 기호 P {\displaystyle P} , Q {\displaystyle Q} , R {\displaystyle R} 를 사용하여) 다음과 같이 나타낼 수 있다.
추론 규칙
(선언 도입 , 영어 : disjunction introduction , 또는 확장 규칙, 영어 : expansion rule )P P ∨ Q {\displaystyle {\begin{matrix}P\\\hline P\lor Q\end{matrix}}}
(축소 규칙, 영어 : contraction rule )P ∨ P P {\displaystyle {\begin{matrix}P\lor P\\\hline P\end{matrix}}}
(결합 규칙, 영어 : associative rule )P ∨ ( Q ∨ R ) ( P ∨ Q ) ∨ R {\displaystyle {\begin{matrix}P\lor (Q\lor R)\\\hline (P\lor Q)\lor R\end{matrix}}}
(절단 규칙, 영어 : cut rule )P ∨ Q , ¬ P ∨ R Q ∨ R {\displaystyle {\begin{matrix}P\lor Q,\;\lnot P\lor R\\\hline Q\lor R\end{matrix}}}
공리 기본꼴
(배중률 ) P ∨ ¬ P {\displaystyle P\lor \lnot P}
명제 논리의 모든 논리식의 집합을 Sent ( L I ) {\displaystyle \operatorname {Sent} ({\mathcal {L}}_{I})} 라고 표기하자. 그렇다면 명제 논리의 구조 (構造, 영어 : structure )는 다음 조건들을 만족시키는 함수 v : Sent ( L I ) → { 0 , 1 } {\displaystyle v\colon \operatorname {Sent} ({\mathcal {L}}_{I})\to \{0,1\}} 이다.
모든 논리식 P {\displaystyle P} 에 대하여,v ( ¬ P ) = { 1 v ( P ) = 0 0 v ( P ) = 1 {\displaystyle v(\lnot P)={\begin{cases}1&v(P)=0\\0&v(P)=1\end{cases}}}
모든 논리식 P {\displaystyle P} , Q {\displaystyle Q} 에 대하여,v ( P ⟹ Q ) = { 1 v ( P ) = 0 ∨ v ( Q ) = 1 0 v ( P ) = 1 ∧ v ( Q ) = 0 {\displaystyle v(P\Longrightarrow Q)={\begin{cases}1&v(P)=0\lor v(Q)=1\\0&v(P)=1\land v(Q)=0\end{cases}}} (여기서 ∨ {\displaystyle \lor } , ∧ {\displaystyle \land } 는 메타 언어의 논리합·논리곱 기호이다.)
논리식 P {\displaystyle P} 와 구조 v {\displaystyle v} 에 대하여 v ( P ) = 1 {\displaystyle v(P)=1} 이 성립한다면, v {\displaystyle v} 가 P {\displaystyle P} 를 만족 (滿足, 영어 : satisfy )시킨다고 하며, 이를
v ⊨ P {\displaystyle v\models P} 로 표기한다.
명제 논리의 논리식의 집합(즉, Sent ( L I ) {\displaystyle \operatorname {Sent} ({\mathcal {L}}_{I})} 의 부분 집합)을 명제 논리의 이론 (理論, 영어 : theory )이라고 한다. 명제 논리의 이론 T {\displaystyle {\mathcal {T}}} 와 구조 v {\displaystyle v} 가 주어졌을 때, 임의의 P ∈ T {\displaystyle P\in {\mathcal {T}}} 에 대하여 v ⊨ P {\displaystyle v\models P} 라면, v {\displaystyle v} 가 T {\displaystyle {\mathcal {T}}} 의 모형 (模型, 영어 : model )이라고 하며, 이를
v ⊨ T {\displaystyle v\models {\mathcal {T}}} 로 표기한다. 모형을 갖는 이론을 만족 가능 이론 (滿足可能理論, 영어 : satisfiable theory )이라고 한다.
명제 논리는 건전성 , 완전성 , 콤팩트성 정리 를 만족시킨다.
논리 연산과 함수적 완전 집합
편집
n {\displaystyle n} 개의 원자 명제로 구성된 명제 논리의 논리식이 가질 수 있는 진리표 는 총 2 2 n {\displaystyle 2^{2^{n}}} 개이다. 특히, 명제 논리는 총 16개의 (서로 동치가 아닌) 2항 논리 연산이 존재하며, 이들은 다음과 같다.
p {\displaystyle p}
q {\displaystyle q}
모순 명제 ⊥ {\displaystyle \bot }
논리곱 p ∧ q {\displaystyle p\land q}
비함의 p ⟹̸ q {\displaystyle p\not \Longrightarrow q}
역비함의 p ⟸̸ q {\displaystyle p\not \Longleftarrow q}
부정 논리합 p ↓ q {\displaystyle p\downarrow q}
첫째 성분 p {\displaystyle p}
둘째 성분 q {\displaystyle q}
실질적 동치 p ⟺ q {\displaystyle p\Longleftrightarrow q}
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
p {\displaystyle p}
q {\displaystyle q}
항진 명제 ⊤ {\displaystyle \top }
부정 논리곱 p ↑ q {\displaystyle p\uparrow q}
실질적 함의 p ⟹ q {\displaystyle p\Longrightarrow q}
역함의 p ⟸ q {\displaystyle p\Longleftarrow q}
논리합 p ∨ q {\displaystyle p\lor q}
첫째 성분의 부정 ¬ p {\displaystyle \lnot p}
둘째 성분의 부정 ¬ q {\displaystyle \lnot q}
배타적 논리합 p ⊻ q {\displaystyle p\veebar q}
1
1
1
0
1
1
1
0
0
0
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
0
0
1
1
1
1
0
1
1
0
주어진 명제 논리의 2항 이하의 논리 연산의 집합으로부터 구성된 논리식이 모든 진리표를 나타낼 수 있고, 임의의 한 논리 연산을 제거하였을 때 나타낼 수 없는 진리표가 존재하게 된다면, 이 집합을 (극소) 함수적 완전 집합 ((極小)函數的完全集合, 영어 : (minimal) functionally complete set )이라고 한다. 명제 논리의 극소 함수적 완전 집합은 정확히 다음과 같다.[2] :132
크기 1 (총 2개)
{ ↑ } {\displaystyle \{\uparrow \}}
{ ↓ } {\displaystyle \{\downarrow \}}
크기 2 (총 18개)
{ ⟹ , ¬ } {\displaystyle \{\Longrightarrow ,\lnot \}}
{ ⟸ , ¬ } {\displaystyle \{\Longleftarrow ,\lnot \}}
{ ⟹̸ , ¬ } {\displaystyle \{\not \Longrightarrow ,\lnot \}}
{ ⟸̸ , ¬ } {\displaystyle \{\not \Longleftarrow ,\lnot \}}
{ ∧ , ¬ } {\displaystyle \{\land ,\lnot \}}
{ ∨ , ¬ } {\displaystyle \{\lor ,\lnot \}}
{ ⟹ , ⊥ } {\displaystyle \{\Longrightarrow ,\bot \}}
{ ⟸ , ⊥ } {\displaystyle \{\Longleftarrow ,\bot \}}
{ ⟹ , ⟺̸ } {\displaystyle \{\Longrightarrow ,\not \Longleftrightarrow \}}
{ ⟸ , ⟺̸ } {\displaystyle \{\Longleftarrow ,\not \Longleftrightarrow \}}
{ ⟹̸ , ⊤ } {\displaystyle \{\not \Longrightarrow ,\top \}}
{ ⟸̸ , ⊤ } {\displaystyle \{\not \Longleftarrow ,\top \}}
{ ⟹̸ , ⟺ } {\displaystyle \{\not \Longrightarrow ,\Longleftrightarrow \}}
{ ⟸̸ , ⟺ } {\displaystyle \{\not \Longleftarrow ,\Longleftrightarrow \}}
{ ⟹ , ⟹̸ } {\displaystyle \{\Longrightarrow ,\not \Longrightarrow \}}
{ ⟹ , ⟸̸ } {\displaystyle \{\Longrightarrow ,\not \Longleftarrow \}}
{ ⟸ , ⟹̸ } {\displaystyle \{\Longleftarrow ,\not \Longrightarrow \}}
{ ⟸ , ⟸̸ } {\displaystyle \{\Longleftarrow ,\not \Longleftarrow \}}
크기 3 (총 6개)
{ ⟺ , ∧ , ⊤ } {\displaystyle \{\Longleftrightarrow ,\land ,\top \}}
{ ⟺ , ∨ , ⊤ } {\displaystyle \{\Longleftrightarrow ,\lor ,\top \}}
{ ⟺̸ , ∧ , ⊥ } {\displaystyle \{\not \Longleftrightarrow ,\land ,\bot \}}
{ ⟺̸ , ∨ , ⊥ } {\displaystyle \{\not \Longleftrightarrow ,\lor ,\bot \}}
{ ⟺ , ⟺̸ , ∧ } {\displaystyle \{\Longleftrightarrow ,\not \Longleftrightarrow ,\land \}}
{ ⟺ , ⟺̸ , ∨ } {\displaystyle \{\Longleftrightarrow ,\not \Longleftrightarrow ,\lor \}}
크기 4 이상의 극소 함수적 완전 집합은 존재하지 않는다. 외부 링크
편집