시간 논리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

시간 논리는 시간의 개념을 형식화하여 표현하고 추론하는 데 사용되는 논리 체계이다. 아리스토텔레스는 미래 사건의 우연성에 대한 논의에서 시간 논리의 개념을 제시했으며, 20세기 전반에 예르지 워스에 의해 처음으로 형식화되었다. 이후 아서 프라이어는 시간 논리를 발전시켜 "미래의 언젠가"와 "과거의 언젠가"를 나타내는 양상 연산자를 도입했다. 한스 캄프는 이진 시간 연산자를 소개했으며, 아미르 프누엘리는 선형 시간 논리를, 에드먼드 클라크와 앨런 에머슨은 계산 트리 논리를 제안했다. 시간 논리는 선형 시간 논리(LTL), 계산 트리 논리(CTL), 구간 시간 논리(ITL) 등 다양한 종류가 있으며, 프로그램 검증, 인공지능, 데이터베이스 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

양상 논리 - 본질
본질은 사물이나 개념의 근본적인 성질이나 특징을 의미하는 철학적 개념으로, 아리스토텔레스에서 유래하여 다양한 철학 사상과 종교에서 논의되었으며, 특히 실존주의는 "존재가 본질에 앞선다"는 관점으로 새로운 해석을 제시하였다.
양상 논리 - 인식 논리
인식 논리는 지식과 믿음 같은 인식 상태를 형식적으로 추론하는 양상 논리의 분야로, '안다'를 나타내는 양상 연산자 K를 사용하여 지식을 표현하고 공통 지식과 분배 지식 같은 개념을 다루며, 가능 세계 모델에 기반한 크립키 구조로 형식화되어 지식 추론을 탐구한다.
병행성 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다.
병행성 - 기아 상태
기아 상태는 컴퓨터 과학에서 프로세스가 필요한 자원을 할당받지 못해 무한정 대기하는 현상으로, 단순한 스케줄링 알고리즘, 우선순위 역전, 교착 상태 등으로 인해 발생하며 시스템 효율성을 저하시키고 작업 완료를 지연시키지만, 에이징 기법과 같은 공정한 스케줄링 알고리즘이나 우선순위 조정으로 해결할 수 있다.
컴퓨터 과학 내 논리 - 자동화된 추론
자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다.
컴퓨터 과학 내 논리 - 혼 절
혼 절은 하나의 긍정 리터럴만을 포함하는 분리절이며, 논리 프로그래밍, 자동 정리 증명, 데이터베이스 이론 등 여러 분야에 응용된다.

시간 논리
개요
분야	논리학, 철학, 컴퓨터 과학
유형	형식 논리
연구 대상	시간의 추론 및 표현
역사
초기 연구	아리스토텔레스의 《명제론》 (De Interpretatione) 제9장 (미래의 우연성에 대한 논의)
창시자	아르투어 프라이어
주요 연구자	아르투어 프라이어 야코 힌티카 니콜라스 레셔 존 메리엄 리처드 몬태규 한스 캄프 도브 가베이 에미르 하피즈
주요 개념
기본 개념	시간의 흐름에 따라 변하는 명제의 참/거짓
주요 연산자	F (미래에 언젠가) G (미래에 항상) P (과거에 언젠가) H (과거에 항상) X (다음에) U (Until, ~까지) S (Since, ~부터)
응용 분야
컴퓨터 과학	프로그램 검증 데이터베이스 에이전트 기반 시스템
인공지능	계획 수립, 추론
철학	시간, 행위, 의무 등 다양한 철학적 개념 분석
언어학	시간 표현 분석

2. 역사

아리스토텔레스는 삼단 논법 이론을 주로 연구했지만, 그의 저서에는 초기, 부분적으로 개발된 형태의 1차 시간 양상 이원 논리를 암시하는 등 현재 시간 논리의 선구로 여겨지는 구절들이 있다.^[1] 찰스 샌더스 퍼스는 논리학자들이 시간을 '비논리적인' 문제로 간주해 왔다고 언급하며, 논리가 시간적 수정을 도입했을 때 큰 혼란이 발생하지 않을 정도로 발전되지 못했다고 생각했다.^[2]

