ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1 기초: 논리와 증명 4
    Discrete mathmatics and Problem Solving/1 논리 2016. 9. 17. 18:09

    //이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//

    1.4 술어와 정량자

    1.1~1.3장에서 배운 명제논리로는 수학 명제와 자연언어에서의 명저를 적절하게 표현할 수 없습니다. 예를 들어, "대학 네트웤에 연결된 모든 컴퓨터들은 정상적으로 작동한다"라는 명제를 가정해봅시다. 명제논리에서의 규칙으로는 다음 명제의 참/거짓을 가릴 수 없습니다. "MATH3은 정상적으로 작동한다" MATH3은 대학 네트웤에 연결된 컴퓨터들 중 하나입니다. 다음과 같은 명제 또한 다룰 수 없습니다. "CS2는 침입자에게 공격받고 있다."  CS2 또한 네트웤에 연결된 컴퓨터들 중 하나입니다. 앞의 명제로부터 "침입자로부터 공격받고 있는 컴퓨터가 대학 네트웤에 연결된 것 들중에 있다." 의 진리값을 가릴 수 없습니다. 

    이제부터는 술어논리라고 불리는 강력한 논리 형식을 배울 것입니다. 객체들간의 관계를 탐색하고 추론하기위해 수학과 컴퓨터 과학에서 사용되는 다양한 명제들을 표현하기위해 사용되는 술어논리를 살펴볼 것입니다.

    술어

    예로  "x >3," "x = y+3," "x+y=z," 그리고 "컴퓨터 x는 침입자에 의해 공격받고 있다." 그리고 "컴퓨터 x는 정상적으로 작동한다" 과 같이 변수들을 포함하는 명제들은 수학 명제, 컴퓨터 프로그램, 시스템 요구사항들에 자주 사용됩니다. 이런 명제들은 변수에 값이 지정되지 않으면 참과 거짓 모두 될 수 없습니다. 이번 장에서는 이런 명제들을 생성하는 법에 대해서 이야기할 것입니다.

    "x는 3보다 크다" 명제는 두 부분을 가지고 있습니다. 첫 부분은, 변수 x이고 명제의 주어입니다. 두번째 부분은 술어 부분입니다. "3보다 크다"는 주어인 변수 x의 속성을 언급하고 있습니다. 우리는 "x는 3보다 크다"라는 명제를 P(x)로 표현 가능합니다. P(x)는 x에 대한 명제함수 P의 값을 말합니다. 변수 x에 값이 할당되면, 구문 P(x)는 명제가 되고 진리값을 가지게 됩니다. 

    예제 1

    P(x)가 "x>3"를 표현한다고 하자. P(4)와 P(2)의 진리값은 무엇인가?

    정답

    P(4) 는 "x>3"에서 x=4로 지정합니다. 따라서, P(4)는 "4>3"이므로 참입니다. 반대로, P(2)는 "2>3"이므로 거짓입니다.

    예제 2

    A(x)가 "컴퓨터 x는 침입자에게 공격받고 있다" 를 표현한다고 하자. 캠퍼스 내의 컴퓨터들에 가정해서, CS2와 MATH1 컴퓨터가 침입자에 의해 공격받고 있다고 하자. A(CS1), A(CS2) 그리고 A(MATH1)의 진리값은 무엇인가?

    정답

    A(CS2), A(MATH1) 은 참이다.

    예제 5

    R(x, y, z)가 "x + y =z"를 뜻한다고 하자. 변수 x, y, z에 값이 할당되면, 이 구문은 명제가 되고 진리값을 가질 수 있다. R(1, 2, 3)과 R(0, 0, 1)의 진리값을 구하시오.

    정답

    R(1, 2, 3)은 "1 + 2 =3"이므로 참이 된다. R(0, 0, 1)은 거짓이다.

    P(x1, x2, ... xn) 형식의 구문은 n-튜플(x1, x2 ... xn)에 대한 P 명제함수의 값이고 P는 n-place 술어 또는 n-ary 술어라고 합니다.

    사전조건과 사후조건

    컴퓨터 프로그램이 사용가능한 입력값을 받을 때 원하는 결과값을 도출하는지 보여주기 위해서, 술어는 컴퓨터 프로그램의 정확함을 입증하기위해 사용될 수 있습니다. 사용가능한 입력값을 서술하는 구문을 precondition이라고 하며 프로그램이 작동하고 있을 때 결과값이 항상 만족해야하는 조건을 postcondition 이라고합니다. 아래의 예제에서 볼 수 있듯이, 사전조건과 사후조건을 설명하기 위해 술어를 사용합니다. 

    예제 7

    변수 x와 y의 값을 교환하기 위해 설계된 아래의 프로그램을 보시오.
    temp := x
    x := y
    y := temp
    이 프로그램의 정확함을 검증하기 위해 사전조건과 사후조건으로 사용할 수 있는 술어를 찾으시오. 그리고 프로그램이 의도한대로 작동하기 위해 사용가능한 입력값을 검증하는 방법을 설명하시오.

    정답

    사건조건을 위해서, 프로그램이 수행되기 전에 x와 y의 값이 특정한 값을 가지고 있다고 표현해야합니다. 그러므로, 사전조건에서는 술어 P(x, y)를 사용할 수 있습니다. P(x, y)는 "x = a 이고 y = b 이다." 으로, 프로그램을 수행하기 전에 x와 y의 값을 a와 b로 지정합니다. 모든 입력값에대해 x와 y의 값을 바꾸는 프로그램을 검증하기를 원하기 때문에, 우리는 사후조건으로 Q(x, y)를 사용할 수 있습니다. Q(x, y)는 "x=b 이고 y=a이다."입니다.
    프로그램이 항상 의도한대로 수행한다고 검증하기 위해서는, P(x, y) 효력이 있다고 가정해야합니다. 즉, 구문 "x = a 이고 y = b이다."를 참이라고 가정해야합니다. x=a이고 y=b입니다. 프로그램의 첫 단계는 temp := x, x의 값을 temp 변수에 할당 합니다. 두 번째 단계는 x :=y, 마지막으로는 y:=temp 입니다. 따라서 프로그램이 수행된 뒤에는, 사후조건 Q(x, y) 효력이 있습니다. 즉, "x=b 이고 y=a이다."는 참입니다.

    Quantifiers 정량자

    정의 1 universal quantifier 전체 정량자

    P(x)의 전체정량자는 "정의된 구간에서 모든 x값에 대한 P(x)" 를 뜻한다. 표기법 ∀xP(x)는 P(x)의 전체정량자를 뜻합니다. ∀는 universal quantifier이라고 불립니다. ∀xP(x)는 "모든 xP(x)에 대해"라고 읽습니다. P(x)가 거짓인 원소에 대해서는 counterexample of ∀xP(x) 라고 부릅니다.

    예제 10

    P(x)를 "x^2 > 0"이라 합시다. ∀xP(x)는 모든 정수일때 거짓입니다. x=0는 x^2=0이기 때문에 반례입니다. 

    전체 정량자의 반례를 찾는 것은 수학을 연구하는데 중요한 활동입니다. 이 책의 다른 섹션에서도 볼 수 있습니다.
    정의역에 있는 모든 요소들이 나열될 때 -x1, x2, ... xn - 전체 정량자 ∀xP(x)는 논리곱과 같습니다.    P(x1) ∧ P(x2) ∧... ∧ P(xn) 
    왜냐하면 논리곱은 P(x1), P(x2) .. P(xn)이 모두 참일때 참이기 때문입니다.

    예제 13

    x의 정의구간이 실수일 때 ∀x(x*x ≥ x)의 진리값은 무엇인가? 정의구간이 정수일때는 진리값이 어떤가?

    정답

    x의 정의구간이 실수일 때 전체정량자 ∀x(x*x ≥ x)의 진리값은 거짓입니다. x*x ≥ x는 x*x - x = x(x-1)≥0와 같습니다. 따라서, x*x ≥ x 는 0 ≥ x 또는 x ≥ 1  입니다. x가 0과 1사이일 때 거짓이므로, 정의구간이 실수일 때 ∀x(x*x ≥ x)는 거짓입니다. 그러나, 정의구간이 정수일 때 ∀x(x*x ≥ x) 는 참입니다. 0과 1사이의 정수는 존재하지 않기때문입니다.

    정의 2 existential quantifier 존재 정량자

    P(x)의 존재 정량자는 "정의된 구간에서 한 원소 x에 대한 P(x)"를 뜻합니다. 표기법 ∃xP(x)는 P(x)의 존재 정량자를 뜻합니다. 여기서 ∃는 존재 정량자라고 부릅니다. 

    구문 ∃xP(x)가 사용될 때는 정의역은 항상 구체적이어야합니다. 더욱 더, ∃xP(x)의 의미는 정의역이 바뀔때마다 바뀝니다. 정의역이 명시되지 않으면, ∃xP(x) 구문은 의미가 없습니다.
    게다가 구절 "there exist"는 다른 방법으로도 표현할 수 있습니다. "for some", "for at least one", "there is"입니다. ∃xP(x)는 다음과 같이 읽을 수 있습니다.
    "There is an x such that P(x)", "There is at least one x such that P(x)", "For some x P(x)"
    존재 정량자의 의미는 다음의 표를 통해 확인할 수 있습니다. 표에는 전체 정량자도 있습니다.

    다음 예제들을 살펴봅시다

    예제 14 

    P(x)가 "x>3"라 합시다. ∃xP(x)의 진리값은 무엇입니까? 정의역은 모든 실수입니다.

    정답

    "x>3"은 가끔 참입니다. 예로 x=4 있을때 존재 정량자 P(x)는 참입니다.

    ∃xP(x)는 정의역에 P(x)를 참으로 만드는 x가 존재하지 않으면 거짓 진리값을 가집니다. 즉, ∃xP(x)는 정의역에 있는 모든 엘리먼트 x에 대해 P(x)가 거짓이면 거짓입니다. 아래 예를 살펴봅시다.

    예제 15

    Q(x)를 "x = x + 1"라하자. ∃xP(x)의 진리값은 무엇이겠습니까? 정의역은 모든 실수역이라고 합니다.

    정답

    Q(x)는 모든 실수에서 거짓이기 때문에, 존재정량자 Q(x), ∃xQ(x)는 거짓입니다.


    일반적으로, 존재 정량자의 정의역은 비어있지 않다고 암묵적으로 가정합니다. 만약 정의역이 비어있다면, ∃xP(x)는 거짓입니다. Q(x) 명제 함수는 상관이 없습니다. 왜냐하면 정의역이 비었기에, Q(x)가 참일 수 있는 원소 x가 존재할 수 없기 때문입니다.

    정의역의 모든 원소들이 나열될 때 -x1, x2, ... xn- 존재 정량자 ∃xP(x)는 다음 논리합과 같습니다.

    P(x1) ∨ P(x2) ∨ ... ∨ P(xn)

    논리합은 적어도 하나의 P(x1), P(x2)... P(Xn)이 참일때 참이기 때문입니다.

    예제 16

    ∃xP(x)의 진리값은 무엇입니까? P(x)는 "x^2 > 10"이라고 합시다. 정의역은 4를 넘지 않는 양의 정수입니다.

    정답

    정의역 {1, 2, 3, 4}이기에, 명제 ∃xP(x)는 다음 논리합과 같습니다.
    P(1) ∨ P(2) ∨ P(3) ∨ P(4)
    P(4)이기에 구문 "4^2 > 10"은 참입니다. 따라서 ∃xP(x)는 참입니다.

    정량자의 진리값을 판단할 때 반복과 검색을 생각하면 도움이 됩니다. 변수 x는 정의역에서 n object가 있다고 가정합시다. ∀xP(x)가 참인지 판단하기 위해서는, x의 모든 n 값을 반복해야합니다. P(x)가 항상 참인지 확인하려면요. 만약 발견한 x 값에 의해 P(x)가 거짓이면, ∀xP(x)가 거짓인 것을 보인것입니다. 그렇지 않다면, ∀xP(x)는 참입니다. ∃xP(x)가 참인지 확인하려면, x의 n의 값을 반복하여 P(X)가 참인 값을 찾습니다. 만약 하나를 찾았으면, ∃xP(x)는 참입니다. 만약 그런 x값을 하나도 찾지 못하였다면, 우린 ∃xP(x)가 거짓이라고 판단합니다. (정의역에 무한한 값이 존재할 경우 이 검색 절차는 적용되지 않습니다. 하지만, 여전히 정량자의 절대값에 대해 생각하는 좋은 방법입니다.)

    uniqueness quantifier 단일 정량자 (?)

    이제 막 전체 정량자와 존재 정량자에 대해 소개했습니다. 수학과 컴퓨터 과학 분야에서 이들은 가장 중요한 정량자입니다. 그러나, 다양한 정량자를 통해 정의할 수 있는 것은 무한합니다. "정확히 두개가 존재한다." "3이하이다." "적어도 100개가 있다" 등등이 있습니다. 이 정량자들 말고는, 가장 자주 보게 될 것은 단일 정량자입니다. ∃! 로 표현됩니다. 표기법 ∃!xP(x)는 "P(x)를 참으로 만드는 단 하나의 x가 존재한다입니다." 예로, ∃!x(x-1=0), 정의역은 실수일 때, 구문은 x-1 =0을 만드는 실수는 단 하나의 실수가 있다 입니다. 이 구문은 참입니다. x=1은 유일한 실수입니다. x-1=0을 만족합니다.  

    제한된 정의역에서 정량자

    단축된 표기법은 종종 정량자의 정의역을 제한하기 위해 사용됩니다. 다음 예를 봅시다.

    예제 17

    ∀x < 0 (x^2 > 0), ∀y ≠ 0 (y^3 ≠ 0),  ∃z > 0 (z^2 = 2) 의 뜻은 무엇입니까? 정의역은 모든 실수입니다.

    정답

    ∀x < 0 (x^2 > 0) 구문은 실수 x <0 인 모든 x에 대해, x^2 > 0 이다. 입니다. 즉, "음의 실수 제곱은 양수이다" 구문입니다. 이 구문은 다음과 같습니다. ∀x(x < 0 → x^2>0).
    구문 ∀y ≠ 0 (y^3 ≠ 0 )는 모든 실수 y, y ≠ 0일 때, y^3 ≠ 0 이다. 입니다. 즉, "0이 아닌 모든 실수의 세제곱은 0이 아니다"입니다. 이 구문은 다음과 같습니다. ∀y(y ≠ 0 → y^3 ≠ 0).
    마지막으로, ∃z > 0 (z^2 = 2)의 뜻은 실수 z는 z>0일때 z^2 =2 이다. 입니다. 즉, "2의 양의 제곱근이 존재한다" 입니다. 이 구문은 ∃z(z>0 ∧ z^2=2)와 같습니다.

    전체 정량자의 제약은 조건문의 전체정량자와 같습니다. 예로, ∀x<0(x^2 > 0) 는 ∀x(x<0 → x^2>0)와 같습니다. 반대로, 존재 정량자의 제약은 논리곱의 존재정량자와 같습니다. 예로, ∃z>0(z^2=2)는 ∃z(z>0 ∧ z^2=2)와 같습니다.

    정량자의 우선 순위 

    정량자 ∀와 ∃는 명제 연산에서 논리 연산자보다 우선 순위가 높습니다. 예로, &forallxP(x) ∨ Q(x)는 ∀xP(x)와 Q(x)의 논리합과 같습니다. 다른 말로, (∀xP(x)) ∨ Q(x) 입니다. ∀x(P(x) ∨ Q(x)).

    변수 바인딩 Binding Variables

    정량자가 변수 x에 사용될 때, 이 상황을 변수가 바운드 되었다고 합니다. 정량자에 의해 변수가 바운드 되지 않거나 특정한 값과 같지 않는 상황을 자유롭다free 라고 표현합니다. 명제 함수에서 발생되는 모든 변수는 명제가 되기위해 반드시 바운드 되거나 특정 값과 같아야 합니다. 이는 전체정량자, 존재정량자와 값 할당 이 세 활동의 조합을 통해 이루어질 수 있습니다. 
    정량자가 사용된 논리표현식 부분을 이 정량자의 범위scope이라고 부릅니다. 따라서, 이 변수를 정의하는 수식에서 사용된 정량자의 범위 바깥에 존재하면 변수는 자유free롭습니다. 

    예제 18

    구문 ∃x(x+y=1)는, 변수 x는 존재 정량자 ∃에 바운드되었지만, 변수 y는 정량자에 의해 바운드 되지도 않았고 어떤 값도 할당 되지 않았습니다. 구문 ∃x(x+y=1)의 의미는, x는 바운드되었지만 y는 프리합니다. 구문 ∃x(P(x) ∧ Q(x)) ∨ ∀xR(x) 에서는, 모든 변수가 바운드되었습니다. 첫번째 정량자의 범위는, P(x) ∧ Q(x) 입니다. 그리고 두번째 정량자의 범위는, R(x) 입니다. 존재 정량자는 P(x) ∨ Q(x)에서 변수 x를 바인드 하고, 전체 정량자 ∀는 R(x)에서 변수 x를 바인드합니다. 만약 변수 x와 y를 이용하여 다음과 같이 구문을 써 ∃x(P(x) ∧ Q(x)) ∨ ∀yR(y) 표현할 수 있습니다. 왜냐하면 두 정량자의 범위가 겹치지 않기 때문입니다. 때로 범위가 겹치지 않는 서로 다른 정량자를 사용해 같은 변수 글자를 이용해 표현할 수 있으니 주의합시다. 

    정량자를 포함한 논리적 동치

    정의 3 

    술어와 정량자를 포함하는 구문은 정의역에 상관없이 같은 진리값을 가진다면 논리적 동치입니다. S &equiv; T는 술어와 정량자를 포함한 구문 S와 T가 논리적 동치라고 말합니다.

    예제 19

    ∀x(P(x) ∧ Q(x))와 ∀xP(x) ∧ ∀xQ(x)는 논리적 동치임을 보이세요. (정의역은 같습니다.) 이 논리적 동치는 전체 정량자를 논리곱에 분배법칙을 사용할 수 있음을 보여줍니다. 그러므로, 우리는 존재 정량자를 논리합에 대해 분배법칙을 사용할 수 있습니다. 그러나 전체 정량자를 논리합에 분배할 수 없고 논리곱에 존재정량자를 분배할 수 없습니다.

    정답

    이 구문들이 논리적 동치임을 보이려고할 때, 항상 같은 진리값임을 보여야합니다. P와 Q의 술어와 정의역이 무엇이든지 말입니다. P와 Q가 특정 술어를 가지고 있고, 일반적인 정의역이라고 가정해봅시다. 우리는 ∀x(P(x)∨Q(x))와 ∀xP(x)∧∀xQ(x)는 논리적 동치인가 두 가지 방법으로 보일 수 있습니다. 처음엔 ∀x(P(x)∧Q(x))가 참이면, ∀xP(x)∧∀xQ(x)가 참입니다. 두번째로, ∀xP(x)∧∀xQ(x)가 참이면, ∀x(P(x)∧Q(x))가 참입니다. 
     우선 ∀x(P(x)∨Q(x))가 참이라 가정합니다. 이 뜻은 정의역에 a가 있으면, P(a)∧Q(a)가 참입니다. 따라서, P(a)도 참, Q(a)도 참입니다. 정의역에 있는 모든 원소들에 대하여 P(a)가 참이고 Q(a)가 참이므로, 우리는 ∀xP(x)와 ∀xQ(x)는 모두 참입니다. 즉, ∀xP(x)∧∀xQ(x)도 참입니다.
    다음은 ∀xP(x)∧∀xQ(x) 가 참이라고 가정합시다. 이는 ∀xP(x)도 참이고 ∀xQ(x)도 참임을 뜻합니다. 따라서 정의역에 있는 a에 대해, P(a)가 참이고 Q(a)도 참입니다. 따라서 모든 a에 대해 P(a)∧Q(a)가 참입니다. 따라서 ∀x(P(x)∧Q(x))가 참입니다. 따라서 다음과 같이 결론 내릴 수 있습니다. 
    ∀xP(x)∧Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x)

    정량자 표현 부정형 만들기

    이제 정량자 표현의 부정형에 대해 생각해볼 것입니다. 예로, 다음과 같은 구문의 부정형을 생각해보세요. 
    "해당 수업의 모든 학생은 미적분을 수강했다."
    이 구문은 전체 정량자를 사용하여 ∀xP(x)로 표현합니다. P(X)는 "x는 미적분학을  수강했다"라는 구문이고 정의역은 해당 수업의 모든 학생들로 이루어집니다. 이 구문의 부정형은 "해당 수업의 모든 학생이 미적분학을 들은건 아니다." 입니다. 이 것은 "해당 수업에서 미적분학을 수강하지 않은 학생이 적어도 하나 존재한다."와 같습니다. 그리고 다음과 같이 원 명제 함수의 부정형에 대한 존재 정량자로 표현할 수 있습니다. ∃x¬P(x).
    따라서 다음은 논리적 동치입니다. ¬∀xP(x)≡∃x¬P(x) 다음도 논리적 동치입니다. ∀x¬P(x)≡¬∃xP(x)

    예제 20

    다음 구문의 부정형은 무엇입니까? "정직한 정치인은 존재한다" "모든 미국인들은 치즈버거를 먹는다."

    정답

    H(x)를 "x 는 정직하다"라고 합시다. 그러면 다음 구문 "정직한 정치인이 존재한다"는 ∃xH(x)로 표현됩니다. 정의역은 모든 정치인들로 이루어집니다. 이 명제의 부정형은 ¬∃xH(x)이고 ∀x¬H(x)와 동치입니다. 이 부정형은 다음과 같이 표현됩니다. "모든 정치인은 불성실하다"입니다. C(x)를 "x는 치즈버거를 먹습니다"라 합시다. 구문 "모든 미국인은 치즈버거를 먹습니다"는 ∀xC(x)로 표현됩니다. 정의역은 모든 미국인으로 이루어집니다. 이 명제의 부정형은 ¬∀xC(x)입니다. ∃x¬C(x)와 동치입니다. 이 부정형은 다음과 같이 표현될 수 있습니다. "미국인 몇 몇은 치즈버거를 안 먹습니다." "치즈버거를 먹지 않는 미국인이 있습니다."

    예제 21

    다음 구문의 부정형은 무엇입니까? ∀x(x^2 > x)와 ∃x(x^2=x)

    정답

    ∀x(x^2 > x)의 부정형은 ¬∀x(x^2>x)입니다. 이는 ∃x¬(x^2>x)와 동치입니다. 다음과 같이 ∃x(x^2 ≤ x)로 다시 쓸 수 있습니다. ∃x(x^2=2)의 부정형은 ¬∃x(x^2=2)입니다. 이는 ∀x¬(x^2=2)입니다. 이는 다음과 같이 ∀x(x^2 ≠ 2) 로 쓸 수 있습니다. 이 구문들의 진리값은 정의역에따라 달라집니다.

    예제 22 

    ¬∀x(P(x) → Q(x))와 ∃x(P(x) ∧ ¬Q(x))가 논리적 동치임을 보이시오

    정답

    ¬(P(x)→Q(x))와 P(x)∧¬Q(x) 임을 알고 있습니다. 따라서 정량자에 대한 드 모르간 법칙에 따라, ¬∀x(P(x) → Q(x))와 ∃x(P(x) ∧ ¬Q(x))가 논리적 동치임을 알 수 있습니다. 

    예제 20

    다음 구문을 고려해봅시다. 앞의 두 구문은 전제라 불리고 마지막은 결론이라고 불립니다. 이들을 논거라고 합니다.
    "모든 사자는 사납다" 
    "어떤 사자는 커피를 마시지 않는다."
    "사나운 생물 중 어떤 것은 커피를 마시지 않는다" 
     P(x), Q(x), R(x)를 "x는 사자다", "x는 사납다", "x는 커피를 마신다"라고 합시다. 정의역은 모든 생물로 이루어져있다고 가정합시다. 다음 논거를 정량자와 P(x), Q(x), R(x)를 통해 표현해보세요.

    정답

    다음과 같이 표현할 수 있습니다.
    ∀x(P(x) → Q(x))
    ∃x(P(x) ∧ ¬R(x))
    ∃x(Q(x) ∧ ¬R(X))

    두 번째 구문이 ∃x(P(x) → ¬R(x))로 쓰여질 수 없음을 확인해야합니다. 이유는 P(x) → ¬R(x)가 참인경우는 x가 사자가 아니면 항상 참입니다. 따라서 ∃x(P(x) → ¬R(x))는 단 하나의 생명이라도 사자가 아니면 참이 됩니다. 모든 사자가 커피를 마시더라도요. 유사하게 마지막 구문도 다음으로 대체될 수는 없습니다. ∃x(Q(x) → ¬R(X))

    예제 27

    다음의 구문들을 살펴봅시다. 앞 세 구문은 전제이고 마지막은 결론입니다. 
    "모든 벌새는 색이 풍부합니다"
    "어떤 큰 새도 꿀을 먹고 살지 않습니다."
    "꿀을 먹지 않는새는 색이 단조롭습니다"
    "벌새는 몸집이 작습니다."
    P(x), Q(x), R(x), S(x) 를 "x는 벌새입니다" "x는 큽니다" "x는 꿀을 먹고 삽니다." "x는 색이 풍부합니다" 라 합시다. 정의역은 모든 새로 이루어져있다고 가정합시다. 다음 논거를 P(x) Q(x) R(x) S(x)로 표현해보세요.

    정답

    다음과 같이 표현할 수 있습니다.
    ∀x(P(x) → S(x))
    ¬∃x(Q(x) ∧ R(x))
     ∀x(¬R(x) → ¬S(x))
    ∀x(p(x) → ¬Q(x))

    논리 프로그래밍

    프로그래밍 언어의 중요한 타입은 술어 논리의 규칙을 추론하기 위해서입니다. Prolog (Programming in Logic)는 1970년대 인공지능 분야에서 일하는 컴퓨터 과학자에게의해 개발되었습니다. Prolog 프로그램은 두 종류의 구문으로 이루어진 선언을 포함합니다. Prolog facts 와 Prolog rules 입니다. Prolog facts는 술어를 정의하는데 술어를 만족하는 요소를 명시합니다. Prolog rules는 새로운 술어를 정의하기 위해 사용됩니다. Prolog facts에 의해 이미 정의된 것을 사용합니다. 다음 예제를 살펴봅시다.

    예제 29 

    Prolog 프로그램에게 facts를 전달하는 것을 고려해봅시다. facts는 각 반의 선생님과 각 반의 학생들에 대해 이야기합니다. 프로그램은 이 facts를 특정 학생을 가르치는 교수를 물어보는 쿼리문에 답하기위해 사용합니다. 이 프로그램은 술어 instructr(p, c)와 enrolled(s, c)를 교수 p는 c 강의이다. 와 학생 s는 c를 수강한다로 표현합니다. 예로, Prolog facts는 다음과 같이 포함합니다.

    instructor(chan,math273) 
    instructor(patel,ee222) 
    instructor(grossman,cs301) 
    enrolled(kevin,math273) 
    enrolled(juana,ee222) 
    enrolled(juana,cs301) 
    enrolled(kiko,math273)
    enrolled(kiko,cs301)

    (소문자 글자는 엔트리로 사용됩니다. Prolog에서는 대문자로 시작하는 글자를 변수로 고려하기 때문입니다.)

    새로운 술부 teaches(p,s)는 p 교수가 s 학생을 가르친다고 합니다. Prolog rule을 통해 정의됩니다.

    teaches(p,s) :- instructor(p,c), enrolled(s,c)

    teaches(p,s)는 참입니다. 만약 p 교수가 가르치는 c 강의가 존재하고 학생 s가 c 강의를 수강중이면요. 쉼표는 Prolog에서 논리곱을 표현합니다. 유사하게, 세미콜론은 논리합을 표현하는데 사용합니다.

    Prolog는 facts와 rules를 사용하여 쿼리를 물을 수 있습니다. 예로, facts와 rules를 나열하여 쿼리 

    ?enrolled(kevin,math273)은 응답값 yes 를 제공합니다. fact enrolled(kevin,math273)은 입력값으로 제공되었기 때문에 쿼리 ?enrolled(X,math273)은 응답값 kevin, kiko를 반환합니다.

    이 응답을 생산하기 위해, Prolog는 모든 가능한 X를 고려합니다.  Prolog fact로 포함된 enrolled(X, math273)에 대한 X값을 고려합니다. 유사하게, juana를 가르치는 교수를 찾기위해선 다음과 같은 쿼리를 쓸수 있습니다.

    ?teaches(X, juana) 

    이 쿼리는 다음과 같이 반환합니다.

    patel

    grossman 


    'Discrete mathmatics and Problem Solving > 1 논리' 카테고리의 다른 글

    0 Introduction  (0) 2016.12.26
    1 기초: 논리와 증명 5  (0) 2016.09.26
    1 기초: 논리와 증명 4  (0) 2016.09.17
    1 기초: 논리와 증명 3  (0) 2016.09.17
    1 기초: 논리와 증명 2  (0) 2016.09.12
    1 기초: 논리와 증명  (0) 2016.09.10

    댓글 0

Designed by Tistory.