https://youtu.be/MvJvu2iUrNA

명제와 증명

명제와 연결사

• 명제: 참, 거짓이 분명히 판단되는 문장
  • 단순 명제: p, q, r
  • 합성 명제: 몇 개의 단순 명제들이 연결사에 의해 결합된 명제
• 연결사: 두 명제 p와 q에 대해
  • 부정
    • $\sim p$
    • not p
  • 논리곱
    • $p \wedge q$
    • p and q
  • 논리합
    • $p \vee q$
    • p or q
  • 조건
    • $p \to q$
    • if p then q
  • 쌍조건
    • $p \leftrightarrow q$
    • p if and only if q
    • 줄여서 iff 라고도 함

진리표

• 진리표란 명제의 진리값을 표로 나타낸 것

제목 없는 데이터베이스

• 진리집합
  • 해당 명제가 참이 되도록 하는 모든 원소들의 집합
  • 집합이므로 대문자로 표기
• 명제 P가 거짓이라는 것은 진리집합에 해당 하는 원소들이 없다는 의미이고, P는 공집합이라는 의미가 된다.
• $p \to q$ 는 p가 q의 부분집합인지를 묻는 것과 같다. 만일 p가 거짓이면 p가 공집합이 되는 것이므로, p가 거짓일 때는 q와 관계 없이 참이 된다.
• 진리표에 의해 다음 명제들은 참이다.
  • $p \to q \equiv \sim p \vee q$
  • $\sim (p \wedge q) \equiv \sim p \vee \sim q$ (드모르간의 법칙)
  • $p \to q \equiv \sim q \to \sim p$ (대우 법칙)
  • $(p \vee q) \vee r \equiv p \vee (q \vee r)$ (결합 법칙)
  • $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ (분배 법칙)
  • 위 명제들의 and를 or로, or를 and로 동시에 바꾸면 결과는 같다.

연역적 추론

• 연역적 추론이란 이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 것

명제 함수

명제함수와 한정기호

• 명제함수: 변수 x가 결정되어야만 참, 거짓이 판단되는 문장
  • $p(x), q(x)...$
• 한정기호: 전칭기호와 존재기호
  • $\forall$: for every
  • $\exists$: for some

명제의 부정