20세기 전반, 예르지 워스는 1947년에 밀의 정경을 형식화하면서 시간적 기능을 형식화하기 위한 논리를 제시했다. 이 논리는 아서 프라이어의 시제 논리와는 다른 구문을 가지며, 위치 논리에 특정한 실현 연산자를 사용하여 표현식을 특정 시간의 순간 또는 간격에 바인딩했다.^[3]^[4]

아서 프라이어는 자유 의지와 운명 예정설의 철학적 함의에 관심을 가지면서 시간 논리를 연구했다. 1954년 웰링턴에서 열린 컨퍼런스에서 처음 발표되었고,^[4] 1957년에는 ''시간과 양상''이라는 책을 출판하여 "미래의 언젠가"와 "과거의 언젠가"에 해당하는 두 개의 시간적 접속사(양상 연산자) F와 P를 가진 명제 양상 논리를 소개했다. 초기에는 시간을 선형적인 것으로 간주했지만, 1958년에 솔 크립키의 지적을 받아들여 "오컴주의자"와 "퍼스주의자"라고 불리는 두 가지 분기 시간 이론을 개발했다.^[2] 1967년에는 이 주제에 대한 연구를 집대성한 ''과거, 현재, 그리고 미래''를 출판했다.^[5]

한스 캄프는 1968년 박사 학위 논문에서 이원 시제 연산자 ''Since''와 ''Until''을 소개하고,^[7] 시간 논리를 1차 논리와 관련된 중요한 결과인 캄프의 정리를 제시했다.^[8]^[9]^[10]

아미르 프누엘리의 선형 시간 논리와 계산 트리 논리(CTL)는 형식적 검증의 초기 경쟁자였다. E. M. 클라크와 E. A. 에머슨은 CTL과 거의 동등한 형식을 제안했다. 에머슨과 레이는 모든 선형 시간 논리를 동일한 복잡성으로 결정될 수 있는 분기 시간 논리로 확장할 수 있음을 보여주었다.

2. 1. 아리스토텔레스와 고대 논리학

아리스토텔레스는 삼단 논법을 주로 연구했지만, 현대 시제 논리의 기원이 되는 개념도 탐구했다. 그는 불확실한 미래 사건을 다루면서, "내일 해전이 벌어질 것이다"와 같은 명제의 참/거짓 여부를 현재 시점에서 확정할 수 없다고 보았다.^[1] 이는 진리값이 시간에 따라 변할 수 있다는 시제 논리의 핵심 아이디어와 연결된다.

2. 2. 중세 및 근대 논리학

아리스토텔레스는 삼단 논법을 주로 연구했지만, 현대의 시제 논리와 같은 연구도 진행하여 일차 시제 이원 논리와 같은 형식을 부분적으로 검토했다. 특히 불확실한 미래의 사상을 다룰 때, 아리스토텔레스는 이치 의미론을 적용할 수 없다고 생각하여, 예를 들어 "내일, 해전이 발발할 것이다"와 같은 문장의 진위를 현시점에서 결정할 수 없다고 보았다.^[1]

이후 수천 년 동안 시제 논리는 큰 발전이 없었다. 19세기 찰스 샌더스 퍼스는 논리학이 아직 시간을 다룰 만큼 발전하지 못했다고 지적하며, 시제 논리의 필요성을 언급했다.^[2]

2. 3. 예르지 워스와 위치 논리 (1947)

20세기 전반, 폴란드 논리학자 예르지 워스는 최초로 시제 논리를 형식화했다.^[3] 1947년 저서 ''Podstawy Analizy Metodologicznej Kanonów Milla'' (''밀의 방법론적 분석의 기초'')에서 그는 밀의 정경의 형식화를 제시했다.^[3] 워스의 접근 방식에서 시간 요소가 강조되었다. 그는 자신의 목표를 달성하기 위해 시간적 기능을 형식화할 수 있는 수단을 제공할 수 있는 논리를 만들어야 했다. 이 논리는 워스의 주요 목표의 부산물로 볼 수 있었다.^[4] 비록 그것이 프레임워크로서 나중에 워스의 인식 논리 발명에 사용된 최초의 위치 논리였지만 말이다. 논리 자체는 양상 연산자를 사용하는 프라이어의 시제 논리와 매우 다른 구문을 가지고 있다. 워스의 논리 언어는 오히려 표현식을 진리값이 고려되는 특정 컨텍스트에 바인딩하는 위치 논리에 특정한 실현 연산자를 사용한다. 워스의 작업에서 이 고려된 컨텍스트는 단지 시간적이었고, 따라서 표현식은 특정 시간의 순간 또는 간격에 바인딩되었다.

