[이산수학] 명제와 논리의 기초 (Logic and Proofs)

1. 명제

 논리의 기본적인 구성 요소로,참 또는 거짓 둘 중 하나로 나타내는 선언적 문장(즉, 어떤 사실을 선언하는 문장)이다.
아래 예시 문장을 보면 문장이 사실이 아니더라도 참 또는 거짓으로 구별할 수 있어야 명제가 될 수 있다.

• 대한민국의 수도는 서울이다.
• 1 + 2 = 4
• 1 + 1 = 2

아래 예시 문장은 명제가 아닌데 이유는 참 또는 거짓으로 판정할 수 없고, 변수가 있을 경우 값이 배정되어야만 참 또는 거짓을 구분할 수 있기 때문이다.

• 어디가십니까?
• x + 2 = 4
• x + y = 100

2. 명제 산술 (명제 논리)

 명제를 다루는 논리를 명제 산술 또는 명제 논리라고 부르는데, 이산 수학에서는 해당 논리를 통해 새로운 명제(복합명제)를 만들기도 하며 여러가지 증명을 할 수도 있다.

• 만약 P라는 명제가 "IT is a dog." 라면 p의 부정, 즉 ¬p는 "It is not a dog."가 되는 것이다.
  

3. 논리곱 (Logical AND)

논리곱은 두 개의 명제가 모두 참인 경우에만 전체 명제가 참인 연산이며, 이를 표현할 때 주로 ∧ (앤드) 기호를 사용한다. 다음은 논리곱의 예시이다.

• P: "오늘 비가 온다."
• Q: "나는 우산을 가지고 있다."

P ∧ Q는 "오늘 비가 온다 그리고 나는 우산을 가지고 있다."라고 읽을 수 있으며, P와 Q가 모두 참일 때만 P ∧ Q는 참이 된다. 즉, 비가 오고 동시에 우산을 가지고 있을 때만 이 명제가 참이 되는 것이다.

논리곱

 

4. 진리합 (Logical OR)

진리합은 두 개의 명제 중 하나 이상이 참인 경우 전체 명제가 참인 연산으로, 이를 표현할 때 주로 ∨ (오어) 기호를 사용한다. 다음은 진리합의 예시이다.

• P: "오늘 비가 온다."
• Q: "내일 햇빛이 비친다."

P ∨ Q는 "오늘 비가 온다 또는 내일 햇빛이 비친다."라고 읽을 수 있으며, P와 Q 중 하나 이상이 참이면 P ∨ Q는 참이 된다. 즉, 오늘 비가 오거나 내일 햇빛이 비칠 경우 이 명제가 참이 되는 것이다.

진리합

5. 조건문

 이제 기존 명제들로부터 새로운 명제를 만들어 내는 몇 가지 중요한 방법에 대해 살펴보자.

1. 명제 "p→q"의 뜻은 p가 성립하는 조건상에서 q가 참이다. 라는 뜻이다. 이를 함축이라고도 표현하며 P가 참일 경우 q도 참이라는 것이다. 하여 논리에서는 다양한 문장으로 조건문에 대해 표현하게 되는데 내용이 많아 다른 포스터에서 넣도록 하겠다.
2. 명제 "p↔q"의 뜻은 p와 q가 동일한 진리값을 가질 때, 참이라는 것으로, 비교대상의 명제의 진리값이 같아야한다. 

2023.10.09 - [코딩/이산수학] - [이산수학] 다양한 조건문 표현 모음 (if~, then~)

[이산수학] 다양한 조건문 표현 모음 (if~, then~)

6. 논리 연산자의 우선 순위

논리 연산자에는 다양한 기호들이 사용되는데 아래의 순서와 같이 계산의 우선순위를 갖는다.

1. 부정(~): 가장 높은 우선 순위를 가집니다. 부정 연산자는 다른 연산자보다 먼저 계산됩니다.
2. 논리곱(∧): 논리곱은 다음으로 높은 우선 순위를 가집니다. 따라서 논리곱 연산은 부정 연산자 다음으로 계산됩니다.
3. 진리합(∨): 논리합은 논리곱보다 낮은 우선 순위를 가집니다. 그래서 논리합은 논리곱 다음으로 계산됩니다.
4. 배타적 논리합(XOR): 배타적 논리합은 논리합보다 우선 순위가 낮습니다.