[이산수학] 2강 - 논리

✅ 1. 명제

(1) 명제 정의

• 문장이 주어졌을 때 해당 문장을 참과 거짓으로 구별이 가능하면 명제라고 함.
• 명제의 진리값: 참과 거짓 자체를 명제의 진리값이라고 부름

(2) 명제의 종류

• 합성명제, 조건명제, 쌍조건명제, 항진명제, 모순명제 등이 있음.

(3) 명제 예시

• (1) 6은 2의 배수다. = 참(True) = 명제임.
• (2) 철수는 공부를 잘 한다. = 참 or 거짓 가능 = 명제가 아님.
• (3) 2 + 3 = 7 = 거짓(False) = 진리값이 거짓이므로 명제가 맞음.
• (4) x + 2 = 0 = 참 or 거짓 가능 = 명제가 아님. ( 하지만, 명제함수로 분류가 됨 )

• 참과 거짓으로 식을 판별 할 수 있는것이 명제이기 때문에 진리값이 존재하는것이 곧 명제가 되는 것임.

---

✅ 2. 논리연산

(1) 논리 연산자

• 실수집합에서 실수연산을 정의해서 나온 연산자가 +, -, *, / 이런식으로 구현 또는 구성이 되어있음.
• ** 마찬가지로 논리연산은 논리적인 연산에 대한 연산자를 통해서 논리연산을 보여주고 있음. **
• 합성명제: p, q 는 논리 변수(명제)라고 하며, 논리연산(or, and, not, xor:논리 연산자) 을 통해서 나오는 논리 연산식을 합성 명제라고 부르며, 합성 명제를 통해서 나오는 값은 T,F 와 같은 논리상수가 나오게 될 것임.
• ** 쉽게말해, 기본적인 명제인 p와 q를 논리 연산식을 통해 합성해놓은 것이기 때문에 합성명제로도 볼 수 있음. **

[ 합성 명제 ]

• 하나 이상의 명제와 논리연산자로 이루어진 논리 연산식 자체를 합성명제로 부름.

(2) 논리 연산자 - 논리합

• 합성명제 논리합은 OR 연산이라고 부르며, 연산자는 OR 연산자(V)라고 부름
• T = 1, F = 0 으로 볼 때, 합성명제의 명제간의 진리값을 더했을 때 나오는 진리값을 논리합이라고 부름.
• ** 해당 논리 연산자의 진리표는 논리 연산에 대한 약속이기 때문에 외워야함. **

[ 논리 연산자 - 논리합 예제 ]

• (1) p = true, q = false -> 논리합(or) T + F = T -> 즉, 합성명제 논리합 결과값은 T가 나옴.
• (2) p = false, q = false -> 논리합(or) F + F = F -> 즉, 합성명제 논리합 결과값 = F

(3) 논리 연산자 - 논리곱

• 합성명제 논리곱은 AND 연산이라고 부르며, 해당 연산자 자체는 AND 연산자라고 부름.

[ 논리 연산자 - 논리곱 예제 ]

• (1) p = true, q = true; T(1) * T(1) = T 이기 때문에 논리곱 연산 결과에 따라 T가 될 수 있음.
• (2) p = true, q = false; T(1) * F(0) = F(0) 이기 때문에 논리곱 연산 결과에 따라 F가 될 수 있음.
• ** 즉, 합성명제 논리곱은 명제 둘 다 True(참) 인 경우에만 True(참)이 된다. **

(3) 논리 연산자 - 부정

• 합성명제 부정은 하나의 명제에 논리연산인 부정을 넣어 합성명제의 형태를 가지고 있음.
• 1항 연산(피연산자 1개)에서 쓰이는 논리 연산자임.
• ** 쉽게말해, 피연산자가 참인 경우 거짓으로 만들어주고 거짓인 경우 참으로 만들어주는 연산임. **

(4) 논리 연산자 - 베타적 논리합

• or, and ,not 기본 논리 연산자들을 활용해서 만든 파생 연산자로 보면 됨.
• p와 q 둘 다 참 또는 거짓인 경우에는 거짓이 나오고, p와 q가 참 또는 거짓으로 둘 다 다른 진리값인 경우에만 참이 됨.
• ** 쉽게말해, 걍 합성명제의 명제가 둘 다 다를 경우에만 참이 되는 것임. **

(5) 조건명제