워스의 논리는 1947년 석사 학위 논문 ''Podstawy Analizy Metodologicznej Kanonów Milla'' (''밀의 방법론적 분석의 기초'')로 출판되었다.^[11] 그의 철학적, 형식적 개념은 그의 지도 교수가 얀 우카시에비치의 제자인 예르지 스우페츠키였기 때문에 르비우-바르샤바 논리 학파의 개념을 계승한 것으로 볼 수 있다.

논리 언어는 ''Podstawy Analizy Metodologicznej Kanonów Milla''(밀의 방법론적 분석 기초)에서 처음 발표되었으며, 다음과 같이 구성되었다:^[3]

일계 논리 연산자 ‘¬’, ‘∧’, ‘∨’, ‘→’, ‘≡’, ‘∀’ 및 ‘∃’
실현 연산자 U
함수 기호 δ
명제 변수 p₁,p₂,p₃,...
시간 순간을 나타내는 변수 t₁,t₂,t₃,...
시간 간격을 나타내는 변수 n₁,n₂,n₃,...

항의 집합(S로 표시)은 다음과 같이 구성된다.

시간 순간 또는 간격을 나타내는 변수는 항이다.
만약 $\tau \in S$ 이고 $\epsilon$ 이 시간 간격 변수이면, $\delta(\tau, \epsilon) \in S$

수식의 집합(For로 표시)은 다음과 같이 구성된다:^[11]

모든 일계 논리 수식은 유효하다.
만약 $\tau \in S$ 이고 $\phi$ 가 명제 변수이면, $U_{\tau}(\phi) \in For$
만약 $\phi \in For$ 이면, $\neg \phi \in For$
만약 $\phi, \psi \in For$ 이고 $\circ \in \{\wedge, \vee, \rightarrow, \equiv\}$ 이면, $\phi \circ \psi \in For$
만약 $\phi \in For$ 이고 $Q \in \{\forall, \exists\}$ 이며 υ가 명제, 순간 또는 간격 변수이면, $Q_{\upsilon}\phi \in For$

#

U_{t_{1}}\neg p_{1} \equiv \neg U_{t_{1}} p_{1}

#

U_{t_{1}}(p_{1} \rightarrow p_{2}) \rightarrow (U_{t_{1}} p_{1} \rightarrow U_{t_{1}} p_{2})

#

U_{t_{1}}(p_{1} \rightarrow p_{2}) \rightarrow ((p_{2} \rightarrow p_{3}) \rightarrow (p_{1} \rightarrow p_{3}))

#

U_{t_{1}}(p_{1} \rightarrow (\neg p_{1} \rightarrow p_{2}))

#

U_{t_{1}}((\neg p_{1} \rightarrow p_{1}) \rightarrow p_{1})

#

\forall_{t_{1}}U_{t_{1}}p_{1} \rightarrow p_{1}

#

\forall_{t_{1}}\forall_{n_{1}}\exists_{t_{2}}\forall_{p_{1}}(U_{\delta(t_{1},n_{1})} p_{1} \equiv U_{t_{2}}p_{1})

#

\forall_{t_{1}}\forall_{n_{1}}\exists_{t_{2}}\forall_{p_{1}}(U_{\delta(t_{2},n_{1})} p_{1} \equiv U_{t_{1}}p_{1})

#

\forall_{t_{1}}\exists_{p_{1}}\forall_{t_{2}}(U_{t_{2}} p_{1}\equiv \forall_{p_{2}}(U_{t_{1}}p_{2} \equiv U_{t_{2}}p_{2}))

2. 4. 아서 프라이어와 시제 논리의 탄생 (1950년대)

아서 프라이어는 시제 논리의 창시자로 널리 알려져 있다. 그는 자유 의지와 예정설에 대한 철학적 문제에 관심을 가지면서 시제 논리를 연구하기 시작했다.^[4] 1953년에 처음 시간 논리를 형식화하는 것을 고려했고, 1954년 웰링턴에서 열린 컨퍼런스에서 연구 결과를 처음 발표했다.^[4] 1957년 저서 ''Time and Modality''에서 프라이어는 과거('P'), 미래('F'), 항상 과거('H'), 항상 미래('G')를 나타내는 네 가지 시제 연산자를 도입하여 현대적인 시제 논리 체계를 제시했다.

