논리 행렬

논리 행렬, 이진 행렬, 관계 행렬, 부울 행렬 또는 (0, 1) 행렬은 부울 도메인 B = {0, 1}의 항목이 있는 행렬이다. 그러한 행렬은 유한 집합 쌍 사이의 이항 관계를 나타내기 위해 사용될 수 있다.

관계의 행렬 표현

R이 유한 지수 집합 X와 Y 사이의 이항 관계인 경우(그러므로 R × X×Y), R은 행과 컬럼 지수가 각각 X와 Y의 요소를 지수화하는 논리 행렬 M으로 나타낼 수 있다(M의 항목이 정의됨).

M_{i,j}={\begin{case}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\in R.\end{case}}

행렬의 행과 열 번호를 지정하기 위해, 집합 X와 Y는 양의 정수로 색인화된다: i는 X의 카디널리티(크기)에서 X의 카디널리티(크기)까지, j는 Y의 카디널리티에서 1까지이다. 자세한 내용은 인덱스 세트의 항목을 참조하십시오.

예

{1, 2, 3, 4} 세트의 이진 관계 R은 aRb가 b를 균등하게 나누고 나머지는 없는 경우에만 유지하도록 정의된다. 예를 들어 2R4는 2가 4를 나누면 나머지가 남지만 3이 4가 남으면 1이 남기 때문에 3R4는 버티지 못한다. 다음 집합은 R이 보유하는 쌍들의 집합이다.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

논리 행렬로서의 해당 표현은

{\pmatrix}1&1&1\0&1&1\0&0&0&0\\nd{pmatrix},

대각선도 있고, 각 숫자는 스스로를 나누기 때문에.

기타 예

순열 행렬은 (0, 1)-매트릭스로, 열과 행이 각각 0이 아닌 원소를 정확히 하나씩 가지고 있다.
- 코스타스 배열은 순열 매트릭스의 특별한 경우다.
결합기법과 유한 기하학의 발생 행렬은 점(또는 정점)과 지오메트리의 선, 블록 설계의 블럭 또는 그래프의 가장자리(구체 수학) 사이의 발생률을 나타내는 행렬을 가지고 있다.
분산 분석에서 설계 행렬은 일정한 행 합계를 갖는 a(0, 1) 행렬이다.
논리 행렬은 그래프 이론에서 인접 행렬을 나타낼 수 있다. 비대칭 행렬은 지시된 그래프에 해당하고, 대칭 행렬은 일반 그래프에 해당하며, 대각선의 1은 해당 정점의 루프에 해당한다.
단순하고 간접되지 않은 초당적 그래프의 생체역량 행렬은 (0, 1) 매트릭스이며, 모든 (0, 1) 매트릭스는 이러한 방식으로 발생한다.
m 제곱이 없는 n-smooth 숫자 목록의 주요 인자는 m × ×(n) (0, 1)-매트릭스로 설명할 수 있으며, 여기서 π은 prime-counting 함수로서, j번째 prime이 ih 숫자를 나눈 경우에만 a가_ij 1이다. 이 표현은 2차 체 인수 알고리즘에서 유용하다.
두 가지 색상으로만 픽셀을 포함하는 비트맵 이미지는 0이 한 색의 픽셀을 나타내고, 0은 다른 색의 픽셀을 나타내는 a(0, 1) 매트릭스로 나타낼 수 있다.
바둑^[1] 게임에서 게임 규칙을 확인하는 데 바이너리 매트릭스를 사용할 수 있다.

일부 속성

유한 집합에 대한 동등 관계 행렬은 I, 즉 대각선의 항목이 모두 1인 반면 다른 것은 모두 0인 ID 행렬이다. 보다 일반적으로 관계 R이 I ⊂ R을 만족하면 R은 반사적 관계다.

부울 도메인을 의미 부여로 보는 경우, 여기서 덧셈은 논리적 OR에 해당하고, 곱셈은 논리적 AND에 해당하며, 두 관계 구성의 행렬 표현은 이러한 관계의 행렬 표현 매트릭스 제품과 동일하다. 이 제품은 예상 시간 O(n²)로 계산할 수 있다.^[2]

