Discrete mathematics: Exercises note

Because This note is written by myself, so maybe contains wrong english sentences or solutions.
If you let me know those wrong things, I'll be glad, thanks.

私が書いたノートなので、間違った英語や解法が含まれているかもしれません。
間違った箇所を伝えていただけると嬉しいです。

• Discrete mathematics: Exercises note
• 1.1
  • 31 (self practice)
  • 31 Answer (verified)
  • 32
  • 32 Answer (verified)
  • 33
  • 33 Answer (verified)
  • 34
  • 34 Answer (not verified)
  • 53
  • 53 Answer (verified)

1.1

31 (self practice)

How many rows appear in a truth table for each of these compound propositions?

それぞれの複合命題の真偽表は何行になるか？

a: \( p \to \neg{p} \)
b: \((p \lor ¬r)∧(q∨¬s)\)
c: \(q \lor p \lor ¬s \lor ¬r \lor ¬t \lor u\)
d: \((p \land r \land t) \leftrightarrow (q \land t)\)

31 Answer (verified)

Each variable can take 2 truth values.
Each of the truth table contains every possible combination for each variable.
And there are \( 2^n \) rows in a truth table when there are \(n\) different variables.

それぞれの変数は二値である。
それぞれの真偽表には各変数の組み合わせが取り得る全てのパターンを含んでいる。
ゆえに真偽表の行数は異なる変数の数を \(n\) として \(2^n\) となる。

a: \( p \to \neg{p} \) contains only one variable \(p\), thus \(n = 1\).
Number of rows \( = 2^1 = 2\)

\( p \to \neg{p} \) の変数は \(p\) のみだから、\(n = 1\)。
行数は \( 2^1 = 2\) となる。

b: \((p \lor ¬r)∧(q∨¬s)\) contains 4 variables (p, r, q, s).thus \(n = 4\).
Number of rows \( = 2^4 = 16 \)

\((p \lor ¬r)∧(q∨¬s)\) は 4 つの変数 (p, r, q, s) を含むので、\(n = 4\)。
行数は \( 2^4 = 16 \)。

c: \(q \lor p \lor ¬s \lor ¬r \lor ¬t \lor u\) contains 6 variables (q, p, s, r, t, u). thus \(n = 6\).
Number of rows \( = 2^6 = 64 \)

\(q \lor p \lor ¬s \lor ¬r \lor ¬t \lor u\) は 6 つの変数 (q, p, s, r, t, u) を含むので、\(n = 6\)。
行数は \( 2^6 = 64 \)

d: \((p \land r \land t) \leftrightarrow (q \land t)\) contains 4 variables (p, r, t, q). thus \(n = 4\).
Number of rows \( = 2^4 = 16 \)

\((p \land r \land t) \leftrightarrow (q \land t)\) は 4 つの変数 (p, r, t, q)を含むので、\(n = 4\)。
行数は \( 2^4 = 16 \)

32

How many rows appear in a truth table for each of these compound propositions?

それぞれの複合命題の真偽表は何行になるか？

a: \((q→¬p)∨(¬p→¬q)\)
b: \((p∨¬t)∧(p∨¬s)\)
c: \((p→r)∨(¬s→¬t)∨(¬u→v)\)
d: \((p∧r∧s)∨(q∧t)∨(r∧¬t)\)

32 Answer (verified)

this solution is same with exercise 31.

この解法は exercise 31 と同様である。

a: \((q→¬p)∨(¬p→¬q)\) contains 2 variables (q, p). thus \(n = 2\).
Number of rows \( = 2^2 = 4 \)

\((q→¬p)∨(¬p→¬q)\) は 2 つの変数(q, p)を含むので、\(n = 2\)。
行数は \( 2^2 = 4 \)

b: \((p∨¬t)∧(p∨¬s)\) contains 3 variables (p, t, s). thus \(n = 3\).
Number of rows \( = 2^3 = 8 \)

\((p∨¬t)∧(p∨¬s)\) は 3 つの変数(p, t, s)を含むので、\(n = 3\)。
行数は \( 2^3 = 8 \)

c: \((p→r)∨(¬s→¬t)∨(¬u→v)\) contains 6 variables (p, r, s, t, u, v). thus \(n = 6\).
Number of rows \( = 2^6 = 64 \)

\((p→r)∨(¬s→¬t)∨(¬u→v)\) は 6 つの変数(p, r, s, t, u, v)を含むので、 \(n = 6\)。
行数は \( 2^6 = 64 \)

d: \((p∧r∧s)∨(q∧t)∨(r∧¬t)\) contains 5 variables (p, r, s, q, t). thus \(n = 5\).
Number of rows \( = 2^5 = 32 \)

\((p∧r∧s)∨(q∧t)∨(r∧¬t)\) は 5 つの変数(p, r, s, q, t)を含むので、\(n = 5\)。
行数は \( 2^5 = 32 \)

33

Construct a truth table for each of these compound propositions.

それぞれの複合命題の真偽表を作成せよ

