[이산수학] 시스템 명세, 명제적 동치, 논리적 동치

시스템 명세란?

시스템 공학자나 소프트웨어 공학자는 영어와 같은 자연언어로 요구 사항을 접수 받아 논리에 기반한 정확하고 모호하지 않은 명세서를 작성합니다. 

 

일관성있는 명세가 되기 위해서는 각 명제가 참 이 되도록 명제 변수에 진리 값을 할당할 수 있다면, 명제들의 목록은 일관성이 있다고 봅니다. 즉 시스템 명세는 모순이 나오게 하는 상호 배치되는 요구 사항을 포함해서는 안됩니다. 

---

예시

- 진단 메세지는 버퍼에 저장되거나 또는 재전송된다.

- 진단 메세지는 버퍼에 저장되지 않는다.

- 진단 메세지는 버퍼에 저장된다면, 재전송된다.

---

 풀이

p : "진단 메세지는 버퍼에 저장된다."

q : "진단 메세지는 재전송된다."

 

시스템 명세 문장들

- p U q

- ~ p 

- p -> q 

p가 거짓이고 q가 참이면 위의 세개의 설계 문장들이 참이 되므로 일관성이 있다고 할 수 있습니다. 

 

명제와 동치

항진명제

복합명제를 구성하는 단위명제의 진리 값이 어떠한 값을 가진다 하더라도 해당 복합명제가 항시 참이면 이것을 항진 명제라고 합니다.

 

- p U ~p 

이것은 p가 어떤 값을 가지던지 항상 참의 값을 가지게 됩니다. 

 

- p -> (p U q )

이 명제 없이 어떠한 진리값을 가지더라도 항상 참의 값을 가집니다. 이 명제를 항진명제라고 합니다.

 

부정명제

복합명제를 구성하는 단위명제의 진리 값이 어떠한 값을 가지더라도 복합명제가 항시 거짓이면 이를 부정명제라고 합니다. 예를들면  ( p ^ ~p) 교집합은 p가 어떠한 값이 나오더라도 False가 나오기 때문에 이는 부정명제라고 할 수 있습니다.

 

항진도 부정도 아닌 것은 불확정 명제라고 합니다.  

 

 

논리적 동치

 P와 Q가 n개의 명제들 로 구성된 복합명제라고 했을 때 P 와 Q에 대해 P <-> Q 가 항진이면 두 복합명제 P와 Q는 논리적 동치라고 합니다. 

 

~(P U Q ) 가 ~P ^ ~Q 와 논리적 동치인지 확인하려면 진리지표값을 그려보면 됩니다. 

이 예제는 드모르간 법칙으로 유명한데요. 보시다시피 위의 진리지표가 같은 것을 볼 수 있습니다. 

 

동치법칙

 

 

 

풀이

~p ^ (~(~p U q))

~p ^ (p U ~q)

(~p ^ p) U (~p ^ ~q)

F U (~p ^ ~q) 

== > ~p ^ ~q 만 나오게 됩니다. F는 false를 의미합니다. p와 ~p의 교집합은 f이 나오기 때문입니다. 

 

 

명제의 만족 가능성

어떤 복합 명제에 대해 그 명제가 참이 되도록 그 명제의 변수들에 진리값을 할당할 수 있다면, 그 명제는 만족가능하다고 합니다. 그러한 진리값을 할당할 수 없는 경우, 그 복합명제는 만족불가능이라고 합니다.

 

복합명제가 만족불가능일 필요충분조건은 그 명제의 부정이 항진 명제가 되는 것입니다. 

 

 p q r을 할 때 참이되는 것이 있는지 보면 됩니다. p q r에 대해서 true값을 할당해보면 p가 참이면 or의 특성에 의해서 true, q또한 q가 참이면 true, r도 true면 T T T 가 되어서 T가 나옵니

 

리고 두 복합명제 p, q에 대하여 p↔q가 항진이면, p와 q는 논리적으로 동치라 하고, p≡q(p⇔q) 로 나타냅니다.

 

아 그리고 항진과 모순을 설명 하자면 항진은 p∨￢p 처럼 항상 참인것을 항진이라 하고,

p∧￢p 처럼 항상 거짓인 식을 모순이라 합니다.

 

p	q	p∨￢p	p∧￢p
T	F	T	F
F	T	T	F

 

술어와 한정 기호

P(x)를 변수 x를 포함하는 문장이라고 하고 D를 집합이라고 합니다. 그러면 

 

P is a propositional function or predicate

 

if p(x) is a proposition for each x in D

 

Dis called the domain of discourse of p(x)

 

x is greater than 3 

이 문장에서 변수는 x입니다. 그리고 is greater than 3은 술어입니다. 

 

P(x) = "x is greater than 3" 이게 명제함수가 됩니다. 

 

한정기호

명제 함수를 명제로 반드는 방법은

1. 변수에 특정 값을 할당하는 방법

2. 한정(quantification)을 적용하는 방법

 

이 있습니다. 

 

1) 변수에 특정 값을 할당하는 방법

-p(x) = " x > 3"

-만약 x = 4라면 p(x)는 true가 되는 것이고 x = 2 라면 p(x)는 false가 됩니다.

 

2) 한정을 적용하는 방법

-p(x) = " x > 3";

-x의 정의역(domain)이 "4 이상인 모든 실수 " 라면 p(x)를 true가 됩니다.

 

전칭한정자는 A를 거꾸로 뒤집은 것입니다. 

- for every, for all이라는 의미로 모든이라는 뜻을 지닌 것입니다. 

이렇게 쓰는 것이 바로 전칭한정자입니다. 명제 함수에 대해서 전치한정자를 붙였다 이것은 위와 같이 

p(x) for every x in a domain D 

정의역 X에 있는 모든 원소에 대한 D

 

모든 x 명제함수 p(x)에 대해서 true다 하면 전칭 한정자가 됩니다.  집합 D에 어떤 원소 x에 대해서 거짓인 경우가 존재하면 명제함수는 거짓이 됩니다. 

 

따라서 전칭한정자는 집합의 모든 원소에 대해서 원소가 참이어야 합니다. 그렇지 않으면 거짓이라고 판단을 합니다. 예를들어 p(n) 명제함수를 n^2 + 2n이 홀수다 이러면 집합 D는 정수들의 집합이고 여기에 전칭한정자가 붙습니다. 

 

모든 정수에 대해서 N^2 + 2N은 홀수 이것이 참이냐 거짓이냐 p(n)은 n이 홀수일때만 true입니다. 만약 n이 짝수가 되면 거짓이 됩니다. 그래서 이 명제함수는 집합 D의 모든 원소에 대해서 참이 아니기 때문에 이 명제함수는 거짓이 됩니다. 

 

반례

 

P(X)가 명제함수라 할 때, ∀xP(x)가 거짓임을 보이기 위해서 domain에 속하는 값 중 하나라도 p(x)가 거짓임을 보이면 됩니다. 이것을 바로 반례라고 합니다. 

---

ex)

p(x)가 "x^2 > 0" 이고 domain이 모든 실수라 할 때, ∀xP(x)의 반례는?

- x = 0 이면 x^2 = 0 이므로 x^2 > 0을 만족하지 않는다.

따라서 ∀xP(x)는 거짓이 되고 x = 0을 반례라고 한다. 

---