논리(Logic)
- QUESTION
- 수학적 진술의 의미를 정확히 표현하려면?
- ANSWER
- 논리 규칙을 사용
- 논리 규칙 (The rules of logic)
- 논리규칙들을 사용하여 수학적 논증이 정당한지, 정당하지 않은지를 구분
- The rules of logic give precise meaning to mathematical statements.
- 논리 규칙은 수학적 표현의 의미를 정확하게 기술할 수 있게 함
- 수학적 추론을 이해하는데 이용
- 컴퓨터 회로 설계, 프로그램 작성, 프로그램 정확성 검증 등에 활용
명제 (Proposition)
- 정의
- 참(true, T) 또는 거짓(False, F)을 판정할 수 있는 선언적 문장
- A proposition (p, q, r, s, ⋯) is a declarative statement that is either true (T) or false (F), but not both.
- 예제
- 1+1=2. (T)
- 2+2=5. (F)
- 서울은 대한민국의 수도이다. (T)
- 11213은 소수이다. (T)
- 명제가 아닌 예제
- 걔 누구니? (질문은 선언적 문장이 아님. )
- 이거 해! (명령은 선언적 문장이 아님.)
- x+2=5. (변수에 값이 대입되지 않았으므로 선언적 문장이 아님.)
논리 연산자(Logical Operator)
-
용어의 정의
- 복합명제(compound proposition)
- 하나 또는 여러 명제를 조합하여 새로운 수학적 명제를 만들 수 있음.
- 논리 연산자(logical operator) 혹은 접속사(connective)
- 복합명제를 만들 때 사용하는 연산자.
- 논리 연산자는 명제 연산자(propositional operator) 혹은 불리언 연산자(Boolean operator)라고도 함
- 피연산자(operand)로서 명제 혹은 진리값(truth value)을 취함.
- 복합명제(compound proposition)
-
논리 연산자의 종류
명칭(영어) 명칭(한글) 표현 Arity 기호 Negation operator 부정 연산자 NOT Unary ¬ Conjunction operator 논리곱 연산자 AND Binary ∧ Disjunction operator 논리합 연산자 OR Binary ∨ Exclusive-OR operator 배타적OR 연산자 XOR Binary ⊕ Implication operator 함축 연산자 IMPLIES Binary → Biconditional operator 상호조건 연산자 IFF Binary ↔ ※ A conditional statement is also called an implication.
※ IFF - if and only if
- 부정(Negation)
-
정의 1
- p가 명제이면, "It is not the case that p" 역시 명제이고,
이를 p의 부정(negation)이라 하며, ¬p(not p)로 표기함
- p가 명제이면, "It is not the case that p" 역시 명제이고,
-
예제
- 명제(p) "I have brown hair."의 부정 명제 (¬p)
- "I do NOT have brown hair."
- 명제 "Today is Sunday."의 부정 명제
- "Today is NOT Sunday."
- 명제(p) "I have brown hair."의 부정 명제 (¬p)
-
부정 연산자의 진리표(Truth table)
p ¬p T F F T
- 논리곱(Conjunction)
-
정의2
- p와 q가 명제이면, "p and q"도 명제이며, 이를 p와 q의 논리곱(conjunction)이라 하고, p∧q라 표기함
- 이 명제는 p, q가 모두 참일 때만 참이 되며, 그 외는 모두 거짓이 됨
- p와 q가 명제이면, "p and q"도 명제이며, 이를 p와 q의 논리곱(conjunction)이라 하고, p∧q라 표기함
-
예제
-
p = "I will have salad for lunch.",
q = "I will have a steak for dinner." -
p∧q = "I will have salad for lunch and I will have a steak for dinner."
-
-
논리곱 연산자의 진리표(Truth table)
p q p∧q T T T T F F F T F F F F
- 논리합(Disjunction)
-
정의 3
- p와 q가 명제이면, "p or q"도 명제이며, 이를 p와 q의 논리합(disjunction)이라 하고, p∨q라 표기함
- 이 명제는 p, q가 모두 거짓일 때만 거짓이 되며, 그 외는 모두 참이 됨
- p와 q가 명제이면, "p or q"도 명제이며, 이를 p와 q의 논리합(disjunction)이라 하고, p∨q라 표기함
-
예제
-
p = "My car has a bad engine.",
q = "My car has a abd carburetor." -
p∨q = "My car has a a bad engine, or my car has a abd carburetor."
-
-
논리합 연산자의 진리표(Truth table)
p q p∨q T T T T F T F T T F F F
- 배타적-OR(Exclusive-OR)
-
정의 4
- p와 q가 명제이면, "p exclusive-or q"도 명제이며, 이를 p와 q의 논리합(disjunction)이라 하고, p⊕q라 표기함
- 이 명제는 p, q 중 어느 하나만이 참일 때만 참이 되며, 그 외는 모두 거짓이 됨
- p와 q가 명제이면, "p exclusive-or q"도 명제이며, 이를 p와 q의 논리합(disjunction)이라 하고, p⊕q라 표기함
-
예제
-
p = "I will earn an A in this course.",
q = "I will drop this course." -
p⊕q = "I will either earn an A for this course, or I will drop it
(but not both !)"
-
-
배타적-OR 연산자의 진리표(Truth table)
p q p⊕q T T F T F T F T T F F F
- 조건문(Conditional Statements)
-
정의 5
-
p와 q가 명제이면, 조건문 "p→q"도 명제이며,
이 명제는 p가 참이고 q가 거짓일 경우에만 거짓이 되며, 그 외는 모두 참이 됨- p : 가정, 전제 (hypothesis, antecedent)
- q : 결론, 결과 (conclusion, consequent)
-
-
예제
-
p = "You study hard.",
q = "You will get a good grade." -
p→q = "If you study hard, then you will get a good grade."
(else it could go either way)
-
-
함축 연산자(→) 또는 조건문(p→q)의 진리표(Truth table)
p q p→q T T T T F F F T T F F T -
Conditional statements(p→q)을 표현하는 영어 문장
- p implies q : p는 q를 함축한다
- If p, then q (= If p, q) : p이면 q이다
- p only if q : q일 경우에만 p이다
- p is sufficient for q
- q is necessary for p
- p follows from q : q로부터 p가 귀결된다
- 역(converse), 이(inverse), 대우(contrapositive)
-
정의 5 (조건문 p→q)로부터의 새로운 조건문
- 역(converse): q→p
- 이(inverse): ¬p→¬q
- 대우(contrapositive): ¬q→¬p
-
예제
- 명제: "If it is raining, then the home team wins."
- 역: "If the home team wins, then it is raining."
- 이: "If it is not raining, then the home team does not win."
- 대우: "If the home team does not win, then it is not raining."
- 여기서 '명제,대우' 와 '역,이' 는 동치(equivalent)
-
역/이/대우의 진리표(Truth table)
p q ¬p ¬q p→q q→p ¬p→¬q ¬q→¬p T T F F T T T T T F F T F T T F F T T F T F F T F F T T T T T T
- 상호조건명제(Biconditional)
-
정의 6
- p와 q가 명제이면, 조건문 "p↔q"를 상호조건명제(biconditional)라 하고, p와 q가 동일한 진리값을 가질 때(모두 참이거나 모두 거짓일 때) 참이 되며, 다른 진리값을 가지면 거짓이 됨
- p↔q ⇔ (p→q) ∧ (q→p) ⇔ ¬(p⊕q)
-
예제
-
p = "You can take the flight.",
q = "You buy a ticket." -
p↔q = "You can take the flight if and only if you buy a ticket."
-
-
상호조건명제 연산자의 진리표(Truth table)
p q p↔q T T T T F F F T F F F T -
"p↔q"을 표현하는 영어 문장
- p if and only if q
- p is necessary and sufficient for q
- q is necessary and sufficient for p
논리 연산자의 우선순위(Precedence)
-
연산자 우선순위
연산자 우선순위 ¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5 -
¬p∧q는 (¬p)∧q를 의미하며, ¬(p∧q)를 의미하지 않음
-
p∧q∨r은 (p∧q)∨r를 의미하며, p∧(q∨r)를 의미하지 않음
-
우선 순위를 명확히 하기 위하여 괄호 "()"를 사용!!!
다른 표기법들
비트 연산자
-
비트(bit)란?
- binary digit(이진수)에서 따온 단어임
- 비트는 1 (true)과 0 (false)의 값을 가짐
- True 혹은 false를 값으로 갖는 변수(variable)를 Boolean variable이라 함
-
비트연산자의 진리표(Truth table) - OR, AND, XOR
p q p∨q p∧q p⊕q 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 -
예제
