이산 수학-명제 논리
수학적 논리의 규칙은 수학적 진술을 추론하는 방법을 지정합니다. 그리스 철학자 아리스토텔레스는 논리적 추론의 선구자였습니다. 논리적 추론은 수학의 많은 영역과 결과적으로 컴퓨터 과학에 대한 이론적 기반을 제공합니다. 그것은 컴퓨팅 기계 설계, 인공 지능, 프로그래밍 언어를위한 데이터 구조 정의 등과 같은 컴퓨터 과학에서 많은 실용적인 응용 프로그램을 가지고 있습니다.
Propositional Logic진실 값 "참"및 "거짓"이 할당 될 수있는 진술과 관련됩니다. 목적은 이러한 진술을 개별적으로 또는 복합적으로 분석하는 것입니다.
전치사 논리 – 정의
명제는 진리 값이 "true"또는 진리 값 "false"인 선언문 모음입니다. 명제 문은 명제 변수와 연결어로 구성됩니다. 명제 변수는 대문자 (A, B 등)로 표시합니다. 연결은 명제 변수를 연결합니다.
제안의 몇 가지 예는 다음과 같습니다.
- "Man is Mortal", 진리 값 "TRUE"를 반환합니다.
- "12 + 9 = 3 – 2", 진리 값 "FALSE"를 반환합니다.
다음은 제안이 아닙니다-
"A는 2보다 작습니다". A의 특정 값을 지정하지 않으면 그 진술이 참인지 거짓인지 말할 수 없기 때문입니다.
연결
명제 논리에서 일반적으로 우리는 다음과 같은 5 개의 연결을 사용합니다.
또는 ($ \ lor $)
그리고 ($ \ land $)
부정 / 아님 ($ \ lnot $)
의미 / if-then ($ \ rightarrow $)
경우에만 ($ \ Leftrightarrow $).
OR ($\lor$) − 두 명제 A와 B의 OR 연산 ($ A \ lor B $로 작성)은 명제 변수 A 또는 B 중 적어도 하나가 참이면 참입니다.
진리표는 다음과 같습니다-
| ㅏ | 비 | A ∨ B |
|---|---|---|
| 진실 | 진실 | 진실 |
| 진실 | 그릇된 | 진실 |
| 그릇된 | 진실 | 진실 |
| 그릇된 | 그릇된 | 그릇된 |
AND ($\land$) − 두 명제 A와 B의 AND 연산 ($ A \ land B $로 작성)은 명제 변수 A와 B가 모두 참이면 참입니다.
진리표는 다음과 같습니다-
| ㅏ | 비 | A ∧ B |
|---|---|---|
| 진실 | 진실 | 진실 |
| 진실 | 그릇된 | 그릇된 |
| 그릇된 | 진실 | 그릇된 |
| 그릇된 | 그릇된 | 그릇된 |
Negation ($\lnot$) − 명제 A ($ \ l 아님 A $로 작성)의 부정은 A가 참이면 거짓이고 A가 거짓이면 참입니다.
진리표는 다음과 같습니다-
| ㅏ | ¬ A |
|---|---|
| 진실 | 그릇된 |
| 그릇된 | 진실 |
Implication / if-then ($\rightarrow$)− 암시 $ A \ rightarrow B $는 "if A, then B"라는 명제입니다. A가 참이고 B가 거짓이면 거짓입니다. 나머지 경우는 사실입니다.
진리표는 다음과 같습니다-
| ㅏ | 비 | A → B |
|---|---|---|
| 진실 | 진실 | 진실 |
| 진실 | 그릇된 | 그릇된 |
| 그릇된 | 진실 | 진실 |
| 그릇된 | 그릇된 | 진실 |
If and only if ($ \Leftrightarrow $) − $ A \ Leftrightarrow B $는 p와 q가 같을 때 참이되는, 즉 둘 다 거짓이거나 둘 다 참일 때 참인 쌍 조건부 논리 연결입니다.
진리표는 다음과 같습니다-
| ㅏ | 비 | A ⇔ B |
|---|---|---|
| 진실 | 진실 | 진실 |
| 진실 | 그릇된 | 그릇된 |
| 그릇된 | 진실 | 그릇된 |
| 그릇된 | 그릇된 | 진실 |
토톨 로지
Tautology는 명제 변수의 모든 값에 대해 항상 참인 공식입니다.
Example − $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $가 팽팽하다는 것을 증명하십시오
진리표는 다음과 같습니다-
| ㅏ | 비 | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| 진실 | 진실 | 진실 | 진실 | 진실 |
| 진실 | 그릇된 | 그릇된 | 그릇된 | 진실 |
| 그릇된 | 진실 | 진실 | 그릇된 | 진실 |
| 그릇된 | 그릇된 | 진실 | 그릇된 | 진실 |
$ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $의 모든 값이 "True"라는 것을 알 수 있듯이 이는 팽팽한 것입니다.
모순
모순은 명제 변수의 모든 값에 대해 항상 거짓 인 공식입니다.
Example − $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $이 모순임을 증명
진리표는 다음과 같습니다-
| ㅏ | 비 | A ∨ B | ¬ A | ¬ B | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| 진실 | 진실 | 진실 | 그릇된 | 그릇된 | 그릇된 | 그릇된 |
| 진실 | 그릇된 | 진실 | 그릇된 | 진실 | 그릇된 | 그릇된 |
| 그릇된 | 진실 | 진실 | 진실 | 그릇된 | 그릇된 | 그릇된 |
| 그릇된 | 그릇된 | 그릇된 | 진실 | 진실 | 진실 | 그릇된 |
$ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $의 모든 값이 "False"임을 알 수 있듯이 모순입니다.
우연성
우발성은 명제 변수의 모든 값에 대해 참 값과 거짓 값을 모두 포함하는 공식입니다.
Example − $ (A \ lor B) \ land (\ l 아님 A) $ 우발 상황 증명
진리표는 다음과 같습니다-
| ㅏ | 비 | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| 진실 | 진실 | 진실 | 그릇된 | 그릇된 |
| 진실 | 그릇된 | 진실 | 그릇된 | 그릇된 |
| 그릇된 | 진실 | 진실 | 진실 | 진실 |
| 그릇된 | 그릇된 | 그릇된 | 진실 | 그릇된 |
$ (A \ lor B) \ land (\ lnot A) $의 모든 값에 "True"와 "False"가 모두있는 것을 볼 수 있듯이 이는 우발적입니다.
명제 동등성
다음 두 조건 중 하나라도 유지되면 두 문 X와 Y는 논리적으로 동일합니다.
각 진술의 진리표는 동일한 진리 값을 갖습니다.
이중 조건문 $ X \ Leftrightarrow Y $는 팽팽한 표현입니다.
Example − $ \ lnot (A \ lor B) 및 \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $이 동등 함을 증명
첫 번째 방법으로 테스트 (Matching 진리표)
| ㅏ | 비 | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| 진실 | 진실 | 진실 | 그릇된 | 그릇된 | 그릇된 | 그릇된 |
| 진실 | 그릇된 | 진실 | 그릇된 | 그릇된 | 진실 | 그릇된 |
| 그릇된 | 진실 | 진실 | 그릇된 | 진실 | 그릇된 | 그릇된 |
| 그릇된 | 그릇된 | 그릇된 | 진실 | 진실 | 진실 | 진실 |
여기에서 $ \ lnot (A \ lor B) 및 \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $의 진리 값이 동일하므로 문이 동일하다는 것을 알 수 있습니다.
두 번째 방법으로 테스트 (Bi-conditionality)
| ㅏ | 비 | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| 진실 | 진실 | 그릇된 | 그릇된 | 진실 |
| 진실 | 그릇된 | 그릇된 | 그릇된 | 진실 |
| 그릇된 | 진실 | 그릇된 | 그릇된 | 진실 |
| 그릇된 | 그릇된 | 진실 | 진실 | 진실 |
$ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $은 팽팽한 표현이므로이 문장은 동일합니다.
역, 대화 및 반대 양성
암시 / if-then $ (\ rightarrow) $는 조건문이라고도합니다. 두 부분으로 나뉩니다.
- 가설, p
- 결론, q
앞서 언급했듯이 $ p \ rightarrow q $로 표시됩니다.
Example of Conditional Statement−“숙제를하면 처벌을받지 않습니다.” 여기서 "당신은 숙제를한다"는 가설, p이고 "당신은 벌을받지 않을 것입니다"는 결론, q입니다.
Inverse− 조건 문의 반대는 가설과 결론 모두의 부정입니다. 문이 "If p, then q"이면 역은 "If not p, then not q"가됩니다. 따라서 $ p \ rightarrow q $의 역은 $ \ lnot p \ rightarrow \ lnot q $입니다.
Example −“숙제를하면 벌을받지 않는다”의 역은“숙제를하지 않으면 벌을 받는다”입니다.
Converse− 조건 문의 반대는 가설과 결론을 교환하여 계산됩니다. 문장이“If p, then q”이면 반대는“If q, then p”가됩니다. $ p \ rightarrow q $의 반대는 $ q \ rightarrow p $입니다.
Example −“숙제를하면 벌을받지 않는다”의 역은“벌을받지 않으면 숙제를한다”입니다.
Contra-positive− 조건 문의 반대 양성은 가설과 역문의 결론을 교환하여 계산됩니다. 만약 문장이 "If p, then q"이면 반대 양성은 "If not q, then not p"가됩니다. $ p \ rightarrow q $의 반대 양성은 $ \ lnot q \ rightarrow \ lnot p $입니다.
Example − "숙제를하면 벌을받지 않는다"의 반대 양성은 "벌을 받으면 숙제를하지 않았다"입니다.
이중성 원칙
이중성 원칙은 모든 실제 문에 대해 공용체를 교차로 (또는 그 반대로) 교환하고 Universal 집합을 Null 집합으로 (또는 그 반대로) 교환하여 얻은 이중 문도 참이라고 말합니다. 어떤 진술의 이중이 진술 자체라면,self-dual 성명서.
Example − $ (A \ cap B) \ cup C $의 이중은 $ (A \ cup B) \ cap C $입니다.
일반 형식
우리는 모든 명제를 두 가지 정규 형식으로 변환 할 수 있습니다.
- 결합 정상형
- 분리형 정규형
결합 정규형
OR로 연결된 변수 (변수의 부정 포함) 중 AND를 연산하여 얻은 복합 문은 결합 정규형입니다. 집합 연산의 경우 Union으로 연결된 변수 중 Intersection에서 얻은 복합 문입니다.
Examples
$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ 컵 Q) \ cap (Q \ 컵 R) $
분리형 정규형
AND로 연결된 변수 (변수의 부정 포함) 중 OR을 연산하여 얻은 복합 문은 분리 정규형입니다. 집합 연산의 경우 교차점과 연결된 변수 중 Union을 통해 얻은 복합 문입니다.
Examples
$ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $
$ (P \ cap Q) \ cup (Q \ cap R) $