a: \(p∧¬p\)
b: \(p∨¬p\)
c: \((p∨¬q)→q\)
d: \((p∨q)→(p∧q)\)
e: \((p→q)↔(¬q→¬p)\)
f: \((p→q)→(q→p)\)

33 Answer (verified)

a: \(p∧¬p\)

b: \(p∨¬p\)

c: \((p∨¬q)→q\)

d: \((p∨q)→(p∧q)\)

e: \((p→q)↔(¬q→¬p)\)

f: \((p→q)→(q→p)\)

34

Construct a truth table for each of these compound propositions.

それぞれの複合命題の真偽表を作成せよ

a: \(p→¬p\)
b: \(p↔¬p\)
c: \(p⊕(p∨q)\)
d: \((p∧q)→(p∨q)\)
e: \((q→¬p)↔(p↔q)\)
f: \((p↔q)⊕(p↔¬q)\)

34 Answer (not verified)

a: \(p→¬p\)

b: \(p↔¬p\)

c: \(p⊕(p∨q)\)

d: \((p∧q)→(p∨q)\)

e: \((q→¬p)↔(p↔q)\)

f: \((p↔q)⊕(p↔¬q)\)

53

The nth statement in a list of 100 statements is “Exactly n of the statements in this list are false.”

100 個の文のリストの内、n 番目の文は「リスト内の n 個の文は偽である」

a: What conclusions can you draw from these statements?
b: Answer part(a) if the nth statement is “At least n of the statements in this list are false.”
c: Answer part(b) assuming that the list contains 99 statements.

a: これらの文からどのような結論が導き出せるか？
b: n 番目の文は「リスト内の少なくとも n 個の文が偽である」の場合についてパート a の問いに答えよ。
c: リストには 99 個の文があると仮定して、パート b の問いに答えよ。

53 Answer (verified)

a: The nth statement in a list of 100 statements is like the following table.

100 個の文のリストの内、n 番目は以下の表のようになる。

The statement is "Exactly n of ...",
So if let n = 1, then the 1st statement be TRUE, and "Exactly 1 of the statements in this list are false."
and let the 3th statement be FALSE for example, and let others be TRUE.

文には「（まさしく）n 個は...」となっている。
そのため、仮に n = 1 として、1 番目の文を真としてあげると、「リスト中、まさしく 1 個の文は偽である。」となり、例えば 3 番目の文を偽とすると、他は真となる。

According to above truth table, the 100th statement is also TRUE, so all statements should be false,
But it'll be conflict with the first condition of n = 1.

上記の真偽表に従えば、100 番目の文も真となり、そうなると全ての文は偽となるべきである。
しかし、これでは最初の条件である n = 1 と矛盾が生じてしまう。

If n = 98, and the 98th statement is TRUE, “Exactly 98 of the statements in this list are false.”,
then the truth table is like the following table.

n = 98 で 98 番目の文が真である場合、「リスト中の 98 個の文は偽である」となり、
真偽表は以下のようになる。

It's the same logic with the first one n = 1,
Because the 98th statement is TRUE, other 98 of statements should be FALSE, include at least one statement that over 98th(for example 99th, or 100th).
If the 99th statement is TRUE for example, then other 99 of statements should be FALSE,
But it'll be conflict with the first condition of n = 98.

n = 1 と同じ論理で、98 番目が真であるから、他の 98 個の文は偽となり、これには少なくとも 1 つの n 番目を超える文（例えば 99 番目や 100 番目）が含まれている。
例えば 99 番目が真となるなら、99 個の文が偽となるべきだが、それでは最初の条件である n = 98 と矛盾が生じてしまう。

And if n = 100, let the 100th statement is TRUE, then all statements should be false, include the 100th statement itself.

そしてさらに、n = 100 の場合、全ての文は偽となり、100 番目の文自身もこれに含まれてしまう。

So the answer is when n = 99,
that is 99 of statements be false, except the 99th statement.

ゆえに答えは n = 99 の時で、99 番目の文を除いた 99 個の文が偽となる場合である。

Therefore you can conclude like this "The 99th statement is TRUE and the rest are FALSE.".

従って、結論は「99 番目の文が真で、それ以外が偽となる」となる。

b: Answer part(a) if the nth statement is “At least n of the statements in this list are false.”

The nth statement in a list of 100 statements is like the following table.

100 個の文のリストの内、n 番目は以下の表のようになる。

The statement is "At least n of ...",
First, let's think about n = 100, and the 100th statement is TRUE, then it should be all statements going to be FALSE including the 100th statement itself. So there is a contradiction obviously.

文には「少なくとも n 個は...」となっている。
まず n = 100 の場合を考えてみると、100 番目は真となり、100 番目も含めて全ての文が偽となる。
これは明らかに矛盾が生じてしまう。

Second, let's think about when n = 99, So the 99th statement is TRUE, and the rest should be all FALSE.
That truth table is like bellow

次に n = 99 の場合を考えると、99 番目が真となり、その他は偽となる。
その真偽表は以下のようになる。

According to the above truth table, statements is FALSE from the 1st to 98th.
But there are 99 of FALSE statements, so for example, the statement “At least 98 of the statements in this list are false.” should be TRUE, and it's same with those statements from 1st to 97th.