이항 행렬에 대한 빈번한 연산은 모듈식 산술모드 2의 관점에서 정의된다. 즉, 요소는 갈루아 필드 GF(2) = =의₂ 요소로 처리된다. 그것들은 다양한 표현에서 발생하며, 많은 더 제한적인 특수 형식을 가지고 있다. 그것들은 예를 들어 XOR 만족도에 적용된다.

구별되는 m-by-n 이항 행렬의 수는 2와^mn 같으며, 따라서 유한하다.

격자

n과 m을 주고 U는 모든 논리 m × n 행렬의 집합을 나타내도록 한다. 그러면 U는 다음과 같은 부분적인 명령을 받는다.

m\property n\cHB {\text}\when}\when \all i,j\properties m_{ij}=1\put n_{ij}=1.

실제로 U는 구성 요소별로 적용된 연산 및 두 행렬 사이에 부울 대수를 형성한다. 논리 행렬의 보완은 모든 0과 1을 반대편에 맞바꾸어 얻는다.

모든 논리 행렬 a = ( a )에는 전치^T a = ( a )가 있다. a가 열이나 행이 동일한 0이 없는 논리 행렬이라고 가정해 보십시오. 그 다음, 부울 산수를 사용하는 매트릭스 제품은 a가^T m × m 아이덴티티 매트릭스를 포함하고 a^T 제품은 n × n 아이덴티티를 포함한다.

수학 구조로서, 부울 대수 U는 포함에 의해 정렬된 격자를 형성한다. 추가적으로 그것은 행렬 곱셈에 의한 곱셈 격자다.

U의 모든 논리 행렬은 이진 관계에 해당한다. U에 관한 이러한 열거된 작업과 순서는 행렬 곱셈이 관계의 구성을 나타내는 관계의 미적분학에 해당한다.^[3]

논리 벡터

m 또는 n이 1이면 m × n 논리 행렬(M_ij)은 논리 벡터다. m = 1이면 벡터가 행 벡터, n = 1이면 열 벡터다. 어느 경우든 1과 동일한 지수는 벡터의 변위로부터 떨어진다.

