모양이 다른 두 식이 언제 논리적으로 동치인가요?

이번에는 두 식을 같은 경우에 넣어 보며 전체의 값이 같은지 확인합니다. “연필도 없고 지우개도 없다”와 “연필이나 지우개가 있다는 것은 아니다”를 떠올려 보세요. 말의 순서는 다르지만, 두 말이 참이 되는 상자의 상태는 같을까요?

좋습니다. 이제 그 경우뿐 아니라 다른 구성도 살펴봅시다. 모든 진리값 배정에서 두 식의 값이 같으면 논리적으로 동치라고 합니다. 이 편에서는 “서로 동치입니다”를 짧게 표시할 때 ≡를 쓰겠습니다. 예를 들어 ¬(p∨q) ≡ ¬p∧¬q입니다.

맞습니다. 또 여기서 같다는 것은 참이 되는 조건과 거짓이 되는 조건이 같다는 뜻입니다. 우리말의 강조·말투·설명 목적까지 모두 같다는 주장은 아닙니다. 오늘도 참과 거짓 두 값을 쓰는 고전 명제논리 안에서 살펴봅니다.

그 경우의 값이 같다는 것만 확인했습니다. 연필만 있고 지우개는 없는 경우로 바꾸어 볼까요?

이렇게 값이 다른 배정이 하나라도 있으면 동치가 아닙니다. 두 식이 항상 참이어야 동치인 것도 아닙니다. 모두 거짓인 줄에서도 두 식의 값이 서로 같으면 그 줄에서는 일치한 것입니다.

처음의 ¬(p∨q)와 ¬p∧¬q를 네 경우에서 직접 계산해 봅시다. 첫째 식은 먼저 p∨q를 계산하고 그 전체를 부정합니다.

네 줄에서 마지막 두 값이 모두 같습니다. 연필 또는 지우개가 있다는 주장이 거짓이려면 두 종류 모두 없어야 합니다. 그래서 전체의 부정을 풀 때 ∨가 ∧로 바뀝니다. 이것이 드모르간 법칙의 한 형태입니다.

연필만 있는 상자를 보세요. 두 물건이 모두 있다는 말은 거짓이므로 ¬(p∧q)는 참입니다. 하지만 연필은 있으므로 둘 다 없다는 말은 거짓입니다.

그렇습니다. 그래서 ¬(p∧q) ≡ ¬p∨¬q입니다. 드모르간 법칙의 다른 형태이지요. 두 법칙은 ∧와 ∨를 서로 바꾸면서 각각을 부정합니다. 어느 방향으로 바꾸어도 진리조건이 같습니다.

p가 참일 때 ¬p와 ¬¬p의 값은 각각 무엇인가요?

따라서 ¬¬p ≡ p입니다. 이중 부정은 글자 하나에만 적용하는 규칙이 아닙니다. ¬¬(p∨q)에서는 p∨q 전체를 두 번 부정하므로 p∨q와 동치입니다.

그 두 부정은 서로 다른 부분에 붙어 있습니다. 한 식을 연달아 두 번 부정한 모양이 아닙니다. 연필과 지우개가 모두 없는 경우에 ¬p∧¬q는 참이지만 p∧q는 거짓이지요. 기호의 개수가 아니라 부정하는 범위를 봅니다.

말투에서 바로 결론내리지 말고, 고전 명제논리에서 정한 두 연결사의 진릿값을 비교해 봅시다. p→q가 거짓인 경우는 언제였나요?

나머지 배정에서도 두 값이 일치하므로 p→q ≡ ¬p∨q입니다. 반대 방향으로 ¬p∨q를 조건문으로 바꿀 수도 있습니다.

p→q의 대우는 ¬q→¬p입니다. 먼저 앞뒤를 바꾼 다음 각각을 부정합니다. 왜 동치인지 하나씩 확인해 봅시다.

그래서 p→q ≡ ¬q→¬p입니다. q→p는 역이며 일반적으로 원래 조건문과 동치가 아닙니다. 지우개는 있고 연필은 없는 경우에 원래 조건문은 참, 역은 거짓이지요.

이 편에서 쓰는 용도를 구별하겠습니다. p↔q는 p와 q를 묶은 하나의 식입니다. 주어진 배정에서 참일 수도 거짓일 수도 있습니다. p ≡ q라는 표시는 p와 q가 모든 배정에서 같은 값을 갖는다는 주장인데, 그 주장은 성립하지 않습니다.