• p(조건) 가 참이고, q(결론) 가 참인 경우 조건명제의 결과는 항상 참(T)이 됨.
• 반면, p(조건) 가 참이고, q(결론) 가 거짓인 경우 조건명제의 결과는 항상 거짓(F)이 됨.
• 하지만, p(조건) 가 거짓이고, q(결론) 가 참인 경우 조건명제의 결과는 항상 참(T)이 됨.
• 조건과 결론이 애초에 거짓인 경우 참(T) 이라고 약속을 하고 있음.
• ** 결론은, 조건 보다 결론이 중요하게 작용함. **

[ 조건명제 - 예제 ]

• (1) 1+2=3 true, 10-2=8 true -> 조건명제의 명제 둘 다 참이므로, 결과값 = True
• (2) 1+2=3 true, 10-2=7 false -> 조건은 true 지만, 결론이 false 이기 때문에 결과값 = False
• (3) false, true -> 조건은 false 이지만, 결론은 true 이기 때문에 결과값 = True
• (4) false, false -> 조건과 결과 둘 다 false 이지만, 결과값 = True
• ** 즉, 결과 명제에서 갈리며, 둘 다 false 인 경우 True 만 알고 있으면 됨. **

(6) 조건명제 - 쌍조건명제

• 쌍조건명제: 명제 p와 q가 조건과 결론의 역할을 동시에 수행하는 경우
• p -> q 간의 조건명제를 구하고, 자리를 바꿔 q -> q 간의 조건명제를 구한 결과값을 토대로 진리값이 나오는 원리임.
• 조건명제 둘 다 참인 경우 T, 하나라도 거짓인 경우 거짓이 나옴. 즉, AND 연산이 활용이 됨.

[ 쌍조건명제 - 예제 ]

• (1) True, True 둘 다 참이기 때문에 쌍조건명제의 결론은 참이다.
• (2) False, False 둘 다 거짓이지만, 조건명제 거짓은 True로 보기 때문에 쌍조건명제의 결론은 참이 된다.

(7) 동치

• 두 명제에 대한 진리값이 항상 같은 경우에는 "논리적 동치" 라고 한다.
• 쉽게말해, 표현방식은 다르지만 결국 같은 의미를 담고 있는 관계를 의미 할 수 있다.
• ** 예를들면, A = not not A(A에 대해서 부정을 두 번 하면 동일한 의미가 됨) 이런식으로 두 명제에 대해 진리값이 항상 같은 경우와 서로간의 의미적으로 치환이 가능한 경우가 논리적 동치에 해당 할 수 있음. **
• 논리적 동치를 구한다: 똑같은 결론을 내는 가장 단순한 논리연산식을 구하는 것과 같음.
• 핵심: 논리적 동치를 구함으로써, 복잡한 논리연산식을 간단한 논리연산식으로 바꾸어 진리값을 도출 할 수 있는데, 이것을 통해 한 눈에 논리연산식을 이해 할 수 있음. ( 식을 좀 더 간단하게 만들기 위함이며, 치환이 목적이 되는 것임 )

[ 논리적동치 - 예제 ]

p

q

r

q∧r

(1) p∨(q∧r) (A)

p∨q

p∨r

(2) (p∨q)∧(p∨r) (B)

• (1) 명제에 해당하는 논리연산식을 수학적인 관점에서 분배법칙을 하게 되면, (2) 논리 연산식을 도출 할 수 있게 됨.
• 위의 표를 통해서 (1) 과 (2) 이 논리적 동치임을 직접적으로 증명을 하고 있으며, 완벽하게 일치하는 것을 볼 수 있음.
• ** 결론은 분배법칙이 적용이 될 수 있고, 분배법칙을 통해서 나온 식은 식의 일부분을 제거해서 가독성을 높일 수 있게 됨. **
• 또한, 위와 같은 논리연산식을 이용해 논리 게이트라는 회로를 직접 구현할 수 있음. ( 반도체 회로에 사용이 됨. )

(8) 논리적 동치법칙

• 교환법칙: 피연산자의 순서를 바꾸어 계산해도 그 결과는 같음 ( a + b = b + a )
• 결합법칙: 어느 부분을 먼저 묶어서 계산해도 그 결과는 같음 (a+b) + c = a + (b+c); (a*b)*c = a*(b*c); 동일함.
• 분배법칙: a * (b+c) = (a*b) + (a*c) 형태로 분배법칙을 통해서 치환이 가능함.
• 분배법칙에서 특이점은 a+(b*c) 의 형태가 실수에서는 불가능한데, 논리연산식에서는 분배법칙이 가능함.

