논리학
어떤 가정에서 어떤 결론이 실제로 따라 나오는지 연구하는 학문.
논리학은 추론의 내용이 아니라 형식을 다룬다. 형식논리는 문장을 기호로 바꾸어, 결론이 따라 나오는지를 논증의 모양만으로 판정하고 기계적으로 확인할 수 있게 한다.
논리학 용어 사전
계산기와 안내서, 연습문제가 쓰는 모든 용어를 한곳에 정의했습니다.
용어를 찾아 기호를 확인하고, 예시를 계산기에서 열어 어떻게 작동하는지 보세요. 여기 실린 용어는 안내서에 처음 나올 때 강조 표시됩니다.
전체 62개 용어
기초 개념
명제
참이거나 거짓이며 둘 다일 수는 없는 진술.
명제는 정확히 하나의 진리값을 갖는 평서문이다. “비가 온다”는 명제이지만, 물음이나 명령은 명제가 아니다. 참이거나 거짓일 만한 내용이 없기 때문이다.
진리값
⊤ / ⊥명제가 가질 수 있는 두 값 중 하나: 참 또는 거짓.
고전 논리는 각 명제에 정확히 하나의 진리값을 준다. 기호로는 ⊤와 ⊥(또는 1과 0)이다. 진리표의 각 행은 변항에 값을 배정한 것이며, 그 배정에서 논리식이 갖는 값을 함께 보여 준다.
원자명제
안에 어떤 연결사도 들어 있지 않은 명제.
원자명제는 더 작은 명제로 쪼갤 수 없다. 부정도 연언도 다른 어떤 연결사도 들어 있지 않다. 나머지는 모두 복합명제로, 원자에서 조립되며 진리값도 원자들의 값으로 정해진다.
명제변항
임의의 명제를 대신하는 p나 A 같은 글자.
명제변항은 어떤 명제든 들어갈 수 있는 자리이다. 계산기는 한 글자를 변항으로 받아들여 진리표에 한 열씩 배정하고, 가능한 값의 조합마다 한 행을 만든다.
계산기에서p → q정형식
그 언어의 문법이 실제로 허용하는 기호열.
정형식은 규칙에 따라 만들어진다. 변항은 정형식이고, 더 작은 식을 연결사로 이은 것도 정형식이다. “p ∧ ∨ q”는 아니며, 그래서 계산기는 추측하지 않고 오류를 알린다.
해석
논리식의 모든 변항에 진리값을 한 번 배정한 것.
해석은 각 변항의 값을 정하고, 그로써 논리식 전체의 값을 확정한다. 변항이 n개인 식에는 2ⁿ개의 해석이 있으며, 그것이 곧 진리표의 행이다.
논증
결론을 뒷받침하려고 제시한 전제들의 묶음.
논증은 결론이 전제로부터 따라 나온다고 주장한다. 계산기에 귀결 기호로 적으면—앞에 전제, 뒤에 결론—전제가 참인데 결론이 거짓인 경우가 있는지 각 행이 검사된다.
계산기에서p → q, p ⊨ q전제
논증이 결론에 이르려고 받아들이는 진술.
전제는 논증의 출발점이다. 타당성은 모든 전제가 참인 곳마다 결론도 참인지만 묻는다. 전제가 실제로 참인지는 별개의 물음이며, 건전성이 더하는 부분이다.
계산기에서p → q, p ⊨ q결론
논증이 세우려고 하는 진술.
결론은 전제들이 뒷받침하려는 것이다. 계산기에서는 귀결 기호 뒤의 식이며, 전제를 참으로 만들면서 결론을 거짓으로 만드는 해석이 하나도 없을 때 그 논증은 타당하다.
계산기에서p → q, p ⊨ q논리 연결사
논리 연결사
더 단순한 명제로 복합명제를 만드는 기호.
¬, ∧, ∨, →, ↔ 같은 연결사는 명제들을 이어 더 큰 명제를 만들며, 그 진리값은 부분들의 값에만 달려 있다. 진리표가 기록하는 것이 바로 그 의존 관계이고, 입력 조합마다 한 행이 된다.
부정
¬진리값을 뒤집는다. ¬p는 p가 거짓일 때 참이다.
부정은 명제논리의 유일한 1항 연결사다. ¬p, ~p, !p로 쓰며 참을 거짓으로, 거짓을 참으로 바꾼다. 그래서 두 번 부정하면 원래 명제로 돌아온다.
계산기에서¬p연언
∧두 부분이 모두 참일 때만 참이다: p ∧ q.
연언은 두 부분(연언지)을 모두 주장한다. 진리표에서 정확히 한 행—두 연언지가 모두 참인 행—에서만 참이며, 그런 뜻에서 2항 연결사 가운데 가장 엄격하다.
계산기에서p ∧ q선언
∨적어도 한 부분이 참이면 참이다: p ∨ q.
논리학의 선언은 포괄적이다. p가 참일 때도, q가 참일 때도, 둘 다 참일 때도 p ∨ q는 참이다. 두 부분이 다를 때만 참인 배타적 “또는”은 별개의 연결사다.
계산기에서p ∨ q배타적 선언
⊕두 명제 가운데 정확히 하나가 참일 때 참이다.
배타적 선언은 ⊕ 또는 XOR로 쓰며, 두 부분이 다르면 성립하고 같으면 성립하지 않는다. 쌍조건의 부정이며 (p ∨ q) ∧ ¬(p ∧ q)로도 쓸 수 있다.
계산기에서(p ∨ q) ∧ ¬(p ∧ q)조건문
→p → q. p가 참이고 q가 거짓일 때만 거짓이다.
실질 조건문은 “전건이 참이면서 후건이 거짓인 일은 없다”는 말 이상을 하지 않으므로, 전건이 거짓이면 자동으로 성립한다. p → q가 ¬p ∨ q와 동치인 까닭이다.
계산기에서p → q쌍조건문
↔p ↔ q. 두 부분의 진리값이 같을 때 참이다.
쌍조건문은 서로를 조건 삼아 양쪽을 주장한다. 두 부분이 모두 참일 때와 모두 거짓일 때 참이다. 항진식인 쌍조건문은 곧 하나의 논리적 동치를 진술한 것이다.
계산기에서p ↔ q전건
조건문의 “만약” 부분 — p → q의 p.
전건은 조건문이 의존하는 조건이다. 전건이 거짓이면 후건이 무엇이든 조건문 전체가 참이 되며, → 의 진리표에서 뜻밖으로 보이는 대목은 대개 여기서 나온다.
계산기에서p → q후건
조건문의 “그러면” 부분 — p → q의 q.
후건은 전건이 성립하면 따라 나온다고 조건문이 말하는 바다. 후건이 참이면 조건문은 참이 되지만 전건이 참이 되지는 않는다. 그렇게 추론하는 것은 형식적 오류다.
계산기에서p → q역
두 부분을 맞바꾼 조건문: q → p.
p → q의 역은 q → p이며 둘은 동치가 아니다. 계산기는 한쪽은 성립하고 다른 쪽은 성립하지 않는 행을 찾아낸다. 둘을 서로 바꿔 써도 된다고 여기는 것이 후건 긍정이다.
계산기에서q → p대우
¬q → ¬p. 언제나 p → q와 같은 진리값을 갖는다.
대우는 조건문의 두 부분을 모두 부정하고 자리를 바꾼다. 역과 달리 원래 식과 실제로 동치이며, 그래서 수학에서 대우를 이용한 증명이 정당하다.
계산기에서(p → q) ≡ (¬q → ¬p)부정 논리곱
↑연언의 부정. 두 입력이 모두 참일 때만 빼고 참이다.
부정 논리곱은 ↑로 쓰며 ¬(p ∧ q)이다. 함수적으로 완전해서 다른 어떤 연결사도 이것만으로 만들 수 있고, 그래서 디지털 회로 설계의 일꾼 노릇을 한다.
계산기에서¬(p ∧ q)부정 논리합
↓선언의 부정. 두 입력이 모두 거짓일 때만 참이다.
부정 논리합은 ↓로 쓰며 ¬(p ∨ q)이다. NAND처럼 그 자체로 함수적으로 완전하므로, 회로를 NOR 게이트만으로 전부 구성할 수도 있다.
계산기에서¬(p ∨ q)연산자 우선순위
괄호가 없을 때 어떤 연결사가 먼저 묶이는지.
부정이 가장 강하게 묶고, 다음이 연언, 선언, 조건문, 마지막이 쌍조건문이다. 그래서 ¬p ∧ q ∨ r는 ((¬p) ∧ q) ∨ r로 읽는다. 의도한 읽기가 다르면 괄호로 순서를 바꾼다.
계산기에서¬p ∧ q ∨ r참과 귀결
진리표
값 배정마다 한 행씩, 그 행에서의 논리식 값을 적은 표.
진리표는 변항이 n개인 식의 2ⁿ개 해석을 모두 나열하고 각 해석에서의 값을 계산한다. 남김없이 훑기 때문에 동치, 타당성, 충족가능성 등 명제논리의 의미론적 물음을 모두 해결한다.
계산기에서p → q항진식
⊤모든 해석에서 참인 논리식.
항진식은 진리표의 모든 행에서 참이므로 세계에 대해 아무것도 말하지 않는다. p가 무엇이든 p ∨ ¬p는 참이다. 두 식이 동치인 것은 그 사이의 쌍조건문이 항진식일 때뿐이다.
계산기에서p ∨ ¬p모순식
⊥모든 해석에서 거짓인 논리식.
p ∧ ¬p 같은 모순식은 진리표의 모든 행에서 거짓이다. 가정들의 묶음에서 모순을 이끌어내면 그 가정이 모두 성립할 수는 없음이 드러난다. 귀류법의 원동력이다.
계산기에서p ∧ ¬p우연식
어떤 해석에서는 참이고 다른 해석에서는 거짓인 논리식.
우연식은 항진식도 모순식도 아니다. 진리표에 참인 행과 거짓인 행이 적어도 하나씩 있다. 사람들이 실제로 쓰는 식은 대개 우연식이고, 그래서 정보를 담는다.
계산기에서p ∧ q충족가능성
논리식을 참으로 만드는 해석이 있는지 여부.
진리표에서 참인 행이 적어도 하나 있으면 그 식은 충족가능하며, 그 행이 곧 모델이다. 충족가능성 판정은 SAT 해결기의 중심 문제이고, 그를 통해 자동 추론의 큰 부분을 떠받친다.
계산기에서p ∧ (p → q)논리적 동치
≡진리표가 똑같은 두 논리식.
동치인 식은 모든 해석에서 값이 같으므로, 뜻을 바꾸지 않고 어디서든 서로 바꿔 쓸 수 있다. 두 식 사이에 등호를 넣으면 계산기가 두 열을 행마다 비교한다.
계산기에서(p → q) ≡ (¬p ∨ q)논리적 귀결
⊨전제가 성립하는 모든 해석에서 결론도 성립함.
Γ ⊨ φ로 쓰는 논리적 귀결은 타당한 논증이 주장하는 바로 그것이다. 확인은 반례 찾기로 한다. 모든 전제를 참으로, 결론을 거짓으로 만드는 해석이 없다면 귀결 관계가 성립한다.
계산기에서p → q, p ⊨ q타당성
전제를 참으로, 결론을 거짓으로 만드는 해석이 없음.
타당성은 사실이 아니라 논증의 형식에 관한 성질이다. 타당한 논증도 거짓 전제와 거짓 결론을 가질 수 있다. 가질 수 없는 것은 참인 전제와 거짓 결론의 조합이다.
계산기에서p → q, p ⊨ q건전성
전제까지 실제로 참인 타당한 논증.
건전성은 형식적 주장에 사실적 주장을 더한다. 논증이 타당하고 그 전제가 참이라는 것이다. 앞의 절반은 논리만으로 정해지고, 뒤의 절반은 논증이 다루는 주제의 몫이다.
반례 모델
전제를 참으로, 결론을 거짓으로 만드는 해석.
반례 모델은 논증이 부당함을 보여 준다. 한 행이면 충분하다. 계산기는 찾아낸 행을 보여 주므로, “이건 따라 나오지 않는다”는 말이 손으로 확인할 수 있는 구체적 배정이 된다.
계산기에서p → q ⊨ q → p무모순성
집합의 모든 진술을 동시에 참으로 만드는 해석이 있음.
전제들의 집합은 그것들이 함께 성립할 수 있을 때 무모순이다. 모순된 전제에서는 무엇이든 따라 나오므로, 그 위에 세운 논증은 형식적으로 타당하되 아무 값어치가 없다.
계산기에서p → q, ¬q ⊨ ¬p정규형
리터럴
변항이거나 그 부정, 예컨대 p나 ¬p.
리터럴은 정규형의 원자다. 절은 리터럴의 선언이고, 최소항은 리터럴의 연언이다. 변항이 그대로 나오면 양의 리터럴, 부정되어 있으면 음의 리터럴이다.
계산기에서¬p절
리터럴의 선언, 예컨대 p ∨ ¬q ∨ r.
절은 연언 정규형을 이루는 괄호 묶음 가운데 하나다. 연언은 모든 부분이 참일 때만 참이므로, CNF 식은 그 모든 절이 성립할 때 정확히 성립한다.
계산기에서p ∨ ¬q ∨ r선언 정규형
AND들의 OR, 곧 리터럴 연언들의 선언.
모든 식에는 선언 정규형이 있고, 진리표에서 곧바로 읽어낼 수 있다. 참인 행마다 연언을 하나씩 만들어 ∨로 잇는다. 계산기는 리터럴을 줄인 최소 DNF도 함께 보여 준다.
계산기에서(p ∧ q) ∨ (¬p ∧ r)연언 정규형
OR들의 AND, 곧 절들의 연언.
연언 정규형은 진리표에서 거짓인 행마다 절을 하나씩 읽어 만든다. SAT 해결기가 기대하는 입력 형식이며, 그래서 CNF 변환은 자동 추론의 일상적인 단계다.
계산기에서(p ∨ q) ∧ (¬p ∨ r)최소항
진리표의 정확히 한 행을 지목하는 연언.
최소항은 각 변항을 부정하거나 하지 않은 채 한 번씩 담으므로, 정확히 하나의 해석만 그것을 만족한다. 참인 행들의 최소항을 모아 ∨로 이으면 그 식의 선언 정규형이 된다.
계산기에서p ∧ ¬q ∧ r최대항
진리표의 정확히 한 행을 배제하는 선언.
최대항은 각 변항을 한 번씩 담으며 오직 하나의 해석에서만 거짓이다. 거짓인 행마다 최대항을 취해 ∧로 이으면 그 식의 연언 정규형이 된다.
계산기에서p ∨ ¬q ∨ r드 모르간 법칙
부정은 ∧를 ∨로, ∨를 ∧로 바꾼다: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
드 모르간 법칙은 부정을 연언이나 선언 안쪽으로 밀어 넣으면서 연결사를 뒤집는다. 식을 정규형으로 몰아가는 방법이자, 코드와 회로에서 부정을 간단히 하는 방법이다.
계산기에서¬(p ∧ q) ≡ ¬p ∨ ¬q이중부정
두 번 부정하면 원래로 돌아온다: ¬¬p ≡ p.
고전 논리에서 이중부정은 양방향으로 성립하므로 ¬¬p와 p는 언제나 바꿔 쓸 수 있다. 직관주의 논리는 p에서 ¬¬p로 가는 방향만 남기며, 두 체계는 그 지점에서 갈라진다.
계산기에서¬¬p ≡ p불 대수와 회로
불 대수
두 값의 대수. 연산은 ∧, ∨, ¬.
불 대수는 명제논리를 0과 1 위의 산술로 적은 것이다. 교환·분배·흡수 법칙과 드 모르간 법칙으로 식을 고쳐 쓰고 간단히 할 수 있다. 디지털 회로는 이 수학으로 설계된다.
계산기에서(p ∧ q) ∨ (p ∧ ¬q) ≡ p카르노 맵
간단히 하기가 눈에 보이도록 배열한 진리표 격자.
카르노 맵은 이웃한 칸이 변항 하나만 다르도록 행을 배열하며, 가장자리는 서로 이어진다. K맵, K-map, kmap으로도 쓴다. 크기가 1, 2, 4, 8인 인접한 1들의 직사각형 묶음이 곧 최소 표현식의 항으로 읽힌다.
계산기에서(p ∧ q) ∨ (p ∧ ¬r)주 함의항
맵에서 더는 키울 수 없는 묶음.
함의항은 식을 참이 되게 강제하는 리터럴 연언이며, 어떤 리터럴을 빼도 그 성질을 잃는다면 주 함의항이다. 카르노 맵에서 주 함의항은 1들로 이루어진 극대 직사각형이다.
필수 주 함의항
어떤 1을 덮는 유일한 주 함의항.
맵의 어떤 1이 극대 묶음 하나에만 속한다면 그 묶음은 모든 최소 덮개에 반드시 들어가므로 먼저 고른다. 남는 부분이 실제로 탐색해야 할 덮개다.
논리 게이트
입력에 대해 연결사 하나를 계산하는 회로 소자.
AND, OR, NOT, NAND, NOR, XOR 게이트는 연결사의 하드웨어 대응물이다. 식과 회로는 같은 대상을 두 번 그린 것이며, 그래서 계산기는 식을 게이트 회로도로 보여 줄 수 있다.
계산기에서(p ∧ q) ∨ ¬r증명과 추론
추론 규칙
이미 얻은 식에서 새 식으로 넘어가는 허용된 한 걸음.
추론 규칙은 전건 긍정 같은 형태로, 알맞은 모양의 식이 있으면 언제든 적용할 수 있다. 증명 체계는 그런 규칙 몇 개로 세워지며, 실제로 따라 나오는 결론만 도출되도록 고른다.
전건 긍정
p → q와 p에서 q를 얻는다.
전건 긍정은 조건문의 기본 규칙이다. 조건문과 그 전건이 있으면 후건이 따라 나온다. 타당성은 진리표에서 바로 보인다. 두 전제가 모두 참인 유일한 행에서 결론도 참이다.
계산기에서p → q, p ⊨ q후건 부정
p → q와 ¬q에서 ¬p를 얻는다.
후건 부정은 조건문을 거꾸로 따라간다. 후건이 성립하지 않으면 전건도 성립했을 수 없다. 대우가 작동하는 것이며, 예측을 시험해 가설을 반박하는 모든 논증의 형태이기도 하다.
계산기에서p → q, ¬q ⊨ ¬p가언 삼단논법
p → q와 q → r에서 p → r를 얻는다.
가언 삼단논법은 조건문들을 사슬처럼 잇는다. 긴 도출이 가능한 것도 이 덕분이며, 고리 하나하나가 어떤 전제도 주장하지 않은 채 논증을 한 걸음씩 밀고 나간다.
계산기에서p → q, q → r ⊨ p → r선언 삼단논법
p ∨ q와 ¬p에서 q를 얻는다.
선언 삼단논법은 배제된 선택지를 지운다. 두 가능성 중 하나가 성립하는데 첫째가 아니라면 둘째가 성립해야 한다. 소거법 추론의 바탕이 되는 규칙이다.
계산기에서p ∨ q, ¬p ⊨ q자연 연역
추론 규칙을 한 걸음씩 적용해 결론을 증명하는 방식.
자연 연역은 연결사마다 도입 규칙과 제거 규칙을 두어 전제에서 결론을 이끌며, 임시 가정을 세웠다가 나중에 해소하도록 허용한다. 진리표가 확인하는 바를 모든 행을 훑지 않고 증명한다.
귀류법
반대를 가정해 모순을 이끌고 원래 주장을 결론짓는다.
φ를 증명하려면 ¬φ를 가정하고 ψ ∧ ¬ψ 꼴의 것을 이끌어낸다. 모순을 참으로 만드는 해석은 없으므로 가정은 성립할 수 없고 φ가 따라 나온다. 무리수성과 무한성 증명이 대개 이런 식이다.
계산기에서p ∧ ¬p후건 긍정
p → q와 q에서 p로 가는 부당한 한 걸음.
후건이 참이라고 해서 전건이 세워지지는 않는다. 다른 무언가가 그것을 일으켰을 수도 있다. 계산기는 반례 모델(p 거짓, q 참)을 보여 주며, 그 행이 전건 긍정과 갈라지는 지점이다.
계산기에서p → q, q ⊨ p전건 부정
p → q와 ¬p에서 ¬q로 가는 부당한 한 걸음.
조건문은 전건이 성립하지 않을 때 무슨 일이 벌어지는지 아무 말도 하지 않으므로, 전건을 물리쳐도 후건은 열린 채로 남는다. 반례 모델은 p가 거짓이고 q가 참인 행이다.
계산기에서p → q, ¬p ⊨ ¬q명제논리 너머
술어논리
명제 안쪽의 대상과 성질까지 들여다보는 논리.
술어논리는 술어와 항, 양화사를 더한다. 그래서 “2보다 큰 모든 소수는 홀수다”가 글자 하나가 아니라 하나의 식이 된다. 명제논리보다 표현력이 엄밀히 크며, 어떤 진리표로도 판정할 수 없다.
양화사
∀ / ∃술어가 몇 개의 대상에 성립하는지 말하는 기호.
고전적인 두 양화사는 ∀(모든)와 ∃(적어도 하나)이며, 각각은 몸통을 부정한 다른 하나의 부정이다. 양화사가 묶는 변항이야말로 술어논리를 명제논리와 가르는 지점이다.
전칭 양화사
∀∀x φ: 영역의 모든 대상에 대해 φ가 성립한다.
전칭 주장은 반례 하나로 반박되며, 빈 영역에서는 공허하게 성립한다. ∀x φ는 ¬∃x ¬φ와 동치이고, 이는 양화사에서의 드 모르간 법칙에 해당한다.
존재 양화사
∃∃x φ: 영역의 적어도 한 대상에 대해 φ가 성립한다.
존재 주장은 증인 하나를 제시하면 세워진다. ∃x φ는 ¬∀x ¬φ와 동치이므로, 두 양화사는 서로와 부정으로부터 정의될 수 있다.
양상논리
□ / ◇“필연적으로”(□)와 “가능적으로”(◇)를 더한 논리.
양상논리는 식을 하나의 해석이 아니라 가능세계에서 평가한다. 접근 가능한 모든 세계에서 φ가 성립하면 □φ, 어떤 세계에서 성립하면 ◇φ가 성립한다. “접근 가능”의 뜻을 달리하면 서로 다른 양상 체계가 나온다.