마인드 맵 갤러리 이산수학 4장 술어논리
이산수학 4장에 나오는 개인, 술어, 수량사와 함수, 술어식과 명제의 기호화, 술어식의 술어 패러다임 등 술어논리에 대한 마인드맵입니다.
2023-11-18 10:36:19에 편집됨술어 논리
개인, 술어, 한정사 및 기능
개인
명제에서 고려되는 대상을 개인이라고 합니다.
개인은 독립적으로 존재하는 것입니다. 개인은 5, 3, 2 등과 같이 구체적일 수 있습니다. 장산(Zhang San)은 사람과 같이 추상적일 수도 있습니다.
특정 개체와 특정 개체를 개별 상수라고 합니다.
불확실한 개인을 개인변수라고 부른다.
개인을 논할 때 일반적으로 D로 대표되는 개인 영역이라 불리는 개별 논의의 범위를 명시할 필요가 있다. 일반적으로 다음과 같이 가정한다. D는 비어 있지 않습니다.
우리는 모든 동물, 모든 식물 등 세상에서 상상할 수 있는 모든 사물을 취합니다. 사물, 모든 문자, 모든 숫자 등으로 구성된 집합을 간단히 말해서 전체 개별 영역이라고 합니다. 글로벌 도메인이라고 불리며, 가장 큰 개별 도메인입니다.
술부
개인의 속성이나 개인 간의 관계를 표현하는 단어를 술어라고 합니다. 술어는 관계이다
개인의 속성을 표현하는 술어를 n개 개인의 속성을 표현하는 1요소 술어라고 합니다. 사이의 관계에 대한 술어를 n-ary 술어라고 합니다.
모든 n항 술어에 대해 술어와 해당 항소수를 동시에 표현하기 위해, n항함수를 표현하는 것과 마찬가지로 P(x1, x2, · · · , xn)의 형태로 표현됩니다.
그리고 G(x, y) : x > y, 이는 명제에 관한 함수, 명제함수(propositional function)라 불린다.
술어 선택은 개별 도메인과 관련됩니다.
우주에서 고려한다면 두 개의 술어가 필요하다
P(x)는 특성 술어라고 하며,
수량자
P(x)를 명제로 만드는 또 다른 방법은 개별 변수 x를 수량화하는 것입니다.
보편적인 수량화
수량화가 존재합니다.
개인의 정량적 특성을 표현하는 단어를 수량사라고 합니다.
만능 수량자 ∀
존재 수량자 ∃
현재 수량화는 술어가 아닌 개인에 대해서만 수행되므로 1차 술어라고 합니다. 단어 논리
수량자 뒤에는 다음이 와야 합니다. ∀x, ∀y, · · · , ∀δ, ∃x, ∃y, · · · , ∃δ와 같은 부피 변수. 따라서 ∀x, ∃x는 전반적인. 수량자 뒤에 오는 개별 변수를 안내 변수라고 합니다.
명제 함수의 모든 개별 변수를 수량화하면 명제를 얻습니다. 질문
수량자 ∀x 또는 ∃x의 역할 또는 관할권을 ∀x 또는 ∃x의 범위 또는 범위라고 하며 범위 내의 개별 변수 x를 제약 변수라고 합니다.
수량자 뒤에 괄호가 있는 경우 괄호 안의 부분은 해당 범위입니다(예: ∀x(P(x)→D(x));
대괄호가 없는 경우 수량자에 인접한 부분은 ∃xP(x)와 같이 범위입니다.
수량자에 의해 묶이지 않는 변수를 자유변수라고 합니다.
편지
"장산의 아버지", "두 숫자의 제곱의 합" 등을 표현하려면 함수를 사용해야 합니다. 숫자는 일반적으로 술어 논리에서 함수라고 합니다.
술어 공식 및 명제의 상징화
술어 공식
술어식(술어식)을 식이라 부르는데 이는 명제식의 이해와 동일하다. 이렇게 해서 올바르게 작성된 기호 문자열이나 의미가 명확한 표현(술어 포함)이라면 술어 공식입니다
임의의 자연수 n, n-진 술어 P 및 n 임의의 개체에 해당합니다. t1,t2, · · · ,tn, P(t1,t2, · · · ,tn)는 술어식입니다.
A는 술어 공식이고, ¬A는 술어 공식입니다.
A와 B가 술어 공식인 경우 A ⋆ B는 술어 공식입니다. 여기서 ⋆는 이진수입니다. 논리적 연결.
A가 술어 공식이면 ∀xA, ∃xA는 술어 공식입니다.
(1)(2)(3)(4)를 유한 횟수 이상 사용하여 얻은 기호 문자열이 유일한 술어입니다. 공식.
A와 B가 술어 공식인 경우 A ⋆ B는 술어 공식입니다. 여기서 ⋆는 이진수입니다. 논리적 연결.
명제의 상징화
술어논리에서 명제를 기호화하는 단계는 다음과 같다.
(1) 명제에서 개별상수를 모두 찾아 a, b, c,···, ai, bi,···로 표현한다.
(2) 속성에 특별한 주의를 기울여 주어진 개별 영역에서 선택해야 하는 모든 술어를 식별합니다. 술어 선택;
(3) 수량자를 결정하는 단계;
(4) 문구를 결정합니다.
(5) 주어진 명제를 상징하는 접속사를 찾아보세요.
술어 공식의 설명 및 유형
술어 공식 설명
술어식의 해석은 무한히 많으며, 각 해석(해석)Ⅰ은 5개로 구성된다. 부품으로 구성되어 있으며,
개별 도메인 지정 D.
술어 공식의 명제 논증에 진리값 할당
개별 도메인 D를 지정하는 것으로 술어 공식의 개별 상수와 자유 변수를 해석합니다. 요소
술어 수식의 함수를 D의 함수로 해석
술어 수식의 술어를 D의 술어로 해석합니다.
두 소거 수량자의 논리적 동등성
술어 수식 유형
어떤 해석에서도 참인 술어 공식을 영구적인 참 또는 유효한 공식이라고 합니다.
(영원히 참인 공식 대체 정리) 다음과 같은 명제 논리의 영원히 참인 공식에 대해 (p → q) ∧ p → q, 모든 명제 변수를 각각 술어 공식 A, B로 대체 p, q로 구한 술어식(A → B) ∧ A → B가 영원한 참 공식이다
1로 해석되는 술어와 0으로 해석되는 술어가 모두 있습니다. 공식은 중립 또는 우연이라고 불립니다.
중립 술어 공식은 유한한 수의 단계 내에서 결정될 수 없습니다. 항상 참인(또는 항상 거짓인) 술어 공식은 다음에서 결정될 수 있습니다. 제한된 단계 내에서의 결정.
술어 논리의 추론
논리적 의미
H1, H2, · · · , Hn과 C가 명제식이라고 가정하면, H1, H2, · · · , Hn이 모두 참이라면, C는 반드시 참이라고 결론을 내릴 수 있고, 그러면 C의 추론은 H1, H2,···,Hn에서 도출된다고 한다. 형식은 유효합니다(유효한 인수 형식). H1, H2, · · · ,Hn ⇒ C로 표시됩니다.
H1, H2, · · · ,Hn 및 C가 명제식이라고 가정하고, H1,H2, · · · ,Hn ⇒ C를 채웁니다. 필요조건은 H1 ∧ H2 ∧··· ∧ Hn → C가 영구식이라는 것이고, 즉, H1 ∧ H2 ∧ · · · ∧ Hn ⇒ C
기본 추론 규칙
다음과 같은 논리적 의미가 성립합니다. (1) ∀xA(x) ∨ ∀xB(x) ⇒ ∀x(A(x) ∨ B(x)). (2) ∃x(A(x) ∧ B(x)) ⇒ ∃xA(x) ∧ ∃xB(x).
술어 공식의 술어 정규형
술어 공식의 술어 정규형 정의
A = Q1x1Q2x2 · · · Qnxn(· · · B · · ·)(n ≥ 0)인 경우 A가 술어 공식이라고 가정합니다. Qi가 ∀ 또는 ∃이고 B에 성분이 없는 경우를 Qi라고 합니다. A = Q1x1Q2x2 · · · Qnxn(· · · B · · ·)는 A의 순방향 정규형입니다.
술어 공식의 정규형 계산
1. 논리 접속사를 ¬, ∧, ∨만 포함하는 술어 공식으로 줄입니다.
2. 다음 두 개의 동일한 표현을 사용하여 부정 접속사를 안쪽으로 이동합니다. (1) ¬∀xA(x) = ∃x¬A(x) (2) ¬∃xA(x) = ∀x¬A(x)
3. 필요한 경우 이름 바꾸기 기술을 사용하여 동등한 표현을 사용하여 모든 수량자를 앞으로 이동합니다.
논리적으로 동등한 술어 공식
술어 공식의 정의
A와 B가 술어 공식이라고 가정합니다. 어떤 해석에서든 A와 B가 동일한 값을 갖는 경우 그러면 A와 B는 논리적으로 동일하다고 말하며 A = B로 표시됩니다.
A = B의 필요충분조건은 술어식 A ← B가 항상 참이라는 것입니다.
기본 동등성
¬∀xA(x) = ∃x¬A(x).
¬∃xA(x) = ∀x¬A(x).
∀x(A(x) ∧ B) = ∀xA(x) ∧ B
∀x(A(x) ∨ B) = ∀xA(x) ∨ B
∃x(A(x) ∧ B) = ∃xA(x) ∧ B
∃x(A(x) ∨ B) = ∃xA(x) ∨ B.
∀x(A(x) ∧ B(x)) = ∀xA(x) ∧ ∀xB(x)
∀는 ∧에 할당할 수 있지만 ∀x(A(x) ∨ B(x)) ̸= ∀xA(x) ∨ ∀xB(x)입니다. 예를 들어, 해석 I가 주어지면 D = Z, A(x) : x는 짝수, B(x) : x는 홀수입니다.
∃x(A(x) ∨ B(x)) = ∃xA(x) ∨ ∃xB(x)
∃는 ∨에 할당할 수 있지만 ∃x(A(x) ∧ B(x) ̸= ∃xA(x) ∧ ∃xB(x)입니다.
이중 가중치 단어
∀x∀yA(x, y) = ∀y∀xA(x, y).
∃x∃yA(x, y) = ∃y∃xA(x, y)
등가 치환 정리는 여전히 술어 논리에 적용됩니다.