명제

• 명제는 참 또는 거짓으로 판별할 수 있는 문장이나 수학적 식으로 평서문 이어야 한다.
  • 대화형, 명령어, 의문문은 명제가 아니다.
• 참과 거짓을 명제의 진리값이라고 한다.

논리 연산

• 참, 거짓을 구별할 수 있는 명제를 대상으로 하는 연산

기본 논리 연산

기본 논리 연산 진리표

• OR, AND, XOR은 두 개의 입력, 한 개의 출력이다.
• NOT은 한 개의 입력, 한 개의 출력이다.

합성명제(compound proposition)

• 하나 이상의 명제와 논리연산자들이 결합되어 만들어진 명제
  • 예) "한국의 수도는 서울이고, 미국의 수도는 워싱턴이다."

합성명제 $(p\lor q) \land (p \oplus q)$의 진리표

조건명제(conditional proposition)

• 명제 p와 q가 있을 때, 명제 p가 조건의 역할을 수행하고 명제 q가 결론의 역할을 수행하는 경우, p와 q의 합성명제를 조건명제라고 하고, $p \rightarrow q$로 나타낸다.
• 조건명제는 어떤 사실의 인과관계를 나타내는 명제이다.
• 명제 p가 참이고 q가 거짓일 경우만 거짓이 되고, 나머지의 경우에는 모두 참이라고 정의한다.

필요조건과 충분조건

• 필요조건
  • 조건명제 $p \rightarrow q$에서 q는 p의 필요조건이다.
• 충분조건
  • 조건명제 $p \rightarrow q$에서 p는 q의 충분조건이다.

쌍조건명제(biconditional proposition)

• 명제 p와 q가 있을 때, p가 조건일 때 q가 결론이 되고 동시에 q가 조건일 때 p가 결론이 되는 경우, p와 q의 합성명제를 싸옺건명제라고한다. $\leftrightarrow$ 로 나타낸다.
• 쌍조건명제는 두 개의 조건명제가 서로 결합되어 만들어진다.
• 쌍조건명제 $p \leftrightarrow q$는 $(p \rightarrow q)\land (q \rightarrow p)$ 로 분해할 수 있다.
  • p는 q이기 위한 필요충분조건이다.
• 쌍조건명제는 p와 q가 동시에 동일한 진리값을 가질 때 참이 된다.

논리적 동치(logical equivalence)

• 두 명제 p와 q가 논리적으로 동등하면 논리적 동치라 하고, $p \equiv q$로 나타낸다.
  • 즉 두 명제 p와 q가 항상 동일한 진리값을 가지면 논리적 동치라고 한다.
• $p \leftrightarrow q$와 동치인 것은 $\sim (p \oplus q)$

• 명제와 대우는 동치이다.
• 역과 이도 서로 대우관계이면서 진리값이 동일한 동치관계이다.
• 주어진 조건명제에 대해 논리적으로 참, 거짓을 증명하기 어려운 경우에는 해당 조건명제의 대우를 이용하여 쉽게 해결할 수 있다.
  • (명제) 영희가 서울에 있다면, 그녀는 한국에 있는 것이다.
  • (대우) 영희가 한국에 없다면, 그녀는 서울에 없는 것이다.
    • 명제와 대우는 동치이므로 서로 진리값이 동일하다. 따라서 주어진 두 문장은 서로 동치관계에 있다고 할 수 있다.

논리적 동치법칙

• 논리 명제가 서로 같은 의미를 가질 때 적용되는 법칙

• 예제) 논리적 동치법칙을 이용하여 $p \lor (p \land q)$와 $p$가 논리적 동치임을 보이시오.

• $p \lor (p \land q) \equiv (p \land T) \lor (p \land q)$ (항등법칙)

  • $\equiv p \land (T \lor q)$ (분배법칙)
  • $\equiv p \land T$ (흡수법칙)
  • $\equiv p$ (항등법칙)

• 예제) 드 모르간 법칙을 이용하여 다음 식의 부정을 나타내시오

