명제 논리만으로는 “모든 사람은 죽는다”와 “소크라테스는 사람이다” 사이의 관계를 표현하기 어렵다. 문장 전체에 참과 거짓을 붙이는 데서 더 나아가, 대상의 성질과 대상 사이의 관계를 나타내는 술어가 필요하다. 여기에 “모든”과 “적어도 하나”를 나타내는 한정 기호를 붙이면 수학적 주장과 시스템의 조건을 정확하게 쓸 수 있다.
연습문제로 바로 가기 · 먼저 풀어 본 뒤 각 문제의 해설 보기를 눌러 확인할 수 있다.
1. 술어와 명제함수
를 “”이라고 하자. 변수 의 값이 정해지지 않은 상태에서는 참과 거짓을 결정할 수 없다. 정의역을 정수로 정하고 값을 대입하면 과 은 거짓, 는 참인 명제가 된다. 이렇게 변수를 포함한 문장을 명제함수라고 한다.
변수가 여러 개일 수도 있다. 가 라면
컴퓨터가 공격받고 있는지 나타내는 는 한 대상의 성질이고, 컴퓨터가 통신망에 연결되어 있는지 나타내는 은 두 대상의 관계다. CS2와 MATH1만 공격받고 있다면 은 차례로 F, T, T다. MATH1이 CAMPUS2에만 연결되어 있다면 은 F, 는 T다.
명제 논리의 연결사는 그대로 사용할 수 있다. 가 이면 은 참이고 은 거짓이므로
다만 처럼 자유변수가 남은 식은 변수의 값이나 한정 범위가 정해져야 진리값을 판단할 수 있다.
프로그램의 전조건과 후조건
술어는 프로그램이 올바르게 실행되는지도 표현한다. 전조건은 실행 전에 만족해야 하는 조건, 후조건은 실행 후에 보장해야 하는 조건이다.
temp := x
x := y
y := temp
위 교환 프로그램의 전조건을 , 후조건을 로 잡으면 각 단계의 상태는 다음과 같다.
| 시점 | |||
|---|---|---|---|
| 실행 전 | 미정 | ||
| 첫 대입 후 | |||
| 둘째 대입 후 | |||
| 셋째 대입 후 |
임의의 입력 에 대해 후조건이 성립하므로 교환이 올바르게 이루어진다. if x > 0 then x := x + 1에서도 이라는 술어의 진리값이 대입문의 실행 여부를 결정한다.
2. 전칭 한정과 존재 한정
전칭 명제를 거짓으로 만들려면 반례 하나면 충분하다. 존재 명제를 참으로 만들려면 조건을 만족하는 증인 하나면 충분하다. 반대로 전칭 명제를 증명하거나 존재 명제를 반박하려면 정의역 전체를 다루어야 한다.
| 정의역과 술어 | 전칭 명제 | 존재 명제 |
|---|---|---|
| , | F: | T: |
| 양의 정수, | T | T: |
| 음의 정수, | F | F |
| , 는 짝수 | F: | T: |
| , | T | T |
| , | F: | T: |
| , | F | F |
같은 식도 정의역에 따라 달라진다. 는 실수에서는 때문에 거짓이지만, 정수에서는 참이다. 이 되는 구간 안에 정수가 없기 때문이다. 도 양의 정수 전체에서는 전칭 명제가 거짓이고 존재 명제가 참이지만, 음의 정수 전체에서는 둘 다 참이다.
정의역이 라면 은 때문에 거짓이고, 은 같은 값 때문에 참이다. 에서는 의 전칭·존재 명제가 모두 참이고, 의 전칭·존재 명제는 모두 거짓이다.
유한 정의역과 공집합
일 때
전칭 한정은 하나라도 거짓이면 중단하는 반복문, 존재 한정은 하나라도 참이면 중단하는 반복문처럼 이해할 수 있다. 무한 정의역에서는 이 생각이 의미를 이해하는 데는 도움이 되지만, 실제로 모든 원소를 순회하는 판정 알고리즘이 되지는 않는다.
공집합에서는 반례가 없으므로 전칭 명제가 참이고, 증인이 없으므로 존재 명제가 거짓이다. 일반적인 술어 논리에서는 정의역이 비어 있지 않다고 가정하지만, 집합에 제한된 한정을 다룰 때는 이 경우를 구별해야 한다.
유일하게 존재한다는 말
는 조건을 만족하는 원소가 정확히 하나라는 뜻이다.
정수에서 의 해는 하나이므로 유일하게 존재한다. 을 만족하는 정수는 여러 개이므로 존재하지만 유일하지는 않다.
3. 변수의 범위와 문장 번역
한정 기호가 묶는 변수를 구속변수, 묶이지 않은 변수를 자유변수라고 한다. 에서 는 구속변수이고 는 자유변수다. 한정 기호가 적용되는 식의 부분이 범위(scope)다.
괄호를 생략하면 범위를 오해하기 쉽다. 여기서는 를 로 읽는다. 까지 한정하려면 라고 써야 한다. 구속변수의 이름은 자유변수를 새로 묶지 않는 범위에서 바꿀 수 있다. 예를 들어
“모든 A는 B”와 “어떤 A는 B”
정의역을 모든 사람으로 놓고 를 “이 반의 학생”, 를 “자바를 배웠다”라고 하자.
전칭 문장에 를 쓰면 모든 사람이 이 반 학생이라고 주장하게 된다. 존재 문장에 를 쓰면 학생이 아닌 사람 하나만 있어도 참이 되어, 자바를 배운 학생의 존재를 보장하지 못한다. 정의역 자체가 이 반 학생들로 제한되어 있다면 각각 와 로 충분하다.
같은 방식으로 여러 문장을 옮길 수 있다.
| 문장 | 식 |
|---|---|
| 어떤 학생이 멕시코를 방문했다 | |
| 모든 학생이 캐나다 또는 멕시코를 방문했다 | |
| 어떤 학생은 캐나다를 방문하지 않았다 | |
| 어떤 도 가 아니다 | |
| 이면서 인 것은 모두 이다 |
메일의 크기를 , 압축 여부를 으로 쓰면 “1MB보다 큰 모든 메일은 압축된다”는
이다. 활성 사용자가 하나라도 있으면 사용 가능한 링크가 있어야 한다는 명세는
으로 쓴다. “각 사용자에게 자기 링크가 있다”는 문장이라면 사용자와 링크의 관계까지 별도로 표현해야 한다.
4. 한정 기호의 부정과 동치
핵심은 부정이 한정 기호를 통과하면 종류가 바뀐다는 것이다.
“모두 자바를 배웠다”의 부정은 “아무도 배우지 않았다”가 아니라 “배우지 않은 사람이 있다”다. “정직한 정치인이 있다”의 부정은 정치인을 정의역으로 삼을 때 다. 정의역이 모든 사람이라면 처럼 대상 조건도 함께 남겨야 한다.
복합식은 한정 기호의 드모르간 법칙과 명제 논리의 드모르간 법칙을 연달아 적용한다.
두 번째 식은 “모든 가 이다”를 반박하려면 이면서 가 아닌 원소를 찾으면 된다는 뜻이다.
분배되는 경우와 그렇지 않은 경우
다음 동치들은 항상 성립한다.
첫 식은 모든 원소에서 두 성질이 동시에 참이라는 말이므로 각 성질을 따로 전칭 한정해도 같다. 둘째 식은 어느 원소에서 둘 중 하나가 참이라는 말이므로 두 존재 주장 중 하나가 참인 것과 같다.
하지만 를 에, 를 에 마음대로 분배할 수는 없다. , , 라고 하면 모든 원소가 또는 이지만 모두가 인 것도 모두가 인 것도 아니다. 또한 의 증인과 의 증인은 각각 존재하지만 두 성질을 동시에 만족하는 증인은 없다.
조건문에서도
에서 , , 로 두면 왼쪽은 때문에 거짓이다. 오른쪽은 전건 가 거짓이라 참이다.
모든 해석에서 참인 식을 타당하다고 하고, 적어도 하나의 해석에서 참이면 만족가능하다고 한다. 비어 있지 않은 정의역에서 는 만족불가능하다. 특정 해석에서 참이라는 것과 논리적으로 타당하다는 것은 구별해야 한다.
5. 중첩된 한정 기호와 순서
는 실수 를 먼저 고른 뒤 그 값에 맞춰 를 고를 수 있다는 뜻이다. 반대로 는 하나의 를 먼저 고르고 모든 에 공통으로 사용해야 하므로 거짓이다.
| 식 | 뜻 | 거짓임을 보이는 방법 |
|---|---|---|
| 모든 쌍에서 성립 | 실패하는 쌍 하나 | |
| 각 마다 적절한 가 있음 | 어떤 에서는 모든 가 실패 | |
| 모든 에 통하는 가 있음 | 각 마다 실패하는 가 있음 | |
| 성립하는 쌍이 있음 | 모든 쌍에서 실패 |
같은 종류끼리는 순서를 바꿔도 된다.
서로 다른 종류라고 해서 반드시 진리값이 달라지는 것은 아니다. 실수에서 은 도 참이고 도 참이다. 각각 과 을 선택하면 된다. 중요한 것은 순서를 바꾼 식이 일반적으로 동치가 아니라는 점이다.
계산으로 확인하는 예제
| 실수에서의 명제 | 판단과 이유 |
|---|---|
| T: | |
| T: | |
| T: | |
| F: 은 실수의 제곱이 될 수 없음 | |
| F: 이면 모든 허용된 에서 몫이 0 |
마지막처럼 나눗셈이 있으면 분모가 0이 아닌 조건도 명시해야 한다.
정수에 관한 주장도 변수마다 한정한다.
사람 사이의 관계를 표현하기
를 “가 를 사랑한다”로 놓으면 다음 문장들은 서로 다르다.
| 문장 | 논리식 |
|---|---|
| 누구나 사랑하는 사람이 있다 | |
| 모두에게 사랑받는 사람이 있다 | |
| 누군가는 누군가를 사랑한다 | |
| 누구나 자신을 사랑한다 | |
| 아무도 모두를 사랑하지는 않는다 | |
| 모두가 자신을 사랑하는 것은 아니다 |
를 “컴퓨터가 있다”, 를 “친구다”라고 하면
는 모든 학생이 컴퓨터를 갖고 있거나 컴퓨터를 가진 친구가 있다는 뜻이다. 또
는 친구들 사이에 서로 친구인 쌍이 없는 학생이 있다는 뜻이다. 이 식 자체는 그 학생에게 친구가 두 명 이상 있다는 조건까지 보장하지 않는다. 친구가 없거나 한 명이어도 조건문이 참일 수 있다.
형제자매 관계 의 대칭성은 다. 관계의 방향과 한정 기호의 순서를 따로 확인해야 번역을 잘못하지 않는다.
6. 중첩된 한정 기호의 부정
한정 기호를 바깥에서부터 하나씩 뒤집는다.
“모든 항공사의 항공편을 적어도 한 번씩 탄 여성이 있다”를 써 보자. 는 여성 가 항공편 를 탔다는 뜻이고, 는 항공편 가 항공사 소속이라는 뜻이다.
그 부정은
즉 여성마다 한 번도 이용하지 않은 항공사가 적어도 하나 있다는 뜻이다. 는 에 따라 달라질 수 있다.
극한 정의에서 순서가 중요한 이유
실수 함수의 극한 은
로 표현한다. 허용 오차 이 주어지면 그에 맞는 를 선택한다. 그 뒤에는 조건을 만족하는 모든 에 대해 오차가 작아야 한다. 가 에 의존할 수 있다는 사실이 순서에 들어 있다.
정해진 이 극한값이 아니라는 것은
이다. 유한한 실수 극한값이 아예 없다는 주장은 이 식 앞에 을 붙인다. 여기서는 가 함수 정의역의 집적점이라고 가정한다.
7. 술어로 추론하기
가 사자, 가 사납다, 가 커피를 마신다는 뜻이라고 하자.
두 번째 전제의 사자 하나를 라고 하면 와 가 참이다. 첫 전제를 에 적용하면 도 참이다. 따라서
를 얻는다. 서로 다른 전제에서 같은 대상을 일관되게 추적하는 것이 중요하다.
새를 정의역으로 놓고 : 벌새, : 크다, : 꿀을 먹고 산다, : 색이 선명하다고 하자.
벌새 를 잡으면 첫 전제로 이고, 셋째 전제의 대우로 다. 둘째 전제에 따라 이므로 가 따라온다. “크지 않다”를 “작다”로 바꾸려면 두 표현이 서로 반대라는 분류 가정도 필요하다.
8. 논리회로를 식으로 읽기
논리회로에서는 AND가 , OR가 , NOT이 에 대응한다. 입력에서 출력 방향으로 각 게이트의 결과에 이름을 붙이고 다음 게이트의 입력으로 연결하면 전체 회로를 논리식으로 기술할 수 있다.
두 입력을 각각 부정한 뒤 OR
연결 순서는 p → NOT → u, q → NOT → v, (u, v) → OR → 출력이다.
따라서 NAND 하나와 같은 출력이다.
분기된 입력과 마지막 NOT
를 그대로 OR에 보내는 가지와, 를 부정한 뒤 와 AND하는 가지를 만든다. 두 가지의 OR 결과를 마지막에 부정한다.
이 회로는 NOR 하나로 줄일 수 있다.
세 입력 회로 두 가지
첫 회로는 을 부정해 와 OR하고, 그 결과를 와 AND한 뒤 전체를 부정한다.
둘째 회로는 를 각각 부정한 뒤 AND하는 가지와, 를 AND하는 가지를 마지막 OR로 합친다.
따라서 다. 이 식은 일 때 , 일 때 을 출력한다. 게이트의 모양을 외우기보다 각 선이 전달하는 식을 차례로 적으면 복잡한 회로도 같은 방법으로 해석할 수 있다.
9. 연습문제
문제를 읽고 풀이를 적어 본 뒤 해설을 펼쳐 비교해 보자. 계산 결과뿐 아니라 사용한 정의와 추론 근거까지 설명하는 연습을 한다.
01. 술어에 값을 대입하기
- 정수에서 일 때 , 의 진리값을 구하자.
- 가 컴퓨터 가 공격받는다는 뜻이고 CS2와 MATH1만 공격받는다. 은?
- 은 컴퓨터 가 네트워크 에 연결됨이다. MATH1은 CAMPUS2에만 연결되어 있다. 과 는?
- 일 때 과 은?
해설 보기
- F, T다. , 을 직접 대입한다.
- F, T, T다. 이름을 대입하면 각각 하나의 명제가 된다.
- F, T다. 컴퓨터와 네트워크의 인수 순서를 유지해야 한다.
- 이므로 두 식 모두 F다. 특히 조건문은 전건 T, 후건 F일 때 거짓이다.
02. 정의역에 따른 전칭 명제
다음 진리값을 구하고 거짓이면 반례를 들자.
- .
- .
- : 정의역이 실수일 때와 정수일 때.
- 가 네트워크에 연결됨일 때, 캠퍼스의 컴퓨터를 정의역으로 하는 의 뜻은?
- 정의역이 공집합이면 는?
해설 보기
- 참이다. 양변에서 를 빼면 이다.
- 거짓이다. 이면 이다.
- 실수에서는 거짓이다. 이면 . 정수에서는 참이다. 이면 , 이면 다. 이 둘 사이에 정수는 없다.
- 캠퍼스의 모든 컴퓨터가 네트워크에 연결되어 있다는 뜻이다.
- 반례가 없으므로 참이다. 이것을 공허하게 참이라고 한다.
03. 존재 증인과 유한 정의역
- 양의 정수에서 , 실수에서 , 실수에서 을 판정하자.
- 에서 과 을 판정하자.
- 정수에서 과 을 판정하자.
해설 보기
- 참, 참, 거짓이다. 앞의 두 증인은 각각 , 다. 마지막 등식은 양변에서 를 빼면 이 되어 어떤 실수에서도 불가능하다.
- 거짓, 참이다. 가 첫 식의 반례이자 둘째 식의 증인이다.
- 거짓, 참이다. 은 전칭 명제의 반례, 은 존재 명제의 증인이다. 반례와 증인이 하는 역할을 구별한다.
04. 한정 기호의 범위와 학생 문장
- 의 범위를 괄호로 명확히 쓰자. 전체를 한정하려면?
- 정의역이 모든 사람일 때 “이 반의 모든 학생은 자바를 들었다”를 번역하자. 는 이 반 학생, 는 자바를 들었다는 뜻이다.
- “이 반의 모든 학생이 자바를 들은 것은 아니다”를 부정을 바깥에 둔 식과 안으로 옮긴 식으로 쓰자.
- 는 이 학교 학생, 는 캐나다 방문 경험이다. “이 학교의 어떤 학생은 캐나다에 가 본 적이 없다”를 번역하자.
해설 보기
- 한정 기호가 바로 뒤의 술어에 먼저 결합하는 관례에서는 다. 뒤의 의 는 자유변수로 남는다. 전체를 한정할 때는 라고 쓴다.
- . 로 쓰면 모든 사람이 이 반 학생이라고까지 주장하게 된다.
- 정의역이 이 반 학생이면 . 모든 사람이 정의역이면 다.
- . 실제 학생이면서 방문 경험이 없는 증인이 필요하므로 AND를 쓴다.
05. 존재 한정의 분배와 부정
다음을 증명하거나 부정을 안으로 옮기자.
- .
- .
- .
해설 보기
- 왼쪽이 참이면 어떤 증인 에서 또는 가 참이다. 따라서 또는 가 참이다. 반대로 오른쪽이 참이면 어느 쪽의 존재 증인이든 를 만족하므로 왼쪽도 참이다.
- .
- 다음처럼 전칭 부정과 조건문 부정을 적용한다.
즉 “모든 가 이다”를 반박하려면 이면서 가 아닌 원소 하나를 찾으면 된다.
06. 자연어의 부정과 정의역
- “정직한 정치인이 있다”, “모든 미국인은 치즈버거를 먹는다”를 부정하자. 각각 정치인·미국인만 정의역으로 할 때와 모든 사람을 정의역으로 할 때의 식도 쓰자.
- 가 세 부류의 대상을 나타낸다. “어떤 도 가 아니다”를 존재 부정과 전칭식으로 쓰자.
- “이면서 인 것은 모두 다”를 번역하자.
해설 보기
- 정치인만 정의역이면 : 정직한 정치인은 없다. 모든 사람이 정의역이면 다. 미국인만 정의역이면 : 치즈버거를 먹지 않는 미국인이 있다. 모든 사람이 정의역이면 다.
- . 마지막은 로 써도 같다.
- . “어떤 것이 이고 라면”이라는 조건이므로 단순히 존재를 주장하는 식과 다르다.
07. 사자와 새에 관한 문장
- : 사자, : 사납다, : 커피를 마신다일 때 “모든 사자는 사납다”를 쓰자.
- 정의역은 모든 새다. : 벌새, : 크다, : 꿀을 먹는다, : 색이 선명하다. 다음 네 문장을 번역하자: 모든 벌새는 색이 선명하다 / 큰 새는 꿀을 먹지 않는다 / 꿀을 먹지 않는 새는 색이 선명하지 않다 / 벌새는 크지 않다.
해설 보기
- . 은 이 문장에는 필요 없다.
- 각각
“작다”를 “크지 않다”로 해석한 표현이다. 첫 세 문장에서 마지막을 추론하려면 , 셋째의 대우 , 둘째의 대우 를 연결하면 된다.
08. 중첩 한정 기호와 계산
정의역은 실수다.
- “모든 실수보다 더 큰 실수가 있다”를 한정 기호로 쓰자.
- , 를 판정하자.
- 을 판정하되 나눗셈의 정의 조건도 명시하자.
- 을 말로 옮기고 과 비교하자.
해설 보기
- 이며 로 고르면 된다.
- 둘 다 참이다. 첫 식은 각 에 대해 , 둘째는 먼저 을 고르면 된다.
- 엄밀히는 인 경우에만 를 쓴다. 로 표현하면 거짓이다. 에는 조건을 만족하는 가 없다.
- “모든 실수에는 더해서 0이 되는 실수가 있다.” 이므로 참이다. 순서를 바꾼 식은 모든 실수에 공통인 역원 하나를 요구한다. 에는 , 에는 이 필요하므로 거짓이다.
09. 관계 문장과 중첩된 부정
- 정수 두 개의 곱이 홀수이면 둘 다 홀수라는 말을 로 쓰자.
- 는 가 를 사랑함이다. “모두가 자신을 사랑하는 것은 아니다”를 쓰자.
- 와 의 부정을 안으로 옮기자.
- 모든 사람을 정의역으로 하고 는 이 학교 학생, 는 컴퓨터 보유, 는 친구 관계다. “이 학교의 모든 학생은 컴퓨터를 갖고 있거나 컴퓨터를 가진 친구가 있다”를 쓰자.
해설 보기
- .
- .
- 한정 기호를 하나 지날 때마다 와 를 바꾼다.
- . 친구 가 같은 학교 학생이어야 한다는 조건은 없으므로 를 임의로 추가하지 않는다.
10. 한정 기호를 옮길 수 있는 조건
다음 동치를 판정하고 거짓이면 반례를 들자.
- .
- .
- .
- .
해설 보기
- 참이다. 둘 다 모든 순서쌍에서 가 참이어야 한다.
- 거짓이다. 정수에서 을 쓰면 왼쪽은 로 참, 오른쪽은 하나의 가 0과 1의 역원일 수 없어 거짓이다.
- 참이다. 왼쪽에서 모든 원소에 대해 두 성분이 각각 참이다. 반대로 두 전칭 명제가 참이면 임의의 같은 원소에서 두 성분을 AND로 묶을 수 있다.
- 거짓이다. 에서 로 두자. 왼쪽은 때문에 거짓이다. 오른쪽은 가 거짓이라 참이다.
11. 실수에서 증인과 반례 찾기
실수에서 다음 명제를 판정하자. 참이면 증인을 고르는 방법, 거짓이면 반례를 쓰자.
- .
- .
- .
해설 보기
- 참이다. 임의의 가 주어지면 로 고른다. 그러면 이다.
- 참이다. 하나를 먼저 정하면 모든 실수 에서 이다.
- 거짓이다. 이면 실수의 제곱 과 같아질 수 없다. 의 정의역을 음이 아닌 실수로 제한하면 참이 되지만 여기서는 모든 실수가 대상이다.
12. 사랑 관계의 네 문장
모든 사람이 정의역이고 는 가 를 사랑한다는 뜻이다. 다음을 번역하자.
- 누구나 누군가를 사랑한다.
- 모두에게 사랑받는 사람이 있다.
- 모든 사람을 사랑하는 사람은 없다.
- 모두가 자기 자신을 사랑한다.
해설 보기
- . 는 에 따라 달라도 된다.
- . 하나의 공통 대상 가 필요하다.
- . 각 사람마다 사랑하지 않는 상대가 적어도 하나 있다는 뜻이다. “아무도 아무도 사랑하지 않는다”보다 약하다.
- . 두 인수가 같은 사람임을 명시한다.
13. 게이트 연결을 식으로 바꾸기
다음 연결의 출력식을 쓰고 가능하면 간단히 하자.
- 를 각각 NOT한 뒤 두 결과를 OR한다.
- 를 NOT한 결과와 를 AND한다. 이를 원래 와 OR한 뒤 최종 출력을 NOT한다.
- 을 NOT하고 와 OR한 결과를 와 AND한 뒤 NOT한다.
- 를 각각 NOT하여 AND한 결과와, 을 AND한 결과를 OR한다.
해설 보기
- . NAND와 같다.
- . 안쪽을 분배하면 이므로 , 즉 NOR다.
- . 두 번의 드모르간과 이중부정을 사용한다.
- . 이면 , 이면 을 출력한다. 입력이 갈라지는 곳에서도 같은 신호 라는 점을 유지한다.
Comments