上記の真偽表によれば、1 番目から 98 番目の文は偽である。
しかし 99 個の偽の文があるから、例えば、「このリストの少なくとも 98 個の文は偽である」も真となるべきである。
そしてそれは 1 番目から 97 番目も同様である。

Then how about when n = 1?
the 1st statement is “At least 1 of the statements in this list are false.”.
And the truth table is like the following table.

では n = 1 の場合はどうなるだろうか？
1 番目は「リスト中の少なくとも 1 個は偽である」である。
そして真偽表は以下のようになる。

This truth table doesn't make a contradiction.
because there are 99 of FALSE, satisfy that statement “At least 1 of the statements in this list are false.”.

この真偽表には矛盾がない。99 個の偽があるから「リストに少なくとも 1 個の偽がある」を満たしている。

Finally, you can find out when does it make a contradiction by increasing the value of n from 1.
And you'll be find that n = 51 make a contradiction, and until n = 50 doesn't make a contradiction.
Let's see the truth table when n = 50, and n = 51.

最後に、n の値を増加させながら、いつ矛盾が生じるのかを見つけれるだろう。
そして、n = 51 の時に矛盾が生じ、n = 50 までは矛盾が生じないのが分かると思う。
n = 50 と n = 51 の真偽表を見てみよう。

n = 50

This satisfy “At least 50 of the statements in this list are false.”, because 50 of statements from 51th to 100th are false.
So n = 50 doesn't make any contradiction.

51 番から 100 番までの 50 個の文が偽であるから、これは「リストに少なくとも 50 個の偽がある」を満たす。
ゆえに n = 50 では矛盾は生まれない。

n = 51

Because the 51th statement is "At least 51 of the statements in this list are false.", the truth table should have 51 of FALSE, and for satisfying this, other 2 statements should be FALSE additionally except from 52th to 100th.
But it makes contradictions of that other 2 statements.
For example if you changes 3th's and 50th's truth value, though there are 51 of FALSE and satisfy the 50th statement “At least 50 of the statements in this list are false.”, that truth value is forced to change.
So n = 51 make a contradiction.

51 番目の文が「リストに少なくとも 51 個の偽がある」だから、真偽表には 51 個の偽が必要で、それを満たすには 52 番目から 100 番目の他に、他 2 つの文を偽としなければならない。
しかし、それではその他の 2 つの文で矛盾が生じる。
例えば、3 番目と 50 番目の真偽値を変更したら、51 個の偽があり、50 番目の「リストに少なくとも 50 個の偽がある」を満たすのに、無理やり真偽値を変更させられている。
だから n = 51 は矛盾を生む。

Therefore this answer is "Statements 1 through 50 are all true and statements 51 through 100 are all false."

従ってこの答えは、「1 から 50 までの文は全て真で、51 から 100 までの文は全て偽である」となる。

c: Answer part(b) assuming that the list contains 99 statements.

assume that the list contains 99 statements, and these statements is same with partB's “At least n of the statements in this list are false.”.
First, you can guess that it's TRUE from 1st to 49th statements, and FALSE from 51th from 99th statements.
A case n = 49 of the truth table is like the following table.

リストには 99 個の文が存在すると仮定する。文はパート B と同様に「リストに少なくとも n 個の偽がある」である。
まず、1 から 49 番目まで真、51 から 99 番目までは偽となることはパート B から推測できる。
n = 49 の真偽表は以下のようになる。

n = 49

Statements from 50th to 99th are FALSE, and because there are 50 of FALSE, it satisfy "At least 49 of the statements in this list are false.”.

50 から 99 番目まで偽だから、50 個の偽があるので「リストに少なくとも 49 個の偽がある」を満たす。

Then how about the truth value of the 50th statement that is just the middle of the list.
Let's think the case of both that is TRUE and that is FALSE.
If the 50th statement is TRUE, Then there are 49 of FALSE from 51th to 99th. Therefore it cannot satisfy the 50th statement "At least 50 of the statements in this list are false.".
If the 50th statement is FALSE, Then there are 50 of FALSE from 50th to 99th. Therefore it satisfy the 50th statement "At least 50 of the statements in this list are false.".
If the 50th statement set as TRUE then it should be FALSE, and set as FALSE then it should be TRUE, So it is a logical paradox.
Therefore this cannot happen. This paradox shows that these cannot be statements.

ではリストのちょうど中間 50 番目の真偽値はどうだろうか？
50 番目が真である場合と偽である場合を考えてみよう。
50 番目が真である場合、偽は 51 から 99 番目までで 49 個である。すると「リストに少なくとも 50 個の偽がある」を満たせないため、50 番目は偽となる。
50 番目が偽である場合、偽は 50 から 99 番目までで 50 個である。すると「リストに少なくとも 50 個の偽がある」を満たすため、50 番目は真となる。
真とすれば偽となり、偽とすれば真となるパラドックスが生じる。
ゆえにリストには 99 個の文が存在することは出来ない。