한 번 읽기 함수

수학에서 한 번 읽기 함수는 각 변수가 한 번만 나타나는 부울식으로 설명할 수 있는 부울함수의 특별한 유형이다.

더 정확히 말하면, 이 표현은 논리 결합, 논리 분리, 부정의 연산만을 사용해야 한다.De Morgan의 법칙을 적용함으로써 그러한 표현은 개별 변수에만 부정(아직도 각 변수는 한 번만 나타냄)이 사용되는 표현으로 변형될 수 있다.각 부정 변수를 부정(negative)을 나타내는 새로운 양의 변수로 대체함으로써, 그러한 함수는 부정(negative)이 없는 읽기-한 번 부울(read-one boolean) 함수로 표현되는 등가의 양의 읽음-한 번 부울 함수로 변환할 수 있다.^[1]

예

예를 들어, 세 변수 a, b, c의 경우 식

$b\displaystyle a\put b\put c}$

$(b\displaystyle a\property(b\vee c)$

${\displaystyle }$(${\displaystyle \wedge }$ ${\displaystyle b}$)$$${\displaystyle \vee }$ ${\displaystyle c}$ ${\displaystyle (a\b)\vee c}$ 및

$a\vee b\vee c}$

모두 한 번 읽음(이러한 식에서 변수를 허용하여 얻은 다른 함수와 동일)그러나 표현식에 의해 주어진 부울 중위수 연산

$(a\displaystyle (a\ve b)\bee(a\ve c)\bee(b\ve c)}$

한 번 읽지 않음: 이 공식은 각 변수의 복사본이 두 개 이상이며, 각 변수를 한 번만 사용하는 동등한 공식은 없다.^[2]

특성화

a (긍정적인) 읽기-한 번 함수의 이격 정상 형태는 일반적으로 그 자체가 읽기-한 번이 아니다.그럼에도 불구하고, 기능에 대한 중요한 정보를 담고 있다.특히 정점들이 변수를 나타내는 공동발생 그래프를 형성하고, 가장자리가 둘 다 결점 정상 형태의 같은 절에서 발생하는 변수 쌍을 연결한다면, 한 번 읽은 함수의 공동발생 그래프는 반드시 cograph가 된다.더 정확히 말하면, 양의 부울 함수는 그것의 공존 그래프가 cograph인 경우에만 한 번 읽히고, 게다가 공동 발생 그래프의 모든 최대 클릭은 분리 정상 형태의 접속사들 중 하나를 형성한다.^[3]즉, 동시 발생 그래프의 정점 집합에 대한 함수로 해석될 때, 읽기-한 번 함수는 최대 클라이크를 포함하는 정점 집합에 대해 참이고, 그렇지 않으면 거짓이다.예를 들어, 중위수 함수는 세 변수의 결합인 삼각형 그래프와 같은 공존 그래프를 가지고 있지만, 이 그래프(전체 그래프)의 3-Vertex 완전 하위 그래프는 중위수가 아닌 결합에 대해서만 절의 하위 집합을 형성한다.^[4]양수 읽기-한 번 식의 두 변수는 식에서 가장 낮은 공통 조상이 접속사일 경우에만 발생 그래프에 인접하므로 표현 트리는 해당 cograph에 대한 cotree로 해석할 수 있다.^[5][6]

긍정적인 읽기-한 번 함수의 또 다른 대체 특성화는 이들의 이격성과 결합적인 정상 형태를 결합한다.모든 변수를 사용하는 특정 변수 시스템의 양의 함수는 분리 정규 형태와 결합 정규 형태의 모든 절이 정확히 하나의 변수를 갖는 경우에만 한 번 읽힌다.^[7]

인식

다항식 시간에서 분리 정규식으로부터 읽기-한 번 함수를 인식할 수 있다.^[8]또한 기능 평가의 2차 횟수만 사용하여 어떤 진실 할당에서도 평가가 가능한 '블랙박스'를 통해서만 기능에 액세스할 수 있는 양수 읽기-한 번 함수에 대한 읽기-한 번 식을 찾을 수 있다.^[9]

메모들

참조