논리연산과 명제

명제

명제란 '참' 혹은 '거짓'임을 검증할 수 있는 '객관적 사태'가 포함된 문장을 말한다.
예를 들어, 아래의 문장이나 수식은 참이나 거짓을 판별할 수 있는 문장으로 명제라 할 수 있다.

• 달은 지구의 위성이다. (참)
• 1+1=2 이다. (참)
• 1 > 2 이다. (거짓)

하지만 아래의 문장들은 참이나 거짓을 판별할 수 없으므로 명제라 할 수 없다.

• 그림이 아름답다.
• x+7 = 10 이다.

조건명제

변수를 포함한 문장이나 식이 변수의 값에 따라 참, 거짓이 판별되는 문장이나 식을 조건이라 한다. 이런 두 조건으로 이루어진 명제를 조건 명제라 한다. 표기는 "p → q" 로 표기하고 "p이면 q이다"로 읽는다. p는 가정, q는 결론이라 한다.
예) 명제 "x=1이면 x+3=4 이다"에서 x=1은 가정, x+3=4는 결론이다.

조건명제의 진리표

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

충분조건 필요조건 필요충분조건

명제 p → q가 참일 때, 기호로 p ⇒ q와 같이 표기하고
p는 q이기 위한 충분조건, q는 p이기 위한 필요조건이라고 한다.
예1) p: x<0, q:x+|x|=0
두 조건 p={x|x<0}, q={x|x≤0} 이므로, p ⇒ q가 성립하고, q ⇒ p는 성립하지 않는다. 따라서 p는 q이기위한 충분조건에 해당한다. 집합 관계로 보면 p⊂q 로 표시된다.

예2) p: △ABC는 이등변삼각형이다., q: △ABC는 정삼각형이다.
예1번과 달리 q ⇒ p가 성립하고, p ⇒ q는 성립하지 않는다. 따라서 p는 q이기 위한 필요조건에 해당한다.

명제 p → q에 대하여 p ⇒ q이고 q ⇒ p일 때, p⟺q로 표기하고 p는 q이기 위한 필요충분조건이라고 한다.
예3) p: x2+y2=0, q:|x|+|y|=0 (단, x,y는 실수)
p={(x,y)|x=0, y=0}, q={(x,y)|x=0, y=0}이므로, p=q이다. 이는 필요충분조건에 해당한다.

명제의 증명

• 정의: 용어의 뜻을 명확하게 정한 문장
• 증명: 정의나 명제의 가정 도는 이미 옳다고 밝혀진 성질을 이용하여 어떤 명제가 참임을 설명하는 것
• 정리: 참임이 증명된 명제 중에서 기본이 되는 것이나 다른 명제를 증명할 대 이용할 수 있는 것(예. 피타고라스의 정리)

명제의 증명

• 직접 증명: p가 참이라는 데에서 시작하여, 공리나 기존의 증명된 다른 정리로부터 q가 참이라는 결론에 바로 도달하는 방식
  예) 모든 홀수는 두 제곱수의 차로 나타낼 수 있다.

  증명) a가 홀수라면
  a = 2k+1
  k2+a = k2+2k+1
  k2+a = (k+1)2
  ∴ a = (k+1)2 - k2

• 간접 증명: 직접 증명이 어려운 경우 대우 또는 귀류법을 통하여 간접적으로 증명하는 방식
  1. 대우: 명제 p → q가 참이면 역인 ~q → ~p도 참이므로 이를 사용하여 증명
  2. 귀류법: 명제 또는 결론을 부정하면 모순이 생기는 것을 보여서 참임을 증명

  명제 '자연수 a,b에 대하여 ab가 짝수이면 a 또는 b는 짝수이다.'
  명제의 대우는 'a와 b가 모두 홀수이면 ab는 홀수이다.' 이를 증명하면,
  a = 2k+1, b=2l+1
  ab = (2k-1)(2l-1)=4kl-2k-2l+1 = 2(2kl-k-l)+1
  이므로 a와 b가 모두 홀수이면 ab는 홀수이다.
  따라서 a,b에 대하여 ab가 짝수이면 a 또는 b는 짝수이다.

논리연산

논리 연산(logical operation, logical connective) 혹은 불 연산(boolean operation)은 참, 거짓 두 가지 원소(진리값으로 불림)만 존재하는 집합 또는 명제에서의 연산을 말한다.
논리 연산에는 논리합(OR), 논리곱(AND), 부정(NOT), 배타적 논리합(XOR)이 존재한다.

논리연산	기호	설명
논리곱(AND)	∧	주어진 명제에 모두가 참인가
논리합(OR)	∨	주어진 명제에 적어도 1개 이상의 참이 있는가
부정(NOT)	¬	주어진 명제의 참과 거짓을 반전
배타적 논리합(XOR)	⊕	2개의 명제 가운데 1개만 참일 경우를 판단

논리연산 진리표

논리 연산의 결과를 표 형태로 나타낸것을 진리표라고 한다. 아래는 논리 연산에 대한 진리표이다.

p	q	p∧q	p∨q	p⊕q
T	T	T	T	F
F	F	F	F	F
T	F	F	T	T
F	T	F	T	T

부정은 아래와 같다.

p	¬q
T	F
F	T

논리연산의 결과가 항상 참인 명제를 항진명제라고 하며, 항상 거짓인 명제를 모순명제라고 한다.
항진명제의 예로는 P∨¬P 가 있다. 모순명제는 P∧¬P 가 있다.

논리연산의 법칙

• 드 모르간의 법칙
  ¬(p∧q) = ¬p∨¬q

• 결합법칙
  (p∨q)∨r = p∨(q∨r)

• 분배법칙
  p∧(q∨r)=(p∧q)∨(p∧r)

파이썬에서의 논리연산

연산자	논리연산
&	AND
|	OR
^	XOR
~	NOT

논리연산을 활용해서 풀 수 있는 알고리즘 문제
[leetcode] 136. Single Number

문제풀이)
1개의 숫자를 제외한 나머지 숫자는 2회씩 반복되기 때문에 XOR연산을 수행할 경우 모두 0으로 치환된다. 2 ^ 2 = 0 이고 0 ^ 1 = 1이기 때문에 xor연산을 수행하면 남은 1개의 숫자를 알 수 있다

def singleNumber(self, nums: List[int]) -> int:
	answer = 0
    for idx, item in enumerate(nums):
    	answer ^= item
    return answer