• $-5 < x < 2$

• $\sim (-5 < x < 2) \equiv \sim((-5 < x) \land (x < 2)) \equiv \sim (-5 < x) \lor \sim (x < 2)$

• $\equiv (x \leqq -5) \lor (2 \leqq x)$

• 예제) 논리적 동치법칙을 이용하여 $\sim (p \lor q) \lor (\sim p \land q)$를 간단히 하시오

  • $(\sim p \land \sim q) \lor (\sim p \land q)$
  • $\sim p \land (\sim q \lor q)$
  • $\sim p \land T$ (부정법칙: $\sim q \lor q \equiv T$)
  • $\sim p$ (항등법칙)

항진명제와 모순명제

• 항진명제: 합성 명제를 구성하는 명제의 진리값에 상관없이 항상 참인 명제
  • $p \rightarrow p$
  • $p \lor p$
  • $p \land q \rightarrow p \land q$
• 모순명제: 합성 명제를 구성하는 명제의 진리값에 상관없이 항상 거짓인 명제
  • $p \land \sim p$
  • $(p \land q) \land \sim p$
  • $(p \leftrightarrow q) \land (p \oplus q)$
    • 쌍조건명제가 참이 되려면 p, q가 같아야 함
    • p, q의 배타적 논리합은 서로 다를 때만 참이된다.

우선순위

1. $\sim$
2. $\land$, $\lor$
3. $\rightarrow$, $\leftrightarrow$
4. $\equiv$

술어논리

• 술어: 문장을 구성하는 기본요소로서 주어의 동작, 상태, 성질에 대해 서술하는 말이다.
• A는 B이다.
  • A: 주어
  • B: 술어

명제함수

• 변수의 값에 의해 참과 거짓을 구별할 수 있는 문장이나 수학적 식
  • 정의역: 변수의 영역

전체한정자(universal quantifier): $\forall$

• 전체한정자는 "모든"을 의미하며, 명제함수 $\forall xP(x)$ 와 같이 사용되었을 경우에는 정의역의 모든 x에 대해서 P(x)가 참임을 의미한다.
• 모든 정수 x에 대하여 "x + 5 = 5 + x"이다.
  • $\forall x(x + 5 = 5 + x)$
• 모든 사람은 죽는다.
  • $\forall x(x는 죽는다.)$

존재한정자(existential quantifier): $\exists$

• 존재한정자는 존재한다를 의미하며, 명제함수 $\exists xP(x)$와 같이 사용되었을 때는 P(x)가 참이 되는 어떤 x가 정의역에 존재한다는 것을 의미한다.
  • $\exists xP(x)$ 식의 의미: 정의역의 어떤 원소 x에 대하여 P(x)는 참이다.
• 어떤 실수 x에 대하여 "x^2 = 4"이다.
  • $\exists x(x^2 = 4)$

전체한정자의 부정

• 모든 사과는 빨갛다의 부정: 어떤 사과는 빨갛지 않다.

  • $\sim \forall x(x는 빨갛다) \equiv \exists x(x는 빨갛지 않다)$
  • $\sim \forall xP(x) \equiv \exists x \sim P(x)$

• 어떤 차는 초록색이다.의 부정: 모든 차가 초록색이 아니다.

  • $\exists xP(x) \equiv \forall x \sim P(x)$

타당성 검사

• 한정자가 사용된 명제함수의 타당성을 분석하기 위해 벤다이어그램을 사용할 수 있다.

추론

• 추론은 참이라고 알려져 있는 명제로부터 논리적인 과정을 거쳐 또 다른 명제를 이끌어 내는 과정을 말한다.

  • 전제: 결론의 근거를 제공하는 이미 알려진 명제
  • 결론: 새로 유도된 명제

• 추론은 하나 이상의 전제와 하나의 결론으로 구성된다.

유효추론

• 정당한 추론
• 유효추론은 전제를 참이라고 가정하였을 때, 결론이 항상 참이 되는 추론을 의미한다.