:

\begin{align}F &\equiv \lnot G\lnot \\P &\equiv \lnot H\lnot\end{align}

초기에는 시간을 선형적인 것으로 간주했으나, 솔 크립키의 지적을 받아들여 "오컴주의자"와 "퍼스주의자"라고 불리는 두 가지 분기 시간 논리(branching time logic)를 개발했다.^[2] 1958년과 1965년 사이에는 찰스 레너드 햄블린과 서신을 교환하며 햄블린 함의를 비롯한 여러 초기 발전을 이루었다.

2. 5. 햄블린, 캄프, 프누엘리 등의 기여 (1960년대-현재)

한스 캄프는 1968년 박사 학위 논문에서 이원 시제 연산자 ''Since''와 ''Until''을 도입했다.^[7] 이 논문에는 시제 논리를 1차 논리와 관련시키는 중요한 결과인 캄프의 정리가 포함되어 있다.^[8]^[9]^[10]

형식 검증 분야에서는 아미르 프누엘리의 선형 시간 논리(LTL)와 계산 트리 논리(CTL)가 경쟁 관계로 발전했다. CTL은 모르데차이 벤-아리, 조하르 마나, 아미르 프누엘리가 제안한 분기 시간 논리의 일종이다. CTL과 거의 동등한 형식은 E. M. 클라크와 E. A. 에머슨에 의해 동시에 제안되었다. 분기 시간 논리가 선형 시간 논리보다 더 효율적으로 결정될 수 있다는 주장이 있었지만, 에머슨과 레이는 모든 선형 시간 논리를 동일한 복잡도로 결정될 수 있는 분기 시간 논리로 확장할 수 있음을 보여주었다.

3. 주요 개념 및 연산자

시간 논리는 시간에 따라 진리값이 변하는 진술을 다루는 논리 체계이다. "나는 배가 고프다"라는 문장은 시간에 따라 참일 수도, 거짓일 수도 있지만, 동시에 참과 거짓일 수는 없다. 이는 진리값이 시간에 따라 변하지 않는 비시간 논리와 대조된다.

시간 논리는 타임라인에 대해 추론하는 능력을 가지며, "선형 시간" 논리는 단일 타임라인에 대한 추론으로 제한된다. 반면, 분기 시간 논리는 여러 타임라인에 대해 추론할 수 있어 예측 불가능한 상황을 다룰 수 있다. 예를 들어, "내가 영원히 배고픔을 유지할 가능성이 있다"와 "결국 더 이상 배고프지 않을 가능성이 있다"는 두 진술은 미래를 알 수 없을 때 모두 참일 수 있다.

아서 프라이어가 제시한 명제 시제 논리는 다음과 같은 네 가지 양상 연산자를 사용한다.^[16]

'''P''': "그것은 ~였다..." (P는 "과거"를 의미한다)
'''F''': "그것은 ~일 것이다..." (F는 "미래"를 의미한다)
'''G''': "그것은 항상 ~일 것이다..."
'''H''': "그것은 항상 ~였다..."

이 연산자들은 다음과 같이 서로 정의될 수 있다.

:

\begin{align}F &\equiv \lnot G\lnot \\P &\equiv \lnot H\lnot\end{align}

시간 논리의 최소 구문은 BNF 문법으로 다음과 같이 표현된다.

:

\phi ::= a \;|\; \bot \;|\; \lnot\phi \;|\; \phi\lor\phi \;|\; G\phi \;|\; H\phi

여기서 ''a''는 원자 공식을 의미한다.^[14]

크립키 모델은 시간 논리 문장의 진리성을 평가하는 데 사용된다. 이진 관계를 가진 집합은 '''프레임'''이라고 하며, '''모델'''은 프레임과 각 원자 공식, 시간 값에 대한 진리값을 할당하는 함수로 구성된다.^[15]