맞습니다. 두 식을 A와 B라고 부르면, A와 B가 동치라는 것은 A↔B가 항진식이라는 것과 연결됩니다. 여기서 A·B는 특정 물건의 새 이름이 아니라, 비교할 식 전체를 임시로 부르는 이름입니다.

따라서 p↔q ≡ (p→q)∧(q→p)입니다. 두 방향 가운데 하나만 남기면 같은 조건이 아닙니다. 예를 들어 연필은 없고 지우개는 있을 때 p→q는 참이지만 p↔q는 거짓입니다.

p∧q와 q∧p를 읽어 볼까요?

이처럼 ∧끼리, 또는 ∨끼리 연결한 두 부분은 순서를 바꾸어도 동치입니다. 이를 교환법칙이라고 합니다. 또 같은 연결사로 세 부분을 묶을 때에는 (p∧q)∧r과 p∧(q∧r), (p∨q)∨r과 p∨(q∨r)가 각각 동치입니다. 이를 결합법칙이라고 합니다.

서로 다른 연결사를 섞었을 때에는 그렇게 할 수 없습니다. p∧(q∨r)는 연필이 반드시 있어야 합니다. 반면 (p∧q)∨r은 공책만 있는 경우에도 참입니다.

뜻부터 읽어 보세요. 연필은 있어야 하고, 지우개와 공책 가운데 적어도 한 종류가 있어야 합니다. 이를 “연필과 지우개가 있거나, 연필과 공책이 있다”로 나누어 적을 수 있습니다. (p∧q)∨(p∧r)이지요.

모든 행에서 같습니다. 이것이 분배법칙의 한 형태입니다. 다른 형태인 p∨(q∧r) ≡ (p∨q)∧(p∨r)도 성립합니다. p가 참이면 양쪽 모두 참입니다. p가 거짓이면 양쪽 모두 q와 r이 함께 참이어야 합니다.

이번에는 r∧(p→q)를 봅시다. 공책이 있고, 연필이 있으면 지우개가 있다는 조건도 성립한다고 읽습니다. 괄호 안 p→q를 어떻게 바꿀 수 있나요?

맞습니다. 어느 배정에서도 바꾸기 전후의 괄호 안 값이 같으므로, r과 ∧로 묶은 전체 값도 같습니다. 진리함수적 식 안의 한 부분을 동치인 식으로 교체하면 전체도 동치입니다.

각 단계가 모든 배정에서 값을 보존하므로 출발 식과 마지막 식도 동치입니다. 조건문을 거짓으로 만드는 유일한 경우가 “전건은 참, 후건은 거짓”이라는 사실과 정확히 이어집니다.

p∧q에서 p를 결론으로 얻는 추론은 타당합니다. 하지만 두 식은 동치가 아닙니다. 연필만 있고 지우개는 없을 때 p는 참이지만 p∧q는 거짓입니다.

그렇습니다. 두 식이 동치이면 한쪽에서 다른 쪽으로, 반대쪽에서도 처음 식으로 타당하게 추론할 수 있습니다. 그러나 한 방향의 타당한 추론만으로 동치를 보장할 수는 없습니다.

표의 A·B는 비교하는 식 전체의 이름입니다. 다음 편에서는 이 가운데 두 번째 관계를 이용해, 전제에서 결론까지 한 줄씩 추론하는 방법을 배웁니다.

한 줄마다 바꾼 부분과 이유를 하나씩 적어 보세요. ¬(p∨(q∧r))를 예로 들어 보겠습니다. 먼저 이 말은 “연필이 있거나 지우개와 공책이 모두 있다는 것은 아니다”입니다.

좋습니다. 값이 다른 경우를 찾지 못했다고 곧바로 동치라고 결론내리지는 마세요. 모든 배정이 있는 진리표를 확인하거나, 동치를 보장하는 변형을 빠짐없이 이어야 합니다. 이미 성립을 확인한 법칙을 정확히 적용하면 큰 표를 매번 다시 그리지 않아도 됩니다.

오늘은 식의 모양이 달라져도 진리조건이 그대로인지 확인했습니다. 다음 편에서는 반드시 같은 정보를 그대로 유지하는 경우뿐 아니라, 전제들이 참이면 따라오는 내용을 근거와 함께 한 단계씩 적어 보겠습니다.