논리곱

3. 정의

고전 논리에서 '''논리곱'''은 두 논리값, 일반적으로 두 명제의 값을 대상으로 하는 논리 연산이며, 두 피연산자가 모두 참일 때만 참 값을 가진다.^[2][1]

예를 들어 "내 키는 160 cm 이상이다."와 "내 몸무게는 50 kg 이상이다."라는 두 명제의 논리곱은 "내 키는 160 cm 이상이고, 내 몸무게는 50 kg 이상이다."와 같이 표현된다.

논리곱의 항등원은 참이다. 즉, 어떤 명제에 참을 AND 연산해도 그 명제의 값은 변하지 않는다. 공허 진리 개념에 따라, 논리곱이 여러 개의 연산자로 정의될 때 피연산자가 없는 빈 논리곱은 참으로 정의된다.

논리곱은 부정과 논리합을 사용하여 나타낼 수 있다. (\[드 모르간의 법칙]).

: ''P'' ∧ ''Q'' = ¬(¬''P'' ∨ ¬''Q'')

반대로, 부정과 논리곱을 사용하여 논리합을 나타낼 수도 있다.

: ''P'' ∨ ''Q'' = ¬(¬''P'' ∧ ¬''Q'')

3. 1. 진리표

4. 성질

논리곱은 부정(¬)과 논리합(∨)으로 표현 가능하다. (\[\[드 모르간의 법칙]])

: ''P'' ∧ ''Q'' = ¬(''P'' ∨ ¬''Q'')

• '''교환성''': P ∧ Q = Q ∧ P
• '''결합성''': (P ∧ Q) ∧ R = P ∧ (Q ∧ R)^[7]
• '''분배성''': 여러 연산, 특히 논리합(or)과 함께 적용된다.
• '''멱등성''': P ∧ P = P
• '''단조성''': (P → Q) ⇒ ((P ∧ R) → (Q ∧ R))
• '''진리 보존''': 모든 입력이 참이면 출력도 참이다.
• '''거짓 보존''': 모든 입력이 거짓이면 출력도 거짓이다.

5. 부정

논리곱 $A\backslash land\; B$는 $\backslash neg\; A$ 또는 $\backslash neg\; B$를 증명함으로써 거짓으로 증명된다. 대상 언어 측면에서 이것은 다음과 같이 읽힌다.

:$\backslash neg\; A\backslash to\backslash neg(A\backslash land\; B)$

이 공식은 다음의 특수한 경우로 볼 수 있다.

:$(A\backslash to\; C)\; \backslash to\; (\; (A\backslash land\; B)\backslash to\; C\; )$

여기서 $C$는 거짓 명제이다.

만약 $A$가 $\backslash neg\; B$를 함의한다면, $\backslash neg\; A$와 $A$ 모두 논리곱이 거짓임을 증명한다.

:$(A\backslash to\backslash neg\{\}B)\backslash to\backslash neg(A\backslash land\; B)$

다시 말해, 논리곱은 실제로 구성 요소의 진릿값이 아닌, 구성 요소 간의 관계에 대한 지식만으로도 거짓임을 증명할 수 있다.

이 공식은 다음의 특수한 경우로 볼 수 있다.

:$(A\backslash to(B\backslash to\; C))\backslash to\; (\; (A\backslash land\; B)\backslash to\; C\; )$

여기서 $C$는 거짓 명제이다.

위의 두 가지 모두 귀류법에 의한 구성적인 유효한 증명이다.

6. 추론 규칙

논리곱 도입은 고전적으로 타당하며, 단순한 논증 형식이다. 이 논증 형식은 두 개의 전제, $A$와 $B$를 가진다. 직관적으로, 이 형식은 두 전제의 논리곱을 추론할 수 있게 해준다.

:$A$,

:$B$.

:따라서, ''A''와 ''B''.

또는 논리 연산자 표기법으로 나타내면, \vdash는 증명 가능성을 나타낸다.

:$\backslash vdash\; A,$

:$\backslash vdash\; B$

:$\backslash vdash\; A\; \backslash land\; B$

다음은 ''논리곱 도입'' 형식을 따르는 논증의 예시이다.

:밥은 사과를 좋아한다.

:밥은 오렌지를 좋아한다.

:따라서, 밥은 사과와 오렌지를 좋아한다.

논리곱 제거는 또 다른 고전적으로 타당하며, 단순한 논증 형식이다. 직관적으로, 논리곱 제거는 논리곱에서 그 논리곱을 구성하는 어느 한 요소라도 추론할 수 있게 해준다.

:$A$와 $B$.

:따라서, $A$.

...또는 다른 형식으로,

:$A$와 $B$.

:따라서, $B$.

논리 연산자 표기법으로 나타내면:

:$\backslash vdash\; A\; \backslash land\; B$

:$\backslash vdash\; A$

...또는 다른 형식으로,

:$\backslash vdash\; A\; \backslash land\; B$

:$\backslash vdash\; B$

7. 컴퓨터 과학 응용

8. 집합론과의 관계

집합론에서 교집합의 원소 포함 여부는 논리곱으로 정의된다. x ∈ A ∩ B는 (x ∈ A) ∧ (x ∈ B)일 때, 그리고 그 때만 성립한다. 이러한 대응을 통해 집합론적 교집합은 결합 법칙, 교환 법칙, 멱등성과 같은 여러 성질을 논리곱과 공유한다.

9. 자연어와의 관계

수학 논리에서 형식화된 개념과 마찬가지로, 논리곱 'and'는 문법적 접속사 'and'와 관련이 있지만, 자연어에서의 'and'와는 의미가 동일하지 않다.

영어의 "and"는 때때로 "그 다음에"와 같이 시간적 순서를 나타내거나, "미국 국기는 빨간색, 흰색, 파란색이다."와 같이 사물을 부분으로 나누는 것을 암시하기도 한다. 이는 논리곱으로 표현되지 않는 특징이다.

9. 1. 한국어에서의 논리곱

• "내 키는 160 cm 이상이다."
• "내 몸무게는 50 kg 이상이다."

• "내 키는 160 cm 이상이고, '''그리고''' 내 몸무게는 50 kg 이상이다."

참조

_[1] 웹사이트 2.2: Conjunctions and Disjunctions https://math.librete[...] 2019-08-13
_[2] 웹사이트 Conjunction, Negation, and Disjunction https://philosophy.l[...] 2020-09-02
_[3] 서적 Logic: the basics Routledge 2010
_[4] 서적 A Précis of Mathematical Logic D. Reidel 1959
_[5] 웹사이트 Conjunction https://mathworld.wo[...] 2024-09-24
_[6] 웹사이트 Types of proof system http://www.logicmatt[...]
_[7] 서적 Logic with trees: an introduction to symbolic logic Routledge 1997
_[8] 서적 論理学概論 岩波書店