명제	...는 다음 경우에만 참입니다.
⊨[]	(,)=true
⊨¬[]	not ⊨[]
⊨(∧)[]	⊨[] 그리고 ⊨[]
⊨(∨)[]	⊨[] 또는 ⊨[]
⊨(→)[]	⊨[] if ⊨[]
⊨G[]	⊨[] for all with <
⊨H[]	⊨[] for all with <

Burgess는 관계 <에 대한 가정 없이 의미 있는 추론을 가능하게 하는 논리를 제시했다.^[16]

시제 논리에서는 논리 연산과 양상 연산자 두 종류의 연산자를 사용한다. 논리 연산자는 일반적인 진리 함수 연산자( $\neg,\lor,\land,\rightarrow$ )이다.

3. 1. 기본 시제 연산자

아서 프라이어가 1950년대에 처음 도입한 시제 논리 체계는 일반적인 1차 논리 연산자에 더하여 다음 4가지 양상 연산자를 사용한다.^[16]

'''P''' a: "과거의 어떤 시점에 a 라는 일이 있었다"
'''F''' a: "미래의 어떤 시점에 a 라는 일이 있을 것이다"
'''G''' a: "미래의 모든 시점에 a 라는 일이 있을 것이다"
'''H''' a: "과거의 모든 시점에 a 라는 일이 있었다"

이 연산자들은 서로 정의될 수 있는데, 예를 들면 다음과 같다.^[16]

:

\begin{align}F &\equiv \lnot G\lnot \\P &\equiv \lnot H\lnot\end{align}

3. 2. 추가 연산자와 확장

시간 논리에서는 기본 연산자 외에 다양한 시제 연산자가 연구되었다.^[18] 추가적인 연산자들은 다음과 같다.

