กลับไปหน้าบทความ

อ่าน 8 นาที

ฟังก์ชันโมโนโทนิก

ใน ทางคณิตศาสตร์ ฟังก์ชัน โมโนโทนิก (หรือ ฟังก์ชันโมโนโทน ) คือ ฟังก์ชัน ระหว่าง เซตที่มีลำดับ ซึ่งรักษาหรือกลับ ลำดับที่ กำหนด [ 1 ] [ 2 ] [ 3 ] แนวคิดนี้เกิดขึ้นครั้งแรกใน...

ฟังก์ชันโมโนโทนิก

รูปที่ 1. ฟังก์ชันที่ไม่ลดลงอย่างต่อเนื่อง
รูปที่ 2 ฟังก์ชันที่ไม่เพิ่มขึ้นอย่างต่อเนื่อง
รูปที่ 3 ฟังก์ชันที่ไม่เป็นฟังก์ชันเอกภาค

ในทางคณิตศาสตร์ฟังก์ชันโมโนโทนิก (หรือฟังก์ชันโมโนโทน ) คือฟังก์ชันระหว่างเซตที่มีลำดับซึ่งรักษาหรือกลับลำดับที่กำหนด[ 1 ] [ 2 ] [ 3 ]แนวคิดนี้เกิดขึ้นครั้งแรกในแคลคูลัสและต่อมาได้รับการขยายไปสู่บริบทที่เป็นนามธรรมมากขึ้นของทฤษฎีลำดับ

ในแคลคูลัสและการวิเคราะห์

ในแคลคูลัสฟังก์ชันเอฟ{\displaystyle f}ฟังก์ชันที่กำหนดบนเซตย่อยของจำนวนจริงที่มีค่าเป็นจำนวนจริงเรียกว่า ฟังก์ชันโมโนโทนิกหากฟังก์ชันนั้นไม่ลดลงเลย หรือไม่เพิ่มขึ้นเลย[ 2 ]กล่าวคือ ตามรูปที่ 1 ฟังก์ชันที่เพิ่มขึ้นแบบโมโนโทนิกไม่จำเป็นต้องเพิ่มขึ้นอย่างเดียว แต่ต้องไม่ลดลง

ฟังก์ชันเรียกว่าเพิ่มขึ้นอย่างต่อเนื่อง (หรือเพิ่มขึ้นหรือไม่ลดลง ) [ 3 ]ถ้าสำหรับทุกๆx{\displaystyle x}และy{\displaystyle y}โดยที่xy{\displaystyle x\leq y}หนึ่งมี เอฟ(x)เอฟ(y){\displaystyle f\!\left(x\right)\leq f\!\left(y\right)}, ดังนั้นเอฟ{\displaystyle f}รักษาลำดับ (ดูรูปที่ 1) ในทำนองเดียวกัน ฟังก์ชันเรียกว่าลดลงอย่างต่อเนื่อง (หรือลดลงหรือไม่เพิ่มขึ้น ) [ 3 ]ถ้าเมื่อใดก็ตามที่xy{\displaystyle x\leq y}, แล้วเอฟ(x)เอฟ(y){\displaystyle f\!\left(x\right)\geq f\!\left(y\right)}ดังนั้นจึงเป็นการสลับลำดับ (ดูรูปที่ 2)

