จำนวนวิธีที่ค่าความจริงของประพจน์.......

[square1zoa]

ให้ $A_i,i=1,2,...,n$ เป็นประพจน์ จำนวนวิธีที่ค่าความจริงของ
$$(...((A_1\rightarrow A_2)\rightarrow A_3)\rightarrow .....)\rightarrow A_n$$ เป็นเท็จมีค่าเท่าไร

[nooonuii]

ผมคิดได้ $\dfrac{2^n-(-1)^n}{3}$ วิธีครับ

[square1zoa]

อยากได้วิธีคิดนะครับ

[nooonuii]

ผมใช้ recurrence relation ครับ ไม่รู้ว่ายากเกินไปมั้ย

ให้ $a_n$ แทนจำนวนวิธีที่จะได้ค่าความจริงเป็นเท็จ

$b_n$ แทนจำนวนวิธีที่จะได้ค่าความจริงเป็นจริง

เราจะได้ว่า $a_n=b_{n-1}$ เพราะว่า

$(((A_1\to A_2)\to\cdots\to A_{n-1})\to A_n$

เป็นเท็จก็ต่อเมื่อ $A_n$ เป็นเท็จ และ $(((A_1\to A_2)\to\cdots\to A_{n-1})$ เป็นจริง

โดยใช้การวิเคราะห์แบบเดีัยวกันจะได้ว่า

$b_n=b_{n-1}+2a_{n-1}$

ดังนั้นเราจะได้ว่า

$\pmatrix{a_n \\ b_n}=\pmatrix{0 & 1 \\ 2 & 1}\pmatrix{a_{n-1} \\ b_{n-1}}$

$~~~~~~~~=\cdots$

$~~~~~~~~=\pmatrix{0 & 1 \\ 2 & 1}^{n-2}\pmatrix{a_2 \\ b_2}$

$~~~~~~~~=\pmatrix{0 & 1 \\ 2 & 1}^{n-2}\pmatrix{1 \\ 3}$

แต่

$\pmatrix{0 & 1 \\ 2 & 1}=\pmatrix{1 & 1 \\ 2 & -1} \pmatrix{2 & 0 \\ 0 & -1} \pmatrix{1 & 1 \\ 2 & -1}^{-1}$

ดังนั้น

$\pmatrix{0 & 1 \\ 2 & 1}^{n-2}=\pmatrix{1 & 1 \\ 2 & -1} \pmatrix{2 & 0 \\ 0 & -1}^{n-2} \pmatrix{1 & 1 \\ 2 & -1}^{-1}$

$~~~~~~~~~~~~~~~~=\pmatrix{1 & 1 \\ 2 & -1} \pmatrix{2^{n-2} & 0 \\ 0 & (-1)^{n-2}}\pmatrix{1 & 1 \\ 2 & -1}^{-1}$

เราจึงได้ว่า

$a_n=\dfrac{2^n-(-1)^n}{3}$

$b_n=\dfrac{2^{n+1}-(-1)^{n+1}}{3}$

[square1zoa]

ข้อความเดิมเขียนโดยคุณ nooonuii

ผมใช้ recurrence relation ครับ ไม่รู้ว่ายากเกินไปมั้ย

ให้ $a_n$ แทนจำนวนวิธีที่จะได้ค่าความจริงเป็นเท็จ

$b_n$ แทนจำนวนวิธีที่จะได้ค่าความจริงเป็นจริง

เราจะได้ว่า $a_n=b_{n-1}$ เพราะว่า

$(((A_1\to A_2)\to\cdots\to A_{n-1})\to A_n$

เป็นเท็จก็ต่อเมื่อ $A_n$ เป็นเท็จ และ $(((A_1\to A_2)\to\cdots\to A_{n-1})$ เป็นจริง

โดยใช้การวิเคราะห์แบบเดีัยวกันจะได้ว่า

$b_n=b_{n-1}+2a_{n-1}$

ดังนั้นเราจะได้ว่า

$\pmatrix{a_n \\ b_n}=\pmatrix{0 & 1 \\ 2 & 1}\pmatrix{a_{n-1} \\ b_{n-1}}$

$~~~~~~~~=\cdots$

$~~~~~~~~=\pmatrix{0 & 1 \\ 2 & 1}^{n-2}\pmatrix{a_2 \\ b_2}$

$~~~~~~~~=\pmatrix{0 & 1 \\ 2 & 1}^{n-2}\pmatrix{1 \\ 3}$

แต่

$\pmatrix{0 & 1 \\ 2 & 1}=\pmatrix{1 & 1 \\ 2 & -1} \pmatrix{2 & 0 \\ 0 & -1} \pmatrix{1 & 1 \\ 2 & -1}^{-1}$

ดังนั้น

$\pmatrix{0 & 1 \\ 2 & 1}^{n-2}=\pmatrix{1 & 1 \\ 2 & -1} \pmatrix{2 & 0 \\ 0 & -1}^{n-2} \pmatrix{1 & 1 \\ 2 & -1}^{-1}$

$~~~~~~~~~~~~~~~~=\pmatrix{1 & 1 \\ 2 & -1} \pmatrix{2^{n-2} & 0 \\ 0 & (-1)^{n-2}}\pmatrix{1 & 1 \\ 2 & -1}^{-1}$

เราจึงได้ว่า

$a_n=\dfrac{2^n-(-1)^n}{3}$

$b_n=\dfrac{2^{n+1}-(-1)^{n+1}}{3}$

ความจริงเอามาจาก ข้ออบโควตา มข. เพียงแต่ให้มา 4 ประพจน์

ตรงสีแดงเป็นต้นไปนี่แหละ คืออะไรครับ ไม่ทราบจริงๆๆๆๆ

[nooonuii]

มาจากความสัมพันธ์

$a_n=b_{n-1}$

$b_n=b_{n-1}+2a_{n-1}$

แต่เขียนในรูป สมการ matrix ครับ

จากนั้นเราสามารถลดทอนสูตรไปเรื่อยๆเนื่องจากเป็นความสัมพันธ์เวียนบังเกิด

งานที่เหลือจึงเป็นการหาสูตรทั่วไปของกำลังของ matrix

ซึ่งตรงส่วนนี้ต้องใช้ทฤษฎีของ matrix มาช่วยด้วยครับ

[square1zoa]

อืม ขอบคุณครับ (ยากนะเนี่ย)

ที่ผมคิดได้ก็ตรงก่อนจะถึงสีแดงนี่แหละ

[nooonuii]

ข้อความเดิมเขียนโดยคุณ square1zoa

อืม ขอบคุณครับ (ยากนะเนี่ย)

ที่ผมคิดได้ก็ตรงก่อนจะถึงสีแดงนี่แหละ

จริงๆแล้วผมทำยากไปเองแหละ

จาก ความสัมพันธ์ข้างบนเราจะได้ว่า

$a_{n+1}=a_n+2a_{n-1}$

ซึ่งอันนี้ใช้ recurrence relation แก้ได้ครับ

[วะฮ่ะฮ่ะฮ่า]

อินดักชั่นสิ วะฮ่ะฮ่ะฮ่า

[square1zoa]

อยากเห็นเหมือนกัน