ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 기초: 논리와 증명.
    수학/이산수학 2018. 7. 31. 12:16

    0. 프롤로그.

    아무래도 프로그래밍 설계에 이산수학 내용이 필요한지라 잠시 연재를 중단하고, 이산수학을 쭈욱 먼저 연재하고자 합니다.


    0과 1로 사고하는 컴퓨터란 것을 알아 감에서 연속적이지 않은 것을 다루는 이산수학은 중요하다.

    연속적인 것으론 미적분, 해석학 같은 게 있겠죠.


    즉, 이산수학은 비연속적인 것을 다루기 때문에 정수 영역($\aleph_0$)에 한정되는 영역.


    참조한 교재는 제가 썼던 Rosen의 이산수학, 이산수학 Express.

    Rosen의 이산수학의 내용이 비교적 탄탄하기 때문에 Rosen의 이산수학의 목차에 기반하여 만들어졌습니다.

    두 책을 요약한 내용들이라 생각하면 됩니다.

    막상 쓰고 보니 요약이라 하기도 좀.. 그러고 이것저것 섞은게 많긴 한데..


    01 기초: 논리와 증명

    02 기본구조: 집합, 함수, 수열, 수열의 합, 행렬

    03 알고리즘

    04 정수론과 암호

    05 귀납법과 재귀

    06 계수

    07 이산적 확률

    08 고급 계수 기법

    09 관계

    10 그래프

    11 트리

    12 부울 대수

    13 계산 모델링


    이렇게 총 13개의 포스트로 구성이 될 예정.


    2018/07/22 - [수학] - 무한, 집합, 그리고 수에 대해서.

    의외로 집합과도 닿아 있는 부분이 있어서 위 글을 읽고 오면 도움이 됩니다.

    나중에 강좌로 쓸 논리회로에도 필요한 내용입니다.


    이 강좌는 컴공생들을 타겟으로 만들어졌습니다.

    1. 기초: 논리와 증명.

    명제 논리와 술어 논리를 다룰 것이다.

    명제 논리는 사고의 최소 구성단위를 명제(원자적 명제)로 하여 명제의 내용·구조에는 개입하지 않고 각 명제 사이의 결합관계만을 연구한다.

    술어 논리는 명제에 '주어'와 '술어'의 구조가 존재하고, '주어'가 될 수 있는 대상에 대한 한정 기호를 사용할 수 있는 논리이다.


    1.1 명제 논리.

    명제는 참 또는 거짓. 즉, 진리값을 가지는 명확히 구분할 수 있는 선언적인 문장이나 식이다.


    집합으로 생각하면 개집합(Open Set).

    개집합이 궁금한 사람들은

    2018/07/30 - [수학] - 집합(위상)과 극한에 대하여[일부 내용 펌].

    을 보고 옵시다.



    예를 들어,

    $1+2=3$(참), $1\times 0=1$(거짓)

    파이어폭스는 웹브라우저다.(참)와 크롬은 마이크로소프트 제품이다.(거짓)

    은 진리값을 가질 수 있으므로 명제이다.


    반면,

    빵은 밥보다 맛있다.

    강좌 쓰기 귀찮지??

    $x+1=3$

    $x+y=3$

    은 명확히 구분되지 않으므로 명제가 아니다.

    두번째가 참인거 같은 기분이면 지는거. ㅜㅜ


    - 참과 모순.

    항상 참인 명제는 $\top$, 항상 모순인 명제는 $\bot$으로 나타낸다.

    $\top$은 True의 T모양을, $\bot$은 $\top$을 뒤집은 모양이라 한다.

    $\bot$은 집합에서 $\emptyset$이라 할 수 있다.


    - 명제와 선험성.

    철학쪽 공부를 해본 사람이라면, [나는 겉핥기 식으로 아아주 조금 했다.]

    인식론쪽에서 선험적 명제와 후험적 명제에 대해 들어봤을 것이다.


    수학을 배우기 때문에 간략하게만 설명하자면,

    선험적(a priori) 명제: 경험에 앞서 인식이 가능한 내용.(경험에 독립적이다)

    후험적(a posteriori) 명제: 경험 후에 인식이 가능한 내용.(경험에 의존적이다)


    그럼 명제랑 도대체 어떠한 관계가 있는가?

    로봇은 생명체가 아니다.

    라는 명제가 있다고 치자.

    [생명체에 대한 특성은 위키피디아-생물을 기준으로 정한다.]

    생물의 특성.

    생물이 무생물과 구별되는 일반적인 특징으로서, 생물은 자기증식능력, 에너지변환능력, 항상성 유지능력이라고 하는 3가지의 능력을 가지고 있다.

    1. 물질대사를 한다.
      • 체내에 필요한 물질이 합성, 분해되는 화학반응
      • 에너지의 출입이 반드시 따름
      • 효소가 반응을 매개함.
    2. 자극과 반응
      • 생존을 위해 필수적인 것으로 환경의 변화(자극)를 감지하고 반응함
    3. 항상성 유지
      • 외부 환경이 변하더라도 체내 환경을 일정하게 유지하려는 성질을 가진다.
        체온, 혈당량, 체액 농도 등을 유지
    4. 생식과 유전
      • 종족 유지위해 자신과 닮은 자손을 남기는 것.
    5. 발생과 생장
      • 세포가 커지거나, 세포 분열에 의해 수가 늘어나며 자람.
    6. 적응과 진화
      • 현재의 환경에 적응되고, 환경이 변함에 따라 변화할 수 있음.
        진화론에서는 변화된 형질이 환경에 유리하여 살아남게 되면, 새로운 종으로 된다고 주장.
    7. 정교하고 복잡한 체제
      • 모든 생물은 세포로 구성


    아직 머신러닝과 로봇공학의 발달이 덜 되었기 때문에 생식과 유전, 발생과 생장, 적응과 진화가 부족하다는 이유로 생명체가 아니라 할 수 있다. 그런데 미국 군의 비밀 연구소에서 작전 지역에서의 적응, 증식, 발달을 가능게 한 로봇이 개발되었을 수도 있다. 그렇다면, 그 로봇은 생명체라고도 할 수 있으므로 이 명제는 거짓이다.


    하지만 생명체라 정의할 수 있는 로봇이 있다는 것이 증명이 되었냐? 이건 또 아니다.

    어떠한 명제가 참이라는 것이 증명이 안되었다고 해서 그것을 '거짓'이라고 판단할 수는 없지만, 증명되지 않은 명제는 다른 명제의 성립 선험 조건에서 변수로 작용될 수 없다. 따라서 자동적으로 배제된다. 즉, "로봇은 생명체가 아니다."는 명제로 작용이 될 수 있고, 참이 된다.



    • 명제를 나타낼 때 관습.

    명제는 보통 $p,q,r, \; ...$로 명제 변수(진술 변수)를 표현한다.

    명제변수는 임의의 명제를 간단하게 표현하게 위해 나온 것으로, 정해진 진리값을 갖는 특정명제를 대입하여 진리값을 부여할 수 있다.

    진리값이 참 일때는 $T$, 거짓일 때는 $F$로 표시한다.



    명제를 다루는 분야를 명제 산술(Propositional Calculus) 또는 명제 논리(Propositional Logic)라 부른다.


    기존 명제에서 새로운 명제를 만드는 방법에 대해 알아보자.
    하나 또는 여러 개의 명제를 조합하여 많은 수학적인 명제가 만들어 지는데 이걸 복합 명제(Compound Propositon)이라 하며 논리 연산자로 만든다.


    1.1.1 부정(Negation, $\lnot$).

    연산자 1개만 사용해서 만드는 가장 간단한 명제 산술.

    $p$가 명제면 $\lnot p$ 또는 $\bar{p}$로 표기한다.
    "not $p$"라 읽는다.

    $p$

    $\lnot p$

    T

    F

    F

    T

    부정 연산자라 당연하게도(?) T는 F, F는 T가 된다.


    집합으로 따지면

    여집합[from Wikipedia

    여집합($p^c$)이다. 조금 더 정확하게 할 때 $\lnot p$은 $\operatorname{Int}(X-p)$이라 표현이 가능.

    * 집합 이야긴 $X$라는 위상 공간 하라 가정한다.

    $\operatorname{Int}$가 궁금한 사람들도 극한 글을 읽으면 됩니다.

    1.1.2. 접속사(Connectives).

    접속사를 이용한 명제는 2개 이상의 명제로부터 새로운 명제를 만들어내는 논리 연산자(Logical Operators)다.


    - 논리합(Disjunction, $\lor$).

    $p \lor q$는 논리합이며, "$p$ 또는(or) $q$"라 읽는다.

    모두 거짓일 때만 거짓이며 그 외는 모두 참임을 나타내는데 역시 $0$에 $0$을 제외한 숫자를 더하면 그 숫자가 되는 특성을 떠올리면 쉽게 이해할 수 있다.

    $p$

    $q$

    $p \lor q$

    T

    T

    T

    T

    F

    T

    F

    T

    T

    F

    F

    F


    집합에서는

    합집합[from Wikipedia]

    합집합($p \cup q$)이다.


    - 논리곱(Conjunction, $\land$).

    $p \land q$는 논리곱이며 "$p$ 그리고(and) $q$"라 읽는다.


    모두 참일 때만 참이며 그 외는 모두 거짓임을 나타내는데 곱셈에서 어떤 수든 $0$(여기선 $F$)을 곱하면 $0$($F$)이란 걸 떠올리면 쉽게 이해할 수 있다.

    진리값은 다음과 같다.

    $p$

    $q$

    $p \land q$

    T

    T

    T

    T

    F

    F

    F

    T

    F

    F

    F

    F

    * 가끔 but을 and 대신 사용하기도 한다고 한다.


    집합에서는

    교집합[from Wikipedia]

    교집합($p \cap q$)이다.


    - 배타적 논리합(Exclusive OR, $\oplus$).

    배타적 논리합($\oplus$)은 모두 참이거나 거짓을 때는 F, 하나만 참일때만 T이다.

    배타적일 때(같지 않을 때)만 논리합 과정이 일어나 T가 된다고 생각하면 됩니다.

    $p$

    $q$

    $p \oplus q$

    T

    T

    F

    T

    F

    T

    F

    T

    T

    F

    F

    F

    즉, 진리값이 모두 같을 때만 F, 하나라도 다르면 T.


    집합에서는

    대칭자[from Wikipedia]

    대칭자($p \triangle q$) 위치이다.




    • '포괄적(inclusive)' 논리합(or)과 '배타적(exclusive)' 논리합(or).

    보다시피 포괄적 or과 배타적 or이 존재한다.

    포괄적이란 표현은 넓게넓게 허용한다는 뜻이고, 배타적이란 표현은 같지 않으면 배척한다는 뜻이다.

    이 점을 유의해 두고 기억한다면 쉽게 이해 할 수 있다.



    1.1.3 조건문(Conditional state-ment).

    - 조건문(Conditional state-ment, $\rightarrow$ or $\implies$) or 함축(Implication).

    조건문 $p \rightarrow q$는 명제 "$p$이면 $q$(if $p$ then $q$)이다."란 뜻이다.[$\lnot p \lor q = p \rightarrow q$]

    $p$는 가정(Hypothesis) 또는 전제(Premise), 전항(Antecedent)이라고 하며, $q$를 결론(Conclusion) 또는 결과(Consequence)라고 한다.


    "$\lnot p$가 아니면 $q$($q$ unless $\lnot p$)"는 "$p$이면 $q$이다(if $p$ then $q$)"와 같다.

    $p$

    $q$

    $p \rightarrow q$

    T

    T

    T

    T

    F

    F

    F

    T

    T

    F

    F

    T


    명제 $p \rightarrow q$는 집합 $\operatorname{Int}\left((X-p)\cup q\right)$에 대응한다.

    - 파생된 조건문(Derived conditional state-ments).

    조건문 $p \rightarrow q$로부터 파생된 몇가지 조건문을 만들 수 있다.

    바로 바로 역(Convers), 이(Inverse), 대우(Contrapositive)!!


    $p \rightarrow q$의 역, 이, 대우는 다음처럼 나타낸다.

    역 이 대우[from 국립 공주대학교 수학교육과]


    역: $q \rightarrow p$

    이: $\lnot p \rightarrow \lnot q$

    대우: $\lnot q \rightarrow p$


    - 상호 조건문(Biconditional, iff or $\leftrightarrow$ or $\iff$) or 동치(Equivalent).
    두 개의 명제가 같은 진리값을 갖는다는 것을 표현하기 위하여 두 명제를 결합하는 다른방법.


    $p \leftrightarrow q$는 $p$는 $q$의 필요충분 조건을 뜻한다.

    영어로 하면 $p$ if and only if $q$”(if and only if는 흔히 iff라고도 쓰임). 즉 'q이면, 그때만 p이다'란 뜻이다.


    동일한 진리값을 가질 때 참이다. [$(p \rightarrow q) \land (q \rightarrow p)$]

    $p$

    $q$

    $p \leftrightarrow q$

    T

    T

    T

    T

    F

    F

    F

    T

    F

    F

    F

    T


    보다시피 베타적 논리합의 역이다.

    상호 조건문은 동치(Equivalent)를 뜻한다는 것을 알 수 있다.


    파생된 조건문에서 원래 명제와 대우는 동치이고, 역과 이는 동치다.

    집합으로 나타내면, $\operatorname{Int}\left((p \cap q)\cup\left(X-(p \cup q)\right)\right)$다.




    • 상호 조건문의 묵시적 사용(Implicit use of biconditionals)

    자연어에서는 'If, then' 또는 'Only if'형태로 표현되며, 'if and only if'의 다른 한 부분은 묵시적이다.즉 역(Converse)이 묵시적으로 주어지며 명시적으로 기술되지 않는다.

    자연어의 부정확성 때문에 자연어의 조건문이 그 역을 묵시적으로 포함하는지 아닌지를 가정해야 한다.



    1.1.4 논리 연산자의 우선순위.

    복합명제를 구성하는 연산자의 순서를 명확히 하기 위해 논리 연산자의 우선순위를 알아보도록 하자.

    사칙연산에서 $\times, \; \div$가 $+, \; -$보다 우선순위인 것처럼.

    연산자

    우선순위

    $\lnot$

    1

    $\lor$

    2

    $\land$

    3

    $\rightarrow$

    4

    $\leftrightarrow$

    5


    물론 괄호를 사용하는게 좋은 습관이긴 하다.


    1.1.5 복합명제와 진리표.

    나중에 복잡한 명제를 해석하거나 카노 맵을 그리려면 복합명제로 진리표를 만들 수 있어야 한다.


    말이 나온 김에 $(p \rightarrow q) \land (q \rightarrow p)$(상호 조건문)의 조건표를 그려봅시다.

    $p$

    $q$

    $p \rightarrow q$

    $q \rightarrow p$

    $(p \rightarrow q)\land(q \rightarrow p)$

    T

    T

    T

    T

    T

    T

    F

    F

    T

    F

    F

    T

    T

    F

    F

    F

    F

    T

    T

    T


    각 연산 요소에 대해 연산순서에 따라 하나씩 적어주고, 이를 쌓아 최종적인 명제의 답을 찾아가면 된다.


    1.1.6 논리식(Well-formed  formula, wff).

    대수연산에서 변수, 상수, 연산자등으로 대수식을 만드는 것처럼 논리연산에서도 명제와 접속사(Connectives)를 이용하여 논리식을 만들 수 있다.


    명제식은 이러한 명제변수, 연결사 및 괄호로 구성되는 문자열로서, 다음의 규칙에 의거하여 생성되는 정합논리식에 의해 정형화될 수 있다.


    1. 명제변수와 상수($T, F$)는 논리식.
    2. 접속사를 사용한 명제도 논리식.
    3. 1, 2번을 유한번 반복 적용한 것이 논리식.

    이 정의는 변수 집합이 유한한 경우 배커스-나우르 표기법으로 표현할 수도 있다.


    <alpha set> ::= p | q | r | s | t | u | ... (명제 변수의 임의의 유한 집합)
    <form> ::= <alpha set> | ¬<form> | (<form>∧<form>) | (<form>∨<form>) | (<form>→<form>) | (<form>↔<form>)
    


    배커스-나우르 표기법에 대하여.

    박스 안의 내용은 배커스-나우르 표기법에 필요한 지식들을 다루고 있습니다.

    • 파싱(Parsing, 구문 분석).

    일련의 문자열을 의미있는 토큰(token)으로 분해하고 이들로 이루어진 파싱 트리를 만드는 과정을 말한다.

    파싱 트리 예[from Introduction to Programming Languages, Parsing]

    • 튜플(Tuple).

    유한 개의 사물의 순서있는 열거이다. $n$개의 요소를 가진 튜플을 $n$-튜플($n$-tuple) 또는 $n$중쌍, $n$짝이라고 한다. 비어있는 열은 유일한 $0$-튜플이다. 임의의 $n$-튜플은 순서쌍의 개념을 이용하여 재귀적으로 정의된다.


    몇가지 정의법을 살펴볼까요?


    - 함수.

    $X, Y, F$를 각각 순서를 나타내는 정의역, 튜플의 성분인 공역, 함수라 할 때

    $$(a_1, a_2, a_3, ..., a_n) \equiv(X,Y,F)$$

    에서

    $X=\{1,2,\ldots,n\} \\ Y=\{a_1,a_2,\ldots,a_n\} \\ F=\{(1,a_1),(2,a_2),\ldots,(n,a_n)\}$관계가 성립된다.


    간단히 말해서

    $$(a_1,a_2,\ldots,a_n):=(F(1),F(2),\ldots,F(n))$$


    - 순서쌍.

    1. 0-튜플, 즉 비어있는 튜플은 공집합 $\emptyset$로 정의한다.
    2. 정수 $n>0$에 대해, $n$-튜플은 $n$-튜플의 첫 성분을 첫 성분으로 하고, 나머지 성분들로 이루어진 $(n-1)$-튜플을 둘째 성분으로 하는 순서쌍이다.
      $(a_1,a_2,a_3,\ldots,a_n)=(a_1,(a_2,a_3,\ldots,a_n))$


    $$(a_1,a_2,a_3,\ldots,a_n)=(a_1,(a_2,(a_3,(\ldots,(a_{n-2},(a_{n-1},(a_n,\emptyset)))\ldots))))$$

    라는 건데


    $$(1,2,3,4) = (1,(2,3,4)) = (1,(2,(3,4))) = (1,(2,(3,(4,\emptyset))))$$같은 예를 들 수 있습니다.


    2018/06/10 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 5. - 리스트와 재귀.

    와 상당히 유사하죠?


    - 집합.

    순서쌍을 이용한 방법과 은근 비슷합니다.

    1. 0-튜플, 즉 비어있는 튜플은 공집합 $\emptyset$로 정의한다.
    2. $x$를 $n$-튜플 $(a_1, a_2,... , a_n)$이라 하자. 끝에 $b$를 추가한 튜플 $x \rightarrow b \equiv (a_1, a_2,... , a_n, b)$는 다음과 같은 집합이다.
      $x \rightarrow b \equiv \{\{x\}, \{x, b\}\}$


    예시.

    역시 예를 들자면

    $$   \begin{array}{lclcl}
         ()      & &                     &=& \emptyset                                    \\
                 & &                     & &                                              \\
         (1)     &=& ()    \rightarrow 1 &=& \{\{()\},\{(),1\}\}                          \\
                 & &                     &=& \{\{\emptyset\},\{\emptyset,1\}\}            \\
                 & &                     & &                                              \\
         (1,2)   &=& (1)   \rightarrow 2 &=& \{\{(1)\},\{(1),2\}\}                        \\
                 & &                     &=& \{\{\{\{\emptyset\},\{\emptyset,1\}\}\},     \\
                 & &                     & & \{\{\{\emptyset\},\{\emptyset,1\}\},2\}\}    \\
                 & &                     & &                                              \\
         (1,2,3) &=& (1,2) \rightarrow 3 &=& \{\{(1,2)\},\{(1,2),3\}\}                    \\
                 & &                     &=& \{\{\{\{\{\{\emptyset\},\{\emptyset,1\}\}\}, \\
                 & &                     & & \{\{\{\emptyset\},\{\emptyset,1\}\},2\}\}\}, \\
                 & &                     & & \{\{\{\{\{\emptyset\},\{\emptyset,1\}\}\},   \\
                 & &                     & & \{\{\{\emptyset\},\{\emptyset,1\}\},2\}\},3\}\}                                       \\
        \end{array}
     $$


    성질.

    1. 중복된 원소가 있을 수 있다. 튜플의 원소를 중복해서 쓰면 다른 튜플이 된다. 예: $(1, 2, 3) \neq (1, 2, 2, 3)$, 하지만 집합 $\{1, 2, 3\} = \{1, 2, 2, 3\}$
    2. 정해진 순서가 있다. 튜플의 원소의 순서를 바꾸면 다른 튜플이 될 수 있다. 예: $(1, 2, 3) \neq (3, 2, 1)$, 하지만 집합 ${1, 2, 3} = {3, 2, 1}$
    3. 튜플의 원소의 개수는 유한하다. 하지만 집합, 중복집합은 원소 개수가 무한할 수도 있다.


    • 클레이니 스타(Kleene Star).

    문자열이나 문자의 집합에 쓰이는 단항 연산으로, 0개 이상의 임의 원소의 연쇄를 뜻한다.


    집합 $V$의 $n$회 연쇄는

    $$V^0 = \{\varepsilon\} \\
    V^1 = V \\
    V^n = V \circ V^{n-1} = \{uv|u\in V, v\in V^{n-1}\} (n \ge 2)$$라 할 때


    $$V^* = \sideset{}{_{i=0}^\infty}\bigcup V^i = \bigcup_{i \in \mathbb{N} }V^i = \{\varepsilon\} \cup V \cup V^2 \cup V^3 \cup V^4 \cup \ldots.$$를 클레이니 스타라고 한다.


    예시.

    $$\begin{array} \{ \{a, b\}^* = &\{& \\
    & &\varepsilon,\\
    & &a, b,\\
    & &aa, ab, ba, bb,\\
    & &aaa, aab, aba, abb, baa, bab, bba, bbb,\\
    & &...&\}&\end{array}$$


    $$\begin{array} \{ \{ab,c\}^* = &\{&\\
    & & \varepsilon,\\
    & &ab, c,\\
    & &abab, abc, cab, cc,\\
    & &ababab, ababc, abcab, abcc, cabab, cabc, ccab, ccc,\\
    & &...&\}&\end{array}$$


    • 문맥-자유 문법(Context-free grammar, CFG).

    형식 언어에서 가능한 모든 문자열을 설명하는 생산 규칙 집합이다. 즉, 임의의 문자열이 주어진 문법에 의하여 유도될 수 있는가를 확인하는 것.


    모든 생성규칙이

    $$A \to x$$

    형태를 따른다.


    $A$는 비말단(비종결자) 기호이고,  $x$는 비말단과 말단 기호들로 구성된 문자열이다.

    말단 기호는 $0, 1, 2,...$같이 더 이상 나눌 수 없는 원자적인 기호(알파벳).


    문맥-자유 문법 $G$를 $4$-튜플인  $G = (V, \Sigma, R, S)$라 정의할 때,

    1. $V$는 비말단 기호의 유한집합.
    2. $\Sigma$는 말단 기호의 유한집합으로 $V$와 서로소다.
    3. $R$은 $V$에서 $(V \cup \Sigma)^*$로 연결되는 생성 규칙의 유한집합이다.
      $R$의 멤버는 프로덕션이라 한다. $^*$표시는 클레이니 스타(Kleene Star)이다.
    4. $S$는 시작 기호(변수)로, $V$의 원소다.

    알면 좋은 것.

    생성규칙에서 $A\in V$, $x\in R$에 속한다.

    언어 $L$은 $\Sigma ^*$의 부분집합.

    말단기호는 $a,b,c,...$, 문자열은 흔히 $u,v,w,...$처럼 표현.

    언어 $L$ 에 대해서 $L = L(G)$를 만족하는 문맥-자유 문법 $G$가 존재하고 오직 그럴 때에만 $L$ 을 문맥-자유 언어 (context-free language : CFL)라고 한다.


    예시.

    $$G = (\{S\}, \{a,b\}, P,S)$$

    생성규칙을 보면, $S \to aSa\\
    S \to bSb,\\
    S \to \varepsilon$ 이고,

    $S \to aSa \to aaSaa \to aabSbaa \to aabbaa$처럼 유도된다.


    $L(G)=\{ww^R : w \in \{a,b\}^*\}$가 성립한다.


    문장의 문법적 유도를 따른다는 특성 때문에 컴파일러나 각종 파싱하는 것에서 유용한 이론이다.


    •  배커스-나우르 표기법(Backus–Naur form, BNF).

    문맥 자유 문법(Context-free grammar, CFG)을 정규화 표현하기 위해 만들어진 표기법이다.


    * 정규화

    같은 종류의 표현을 묶어 간소화하는 과정.


    표현법.

    <기호> ::= _표현식_

    으로 표시합니다.

    1. <기호>에는 말단 기호가 될 수 없습니다.(비말단 기호임)
    2. 비말단 기호는 <와 >로 묶어서 표현합니다.
    3. 여러가지 기호 중 선택이 가능함을 표시하기 위해 |를 사용합니다.
    4. ::=는 왼쪽의 기호가 오른쪽의 식으로 대체됨을 의미합니다.


    재귀적인 정의라는 것을 알 수 있습니다.


    1.2 명제 논리의 응용

    1.2.1 자연어 문장 변환.

    우리가 나타내려는 뜻을 논리적으로 표현하려면 자연어를 논리식으로 변환할 필요가 있다.

    자연어의 복잡함과 모호함 때문이다.


    이러한 원인으로는

    - 목적 표현의 복잡성.

    - 대응의 다양성.

    - 구성요소간의 상호작용.

    를 꼽는다.

    자연어의 해석에 대하여 정보를 더 원한다면 자연어 이해를 참고.


    자연어를 논리식으로 바꾸어 보겠습니다.


    교수님이 다음과 같은 공지를 하였다.

    푸린이 같은 교수님 ㅠ[출처]

    목표 진도까지 못나가고 수업 시간이 지나지 않으면 강의를 계속한다.


    1. 문장을 간단히 표현하기 위해 명제 변수를 도입합니다.

    $p$: 목표 진도까지 못나감.

    $q$: 수업 시간이 안지남.

    $r$: 강의를 계속한다.


    2. 명제 변수끼리의 관계를 분석합니다.

    $(p \land q) \rightarrow r$

    [사실 $\lnot$을 도입하는 것이 옳은 방향이나 깔끔한 예제를 위해 쓰지 않았다]


    여기서 $\rightarrow$의 조건이 참일 때만 거짓이 나오는 이유를 이해해보도록 합시다.

    (헷갈려하는 사람들이 많더군요)


    목표 진도까지 못나가고, 수업 시간이 안지나면($p \land q$, 참) 강의를 계속하는 것($r$참)은 당연한 일입니다.($(p \land q) \rightarrow r$, 참)


    그럼 목표 진도까지 못나가고, 수업 시간이 안지났는데($p \land q$, 참) 강의를 끝내는 것($r$, 거짓)은 거짓이겠죠.($(p \land q) \rightarrow r$, 거짓)


    이번엔 거짓의 조건을 해봅시다.

    목표 진도까지 나갔으나 수업시간이 안끝난 상황($\lnot p \land q$, 거짓)

    또는 목표 진도까지 못나갔지만 수업시간은 끝난 상황($p \land \lnot q$, 거짓)에

    강의를 계속하는 것($r$, 참)과 강의를 끝낸 다($r$, 거짓)는 명제 중 어떤 것이 참일까요?


    정답은 둘 다 참입니다.

    강의를 계속할 지, 안할지 결론을 정해놓지 않았기 때문이죠.


    그냥 교수님 마음가는대로 한다는 공지였습니다ㅋㅋㅋ

    $\rightarrow$를 조심하세요.

    죽여줘..[출처]


    자연어를 논리식으로 변환한다니 갑자기 생각나는 것이 있다.

    논리주의에서 수학을 논리학으로 변환한다는 것과 자연어를 명제로 변환하는 것에서 느껴진 유사점이랄까?


    • 수리철학.

    - 논리주의

    수학은 논리학에 포함된다는 주장이다.

    이를 위해서 수학의 개념들은 논리학의 개념들로부터, 수학의 정리들은 순수한 논리적 연역을 써서 논리학의 공리들로부터 도출될 수 있다는 것을 보여야 한다.

    프레게와 러셀은 논리주의를 증명하고자 했으나 환원공리, 선택공리, 무한공리등의 문제가 발생.


    - 직관주의

    브라우어를 필두로한 수학자들은 구성적인 방법을 통하여, 즉 대상을 정의할 대 유한번의 단계로 구성 가능해야 한다고 주장하였다. 따라서 귀류법을 배척하였으며 그 결과 고전 논리의 배중률($p \lor\lnot p$), 이중 부정 삭제($\lnot\lnot p\rightarrow p$), 퍼스의 법칙($\left(p\rightarrow q)\rightarrow p\right)\rightarrow p$)을 거부한다.

    그러나 무한등의 많은 수학적 지식을 포기해야 하는 상황. 이 글에서 집합과의 비교는 직관주의와 관계가 있다.


    - 형식주의

    논리주의에 의한 역리와 직관주의에 의한 고전 수학의 포기를 보완하기 위해 나왔다. 수학을 형식화해 그 형식체계가 무모순임을 분명한 방법(힐베르트는 이를 ‘유한적 방법’이라 불렀다)으로 증명할 수 있다는 것. 수학을 형식화한다는 뜻은 먼저 수학을 공리 체계로 만들고 이를 의미가 없는 형식적인 기호들로 만드는 것과 그 기호들을 문법에 맞도록 하고, 이로부터 다른 논리식을 추론할 수 있도록 규칙을 명시하는 것이다.

    괴델의 불완전성 정리에 의해 형식체계의 '무모순성'에 문제가 생긴다. 그러나 초한귀납법을 통하여 무한을 인정할 경우, 산술의 무모순성이 증명되었기 때문. 때문에 현재 수학계에서 대세이다.



    정리.

    - 논리주의는 수학을 논리학으로 환원하는 것에 의해서 패러독스를 제거하려고 하였음.

    - 직관주의는 논리를 제한하여 일종의 구성 가능한 것만을 수학적 대상으로 취급하여 패러독스를 제거하려 하였음.

    - 형식주의는 무모순성의 증명이 가능한 형식적 체계만을 인정하는 것에 의해서 패러독스를 배제하려 하였다.


    그러나 논리주의는 논리학을 확대하거나 또는 복잡하게 만들어 버렸고,

    직관주의는 수학을 축소시켜 버리는 결과를 낳았으며,

    형식주의는 타당하게 인정할 수 있는 증명 방식의 범위를 확대하지 않을 수 없는 난점을 파생시켰다.


    이 문서도 기본적으로 형식주의에 의해서 써지고 있다.

    더 자세한 것을 알고 싶다면 수학철학 : 논리주의·형식주의·직관주의의 이해와 비판을 참고하기 바란다.



    1.2.2 시스템 명세.

    자연언어로 된 문장을 논리적은 표현으로 변환하는 것은 HW,SW 시스템을 명확히 기술하는데에도 필수적이다.

    자연어로 기획된 것을 실제로 구현할 때에 일관성이 있어야 하기 때문이다.(모순이 되면 안됨)


    예) 다음 시스템은 일관성이 있는가?

    1. 부재중 통화가 있으면 알림이 온다.
    2. 부재중 통화가 있다.
    3. 부재중 통화가 없고 알림이 온다.


    부재중 통화가 있는 것을 $p$, 알림이 온다는 것을 $q$라 한다면 이렇게 된다.

    1. $p \rightarrow q$
    2. $p$
    3. $\lnot p \land q$

    이고 모순이 없다.


    그러나 마지막 조건이 '부재중 통화가 있고 알림이 없다'면 $p \land \lnot q$인데 1번 조건을 위배한 것이 되므로 모순이다.


    1.2.3 논리와 비트(Logic & Bits).

    T=1, F=1로 다룬다. 참 또는 거짓을 값으로 갖는 변수를 불 변수(Boolean variable)라고 한다.

    컴퓨터 비트 연산은 논리 접속사와 대응됨. 프로그래밍에서 $\land \lor \oplus$를 각각 AND, OR, XOR로도 표기함.


    비트 문자열이란 0개 이상의 비트를 갖는 비트열을 말한다. 비트 문자열의 길이란 문자열을 구성하는 비트의 수를 말한다.

    나중에 논리회로에서 더 자세히 다룰 듯.


    - 논리회로에서 자주 사용하는 몇몇 연산.

    부정을 해놓은게 많다.


    부정 논리합(NOR, $\downarrow$): 논리합($\lor$)의 부정이다.

    $p$

    $q$

    $p \downarrow q$

    T

    T

    F

    T

    F

    F

    F

    T

    F

    F

    F

    T


    부정 논리곱(NAND, $\uparrow$): 논리곱($\land$의 부정이다.

    $p$

    $q$

    $p \uparrow q$

    T

    T

    F

    T

    F

    T

    F

    T

    T

    F

    F

    T


    +.

    수학적으로 따지는 건 위키백과의 불 대수를 보면 좋은데, 여기에 쓰기에 넘치는 내용들이 많다.

    나중에 공부해서 정리할 일이 있으면 풀어서 해설해봄.


    1.2.4 퍼지 논리(Fuzzy Logic).

    애매함을 정량적으로 표현하기 위하여 만들어진 이론이다.

    $T$가 아니면 $F$같은 이진법 같은 논리에서 벗어나 속하는 정도(Degree)를 표현할 수 있다.

    $0$을 $F$로, $1$을 T로 하면 중간에 속한 정도를 $0.2, \; 0.5, \; 0.8$처럼 나타낸다는 것이다.


    - 확률과의 차이

    퍼지 이론에서 말하는 '속한 정도'는 어떻게 나타낼 수 있을까?

    그러면 드는 생각이 '이거.. 확률이랑 똑같은거 야냐?' 인데 차이가 있다.

    학률로 $20%$라 하면 $20%$의 확률로 $1$에 $80%$ 확률로 $0$에 결정이 나는 것이라면(확률에 따라 전체가 결정됨), 퍼지 논리는 이미 $20%$는 $1$의 집합에 나머지 $80%$는 $0$집합에 있다는 것이다.(이미 나뉘어진 상태임)


    - 정의.

    이제 약간 더 정교하게 알아봅시다.

    퍼지 집합 $A$, 임의의 집합 $U$, 소속함수(membership function) $\mu_A$라 하며, $\mu_A : U \to [0, 1]$란 조건이 붙는다고 하자.
    * 참고로 소속함수는 '어떤 원소가 집합에 소속된 정도를 나타내어 주는 함수'다.

    $$A = \left\{(x, \mu_A(x))|x \in U \right\}$$


    원소나열법처럼 나타내는 방식이 존재하기도 하다.

    기분이 좋은 정도를 아주 좋음(1), 상당히 좋음(0.8), 약간 좋음(0.6), 약간 나쁨(0.4), 상당히 나쁨(0.2), 나쁨(0)로 여섯가지로 할 때, $U={1,2,3,4,5,6}$과 대응되는 $A={\mu_A(1)=1, \mu_A(2)=0.8, \mu_A(3)=0.6, \mu_A(4)=0.4, \mu_A(5)=0.2, \mu_A(6)=0}$라 나타낼 수 있다.

    그럼 $A$는 튜플을 이용해
    $$A={(1,1), (2,0.8), (3,0.6), (4,0.4), (5,0.2), (6,0)}$$로 표현하면 된다. 뭐.. $\left\{ x \in U | \mu_A(x) \ne 0 \right\}$이 무한집합이면 나열할 수 없겠지만.(초한기수를 원소나열법으로 나타낼 수 없는 것과 같다.)


    - 계산.

    퍼지 논리도 '퍼지 집합'이란 개념이 들어가는 만큼 집합의 연산 방식을 사용하여 계산할 수 있다.

    여집합: $1-소속도$를 하면 된다.

    $$\mu_{A^c}(x) = 1 - \mu_A(x)$$

    예) $\lnot \mu_A(2)= 1-0.8=0.2$


    합집합: 비교한 것 중 큰 소속도를 선택하면 된다.

    $$\mu_{A \cup B}(x) = \max \left ( \mu_A \left ( x \right ), \mu_B \left ( x \right ) \right )$$

    예) $\mu_A(2) \lor \mu_A(5)=\max(0.8,0.2)=0.8$


    교집합: 비교한 것중 작은 소속도를 선택하면 된다.

    $$\mu_{A \cap B}(x) = \min \left ( \mu_A \left ( x \right ), \mu_B \left ( x \right ) \right )$$

    예) $\mu_A(2) \land \mu_A(5)=\min(0.8,0.2)=0.2$


    차집합: 소속도를 빼면 된다.

    $$A - B = A \cap B^c$$

    예) $\mu_A(2) - \mu_A(5)=0.8-0.2=0.6$ 이건 딱히 대응되는게 없네..


    1.2.5 고급 검색 기능.

    검색 엔진에도 명제를 활용한 기능이 있다.

    바로 고급 검색 기능!!


    모두 포함(띄어쓰기를 이용한 검색어)과 정확하게 포함("검색어")는 $\land$를 뜻한다.

    둘의 차이라면 ""사이에 들어가는 것은 구처럼 취급한다는 것.


    검색어 OR 검색어는 $\lor$을 뜻하며 -검색어는 $\lnot$의 의미이다.


    예) 명제 논리 OR 합 "논리 곱" -부정



    1.3 명제의 동치.

    동일한 진리값을 가지는 다른 명제표현으로 대체할 수 있다는 것은 복잡한 명제를 간소화하거나 쉽게 바뀔 수 있다는 것이다.


    전체 복합명제의 값이 항상 참일 때는 항진명제(tautology)

    전체 복합명제의 값이 항상 거짓일 경우는 모순(contradiction)

    참일 수도 있고, 거짓일 수도 있는 경우는 불확정명제(contingency)라 한다.


    1.3.1 논리적 동치.

    두개의 복합명제가 모든 가능한 경우에 대하여 같은 진리값을 가지면 논리적으로 동치(logically equivalent)라 한다.


    복합명제 $p,q$에 대하여, $p\leftrightarrow q$가 항진이면, $p$와 $q$는 논리적으로 동치이며, $p\equiv q$라 표시한다.($\equiv$는 논리 연산자가 아님, $\Leftrightarrow$도 사용 가능.)


    논리적 동치를 보이는 것은 1.1.5 복합명제와 진리표.처럼 진리표를 만들면 된다.


    유명한 논리적 동치 관계를 정리해놓은 표를 첨부한다.

    논리적 동치식

    $p \land T \equiv p$

    $p \lor F \equiv p$

    동일법칙

    $(p \lor q) \lor r \equiv p \lor (q \lor r)$

    $(p \land q) \land r \equiv p \land (q \land r)$

    결합법칙

    $p \lor T \equiv T$

    $p \land F \equiv F$

    지배법칙

    $p \lor (q \land r) \equiv (p\lor q)\land(p \lor r)$

    $p \land (q \lor r) \equiv (p\land q)\lor(p \land r)$

    분배법칙

    $p \lor p \equiv p$

    $p \land p \equiv p$

    멱등법칙

    $\lnot(p \land q)\equiv \lnot q\lor \lnot q$

    $\lnot(p \lor q)\equiv \lnot q\land \lnot q$

    드모르간 법칙

    $\lnot(\lnot p) \equiv p$

    이중부정법칙

    $p \lor(p \land q)\equiv p$

    $p \land(p \lor q)\equiv p$

    흡수법칙

    $p \lor q \equiv q \lor p$

    $p \land q \equiv q \land p$

    $p \leftrightarrow q\equiv q\leftrightarrow p$

    교환법칙

    $\lnot T \equiv F$

    $\lnot F \equiv T$

    $p \lor \lnot p \equiv T$

    $p \land \lnot p \equiv F$

    부정법칙


    조건문을 포함한 논리적 동치

    $p \rightarrow q \equiv \lnot p\lor q$

    $(p\rightarrow q)\land(p\rightarrow r)\equiv p\rightarrow (q\land r)$

    $p \rightarrow q \equiv \lnot q \rightarrow \lnot p$

    $(p\rightarrow r)\land(q\rightarrow r)\equiv (p\lor q)\rightarrow r$

    $p\lor q \equiv \lnot p \rightarrow q$

    $(p\rightarrow q)\lor(p\rightarrow r)\equiv p\rightarrow (q\lor r)$

    $p\land q \equiv \lnot(p\rightarrow \lnot q)$

    $(p\rightarrow r)\lor(q\rightarrow r)\equiv (p\land q)\rightarrow r$

    $\lnot(p\rightarrow q)\equiv p \land \lnot q$

     


    상호 조건문을 포함한 논리적 동치

    $p\leftrightarrow q\equiv (p\rightarrow q)\land(q\rightarrow p)$

    $p\leftrightarrow q\equiv (p\land q)\lor(\lnot p\land \lnot q)$

    $p\leftrightarrow q\equiv \lnot p\leftrightarrow \lnot q$

    $\lnot(p\leftrightarrow q)\equiv p\leftrightarrow \lnot q$


    논리적 동치식을 이용하여 식을 간단하게 만들어봅시다.

    $$\begin{matrix}\lnot(\lnot p \lor q) &\equiv& \lnot (\lnot p)\land\lnot q &...&드모르간 법칙\\
    &\equiv& p \land\lnot q &...&이중부정법칙\end{matrix}$$

    $$\begin{matrix}\lnot(p \rightarrow \lnot q)\lor \lnot(p \rightarrow q) &\equiv& (p\land q)\lor(p \land \lnot q) &...&조건법칙\\
    &\equiv& p\land(q\lor\lnot q) &...&분배법칙\\
    &\equiv& p\land T &...&부정법칙\\
    &\equiv& p &...&동일법칙\end{matrix}$$

    위의 법칙들만 알고 있다면 진리표없이 일반적인 대수계산처럼 할 수 있습니다!!


    1.3.2 명제의 만족가능성.

    어떤 복합명제에 대하여 그 명제가 참이 되도록 그 명제의 변수들에 진리값을 할당할 수 있으면 그 명제가 '만족가능($\top$)'하다고 한다.

    반대로 어떤 값을 주더라도 그 명제가 거짓일 경우 그 복합명제는 '만족불가능($\bot$)'하다고 한다.


    예를 들면,

    $p \land q$는 만족가능하지만, $p \land (q \land \lnot q)$는 어떠한 진리값을 할당하더라도 만족불가능합니다.


    스도쿠가 대표적인 명제 만족가능성을 이용한 활용이라 할 수 있습니다.



    1.4 술어와 한정기호.

    우리가 지금까지 배웠던 명제 논리는 최소단위가 '명제'이므로 명제 관계끼리 독립적이기 때문에 논리적 관계는 알 수 있어도 명제 내부구조를 분석할 수 없다.


    예를 들어 앞서 예제로 나왔던

    $x+1=3$

     

    또는

    모든 사람은 숨을 쉰다.

    를 말미암아

    나는 숨을 쉰다.

    를 증명할 수 없다.


    그래서 나온 것이 바로 술어논리!!

    차근차근 배워보도록 합시다.


    1.4.1 술어(Predicate), 양화(量化).

    자연어 문장의 주성분은 주어(문장의 주체), 서술어(주어를 서술), 보어(서술어를 보충), 목적어(타동사의 대상)으로 나뉘어져 있다.


    이 중 보통 서술어에 해당하는 부분이 바로 술어로 'A는 B이다'에서 B가 바로 술어이다.


    주어 A는 임의의 변수 $x$, B에 해당하는 술어를 $P$라는 기호로 나타내면(관습)

    위 문장은 $P(x)$란 명제함수가 된다.


    $x$에 해당하는 부분(명제함수의 모든 변수)에 특정 값을 대입하면 $P(x)$가 명제가 되며 진리값 판별이 가능해진다.


    명제함수 $P(x)$가 $x+1=3$일 때 $P(2)=T$, $P(5)=F$이다.

    명제함수 $Q(x)$가 "$x$는 숨을 쉰다"일 때 $Q(Me)=T$, $Q(Paper)=F$처럼 할 수 있습니다.


    뭔가 프로그래밍 하는 것 같지 않나요?

    프로그래밍에서 함수에 여러가지 인수를 넣을 수 있는 것처럼, 명제함수에서도 여러개의 변수를 넣을 수 있습니다.


    역시 앞서 나왔던

    $x+y=3$

    를 $R(x,y)$라 하면 $R(1,2)=T$, $R(2,3)=F$같은 결과가 나온다.


    지금까지 살펴본 것처럼 명제함수 $P(x_1, x_2, ...., x_n)$는 명제함수 P의 $n$-튜플 $(x_1,x_2,....,x_n)$의 값이고, $P$를 $n$-변수 술어($n$-place predicate) 또는 $n$-항 술어($n$-ary predicate)라고 한다.



    • 전조건과 후조건.

    컴퓨터 프로그램의 입력-출력을 확증할 때 술어의 원리가 사용된다.

    전조건은 올바른 입력 조건, 후조건은 해당되는 출력 조건.


    Ex) 입력값 $x,y$를 넣을 때, 출력값 $w,z$며 입력 값으로 곱셈, 나눗셈을 한 값이다.

    올바른 입력 조건, 출력 조건은 무엇일까?


    전조건에서는 연산이 가능한 값이 들어가야 한다.

    이 예에서 $y$에는 $0$이 불가(0으로 나누기).


    후조건은 $w = x \times y$, $z = x \div y$라 할 수 있다.



    본격적으로 술어논리(양화논리)를 배워나가도록 합시다.

    1.4.2 한정기호(Quantifier), 양화사.

    한정화는 술어가 원소들의 참이 되는 범위를 표현한다.(모든, 어떤, 아무도 등등)


    열린 문장이 의미를 지닐 수 있게 하기 위해서는 변항(변수)이 한정기호를 통해 속박(bound)되어야 한다.(구속변수, binding variable) 이때 한정기호에 의해 속박되지 않은 변항을 자유 변항(free variable)이라고 한다. 자유 변항만으로 이루어진 표현을 식(formula)이라고 한다. 어떠한 변항도 자유롭게 나타나지 않는 식이 문장(sentence)이다.


    한정기호가 적용되는 부분을 한정기호의 범위(scope)라고 한다.[범위에 속하지 않는게 자유 변항이겠죠?]


    - 전칭 한정기호(Universal Quantifier), 보편양화사.

    고려 대상이 되는(정의역인) 모든 원소들에 대해 술어가 항상 성립하는 것.

    $P(x)$의 전칭 한정은 $\forall xP(x)$로 표시하며 '임의의 $x$에 대하여 $P(x)$는 참이다'는 의미를 가진다.


    정의역에 속하는 값을 $x_1,x_2,x_3,...$ 일 때 $P(x_1)\land P(x_2)\land P(x_3)\land ...$처럼 논리곱의 형태로 나타낼 수 있다.



    - 존재 한정기호(Existential Quentifier) 존재양화사.

    술어가 참이 되는 정의역의 원소가 1개 이상 있는 것.

    $P(x)$의 존재 한정은 $\exists xP(x)$로 표시하며 '어떤 $x$에 대하여 참인 $P(x)$가 존재한다'는 의미를 가진다..

    정의역에 속하는 값을 $x_1,x_2,x_3,...$ 일 때 $P(x_1)\lor P(x_2)\lor P(x_3)\lor ...$처럼 논리합의 형태로 나타낼 수 있다.


    $\exists !$ 또는 $\exists _1$표시는 유일 한정기호로, 유일성을 표현한다.


    예시.

    한정기호($\forall , \exists$)는 명제 논리의 논리 연산자들보다 상위의 우선순위를 가진다.


    $x \in \mathbb{R}$이라 가정할 때.

    $\forall x(x < x + 5)$:  임의의 정수 $x$ 값은 $x+5$ 보다 항상 작으므로 $T$

    $\exists x(x < x + 5)$: 역시 해당하는 $x$는 존재. $T$

    $\forall x<3(x = 2)$: 임의의 정수 $x$ 값이 2와 항상 같지 않으므로 $F$

    $\exists x<2(x = 2)$: $x<2$인 정수 중 $x=2$가 나올 수 없으므로 $F$


    $\forall x<3(x = 2)$는 $\forall x(x<3 \to x=2)$

    $\exists x<2(x = 2)$는 $\exists x(x<2 \land x=2)$와 같은 표현방식이다.


    - 동치와 부정.

    같은 진리값을 가질때 쓰이는 동치($\equiv$)와 부정($\lnot$)을 사용한다.


    부정

    동치식 

    $\lnot \exists xP(x)$

    $\forall x\lnot P(x)$

    $\lnot \forall xP(x)$

    $\exists x\lnot P(x)$

    드모르간 법칙을 이용하면 위와 같은 결과를 얻을 수 있다.


    1.4.3 술어의 활용.

    - 자연어 문장의 논리적 표현 변환.

    카페 서비스의 모든 사용자는 음료를 시킨다.

    카페 서비스의 어떤 사용자는 커피를 마신다.

    를 술어로 바꾸어보자.


    위의 자연어 문장은 다음과 같은 의미를 함유하고 있다.

    모든 사용자 $x$는 카페 서비스를 이용하며, $x$는 음료를 시킨다.

    어떤 사용자 $y$는 카페 서비스를 이용하며, $y$는 커피를 마신다.


    음료를 시키고, 커피를 마시는 동작은 $\operatorname{drink}(x)$, $\operatorname{coffee}(y)$라는 술어가 되며 정의역은 카페를 사용하는 사용자가 된다.


    결과.

    $\forall x \; \operatorname{drink}(x)$, $\exists x \; \operatorname{coffee}(y)$


    만약 $x$(정의역)의 대상이 모든 사람이라면,

    모든 사람인 $x$에 대해 $x$가 카페 서비스를 이용하는 사용자라면, $x$는 음료를 시킨다.

    어떤 사람인 $y$에 대해 $y$가 카페 서비스를 이용하는 사용자라면, $y$는 커피를 마신다.


    카페 서비스를 이용하는 것은 $\operatorname{cafe}(x)$, $\operatorname{cafe}(y)$로 표현 할 수 있다.


    결과.

    $\forall x(\operatorname{cafe}(x) \to \operatorname{drink}(x))$

    $\exists y(\operatorname{cafe}(x) \land \operatorname{coffee}(y))$


    $\forall x(\operatorname{cafe}(x) \land \operatorname{drink}(x))$와 $\exists y(\operatorname{cafe}(y) \to \operatorname{coffee}(y))$가 아닌 이유.

    $\forall x(\operatorname{cafe}(x) \land \operatorname{drink}(x))$일 경우, 모든 사람이 카페를 이용 및 음료를 시킨다는 뜻으로 의미가 달라진다.

    $\exists y(\operatorname{cafe}(y) \to \operatorname{coffee}(y))$는 $F \to T$, $F \to F$가 모두 참이 되기 때문에 원 의미와 달라진다.


    Element of Style이란 책과 영어 문법책, 문장강화등을 고려해 '좋은 글과 프로그래밍'이라는 글을 기획하고 있다. 아마 토익 공부를 열심히 할 때 쯤 심심해서 올리지 않을까 싶다.


    - 시스템 명세에 한정기호 사용.

    1.2.2 시스템 명세와 비슷하거나 확장한 예를 들어보겠다.


    모든 전화는 스팸과 방해금지 모드를 체크한다.

    어떤 부재중 전화는 알림이 온다.


    $\forall $


    - 이상한 나라의 앨리스.



    - 논리 프로그래밍.



    1.5 중첩된 한정기호.

    1.6 추론 규칙.


    예를 들어봅시다.


    행복을 추구하는 인간의 성향도, 자비심과 같은 도덕 감정도 보편 윤리의 토가 될 수 없다 .


    * 2019년도 법학적성시험 추리논증 홀수형 20번에서 가져왔습니다.



    자연어로 된 각종 논증구조 문제를 풀어보려면 법학적성시험(LEET)의 추리논증문제를 풀어보길 바랍니다.

    1.7 증명의 소개.

    1.8 증명 방법과 전략.


    P.S.

    인터넷 밈인 짤을 넣는걸 살짝 시도해봤는데 귀찮아서 다음부터는 안넣을거 같다.

    이것


    - 끝-

    출처: Rosen의 이산수학, 이산수학 Express, 위키피디아 [명제, 명제논리, 튜플, 클레이니 스타술어 논리, 인식론, 퍼지 논리, 퍼지 집합, Well-formed formula, Context-free grammar, Backus–Naur form, ], 나무위키[양화 논리] 문맥-자유 언어, 자연어 이해, 완벽을 추구한 한 수학자의 이야기, 수학 기초론,


    댓글 0

Designed by black7375.