• 항등법칙: p or F => p 가 T 인 경우에 p 의 명제의 진리값과 동일한 결과가 도출이 됨. ( p or F == p 가 성립 즉, 동치임. )
• 지배법칙: 명제 or T 인 경우 항상 T가 되고, 명제 and F 인 경우 항상 F 가 됨. 즉, 동치임.

• 부정법칙: not T = F, not F = T // p or not p = T , p and not p = F 가 됨. 동치임.
• 이중 부정 법칙: not not p = p 이며, 거짓의 거짓은 참이 되는 원리임.

• 멱등법칙: 연산이나 작업을 여러 번 적용하더라도 결과가 달라지지 않는 성질을 의미하는 법칙임.
• p or p or p or p or... 동일한 작업을 여러번 적용하더라도 결과(진리값)가 달라지지 않음. ( 멱등성을 가진다고 보면 됨. )
• 드 모르간 법칙: 전체에 걸린 부정(NOT)을 풀면, 내부의 요소들이 반전되고 연산자도 뒤집히는 법칙을 의미함.
• 쉽게말해, not(p or q) 는 not p and not q 가 되는 원리임. 집합론에선 여집합의 성질로 설명 됨.

• 흡수법칙: 서로 다른 두 연산(and, or)이 섞여 있을 때, 한 항이 다른 항을 흡수하여 식을 단순화하는 법칙임.
• 함축법칙: 조건문인 p -> q 를 not p or q 인 논리합과 부정의 형태로 바꾸는 법칙임.
• 조건 명제를 달리 표현하면 not p or q 와 같은 형태인 함축법칙을 통해서도 표현이 가능함.
• 대우법칙: 어떤 명제가 참이면 그 명제의 대우도 반드시 참이라는 법칙임.

• -2 < x < 3 은 (-2 < x) and (x < 3) 의 형태로 논리연산식으로 치환이 가능함.
• 또한, 드 모르간 법칙을 적용하면 not( -2 < x < 3) 형태이므로, 치환하면 (~(-2 < x)) or (~(x < 3)) 형태가 됨.
• 즉, and 연산에 not이 들어가 or 로 반전이 되는 형태임.
• ** 결과는 not 연산을 풀면 (-2 >= x) and (x >= 3) 형태로 치환이 될것임. **

(9) 향진명제와 모순명제

• 항진명제: 항상 참(T)이 되는 명제를 의미하며, 결과 열이 모두 T(참)으로 채워지는 형태임.
• 예시: p or T = 항상(T) "이 논리연산식은 항상 결과가 True가 나오네? 이건 항진명제다!"
• 모순명제: 항상 거짓(F)가 되는 명제를 의미하며, 결과 열이 모두 F(거짓)으로 채워지는 형태임.
• 예시: p and F = 항상(F) "이 논리연산식을 항상 결과가 False가 나오네? 이건 모순명제다!"

---

 

✅ 3. 술어논리

(1) 술어논리와 명제함수

[ 명제 논리 예시 1 ]
문장 1: 소크라테스는 사람이다. (P)
문장 2: 모든 사람은 죽는다. (Q)
결론: 그러므로 소크라테스는 죽는다. (R)
- 이 문장들은 그 자체로 참/거짓이 결정이 됨.

[ 명제 논리 예시 2 ]
x는 개발자다.

• 명제논리: 명제를 기본 단위로, 명제들을 논리 연산자로 연결되었을 때 문장의 참,거짓이 어떻게 결정되는지 보는 논리 체계
• 명제 논리 예시 1: 세 문장이 각각 독립적인 P, Q, R일 뿐이라서, 1번과 2번을 통해서 3번을 이끌어낼 논리적 연결 고리 자체가 없음. 즉, 각각의 명제는 참과 거짓만 있을 뿐임. 하지만 술어논리는 공통 속성을 통해 이들을 연결함.
• 명제 논리 예시 2: 보면 x가 누구냐에 따라 달라지기 때문에 명제논리로 표현하기에는 부족함.

[ 술어 논리 예시 ]
- P(x): x는 개발자다.

x = 리누스 토발즈 -> 참
x = 뽀로로 -> 거짓

# x → 변수 (대상)
# P( ) → 성질이나 관계를 나타내는 것 (술어, predicate)