텍스트	기호	정의	설명
이항 연산자
U	$\phi ~\mathcal{U}~ \psi$	$(B\,\mathcal{U}\,C)(\phi)= \ (\exists i:C(\phi_i)\land(\forall j$	Until(~까지): 현재 또는 미래 위치에서 $\psi$ 가 참이어야 하고, $\phi$ 는 해당 위치까지 참이어야 한다. 해당 위치에서 $\phi$ 는 더 이상 참일 필요가 없다.
R	$\phi ~\mathcal{R}~ \psi$	$(B\,\mathcal{R}\,C)(\phi)= \ (\forall i:C(\phi_i)\lor(\exists j$	Release(방출): $\phi$ 가 참인 첫 번째 위치까지(또는 그러한 위치가 존재하지 않는 경우 영원히) $\psi$ 가 참인 경우 $\phi$ 가 $\psi$ 를 방출한다.
단항 연산자
N	$\bigcirc \phi$	$\mathcal{N}B(\phi_i)=B(\phi_{i+1})$	Next(다음): $\phi$ 는 다음 상태에서 참이어야 한다. (X는 동의어로 사용된다.)
F	$\Diamond \phi$	$\mathcal{F}B(\phi)=(true\,\mathcal{U}\,B)(\phi)$	Future(미래): $\phi$ 는 결국 (후속 경로의 어딘가에서) 참이어야 한다.
G	$\Box \phi$	$\mathcal{G}B(\phi)=\neg\mathcal{F}\neg B(\phi)$	Globally(전역): $\phi$ 는 전체 후속 경로에서 참이어야 한다.
A	$\forall \phi$	$(\mathcal{A}B)(\psi)= \ (\forall \phi:\phi_0=\psi\to B(\phi))$	All(모든): $\phi$ 는 현재 상태에서 시작하는 모든 경로에서 참이어야 한다.
E	$\exists \phi$	$(\mathcal{E}B)(\psi)= \ (\exists \phi:\phi_0=\psi\land B(\phi))$	Exists(존재): 현재 상태에서 시작하여 $\phi$ 가 참인 경로가 적어도 하나 존재한다.

대체 기호:

연산자 '''R'''은 때때로 '''V'''로 표시된다.
연산자 '''W'''는 '약한 Until' 연산자이다: $f \mathbf W g$ 는 $f \mathbf U g \lor \mathbf G f$ 와 동일하다.

단항 연산자는

B(\phi)

가 잘 형성된 공식인 경우 잘 형성된 공식이다. 이항 연산자는

B(\phi)

와

C(\phi)

가 모두 잘 형성된 경우 잘 형성된 공식이다.

일부 논리에서는 일부 연산자를 표현할 수 없다. 예를 들어, '''N''' 연산자는 행동의 시간 논리에서는 표현할 수 없다.

4. 시제 논리의 종류

시간 논리에는 다음과 같은 종류가 있다.

위치 논리의 일부 시스템
선형 시간 논리(LTL)
계산 트리 논리(CTL)
구간 시간 논리(ITL)
작업의 시간 논리(TLA)
신호 시간 논리(STL)^[21]
타임스탬프 시간 논리(TTL)^[19]
속성 명세 언어(PSL)
CTL*
Hennessy–Milner 논리(HML)
모달 μ-미적분
메트릭 시간 논리(MTL)^[20]
메트릭 구간 시간 논리(MITL)^[21]
시간적 명제 시간 논리(TPTL)
절단된 선형 시간 논리(TLTL)^[22]
하이퍼 시간 논리(HyperLTL)^[23]

선형 시간 논리(LTL)는 분기 타임라인이 없는 시간 논리로, 시간을 하나의 선형적인 흐름으로 가정한다. 계산 트리 논리(CTL)는 시간을 여러 가능한 미래가 있는 트리 구조로 간주하는 분기 시간 논리이며, 에드먼드 클라크와 앨런 에머슨이 제안했다. CTL*는 CTL과 LTL을 일반화한 논리이다. 구간 시간 논리(ITL)는 시간 구간을 기본 단위로 다룬다.

시간 논리와 밀접하게 관련된 변형으로 "위상", "장소" 또는 "공간적 위치"를 기반으로 하는 양상 논리가 있다.^[24]^[25]

4. 1. 선형 시간 논리 (LTL)

선형 시간 논리(LTL)는 분기 타임라인이 없는 시간 논리로, 시간을 하나의 선형적인 흐름으로 가정한다. 프로그램의 동작을 시간에 따라 기술하고 검증하는 데 사용된다.^[24]^[25]

시상 논리는 항상 시계열에 대해 판단하는 능력을 가진다. 선형 시간 논리는 이러한 종류의 추론에 한정되어 있다.

시상 논리에서는 논리 연산과 두 종류의 연산자를 사용한다. 논리 연산자는 일반적인 진리 함수 연산자(

\neg,\lor,\land,\rightarrow

)이다. 선형 시상 논리에서 사용되는 양상 연산자는 다음과 같다.

문자 표기	기호 표기	정의	설명
이항 연산
$\phi$ U $\psi$	$\phi ~\mathcal{U}~ \psi$	$\begin{matrix}(B\,\mathcal{U}\,C)(\phi)= \\ (\exists i:C(\phi_i)\land(\forall j$	Until: $\psi$ 는 현재 또는 미래 위치에서 유효해야 하며, $\phi$ 는 그 이전 위치까지 유효해야 한다. 해당 위치에서 $\phi$ 를 유지할 필요는 없어진다.
$\phi$ R $\psi$	$\phi ~\mathcal{R}~ \psi$	$\begin{matrix}(B\,\mathcal{R}\,C)(\phi)= \\ (\forall i:C(\phi_i)\lor(\exists j$	Release: $\phi$ 가 참이 되는 첫 번째 위치까지 $\psi$ 가 참이면 (또는 그러한 위치가 없으면 영구히), $\phi$ 는 $\psi$ 를 해제한다.
단항 연산
N $\phi$	$\circ \phi$	$\mathcal{N}B(\phi_i)=B(\phi_{i+1})$	Next: $\phi$ 는 다음 상태에서 유효해야 한다. (X는 동의어로 사용)
F $\phi$	$\Diamond \phi$	$\mathcal{F}B(\phi)=(true\,\mathcal{U}\,B)(\phi)$	Finally: $\phi$ 는 결국 유효해져야 한다. (미래의 어느 시점에서)
G $\phi$	$\Box \phi$	$\mathcal{G}B(\phi)=\neg\mathcal{F}\neg B(\phi)$	Globally: $\phi$ 는 그 이후로 계속 유효해야 한다.

연산자 '''R'''은 '''V'''로 표기될 수 있다.
연산자 '''W'''는 ''weak until''을 의미한다. $f W g$ 는 $f U g \lor G f$ 와 동일하다.

B(

\phi

)가 논리식(wff)이면, 모든 단항 연산자는 논리식이다. B(

\phi

)와 C(

\phi

)가 논리식이면 모든 이항 연산자는 논리식이다.

4. 2. 분기 시간 논리 (CTL, CTL*)

계산 트리 논리(CTL)는 시간을 여러 가능한 미래가 있는 트리 구조로 간주하는 분기 시간 논리이다. 에드먼드 클라크와 앨런 에머슨이 제안했으며, 선형 시간 논리(LTL)보다 표현력이 강하다. CTL*는 CTL과 LTL을 일반화한 논리이다.

시간 논리에서는 두 종류의 연산자를 사용한다. 논리 연산과 양상 연산자이다. 논리 연산자는 일반적인 진리 함수 연산자(

\neg,\lor,\land,\rightarrow

)이다. 선형 시간 논리나 계산 트리 논리에서 사용되는 양상 연산자는 다음과 같다.

문자 표기	기호 표기	정의	설명
단항 연산
A $\phi$	$\forall \phi$	$\begin{matrix}(\mathcal{A}B)(\psi)= \\ (\forall \phi:\phi_0=\psi\to B(\phi))\end{matrix}$	All: $\phi$ 는 현재 상태에서 발생하는 모든 경로에서 유효해야 한다.
E $\phi$	$\exists \phi$	$\begin{matrix}(\mathcal{E}B)(\psi)= \\ (\exists \phi:\phi_0=\psi\land B(\phi))\end{matrix}$	Exists: 현재 상태에서 발생하는 경로 중 적어도 하나에서 $\phi$ 가 유효한 것이 있다.

B( $\phi$ )가 논리식(wff)이면, 모든 단항 연산자는 논리식이다.

4. 3. 구간 시간 논리 (ITL)

구간 시간 논리(ITL)는 시간 구간(interval)을 기본 단위로 다루는 시제 논리이다.

4. 4. 기타 시제 논리

위치 논리의 일부 시스템, 선형 시간 논리(LTL), 계산 트리 논리(CTL), 구간 시간 논리(ITL), 작업의 시간 논리(TLA), 신호 시간 논리(STL)^[21], 타임스탬프 시간 논리(TTL)^[19], 속성 명세 언어(PSL), CTL*, Hennessy–Milner 논리(HML), 모달 μ-미적분, 메트릭 시간 논리(MTL)^[20], 메트릭 구간 시간 논리(MITL)^[21], 시간적 명제 시간 논리(TPTL), 절단된 선형 시간 논리(TLTL)^[22], 하이퍼 시간 논리(HyperLTL)^[23] 등이 연구되고 있다. 시간 논리와 밀접하게 관련된 변형으로 "위상", "장소" 또는 "공간적 위치"를 기반으로 하는 양상 논리가 있다.^[24]^[25]

5. 응용 분야

시간 논리는 다양한 분야에 응용된다.

구간 시상 논리
뮤 계산
헤네시-밀너 논리 (HML)
CTL*
계산 트리 논리 (CTL)
선형 시상 논리 (LTL)
Metric Interval Temporal Logic (MITL) ^[30]
Signal Temporal Logic (STL) ^[30]

시간 논리와 밀접하게 관련된 논리로는 토폴로지나 장소, 공간적 위치를 다루는 양상 논리가 있다.^[31]^[32]

프로그램 검증, 인공지능, 데이터베이스 분야에서 시간 논리가 사용되는 예시는 하위 섹션에 상세히 설명되어 있다.

5. 1. 프로그램 검증

시제 논리는 프로그램의 정확성을 검증하는 데 널리 사용된다. 특히 병행 프로그램이나 분산 시스템의 동작을 모델링하고 검증하는 데 유용하다.

5. 2. 인공지능

인공지능 분야에서 시제 논리는 시간적 추론, 계획, 에이전트 모델링 등에 활용된다.^[30]^[31]^[32]

5. 3. 데이터베이스

데이터베이스에서 시제 논리는 시간적 제약 조건(temporal constraint)을 표현하고 질의(query)를 처리하는 데 사용될 수 있다.

6. 한국의 시제 논리 연구 현황 및 전망

한국의 IT 산업 발전과 함께, 시제 논리는 소프트웨어 신뢰성 확보, 시스템 안전성 분석, 인공지능 개발 등 다양한 분야에서 중요한 역할을 할 것으로 기대된다. 특히 4차 산업혁명 시대에 발맞춰, 사이버-물리 시스템(CPS), 사물 인터넷(IoT), 스마트 팩토리 등 복잡한 시스템의 안전성과 신뢰성을 보장하는 데 시제 논리가 핵심적인 기술로 활용될 수 있을 것이다.

계산 트리 논리(CTL), 선형 시상 논리(LTL) 외에도, Hennessy-Milner logic|헤네시-밀너 논리^영어(HML), CTL*|CTL*^영어 등이 있다.^[30] 시상 논리와 밀접하게 관련된 논리로는, 토폴로지나 장소, 공간적 위치를 다루는 양상 논리가 있다.^[31]^[32]

참조

_[1] 서적 Vardi 2008, p. 153
_[2] 서적 Vardi 2008, p. 154
_[3] 간행물 Podstawy analizy metodologicznej kanonów Milla http://dlibra.umcs.l[...] nakł. Uniwersytetu Marii Curie-Skłodowskiej 1947
_[4] 간행물 The Significance of the Contributions of A.N.Prior and Jerzy Łoś in the Early History of Modern Temporal Logic https://vbn.aau.dk/e[...] 2019
_[5] 서적 Temporal logic: from ancient ideas to artificial intelligence Springer
_[6] 간행물 Topological Logic https://www.cambridg[...] 1969-01
_[7] 웹사이트 Temporal Logic (Stanford Encyclopedia of Philosophy) https://plato.stanfo[...] Plato.stanford.edu 2014-07-30
_[8] 서적 Modalities and Multimodalities https://books.google[...] Springer
_[9] 서적 Vardi 2008, p. 154
_[10] 서적 Reasoning Web. Semantic Technologies for Information Systems: 5th International Summer School 2009, Brixen-Bressanone, Italy, August 30 – September 4, 2009, Tutorial Lectures https://books.google[...] Springer
_[11] 간행물 Jerzy Łoś Positional Calculus and the Origin of Temporal Logic https://apcz.umk.pl/[...] 2019
_[12] 서적 Time and modality: the John Locke lectures for 1955–6, delivered at the University of Oxford The Clarendon Press
_[13] 웹사이트 An Introduction to Temporal Logics https://www.cas.mcma[...] 2004
_[14] 서적 The Stanford Encyclopedia of Philosophy https://plato.stanfo[...] Metaphysics Research Lab, Stanford University 2015
_[15] 서적 The continuum companion to philosophical logic A&C Black
_[16] 서적 Philosophical logic Princeton University Press
_[17] 서적 Philosophical logic Princeton University Press
_[18] 웹사이트 Temporal Logic http://plato.stanfor[...] 2020-02-07
_[19] 간행물 Timestamp Temporal Logic (TTL) for Testing the Timing of Cyber-Physical Systems
_[20] 간행물 "Specifying real-time properties with metric temporal logic" 1990
_[21] 간행물 "Monitoring temporal properties of continuous signals" 2004
_[22] 간행물 "Reinforcement learning with temporal logic rewards."
_[23] 서적 Principles of Security and Trust
_[24] 서적 Topics in Philosophical Logic
_[25] 서적 The Philosophy of Nicholas Rescher
_[26] 서적 Temporal logic: from ancient ideas to artificial intelligence Springer
_[27] URL http://plato.stanford.edu/entries/logic-temporal/M http://plato.stanfor[...]
_[28] 서적 Modalities and Multimodalities https://books.google[...] Springer
_[29] 서적 Reasoning Web. Semantic Technologies for Information Systems: 5th International Summer School 2009, Brixen-Bressanone, Italy, August 30 - September 4, 2009, Tutorial Lectures https://books.google[...] Springer
_[30] 문서 O. Maler, D. Nickovic, "Monitoring temporal properties of continuous signals", 2004
_[31] 문서 Nicholas Rescher, James Garson, "Topological Logic" in The Journal of Symbolic Logic, 33(4):537-548, December, 1968
_[32] 문서 Georg Henrik von Wright, "A Modal Logic of Place", in E. Sosa (Editor), pp. 65-73, "The Philosophy of Nicholas Rescher: Discussion and Replies", D. Reidel, Dordrecht, Holland, 1979

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com