หากคำสั่งซื้อ{\displaystyle \leq }ในนิยามของความเป็นเอกรูปนั้น ถูกแทนที่ด้วยลำดับที่เข้มงวด<{\displaystyle <}เมื่อเพิ่มฟังก์ชันที่มีเงื่อนไขที่เข้มงวดมากขึ้น ฟังก์ชันที่มีคุณสมบัตินี้เรียกว่าฟังก์ชันเพิ่มขึ้นอย่างเคร่งครัด (หรือฟังก์ชันเพิ่มขึ้น ) [ 3 ] [ 4 ]อีกครั้ง เมื่อกลับสัญลักษณ์ลำดับ จะได้แนวคิดที่สอดคล้องกันเรียกว่าฟังก์ชันลดลงอย่างเคร่งครัด (หรือฟังก์ชันลดลง ) [ 3 ] [ 4 ]ฟังก์ชันที่มีคุณสมบัติใดคุณสมบัติหนึ่งเรียกว่าฟังก์ชันโมโนโทนอย่างเคร่งครัดฟังก์ชันที่เป็นโมโนโทนอย่างเคร่งครัดเป็นฟังก์ชันหนึ่งต่อหนึ่ง (เพราะสำหรับx{\displaystyle x}ไม่เท่ากับy{\displaystyle y}, ทั้งx<y{\displaystyle x<y}หรือx>y{\displaystyle x>y}และด้วยเหตุนี้ โดยอาศัยคุณสมบัติความเป็นเอกรูป จึงอาจเป็นไปได้ว่าเอฟ(x)<เอฟ(y){\displaystyle f\!\left(x\right)<f\!\left(y\right)}หรือเอฟ(x)>เอฟ(y){\displaystyle f\!\left(x\right)>f\!\left(y\right)}, ดังนั้นเอฟ(x)เอฟ(y){\displaystyle f\!\left(x\right)\neq f\!\left(y\right)}.

เพื่อหลีกเลี่ยงความกำกวม คำว่า"โมโนโทนอ่อน" " เพิ่มขึ้นอ่อน"และ"ลดลงอ่อน"มักถูกใช้เพื่ออ้างถึงความเป็นโมโนโทนที่ไม่เข้มงวด

คำว่า "ไม่ลดลง" และ "ไม่เพิ่มขึ้น" ไม่ควรสับสนกับคำคุณศัพท์เชิงลบ (ที่อ่อนกว่ามาก) อย่าง "ไม่ลดลง" และ "ไม่เพิ่มขึ้น" ตัวอย่างเช่น ฟังก์ชันที่ไม่เป็นไปตามลำดับที่แสดงในรูปที่ 3 ลดลงก่อน จากนั้นเพิ่มขึ้น แล้วลดลงอีกครั้ง ดังนั้นจึงไม่ลดลงและไม่เพิ่มขึ้น แต่ก็ไม่ลดลงและไม่เพิ่มขึ้นเช่นกัน

ฟังก์ชันเอฟ{\displaystyle f}กล่าวกันว่ามีความเป็นเอกรูปอย่างสมบูรณ์ในช่วงเวลาหนึ่ง(เอ,){\displaystyle \left(a,b\right)}ถ้าอนุพันธ์ทุกอันดับของเอฟ{\displaystyle f}มีค่าไม่เป็นลบหรือมีค่าไม่เป็นบวก ทั้งหมด ณ ทุกจุดบนช่วงดังกล่าว

ฟังก์ชันผกผัน

ฟังก์ชันโมโนโทนิกอย่างเคร่งครัดทั้งหมดสามารถหาฟังก์ชันผกผันได้เนื่องจากรับประกันได้ว่าจะมีฟังก์ชันหนึ่งต่อหนึ่งจากช่วงของฟังก์ชันไปยังโดเมนของฟังก์ชัน

อย่างไรก็ตาม ฟังก์ชันที่เป็นโมโนโทนอย่างอ่อนไม่จำเป็นต้องเป็นฟังก์ชันผกผันได้เสมอไป ฟังก์ชันเหล่านั้นอาจมีค่าคงที่ในช่วงใดช่วงหนึ่ง (และดังนั้นจึงไม่ใช่ฟังก์ชันหนึ่งต่อหนึ่ง)

ฟังก์ชันอาจเป็นฟังก์ชันเพิ่มขึ้นอย่างเคร่งครัดในช่วงค่าที่จำกัด และดังนั้นจึงมีฟังก์ชันผกผันในช่วงนั้นได้ แม้ว่าจะไม่ได้เป็นฟังก์ชันเพิ่มขึ้นอย่างเคร่งครัดทุกที่ก็ตาม ตัวอย่างเช่น ถ้าy=จี(x){\displaystyle y=g(x)}กำลังเพิ่มขึ้นอย่างเคร่งครัดในช่วง[เอ,]{\displaystyle [a,b]}จากนั้นมันก็จะมีสิ่งที่ตรงกันข้ามx=ชม.(y){\displaystyle x=h(y)}บนสนามยิงปืน[จี(เอ),จี()]{\displaystyle [g(a),g(b)]}.

บางครั้งมีการใช้ คำว่า"โมโนโทนิก"แทนคำว่า"โมโนโทนิกอย่างเคร่งครัด " ดังนั้นแหล่งข้อมูลอาจระบุว่าฟังก์ชันโมโนโทนิกทั้งหมดสามารถผกผันได้ ในขณะที่ความจริงแล้วหมายความว่าฟังก์ชันโมโนโทนิกอย่างเคร่งครัดทั้งหมดสามารถผกผันได้

การแปลงแบบโมโนโทนิก

คำว่าการแปลงแบบโมโนโทนิก (หรือการแปลงแบบโมโนโทน ) อาจทำให้เกิดความสับสนได้เช่นกัน เนื่องจากหมายถึงการแปลงโดยฟังก์ชันที่เพิ่มขึ้นอย่างเคร่งครัด ซึ่งเป็นกรณีในทางเศรษฐศาสตร์ที่เกี่ยวข้องกับคุณสมบัติเชิงลำดับของฟังก์ชันอรรถประโยชน์ที่ยังคงรักษาไว้ได้เมื่อทำการแปลงแบบโมโนโทนิก (ดูเพิ่มเติมที่ความชอบแบบโมโนโทน ) [ 5 ]ในบริบทนี้ คำว่า "การแปลงแบบโมโนโทนิก" หมายถึงการแปลงแบบโมโนโทนิกเชิงบวก และมีจุดประสงค์เพื่อแยกแยะออกจาก "การแปลงแบบโมโนโทนิกเชิงลบ" ซึ่งกลับลำดับของตัวเลข[ 6 ]

แอปพลิเคชันพื้นฐานและผลลัพธ์บางส่วน

ฟังก์ชันเอกภาคที่มีจุดไม่ต่อเนื่องแบบกระโดดจำนวนมาก (แสดงหลายส่วน)
กราฟแสดงฟังก์ชันการเติบโตแบบโมโนโทนิก 6 ฟังก์ชัน

คุณสมบัติต่อไปนี้เป็นจริงสำหรับฟังก์ชันโมโนโทนิกเอฟ:อาร์อาร์{\displaystyle f\colon \mathbb {R} \to \mathbb {R} }:

  • เอฟ{\displaystyle f}มีขอบเขตจากด้านขวาและด้านซ้ายในทุกจุดของขอบเขตนั้น
  • เอฟ{\displaystyle f}มีขีดจำกัดที่ค่าอนันต์บวกหรือลบ (±{\displaystyle \pm \infty }) ของจำนวนจริงใดจำนวนหนึ่ง{\displaystyle \infty }, หรือ{\displaystyle -\infty }.
  • เอฟ{\displaystyle f}สามารถมีได้เฉพาะการกระโดดและความไม่ต่อเนื่องที่สามารถแก้ไขได้เท่านั้น
  • เอฟ{\displaystyle f}สามารถมีจุดไม่ต่อเนื่องได้ เพียง จำนวนนับ ได้ ในโดเมนของมัน อย่างไรก็ตาม จุดไม่ต่อเนื่องเหล่านั้นไม่จำเป็นต้องประกอบด้วยจุดที่แยกเดี่ยว และอาจหนาแน่นในช่วง ( a , b ) ก็ได้ ตัวอย่างเช่น สำหรับลำดับที่สามารถหาผลรวมได้ ใดๆ(เอฉัน)(AI})ของจำนวนบวกและการนับใดๆ(qฉัน){\displaystyle (q_{i})}ของจำนวนตรรกยะฟังก์ชันที่เพิ่มขึ้นอย่างต่อเนื่องเอฟ(x)=qฉันxเอฉัน{\displaystyle f(x)=\sum _{q_{i}\leq x}a_{i}}มีค่าต่อเนื่องที่จำนวนอตรรกยะทุกจำนวน (ดูภาพประกอบ) มันคือฟังก์ชันการกระจายสะสมของการวัดแบบไม่ ต่อเนื่อง บนจำนวนตรรกยะ โดยที่เอฉัน{\displaystyle a_{i}}น้ำหนักของqฉัน{\displaystyle q_{i}}.
  • ถ้าเอฟ{\displaystyle f}สามารถหาอนุพันธ์ได้ที่x*อาร์{\displaystyle x^{*}\in {\mathbb {R}}}และเอฟ(x*)>0{\displaystyle f'(x^{*})>0}ดังนั้นจึงมีช่วงเวลาI ที่ไม่เสื่อมสภาพ ซึ่งเป็นไปตามเงื่อนไขดังกล่าวx*ฉัน{\displaystyle x^{*}\in I}และเอฟ{\displaystyle f}กำลังเพิ่มขึ้นบนI .
  • ในทางกลับกันบางส่วน ถ้าหากเอฟ{\displaystyle f}สามารถหาอนุพันธ์ได้และเป็นค่าเพิ่มขึ้นในช่วงหนึ่งฉัน{\displaystyle I}ดังนั้นอนุพันธ์ของมันจะมีค่าไม่เป็นลบที่ทุกจุดในฉัน{\displaystyle I}นอกจากนี้ ชุดดังกล่าวเอ={xฉัน:เอฟ(x)>0}{\displaystyle A=\{x\in I:f'(x)>0\}}มีความหนาแน่นสูงและมีมาตรวัดเลเบสบวก คง ไม่มีอะไรจะกล่าวเพิ่มเติมไปมากกว่านี้แล้วเอ{\displaystyle A}ตัวอย่างเช่นเอ{\displaystyle A}อาจน้อยนิดดังเช่นในกรณีของอนุพันธ์ปอมเปอีและสำหรับค่าคงที่ฉัน{\displaystyle I}การวัดแบบเลเบสก์ของเอ{\displaystyle A}สามารถทำให้ใกล้เคียงกับค่าที่กำหนดได้0{\displaystyle 0}โดยการเลือกที่เหมาะสมเอฟ{\displaystyle f}.

คุณสมบัติเหล่านี้เป็นเหตุผลที่ทำให้ฟังก์ชันโมโนโทนิกมีประโยชน์ในงานวิเคราะห์ ทางเทคนิค คุณสมบัติสำคัญอื่นๆ ของฟังก์ชันเหล่านี้ ได้แก่:

  • ถ้าเอฟ{\displaystyle f}เป็นฟังก์ชันโมโนโทนิกที่กำหนดบนช่วงฉัน{\displaystyle I}, แล้วเอฟ{\displaystyle f}สามารถหาอนุพันธ์ได้เกือบทุกที่บนฉัน{\displaystyle I}กล่าวคือ เซตของตัวเลขx{\displaystyle x}ในฉัน{\displaystyle I}โดยที่เอฟ{\displaystyle f}ไม่สามารถหาอนุพันธ์ได้ในx{\displaystyle x}มีมาตรวัดเลเบส เป็นศูนย์ นอกจากนี้ ผลลัพธ์นี้ไม่สามารถปรับปรุงให้เป็นจำนวนนับได้: ดูฟังก์ชันแคนเตอร์
  • ถ้าเซตนี้เป็นเซตที่นับได้แล้วเอฟ{\displaystyle f}ต่อเนื่องอย่างแน่นอน
  • ถ้าเอฟ{\displaystyle f}เป็นฟังก์ชันโมโนโทนิกที่กำหนดบนช่วง[เอ,]{\displaystyle \left[a,b\right]}, แล้วเอฟ{\displaystyle f}สามารถหาปริพันธ์รีมันน์ได้

การประยุกต์ใช้ฟังก์ชันโมโนโทนิกที่สำคัญอย่างหนึ่งคือในทฤษฎีความน่าจะเป็นถ้าX{\displaystyle X}เป็นตัวแปรสุ่มฟังก์ชันการกระจายสะสมของมันเอฟX(x)=ความน่าจะเป็น(Xx){\displaystyle F_{X}\!\left(x\right)={\text{Prob}}\!\left(X\leq x\right)}เป็นฟังก์ชันที่เพิ่มขึ้นอย่างต่อเนื่อง

ฟังก์ชันจะเรียกว่าฟังก์ชัน แบบมีจุดสูงสุดเพียงจุดเดียว ( unimodal function) หากฟังก์ชันนั้นเพิ่มขึ้นอย่างต่อเนื่องจนถึงจุดหนึ่ง ( จุดสูงสุด ) แล้วจึงลดลงอย่างต่อเนื่อง

เมื่อไรเอฟ{\displaystyle f}ถ้าเป็นฟังก์ชันโมโนโทนิกอย่างเคร่งครัด แล้วเอฟ{\displaystyle f}เป็นฟังก์ชันหนึ่งต่อหนึ่งในโดเมนของมัน และถ้าที{\displaystyle T}คือช่วงของเอฟ{\displaystyle f}จากนั้นจะมีฟังก์ชันผกผันบนที{\displaystyle T}สำหรับเอฟ{\displaystyle f}ในทางตรงกันข้าม ฟังก์ชันคงที่แต่ละฟังก์ชันเป็นแบบโมโนโทนิก แต่ไม่ใช่แบบอินเจกทีฟ[ ​​7 ]และด้วยเหตุนี้จึงไม่มีฟังก์ชันผกผัน

กราฟแสดงฟังก์ชันโมโนโทนิกหกฟังก์ชัน รูปแบบที่ง่ายที่สุดของฟังก์ชันเหล่านี้แสดงอยู่ในพื้นที่กราฟ และนิพจน์ที่ใช้ในการสร้างฟังก์ชันเหล่านี้แสดงอยู่บนแกนy

ในทางโทโพโลยี

แผนที่เอฟ:Xวาย{\displaystyle f:X\to Y}กล่าวได้ว่าเป็นแบบโมโนโทน หาก เส้นใยแต่ละเส้นเชื่อมต่อกันนั่นคือ สำหรับแต่ละองค์ประกอบyวาย,{\displaystyle y\in Y,}เซต (ซึ่งอาจว่างเปล่า)เอฟ1(y){\displaystyle f^{-1}(y)}เป็นปริภูมิย่อย ที่เชื่อมต่อกัน ของX.{\displaystyle X.}

ในการวิเคราะห์เชิงฟังก์ชัน

ในการวิเคราะห์เชิงฟังก์ชันบนปริภูมิเวกเตอร์เชิงทอพอโลยีX{\displaystyle X}ตัวดำเนินการ (ซึ่งอาจไม่ใช่เชิงเส้น)ที:XX*{\displaystyle T:X\rightarrow X^{*}}กล่าวกันว่าเป็นตัวดำเนินการเสียงเดียวถ้า

(ทีคุณทีวี,คุณวี)0คุณ,วีX.{\displaystyle (Tu-Tv,u-v)\geq 0\quad \forall u,v\in X.}ทฤษฎีบทของคาชูรอฟสกีแสดงให้เห็นว่าฟังก์ชันนูนบนปริภูมิบานาคมีตัวดำเนินการโมโนโทนิกเป็นอนุพันธ์ของฟังก์ชันเหล่านั้น

เซตย่อยจี{\displaystyle G}ของX×X*{\displaystyle X\times X^{*}}กล่าวกันว่าเป็นชุดสีเดียวหากสำหรับทุกคู่[คุณ1,1]{\displaystyle [u_{1},w_{1}]}และ[คุณ2,2]{\displaystyle [u_{2},w_{2}]}ในจี{\displaystyle G},

(12,คุณ1คุณ2)0.{\displaystyle (w_{1}-w_{2},u_{1}-u_{2})\geq 0.}จี{\displaystyle G}เรียกว่าเซตโมโนโทนสูงสุด (maximal monotone)ถ้าเป็นเซตโมโนโทนสูงสุดในแง่ของการรวมเซต กราฟของตัวดำเนินการโมโนโทนจี(ที){\displaystyle G(T)}เป็นเซตโมโนโทน ตัวดำเนินการโมโนโทนจะเรียกว่าเป็นโมโนโทนสูงสุด ก็ ต่อเมื่อกราฟของมันเป็นเซตโมโนโทนสูงสุด

ในทฤษฎีลำดับ

ทฤษฎีลำดับเกี่ยวข้องกับเซตที่มีลำดับบางส่วนและเซตที่มีลำดับก่อนหน้าโดยพลการ ซึ่งเป็นการขยายความของจำนวนจริง นิยามของความเป็นเอกภาคข้างต้นมีความเกี่ยวข้องในกรณีเหล่านี้เช่นกัน อย่างไรก็ตาม คำว่า "เพิ่มขึ้น" และ "ลดลง" จะถูกหลีกเลี่ยง เนื่องจากภาพแทนแบบดั้งเดิมของคำเหล่านี้ใช้ไม่ได้กับลำดับที่ไม่ใช่ลำดับสมบูรณ์นอกจากนี้ความสัมพันธ์ที่เข้มงวด<{\displaystyle <}และ>{\displaystyle >}มีประโยชน์น้อยในคำสั่งซื้อที่ไม่ครบถ้วนหลายประเภท ดังนั้นจึงไม่มีการนำคำศัพท์เพิ่มเติมมาใช้สำหรับคำสั่งซื้อเหล่านั้น

ให้เช่า{\displaystyle \leq }แสดงถึงความสัมพันธ์ลำดับบางส่วนของเซตที่มีลำดับบางส่วนใดๆ ซึ่ง เป็นฟังก์ชัน เอกภาคหรือเรียกว่าไอโซโทนหรือรักษาความเป็นระเบียบเรียบร้อย ตรงตามคุณสมบัติ

xyเอฟ(x)เอฟ(y){\displaystyle x\leq y\implies f(x)\leq f(y)}

สำหรับทุกค่าxและyในโดเมนของมัน ฟังก์ชันประกอบของฟังก์ชันโมโนโทนสองฟังก์ชันก็จะเป็นฟังก์ชันโมโนโทนเช่นกัน

แนวคิดคู่ขนานมักเรียกว่าแอนติโทนแอนติโมโนโทนหรือการกลับลำดับดังนั้น ฟังก์ชันแอนติโทนf จึง มีคุณสมบัติดังต่อไปนี้

xyเอฟ(y)เอฟ(x),{\displaystyle x\leq y\implies f(y)\leq f(x),}

สำหรับทุกค่าxและyในโดเมนของมัน

ฟังก์ชันคงที่นั้นเป็นทั้งฟังก์ชันเอกโทนและฟังก์ชันปฏิโทน ในทางกลับกัน ถ้าfเป็นทั้งฟังก์ชันเอกโทนและฟังก์ชันปฏิโทน และถ้าโดเมนของfเป็นแลตทิซแล้วfจะต้องเป็นฟังก์ชันคงที่

ฟังก์ชันโมโนโทนเป็นหัวใจสำคัญในทฤษฎีลำดับ ฟังก์ชันเหล่านี้ปรากฏอยู่ในบทความส่วนใหญ่เกี่ยวกับเรื่องนี้ และตัวอย่างจากการประยุกต์ใช้งานเฉพาะด้านก็พบได้ในที่เหล่านั้น ฟังก์ชันโมโนโทนพิเศษที่น่าสนใจบางอย่าง ได้แก่การฝังลำดับ (ฟังก์ชันสำหรับ ซึ่งxy{\displaystyle x\leq y}ก็ต่อเมื่อเอฟ(x)เอฟ(y)){\displaystyle f(x)\leq f(y))}และไอโซมอร์ฟิซึมลำดับ ( การฝังลำดับ แบบทั่วถึง )

ในบริบทของอัลกอริธึมการค้นหา

ในบริบทของอัลกอริธึมการค้นหาความเป็นเอกรูป (หรือเรียกว่าความสอดคล้อง) เป็นเงื่อนไขที่ใช้กับฟังก์ชันฮิวริสติกฮิวริสติ กชม.(n){\displaystyle h(n)}จะเป็นฟังก์ชันโมโนโทนิกก็ต่อเมื่อ สำหรับทุกโหนดnและทุกโหนดถัดไปn'ของnที่สร้างขึ้นโดยการกระทำใดๆaต้นทุนโดยประมาณของการไปถึงเป้าหมายจากnจะไม่เกินต้นทุนของขั้นตอนในการไปถึงn'บวกกับต้นทุนโดยประมาณของการไปถึงเป้าหมายจากn '

ชม.(n)(n,เอ,n)+ชม.(n).{\displaystyle h(n)\leq c\left(n,a,n'\right)+h\left(n'\right).}

นี่เป็นรูปแบบหนึ่งของอสมการสามเหลี่ยมโดยมีn , n'และเป้าหมายG ที่อยู่ใกล้n ที่สุด เนื่องจากฮิวริสติกแบบโมโนโทนิกทุกตัวยังยอมรับได้ ด้วย ดังนั้น ความเป็นโมโนโทนิกจึงเป็นข้อกำหนดที่เข้มงวดกว่าการยอมรับได้ อัลก อริทึมฮิวริสติก บางตัว เช่นA*สามารถพิสูจน์ได้ว่าเหมาะสมที่สุดหากฮิวริสติกที่ใช้เป็นแบบโมโนโทนิก[ 8 ]

ในฟังก์ชันบูลีน

ด้วยฟังก์ชันที่ไม่เป็นไปตามลำดับ "ถ้าaแล้วทั้งbและc " โหนดเท็จ จะปรากฏอยู่เหนือ โหนดจริง
แผนภาพ Hasse ของฟังก์ชันเอกพันธุ์ "อย่างน้อยสองในa , b , cเป็นจริง" สีต่างๆ แสดงค่าผลลัพธ์ของฟังก์ชัน

ในพีชคณิตบูลีนฟังก์ชันโมโนโทนิกคือฟังก์ชันที่สำหรับทุกค่าa และb ใน{0,1}ถ้าa b , a b , ..., a b (กล่าวคือ ผลคูณคาร์ทีเซียน{0, 1} nเรียงลำดับตามพิกัด ) แล้วf( a , ..., a ) ≤ f( b , ..., b )กล่าวอีกนัยหนึ่ง ฟังก์ชันบูลีนเป็นฟังก์ชันโมโนโทนิกก็ต่อเมื่อ สำหรับทุกการรวมกันของอินพุต การเปลี่ยนอินพุตตัวใดตัวหนึ่งจากเท็จเป็นจริง จะทำให้เอาต์พุตเปลี่ยนจากเท็จเป็นจริงเท่านั้น ไม่ใช่จากจริงเป็นเท็จ ในทางกราฟิก หมายความว่า ฟังก์ชันบูลี น n -ary เป็นฟังก์ชันโมโนโทนิกเมื่อการแสดงฟังก์ชันนั้นในรูปของ ลูกบาศก์ nมิติที่กำกับด้วยค่าความจริง ไม่มีขอบขึ้นจากจริงไปเป็นเท็จ ( แผนภาพ Hasseที่มีป้ายกำกับนี้เป็นแผนภาพคู่ขนาน ของ แผนภาพ Vennที่มีป้ายกำกับของฟังก์ชันซึ่งเป็นการแสดงผลที่พบได้บ่อยกว่าสำหรับn ≤ 3 )

ฟังก์ชันบูลีนแบบโมโนโทนิก คือฟังก์ชันที่สามารถกำหนดได้ด้วยนิพจน์ที่รวมอินพุต (ซึ่งอาจปรากฏมากกว่าหนึ่งครั้ง) โดยใช้เฉพาะตัวดำเนินการandและor เท่านั้น (โดยเฉพาะอย่างยิ่งห้าม ใช้ not ) ตัวอย่างเช่น "อย่างน้อยสองในa , b , cเป็นจริง" ( ฟังก์ชันเสียงข้างมากแบบไตร ภาค ) เป็นฟังก์ชันโมโนโทนิกของa , b , cเนื่องจากสามารถเขียนได้ เช่น (( aและb ) หรือ ( aและc ) หรือ ( bและc ))

จำนวนฟังก์ชันดังกล่าวที่มีตัวแปรnตัว เรียกว่าจำนวนเดเดคินด์ของn

การแก้ปัญหา SATซึ่งโดยทั่วไปเป็น งาน NP-hardสามารถทำได้อย่างมีประสิทธิภาพเมื่อฟังก์ชันและตัวบ่งชี้ที่เกี่ยวข้องทั้งหมดเป็นแบบโมโนโทนิกและบูลีน[ 9 ]

ดูเพิ่มเติม

หมายเหตุ

  1. Clapham, Christopher; Nicholson, James (2014). พจนานุกรมคณิตศาสตร์ฉบับย่อของออกซ์ฟอร์ด (  ฉบับที่ 5). สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด.
  2. 1 2 Stover, Christopher. "ฟังก์ชันโมโนโทนิก" . Wolfram MathWorld . สืบค้นเมื่อ2018-01-29 .
  3. 1 2 3 4 5 "ฟังก์ชันโมโนโทน"สารานุกรมคณิตศาสตร์สืบค้นเมื่อ29 มกราคม 2018
  4. 1 2 สปิวัก, ไมเคิล (1994). แคลคูลัส . ฮิวสตัน, เท็กซัส: พับลิช ออร์ เพริช อิงค์ หน้า192. ISBN  0-914098-89-6.
  5. ดูส่วนเกี่ยวกับประโยชน์เชิงปริมาณเทียบกับประโยชน์เชิงลำดับใน Simon & Blume (1994 )
  6. Varian, Hal R. (2010). เศรษฐศาสตร์จุลภาคขั้นกลาง ( ฉบับที่ 8). WW Norton & Company. หน้า56. ISBN   9780393934243.
  7. ถ้าโดเมนมีมากกว่าหนึ่งองค์ประกอบ
  8. เงื่อนไขสำหรับความเหมาะสมที่สุด :การยอมรับได้และความสอดคล้อง หน้า 94–95 ( Russell & Norvig 2010 )
  9. Bayless, Sam; Bayless, Noah; Hoos, Holger H.; Hu, Alan J. (2015). SAT Modulo Monotonic Theories . Proc. 29th AAAI Conf. on Artificial Intelligence. AAAI Press. pp. 3702– 3709. arXiv : 1406.0043 . doi : 10.1609/aaai.v29i1.9755 . เก็บถาวรจากต้นฉบับเมื่อวันที่ 11 ธันวาคม 2023 

บรรณานุกรม

  • บาร์เทิล, โรเบิร์ต จี. (1976). องค์ประกอบของการวิเคราะห์เชิงจริง (  ฉบับพิมพ์ครั้งที่สอง)
  • Grätzer, George (1971). ทฤษฎีแลตติส: แนวคิดเบื้องต้นและแลตติสแบบกระจาย . WH Freeman. ISBN 0-7167-0442-0.
  • เพมเบอร์ตัน, มัลคอล์ม; ราว, นิโคลัส (2001). คณิตศาสตร์สำหรับนักเศรษฐศาสตร์: ตำราเบื้องต้น . สำนักพิมพ์มหาวิทยาลัยแมนเชสเตอร์. ISBN 0-7190-3341-1.
  • เรนาร์ดี, ไมเคิล และ โรเจอร์ส, โรเบิร์ต ซี. (2004). บทนำเกี่ยวกับสมการเชิงอนุพันธ์ย่อย . ตำราคณิตศาสตร์ประยุกต์ 13 (  ฉบับพิมพ์ครั้งที่สอง). นิวยอร์ก: สปริงเกอร์-เวอร์แลก. หน้า 356. ISBN 0-387-00444-0.
  • รีสซ์, ฟริเกซ และเบลา ซโซเคฟัลวี-นากี (1990) การวิเคราะห์เชิงหน้าที่ สิ่งพิมพ์ Courier Dover ไอเอสบีเอ็น 978-0-486-66289-3.
  • Russell, Stuart J.; Norvig, Peter (2010). ปัญญาประดิษฐ์: แนวทางสมัยใหม่ (  ฉบับที่ 3). Upper Saddle River, New Jersey: Prentice Hall. ISBN 978-0-13-604259-4.
  • ไซมอน, คาร์ล พี.; บลูม, ลอว์เรนซ์ (เมษายน 1994). คณิตศาสตร์สำหรับนักเศรษฐศาสตร์ (  ฉบับพิมพ์ครั้งแรก). นอร์ตัน. ISBN 978-0-393-95733-4.(นิยาม 9.31)

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ฟังก์ชันโมโนโทนิก

ใน ทางคณิตศาสตร์ ฟังก์ชัน โมโนโทนิก (หรือ ฟังก์ชันโมโนโทน ) คือ ฟังก์ชัน ระหว่าง เซตที่มีลำดับ ซึ่งรักษาหรือกลับ ลำดับที่ กำหนด [ 1 ] [ 2 ] [ 3 ] แนวคิดนี้เกิดขึ้นครั้งแรกใน...

ในแคลคูลัสและการวิเคราะห์

ใน แคลคูลัส ฟังก์ชัน เอฟ {\displaystyle f} ฟังก์ชันที่กำหนดบน เซตย่อย ของ จำนวนจริง ที่มีค่าเป็นจำนวนจริงเรียกว่า ฟังก์ชันโมโนโทนิก หากฟังก์ชันนั้นไม่ลดลงเลย หรือไม่เพิ่มขึ้นเลย [ 2 ] กล่าวคือ ตามรูปที่ 1...

ฟังก์ชันผกผัน

ฟังก์ชันโมโนโทนิกอย่างเคร่งครัดทั้งหมดสามารถ หาฟังก์ชันผกผันได้ เนื่องจากรับประกันได้ว่าจะมีฟังก์ชันหนึ่งต่อหนึ่งจากช่วงของฟังก์ชันไปยังโดเมนของฟังก์ชัน

การแปลงแบบโมโนโทนิก

คำว่า การแปลงแบบโมโนโทนิก (หรือ การแปลงแบบโมโนโทน ) อาจทำให้เกิดความสับสนได้เช่นกัน เนื่องจากหมายถึงการแปลงโดยฟังก์ชันที่เพิ่มขึ้นอย่างเคร่งครัด ซึ่งเป็นกรณีในทางเศรษฐศาสตร์ที่เกี่ยวข้องกับคุณสมบัติเชิงลำดับของ ฟังก์ชันอรรถประโยชน์...