명제 논리 (命題論理, 영어 : 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}}}
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 이상의 극소 함수적 완전 집합은 존재하지 않는다. 
