[이산구조] L02.논리와 명제

• toc {:toc}

논리와 명제

• 명제 : 사고를 나타내는 문장 중 참, 거짓을 명확하게 구분할 수 있는 문장이나 수학적 식
  • 바나나는 맛있다. → X
  • 28은 4의 배수이다. → O
• 진리값 : 참, 거짓으로 명제를 나타냈을 때의 그 값

논리 연산

• 단순 명제 : 하나의 문장이나 식으로 구성되어 있는 명제
• 합성 명제 : 여러 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제
• 논리 연산자 : 단순 명제를 연결시켜주는 역할을 하는 연결자
• 변수 : 합성 명제를 구성할 경우 합성 명제들의 부분 명제 (단순 명제)

연산자의 이름	기호	연산자의 의미
부정		NOT
논리곱		AND
논리합		OR
배타적 논리합		Exclusive OR
조건		if … then
쌍방 조건		if and only if (iff)

• 부정(negative)

p	p
T	F
F	T

~(~p)의 진리값은 p의 진리값과 같다.

• 논리곱(conjunction)

p	q	p q
T	T	T
T	F	F
F	T	F
F	F	F

• 논리합(disjunction)

p	q	p q
T	T	T
T	F	T
F	T	T
F	F	F

• 배타적 논리합(Exclusive OR)

p	q	p q
T	T	F
T	F	T
F	T	T
F	F	F

논리 회로 구성, parity bit 등에 활용

• 조건(implication)

p	q	p q
T	T	T
T	F	F
F	T	T
F	F	T

p이면 q이다. q가 False 일 때 T가 True 인지 확인한다.

• 조건 연산자는 다양한 표현으로 나타내어진다.

1. p이면 q이다.
2. p는 q의 충분조건이다.
3. q는 p의 필요조건이다.
4. p는 q를 함축한다.

p가 q를 함축하는 구조임을 기억하자. p가 충족하면 q가 되기에 충분하고, q가 충족되려면 p가 필요하다.

명제 p q 에 대하여 아래와 같이 표현한다. q p를 역(converse) ~p ~q를 이(inverse) ~q ~p를 대우(contrapositive)

명제와 그의 대우는 논리적 동치 관계이다.

• 쌍방 조건

p	q	p q
T	T	T
T	F	F
F	T	F
F	F	T

배타적 논리합의 반대이다. p이면 q이고 q이면 p이다.

• 쌍방 조건도 다양한 표현으로 나타내어진다.

1. p이면 q이고, q이면 p이다.
2. p는 q의 필요충분조건이다.

항진 명제와 모순 명제

• 항진 명제 : 합성 명제에서 명제를 구성하는 단순 명제들의 진리값에 관계 없이 합성 명제의 진리값이 전부 참인 경우
• 모순 명제 : 합성 명제에서 명제를 구성하는 단순 명제들의 진리값에 관계 없이 합성 명제의 진리값이 전부 거짓인 경우

p	p	p (p)	p (p)
T	F	T	F
F	T	T	F

p (p) 는 항진 명제, p (p) 는 모순 명제이다.

논리적 동치 관계

논리적 동치 : 두 개의 명제 p, q의 쌍방 조건 p q 가 항진 명제인 경우, p q, p q 로 표현

p	q	p	p q	p q
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

• 논리적 동치 관계임을 입증하는 방법

1. 두 명제에 대한 진리표를 구하고 두 명제의 진리값이 같음을 증명한다.
2. 논리적 동치 관계의 기본 법칙을 이용해 다른 명제를 유도한다.

{: width=“300” height=“300”}

{: width=“500” height=“500”}

추론

• 추론 : 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도하는 방법
• 유효추론 : 주어진 전제가 참이고 결론도 참인 추론
• 허위추론 : 주어진 전제가 참이고 결론이 거짓인 추론

전제가 이라 하고 결론이 라 할 때 추론을 수학적으로 표현하면 다음과 같다.

가장 많이 사용하는 3가지 법칙은 다음과 같다.

1. 긍정 법칙 :
2. 부정 법칙 :
3. 삼단 법칙 :

술어 논리

• 는 x가 -2 또는 -3일 때 참의 값을 가지고 그 외에는 거짓의 값을 가진다. 이 경우 ‘을 만족시키는 변수가 있다’ 고 표현한다.
• 위와 같은 형태의 명제를 p(x)로 표시하고 p(x)를 변수 x에 대한 명제 술어라 한다.
• 술어 논리 : 명제 술어에 대한 논리
• 술어 한정자 : 변수의 범위를 한정시키는 것
  • 전체 한정자 : 모든 x에 대하여 p(x)는 참이다.
    • 가 참이 되기 위한 필요충분조건은 p(x)가 모든 x에 대해 성립해야 한다.
  • 존재 한정자 : 어떤 x에 대하여 p(x)가 참인 x가 존재한다.
    • 가 참이 되기 위한 필요충분조건은 p(x)를 만족시키는 x가 적어도 1개 존재해야 한다.

논리용 언어 - Prolog

프롤로그(Prolog) - 논리와 명제를 컴퓨터 프로그램을 통해 보다 빠르고 쉽게 구현할 수 있는 방법론

• 프롤로그의 특징

1. 사실, 규칙, 질문들로 프로그램 구성
2. 사실과 규칙들을 데이터베이스로 구성한다.
3. 프로그램 실행은 자료에 대한 질문의 응답 형식이다.
4. 대화식의 명령 방식을 사용한다.
5. 답하기 위해 추론 엔진을 사용하고 사용자가 사실과 규칙 등을 입력한다.

• Example

human(socrates).            - 소크라테스는 사람이다.(사실)
human(dongkyukang).         - 강동규는 사람이다.(사실)
animal(wurry).              - 워리는 동물이다.(사실)

animal(x):-human(x).        - 모든 사람은 동물이다.(추론 규칙, x는 변수)
die(x):-animal(x).          - 모든 동물은 죽는다.(추론 규칙)

?-die(socrates).            - 소크라테스는 죽는가?(질문)
yes                         - 시스템 답변 : yes
?- die(x).                  - 모든 죽는 것에 대한 이름
x = socrates.
x = dongkyukang.
x = wurry.

논리의 응용, 4차 산업혁명과의 관계

• 논리 응용 분야

1. 디지털 논리
2. 관계형 데이터베이스

• 논리와 4차 산업혁명과의 관계 추론 엔진을 통해 새로운 사실을 추론해내는 전문가 시스템 → 문제 해결, 로보틱스, 게임, 의료 진단

참고문헌

법칙 표 출처: 4차 산업혁명 시대의 이산수학

연결문서

2023-09-28-DiscreteStructure-L01