千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2015年8月実施 専門 A5

标签：

• Recursion
• Binary-Relations

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の Pascal 関数を考える。

function rel(a, b: integer): boolean;
begin
  if a <= 0 then rel := true
  else if (b <= 0) or ((a mod 2) > (b mod 2)) then rel := false
  else rel := rel(a div 2, b div 2);
end;

(1) rel(x,y) = rel(y,x) = false となる整数の例を挙げよ。

(2) rel(x,y) = rel(y,z) = true なら rel(x,z) = true か。真偽を述べ、証明せよ。

题目描述

考虑上述 Pascal 函数。

(1) 给出使 rel(x,y) 与 rel(y,x) 均为假的整数对。

(2) 判断并证明关系的传递性：若 rel(x,y) 和 rel(y,z) 均为真，rel(x,z) 是否必为真？

Kai

(1)

$x=1,y=2$ とすればよい。二進表現ではそれぞれ $01,10$ である。

(2)

真である。正整数 $a,b$ に対して、rel(a,b) が真となる必要十分条件は「$a$ の二進表現で $1$ の立つ全ての桁で $b$ も $1$」である。実際、各再帰で最下位桁を比較し、その後に両者を二で割って次の桁へ進むからである。

$x\le0$ なら rel(x,z) は無条件で真。$x>0$ なら rel(x,y) が真であることから $y>0$、さらに rel(y,z) が真であることから $z>0$。$1$ の立つ桁の集合を $S(a)$ と書けば

$$S(x)\subset S(y)\subset S(z).$$

従って $S(x)\subset S(z)$ であり、rel(x,z) は真となる。