$(P_{i}),\ i=1,2,\ldots ,m$ $(P_{i}),\ i=1,2,\ldots ,m$ $(P_{i}),\ i=1,2,\ldots ,m$ ) $(P_{i}),\ i=1,2,\ldots ,m$ , $(P_{i}),\ i=1,2,\ldots ,m$ = 1, $(P_{i}),\ i=1,2,\ldots ,m$ , $(P_{i}),\ i=1,2,\ldots ,m$ … $(P_{i}),\ i=1,2,\ldots ,m$ , $(P_{i}),\ i=1,2,\ldots ,m$ $(P_{i}),\i=1,2,\ldots,m$ 및 $(Q_{j}),\ j=1,2,\ldots ,n$ ( $(Q_{j}),\ j=1,2,\ldots ,n$ j $(Q_{j}),\ j=1,2,\ldots ,n$ , $(Q_{j}),\ j=1,2,\ldots ,n$ = $(Q_{j}),\ j=1,2,\ldots ,n$ , $(Q_{j}),\ j=1,2,\ldots ,n$ 2, $(Q_{j}),\=1,2,\ldots ,n$ 이 $(P_{i}),\ i=1,2,\ldots ,m$ $(Q_{j}),\ j=1,2,\ldots ,n$ 두 개의 논리 벡터라고 가정해 보자. P와 Q의 외부 제품은 m × n 직사각형 관계를 만든다.

M_{ij}=P_{i}\land Q_{j}.

그러한 행렬의 행과 열을 다시 정렬하면 모든 행과 열을 행렬의 직사각형 부분으로 조립할 수 있다.^[4]

h를 모든 것의 벡터가 되게 하라. 그런 다음 v가 임의의 논리 벡터인 경우 R^T = v h 관계에는 v에 의해 결정된 상수 행이 있다. 관계의 미적분학에서는 그러한 R을 벡터라고 부른다.^[4] 특정한 예는 보편적 관계 h h이다^T.

주어진 관계 R의 경우 R에 포함된 최대 직사각형 관계를 R에서는 개념이라고 한다. 관계는 개념으로 분해한 다음 유도된 개념 격자에 주목함으로써 연구될 수 있다.

그룹형 구조
	토털리티^α	연관성	아이덴티티	반전성	동시성
세미그룹체	필요없음	필수의	필요없음	필요없음	필요없음
소분류	필요없음	필수의	필수의	필요없음	필요없음
조로이드	필요없음	필수의	필수의	필수의	필요없음
마그마	필수의	필요없음	필요없음	필요없음	필요없음
퀘이시그룹	필수의	필요없음	필요없음	필수의	필요없음
유니탈 마그마	필수의	필요없음	필수의	필요없음	필요없음
세미그룹	필수의	필수의	필요없음	필요없음	필요없음
루프	필수의	필요없음	필수의	필수의	필요없음
역세미그룹	필수의	필수의	필요없음	필수의	필요없음
모노이드	필수의	필수의	필수의	필요없음	필요없음
정류단모노이드	필수의	필수의	필수의	필요없음	필수의
그룹	필수의	필수의	필수의	필수의	필요없음
아벨 군	필수의	필수의	필수의	필수의	필수의
^α 많은 선원에 의해 사용되며 다르게 정의되는 폐쇄 공리는 동등하다.

"필요하지 않음"을 0으로 나타낼 수 있고 "필요함"을 1로 나타내 논리 행렬 R을 형성할 수 있는 그룹 같은 구조물의 표를 고려한다. R R의^T 요소를 계산하려면 이 행렬의 행에 있는 논리 벡터 쌍의 논리적 내적 산출물을 사용할 필요가 있다. 이 내부 제품이 0이면 행이 직교한 것이다. 실제로 세미그룹은 루프에 직교하고, 작은 범주는 퀘이시에 직교하며, 그룹노이드(groupoid)는 마그마에 직교한다. 따라서 R R에는^T 0이 존재하며, 보편적 관계가 되지 못한다.

행 및 열 합

논리 행렬의 모든 것을 추가하는 것은 두 가지 방법으로 이루어질 수 있다: 먼저 행을 합하는 것과 먼저 열을 합하는 것이다. 행 합계가 추가되면 열 합계가 추가될 때와 같은 합이다. 발생 기하학에서 행렬은 "점"에 해당하는 행을 가진 발생 행렬로 해석되며, 열은 "블록"(점들로 이루어진 일반화 선)으로 해석된다. 행 합은 점 도라고 하며, 열 합은 블럭 도라고 한다. 설계 이론의^[5] 제안 1.6은 점의 합이 블럭의 합과 같다고 말한다.

이 영역의 초기 문제는 "특정 점 정도와 블럭 도(또는 매트릭스 언어로, 주어진 행과 열 합계가 있는 타입 v × b의 a (0, 1)- 매트릭스가 존재하기 위해 필요하고도 충분한 조건을 찾는 것"이었다.^[5] 그러한 구조는 블록 설계다.

참고 항목

메모들

^ Petersen, Kjeld (February 8, 2013). "Binmatrix". Retrieved August 11, 2017.
^ Patrick E. O'Neil; Elizabeth J. O'Neil (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure". Information and Control. 22 (2): 132–138. doi:10.1016/s0019-9958(73)90228-3. — 알고리즘은 idempotent, cf. p.134 (하단)의 덧셈에 의존한다.
^ 어빙 코필로위시 (1948년 12월) "관계 미적분학의 매트릭스 개발", Journal of Symbolic Logic 13(4): 193–203 Jstor 링크
^ ^a ^b Gunther Schmidt (2013). "6: Relations and Vectors". Relational Mathematics. Cambridge University Press. p. 91. doi:10.1017/CBO9780511778810. ISBN 9780511778810.
^ ^a ^b Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). Design Theory (2nd ed.). Cambridge University Press. p. 18. ISBN 978-0-521-44432-3.

참조

Hogben, Leslie (2006), Handbook of Linear Algebra (Discrete Mathematics and Its Applications), Boca Raton: Chapman & Hall/CRC, ISBN 978-1-58488-510-8, § 31.3, 이진 행렬
Kim, Ki Hang (1982), Boolean Matrix Theory and Applications, ISBN 978-0-8247-1788-9
H. J. 라이저(1957) "0과 1의 행렬의 조합 특성" 캐나다 수학 저널 9: 371–7.
Ryser, H.J. (1960) "0과 1의 행렬" 캐나다 수학 저널 12: 463–76.
Ryser, H.J. (1960) "Zeros and One의 매트릭스", 미국수학협회 회보 66: 442–64.
D. R. 풀커슨(1960) "추적이 0인 행렬 제로", 태평양 수학 저널 10; 831–6
D. R. 풀커슨 & H. J. 라이서(1961) "폭과 높이 (0, 1)-함수" 캐나다 수학 저널 13: 239–55.
L. R. 포드 주니어 & D. R. 풀커슨(1962) § 2.12 "0과 1로 구성된 행렬", 네트워크 흐름에서 79페이지에서 91페이지까지, 프린스턴 대학교 출판부 MR0159700

외부 링크

"Logical matrix", Encyclopedia of Mathematics, EMS Press, 2001 [1994]

[1] Petersen, Kjeld (February 8, 2013). "Binmatrix". Retrieved August 11, 2017.

[2] Patrick E. O'Neil; Elizabeth J. O'Neil (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure". Information and Control. 22 (2): 132–138. doi:10.1016/s0019-9958(73)90228-3. — 알고리즘은 idempotent, cf. p.134 (하단)의 덧셈에 의존한다.

[3] 어빙 코필로위시 (1948년 12월) "관계 미적분학의 매트릭스 개발", Journal of Symbolic Logic 13(4): 193–203 Jstor 링크

[GS-4] Gunther Schmidt (2013). "6: Relations and Vectors". Relational Mathematics. Cambridge University Press. p. 91. doi:10.1017/CBO9780511778810. ISBN 9780511778810.

[BJL-5] Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). Design Theory (2nd ed.). Cambridge University Press. p. 18. ISBN 978-0-521-44432-3.

[1]

[2]

[3]

[4]

α

[5]

v t 매트릭스 클래스
명시적으로 제한된 항목	교번트 반대각형 반헤르미티아누스 반대칭 화살촉 밴드 비다이각형 이대칭 블록 대각선 블록 블록삼각형 부울 카우치 중심대칭 회의 콤플렉스 하다마드 코포시티브 대각선 우세 대각선 이산 푸리에 변환 초급 등가 프로베니우스 일반화 순열 하다마드 행클 에르미트어 헤센베르크 할로우 정수 논리적인 매트릭스 단위 메츨러 무어 비음성 펜타디각형 순열 당칭 다항식 쿼터니온어 서명 스큐헤르미티안 스큐 대칭 스카이라인 스파스 실베스터 대칭 토플리츠 삼각형 삼두각형 유니타리 반데르몽드 월시 Z
상수	교환 힐베르트 아이덴티티 레머 1개 중 파스칼 파울리 레데퍼 시프트 영
고유값 또는 고유벡터 조건	동반자 수렴성 결함이 있는 대각선 가능 후르비츠 포지티브-확정성 슈틸트제스
제품 또는 역에 대한 만족도 조건	컨그루엔트 Idempotent 또는 Projection 되돌릴 수 없는 비자발적 닐포텐트 정상 직교 단모듈라 전지전능 완전히 단변성 체중 측정
특정 애플리케이션 사용	애드주게이트 교대 부호 증강됨 베주트 칼레만 카르탄 서큘런트 공동 인자 정류 혼란 콕시터 거리 중복 및 제거 유클리드 거리 기본(선형 미분 방정식) 제너레이터 그램 헤시안 세대주 야코비안 모멘트 모두 다 갚다, 청산하다 뽑다 무작위 회전 세이퍼트 전단 유사성 심플렉틱 완전히 긍정적이다. 변환
통계에 사용됨	센터링 상관 관계 공분산 디자인 이중 확률적 피셔 정보 모자 정밀도 스토카스틱 전이
그래프 이론에 사용됨	인접 바이애드제이컨시 정도 에드먼즈 발생 라플라시안 사이델 인접 투테
이공계에 사용됨	카비보-코바야시-마사와 밀도 기본(컴퓨터 비전) 퍼지 연관성 감마 겔만 해밀턴어 불규칙한 겹치다 S 국가전환 대체 Z(화학)
관련 용어	요르단 정상 형태 선형독립 행렬 지수 원뿔 단면의 행렬 표현 퍼펙트 매트릭스 사이비인버스 행 에슐론 양식 룬스키안
행렬 목록 범주:행렬

Search