이산수학 (Discrete Mathematics) 1.1 논리 (Logic) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

논리(Logic)란? 논리(logic)란 수학적 표현의 의미를 정확하게 기술할 수 있게 함 논리는 회로 설계, 프로그램 작성, 프로그램 정확성 검증 등에 활용

명제(Proposition) 명제의 정의 명제의 예제 명제가 아닌 예제 1.1 Logic 명제의 정의 명제란 참(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) Seoul is the capital of Korea. 11213 is prime. 명제가 아닌 예제 Who is there? (not declarative, question) Just do it! (command) x + 2 = 5. (non-constant value, variable)

논리 연산자(Logical Operator) (1/2) 논리 연산자 관련 용어 정의 하나 또는 여러 명제를 조합하여 새로운 수학적 명제를 만들 수 있으며, 이를 복합명제(compound proposition)라 한다. 복합명제를 만들 때 사용하는 연산자를 논리 연산자(logical operator) 혹은 접속사(connective)라 한다. 논리 연산자는 명제 연산자(propositional operator) 혹은 불리언 연산자(Boolean operator)라고도 불리며, 피연산자(operand)로서 명제 혹은 진리 값(truth value)을 취한다. ( 본 강의에서는 이들 용어를 동일한 의미로 혼용하여 사용할 예정임)

논리 연산자(Logical Operator) (2/2) Boolean Operator의 예 명칭(영어) 명칭(한글) Nickname Arity Symbol Negation operator 부정 연산자 NOT Unary ¬ Conjunction operator 논리곱 연산자 AND Binary  Disjunction operator 논리합 연산자 OR  Exclusive-OR operator 배타적OR 연산자 XOR  Implication operator 함축 연산자 IMPLIES  Biconditional operator 상호조건 연산자 IFF ↔

부정 명제의 예제 부정(Negation) (1/2) 부정의 정의 1.1 Logic 부정의 정의 p가 명제이면, “It is not the case that p” 역시 명제이며, 이를 p의 부정(negation)이라 하며, ¬p(not p)로 표기한다. The unary negation operator “¬” (NOT) transforms a proposition into its logical negation. 부정 명제의 예제 명제(p) “I have brown hair.”의 부정 명제(¬p)는 “I do NOT have brown hair.”이다. 명제 “Today is Sunday.”의 부정 명제는 “Today is NOT Sunday.”이다.

Negation operator의 truth table 1.1 Logic Negation operator의 truth table p ¬p T F Operand column Result column

논리곱(Conjunction) (1/2) 논리곱의 정의 논리곱 사용의 예제 1.1 Logic 논리곱의 정의 p와 q가 명제이면, “p and q”도 명제이며, 이를 p와 q의 논리곱(conjunction)이라 하고, pq라 표기한다. 이 명제는 p, q가 모두 참일 때만 참이 되며, 그 외는 모두 거짓이 된다. The binary conjunction operator “” (AND) combines two propositions to form their logical conjunction. 논리곱 사용의 예제 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 steak for dinner.”

Conjunction operator의 truth table 1.1 Logic Conjunction operator의 truth table p q pq T F

논리합(Disjunction) (1/2) 논리합의 정의 논리합 사용의 예제 1.1 Logic 논리합의 정의 p와 q가 명제이면, “p or q”도 명제이며, 이를 p와 q의 논리합(disjunction)이라 하고, pq라 표기한다. 이 명제는 p, q가 모두 거짓일 때만 거짓이 되며, 그 외는 모두 참이 된다. The binary disjunction operator “” (OR) combines two propositions to form their logical disjunction. 논리합 사용의 예제 p = “My car has a bad engine.”, q = “My car has a bad carburetor.” pq = “My car has a bad engine, or my car has a bad carburetor.”

Disjunction operator의 truth table 1.1 Logic Disjunction operator의 truth table p q pq T F

배타적-OR (Exclusive-OR) (1/2) 1.1 Logic 배타적-OR의 정의 p와 q가 명제이면, “p exclusive-or q”도 명제이며, 이를 p와 q의 배타적-OR(exclusive-or)라 하고, pq라 표기한다. 이 명제는 p, q 중 어느 하나만이 참일 때만 참이, 그 외는 모두 거짓이 된다. The binary exclusive-or operator “” (XOR) combines two propositions to form their logical “exclusive or”. 배타적-OR 사용의 예제 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 (Exclusive-OR) (2/2) 1.1 Logic Exclusive-OR operator의 truth table p q pq T F

함축 (Implication) (1/2) 함축의 정의 함축 사용의 예제 1.1 Logic 함축의 정의 p와 q가 명제이면, 함축(implication) “pq”도 명제이며, 이 명제는 p가 참이고 q가 거짓일 경우에만 거짓이 되며, 그 외는 모두 참이 된다. 이때, p를 hypothesis, antecedent라 부르고, q를 conclusion, consequent라 부른다. The implication pq states that p implies q. That is, if p is true, then q is true; but p is not true, then q could be either true or false. 함축 사용의 예제 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)

Implication operator의 truth table 1.1 Logic Implication operator의 truth table p q pq T F “pq”를 표현하는 영어 문장 p implies q. If p, then q. p only if q. p is sufficient for q. q is necessary for p.

역(converse), 이(inverse), 대우(contrapositive) 1.1 Logic 역, 이, 대우의 정의 역(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.” Converse/Inverse/Contrapositive의 truth table 동치(equivalent) p q ¬p ¬q pq qp ¬p¬q ¬q¬p T F

상호조건명제 (Biconditional) (1/2) 1.1 Logic 상호조건명제의 정의 p와 q가 명제이면, “p↔q”를 상호조건명제(biconditional)라 하고, p와 q가 동일한 진리 값을 가질 때 참이 되며, 다른 진리 값을 가지면 거짓이 된다. The biconditional p↔q states that p is true if and only if (IFF) q is true. 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.”

상호조건명제 (Biconditional) (2/2) 1.1 Logic Biconditional operator의 truth table p q p↔q T F “p↔q”를 표현하는 영어 문장 p if and only if q. p is necessary and sufficient for q. q is necessary and sufficient for p.

논리 연산자의 우선순위(Precedence) 1.1 Logic 우선 순위 테이블 Operator Precedence ¬ 1  2  3  4 ↔ 5 ¬pq는 (¬p)q를 의미하며, ¬(pq)를 의미하지 않는다. pqr은 (pq)r를 의미하며, p(qr)를 의미하지 않는다. 우선 순위를 명확히 하기 위하여 괄호 “()”를 사용

Some Alternative Notations 1.1 Logic

Logic and Bit Operations 비트(bit)란 binary digit(이진수)에서 따온 단어임 비트는 1(true)과 0(false)의 값을 가짐 True 혹은 false를 값으로 갖는 변수(variable)을 Boolean variable이라 함 Bit operator(OR, AND, XOR)의 truth table p q pq pq pq 1 Bit operation의 예제 01 1011 0110 11 0001 1101 11 1011 1111 bitwise OR 01 0001 0100 bitwise AND 10 1010 1011 bitwise XOR