수학은 모델의 설정에 가장 효과적인 수단으로  대상을 정확하고 엄밀하게 기술할 도구로서의 "언어"를 필요로 한다.이때 언어의 역할을 담당하는 것을 수리논리 (mathematical logic)라고 한다. 언어에서 명확하게 정의되는 기호에 의해 논리의 모호성을 없애고 기술의 편의를 위해 기호가 사용된다. 수리논리를 기호논리라고도 한다. computer에서는 수학을 이용해서 여러현상을 모형화하고 분석하므로 논리는 집합과 함께 computer를 연구발전 시키는데 필수적인 수단이다   

명제 계산(Propositional Calculus)

서술문으로서 진리값 true , false 중 하나만을 부여할수 있는 문장을 명제 (Proposition) 라 한다."울릉도는 섬이다" 는 명제가 될 수 있지만  "정수 x 에 대해 x = x+1 이다" 는 명제라 할 수 없다.명제는 기본 명제와 논리연산자 로 결합한 합성명제가 있다. 어떤 한 문장 (sentence) 가 주어졌을 때 이 문장이 참인지 거짓인지를 평가하는 것을 해석 (Interpretation) 이라 한다. 논리연산자 or 연결사 (connective) 에는 다음과 같은 것이 있다.

부정 (negation)

~P, NOT P,  P`,  ¬P

논리곱 (conjuction)

P∧Q, P AND Q,  P*Q,  P&Q   
두명제가 모두 참일 때만 참

논리합 (disjunction)

P∨Q, P OR Q, P+Q,    
두명제가 모두 거짓일 때만 거짓

배타적논리합 (exclusive disjunction)

P XOR Q ,
모두 참이거나 거짓이면 거짓

조건 (conditional) 또는 implication

P->Q  '(만일) P이면 Q이다'
P가 참이고 Q가 거짓일 때만 거짓

쌍조건 (biconditional)

P<->Q , (P->Q)∧(Q->P)인 경우
같은 진리값을 가질 때만 참

논리연산자의 연산 우선순위는 다음과 같다

부정(가장 높은)->논리곱->논리합->조건->쌍조건(가장낮음)

Errors in Propositional Calculus

 

술어 계산( Predicate Calculus)

명제계산은  간단한 문제영역에서의 표현언어로서는 문제가 없으나, 많은 문장을 효과적으로 표현하기위한 수단으로서는 부족하다는 단점이 있다. 합성명제인 경우 각 명제 간을 연결하는 연결사를 이용한 분석만이 가능할뿐이다.

이 추론은 직관이나 상식에 의하면 타당하지만 위와같이 기호화하면 명제계산에서는 타당하지 않다. 이는 표현상의 제약으로 인해 문장 내의 각 성분을 분리하여, 다른 문장의 성분과 조합하여 이용할수 없기 때문이다. 이런 단점을 보완한 논리언어가 술어 계산이다. 사물들의 관계를 나타내기 위해 술어 부호를 이용하기때문에 문장의 각 성분을 자유로이 분리하여 사용할수 있으며 변수를 사용하여 불특정다수의 개념 또한 도입할수 있다.

위에서 " 국화"는 주어로서 x (소문자) 로 표현하고 "꽃이다" 는 술어로서 P (대문자) 로 표현하면 " 국화는 꽃이다" 라는 문장은 P(x) 로서 표기될수 있다. P(x)에서 P 는 술어부호라고 하고 x 는 상수부호,또는 변수라고 한다. 문장에서 양을 나타내는단어를 정량자(quantifier) 라고 하며 다음과 같다.

1.  전칭기호  ∀x : 모든 x 에 대하여, for all x.

     ∀x( B(x) → C(x) )  모든 x 에 대하여 x 가 자연수이면 x 는 정수이다.

2.  존재기호  ∃x : 어떤 x 에 대하여 ...인 x 가 적어도 하나 존재한다. for some x, there exist at least one x such that...

      ∃x ( B(x) ∧ C(x) )   어떤 x 에 대하여 자연수이면서 정수인 x 가 적어도 하나 존재한다

quantifier를 갖는 변수를 Bound Variable 이라 하고 , 갖지 않는 변수를 Free Variable 이라 한다.

술어계산에서 quantifier 가 변수부호 x 에만 적용되고 , 술어부호에 대해서는 적용되지 않는 경우를 일차술어계산 (First Order Predicate) 이라 한다.  즉  (∀ P) P(x)에서 술어부호 P 에대해서 quantifier 가 적용되지 않으므로 일차술어계산 에서는 허용되지 않는 문장이다. Prolog 같은 AI 언어들은 일차술어계산에 근거하고 있다. 대부분의 모든 논리적인 표현들은 일차술어계산으로 나타낼수 있기 때문이다.  

술어논리의 추론규칙

전칭기호와 존재기호를 첨삭하여 추론을 유도할 수 있게 하는 4가지의규칙