• 술어논리: 명제논리에서 대상이 무엇인지까지 포함해서 참/거짓을 따지는 논리 체계임.

• 명제함수: 술어논리 자체의 논리 체계를 실제로 위와 같이 함수로 표현한 것을 의미함.
• ** 쉽게말해, 변수의 값에 의해 함수의 진리값이 결정되는 문장이나 식을 의미함. **
• 변수의 명세: 명제 함수에 변수 값을 적시함으로써 진리값을 얻어낼 수 있음.
• 변수의 명세: 한정화(변수의 범위를 제시:∀, ∃) 를 통해서 변수의 범위를 지정 할 수 있음.

(2) 술어논리와 명제함수 - 한정화

• 한정화: 명제 함수의 변수를 특정 범위 안에서 묶어주는 그러한 과정을 한정화 라고 함.
• ** 즉, 변수를 그냥 두는 것이 아닌 "이 변수는 이런 범위에서 말하는 거야" 라고 지정하는 것임. **
• 한정화에는 전체한정자(∀) ,  존재한정자(∃) 총 두 종류가 존재함.

[ 전체한정자 ∀(양화사: 변수가 얼마나 어떻게 존재하는지 말해주는 기호임)  ]

[ 전체한정화 - 예시 ]
x는 학생이다      - 특정 x
어떤 x는 학생이다 - 존재한정
모든 x는 학생이다 - 전체한정

** 명제함수: P(x) ** 
** 전체한정화: ∀x P(x) **

예제1: ∀x (x는 우리반 학생 → x는 사람이다)
- 우리반 모든 학생은 사람이다 => 참
예제2: ∀x (x는 사람 → x는 개발자)
- 모든 사람은 개발자다 => 거짓

즉, 전체한정화는 명제 x에 접두사 모든(임의의)가 붙는다고 보면됨.

• 전체한정자: 모든 대상을 대상으로 묶는 양화사 즉, 전체를 한정으로 모든 임의의 x에 대한것을 의미하는 것임.
• ** 즉, 위의 예제2 와 같이 모든 사람은 개발자다는 거짓이 되며, 한 명이라도 개발자가 아니면 전체가 거짓이 되는 것임. **

[ 존재한정자 ∃(양화사: 변수가 얼마나 어떻게 존재하는지 말해주는 기호임) ]

• 어떤 특정 값이 하나라도 존재함을 의미하는 논리 기호임.
• 쉽게말해, 어떤 x에 값을 대입했을 때 하나라도 참인 값이 존재하면 참으로 본다는 의미임.
• ** 즉, ∃𝒙 𝑷(𝒙)는 참이다. 또는 거짓이다로 판별함. **

• ** 명제 함수 P(x) 에서 x가 무리수인 경우, x의 정의역이 유리수일 수 없기 때문에 하나도 없기에 ∃xP(x) 는 거짓이 된다. **

(3) 타당성검사

• 벤 다이어그램: 한정자가 사용된 명제함수의 타당성은 벤 다이어그램으로 직관적으로 검사 할 수 있음.

• 삼단논법: 삼단논법을 벤 다이어그램에 위와 같은 방식으로 표현해 타당성 검사를 할 수 있음.

---

✅ 4. 추론

• 추론: 특정 명제를 증명하기 위해서, 참으로 알려진 명제들을 기반해서 해당 명제를 증명해 나가는 그러한 과정을 추론이라함.
• 전제: 결론의 근거를 제공하는 이미 참으로 알려진 명제를 의미한다.
• 결론: 전제를 근거로 새롭게 명제로써 참이 된 것을 결론이라함.

• 유효추론: 전제가 참이되면, 결론이 항상 참이 되는 추론을 의미함. ( 전제가 참인 경우 유효추론 으로 보면 됨. )
• 예시를 보면, p가 q일 때 q 는 r 인가 하는 추론이라고 보면 됨. (삼단논법)
• ** 쉽게말해, 전제는 명제가 될 것이고, 해당 명제 모두가 참일 때 진리표의 결과값이 참인 경우에는 유효추론임. **

• p -> q 인 경우 참이라고 가정하면, q -> p 가 된다고 해서 참이 되지는 않음.
• ** 즉, 진리표를 보면 q 는 p 전제가 참임에도 결론이 거짓이 나오기 때문에 유효하지 않은 추론임을 알 수 있음. **