定理設t(n)是乙個函式，t(n)>=n,則每乙個t(n)時間的多帶圖靈機都和某乙個o(t2(n))時間的單帶圖靈機等價
設t(n)是乙個函式，t(n)>=n,則每乙個t(n)時間的非確定型單帶圖靈機都與某乙個2 o(t(n))時間的確定型單帶圖靈機等價
定義 p是確定型單帶圖靈機在在多項式時間內可判定的語言類，換言之：p1）對於所有與確定型單帶圖靈機多項式的等價的計算模型來說，p是不變的2）p大致對應於在計算機上時即可解的那一類問題
定理path屬於p
證明 path的乙個多項式時間演算法m執行如下：
m=「對輸入,g是包含結點s和t的有向圖：1)在結點s上做標記2）重複下面步驟3，知道不再有節點被標記3）掃瞄g的所有邊，如果找到一條邊(a,b),a被標記而b沒有標記，那麼標記b4）若t被標記，則接受；否則，拒絕」分析該演算法，證明他在多項式時間內執行，顯然，步驟1和4只執行一次，步驟3最多執行m此，因為出最後一次外，每一次執行都要標記g中的乙個未標記的結點，所以用到的總步驟數最多是1+1+m，是g的規模的多項式，m的步驟1和4很容易用任何合理的確定型模型在多項式時間內實現，捕捉3需要掃瞄輸入，檢查某些結點是否被標記，這也容易在多項式時間內實現，所以m是path的多項式時間演算法
定理 relprime屬於p 歐幾里德演算法
證明歐幾里德演算法e如下：e=「對輸入，x和y是二進位制表示的自然數：1）重複下面的操作，知道y=0 2）賦值x←x mod y3）交換x和y的值 4）輸出x」算反r以e為子程式求解relprime，r=」對輸入x和y是二進位制表示的自然數：
1）在上執行e， 2）若結果為1，就接受；否則，就拒絕」顯然，若e在多項式時間內執行且正確，則r也在多項式時間內執行且正確，所以只需分析e的時候和正確性，步驟2的每一次執行（除了第一次有可能例外）都把x的值至少減少一半，執行步驟2以後，由函式mod的性質知xy因為這兩個值已經交換，於是當步驟2隨後執行時有x>y，若x/2>=y,則x mod y根號n正則的《上下文無關的《可判定的《圖靈可識別的
定理：adfa是乙個可判定語言
證明：首先檢查輸入，他表示輸入串w和dfa b，b的乙個合理的表示方法是簡單地列出它的五個元素q,∑,δ,q0及f，當m收到輸入時，首先檢查他是否正確地表示了dfa b和串w，如果不是，則拒絕。
然後m直接執行模擬，用在帶上寫下資訊的方法，他可以跟蹤b在輸入m上執行時的當前狀態和當前位置，執行開始時，b的當前狀態時q0，讀寫頭的當前位置是w的最左端符號，狀態和位置的更新是由轉移函式決定的，當m處理完w的最後乙個符號時，如果b處於接受狀態，則m接受這個輸入，如果不是，則m拒絕
定理：anfa是乙個可判定語言
證明：構造乙個判定anfa的tm n ，用m作為n的子程式，因為m被設計成只接受dfa作為輸入，故n先將作為輸入所受到的nfa轉換成dfa，然後再將它傳給m
n=「對於輸入,其中b是nfa，w是串：
1） 將nfa b 轉換成乙個等價的dfa c
2） 再輸入上像上面定理一樣執行tm m
3） 如果m解說，則接受，否則拒絕」
定理：arex是乙個可判定語言(正規表示式是否派生乙個給定的串)
證明下面的圖靈機判定arex，
p=「在輸入上，其中r是正規表示式，w是串：
1） 將正規表示式r轉換成乙個與之等價的nfa a
2） 再輸入上執行tm n
3） 如果n接受，則接受；如果n拒絕，則拒絕「
定理：edfa是乙個可判定語言(空性質測試)
證明 dfa接受乙個串當且僅當：從騎士裝他i出發，沿著此dfa的箭頭方向，能夠到達乙個接受狀態，為檢查這個條件，設計乙個使用標記演算法的tm t
t=「對於輸入,其中a是乙個dfa:
1) 標記a的起始狀態
2) 重複下列步驟，直到所有狀態都被標記
3) 對於乙個狀態，如果有乙個到達他的轉移是從某個已經標記過的狀態出發的，則將其標記
4) 如果沒有接受狀態被標記，則接受，否則拒絕「
定理：eqdfa是乙個可判定語言(檢查兩個dfa是否識別同乙個語言)
證明下面由a和b來構造乙個新的dfa c 使得c只接受這樣額串：a或b接受但不是都接受，這樣如果a和b識別相同的語言，則c什麼串也不接受，c的語言是l(c)=l（a） 交非l(b)並非 l（a）交l(b)，因為正則語言了i再補，並和交下是封閉的，檢查l（c） 是否為空，如果是空的l(a)和l(b)必定相等
f=「對於輸入,氣宗a和b都是dfa
1） 如上面數那樣構造dfa c
2） 再輸入上檢查l（c）是否為空
3） 如果t接受，則接受；如果t拒絕，則拒絕「
定理：acfg是乙個可判定語言
證明識別acfg的tm s如下：
s=「對於輸入其中，g是乙個cfg，w是乙個串
1) 將g轉換成乙個與之等價的喬姆斯基文法
2) 列出所有2n-1步的派生其中n是w的長度，除非n=0，此時列出一步以內的派生
3) 如果這些派生中有乙個產生w，則接受；如果沒有，則拒絕「
定理：ecfg是乙個可判定語言（檢查乙個cfg是否不派生任何串）
證明 r=「對於輸入，其中g是乙個cfg
1）將g中所有的終結符的全都作上標記，重複下列步驟，直到找不到可以做標記的變元
2）重複下列步驟，直到找不到可以做標記的變元
3）如果g有規則a→u1u2…uk，且u1，u2，…uk中的每個符號都已被做過標記，則將變元a做標記
4）如果起始狀態沒有被標記，則接受；否則拒絕「
eqcfg是不可判定的
定理：每個上下文無關語言都是可判定的
證明設g是a的乙個cfg，下面設計乙個判定的tm mg他在自己內部建立g的乙個備份，其工作方式如下：
mg=」對於輸入w：
1） 再輸入上執行tm s
2） 如果該機器接受，則接受；否則拒絕」
定理 halttm是不可判定的（確定乙個圖靈機對給定的輸入是否停機）
證明為了得到矛盾，假設tm r判定halttm,由之可以構造tm s來判定atm,其構造如下：
s=「再輸入上，此處 是tm m的和串w的編碼：
1） 在輸入 上執行tm r
2） 如果r拒絕，則拒絕
3） 如果r接受，則在w上模擬m，直到他停機
4） 如果m已經接受，則接受；如果m已經拒絕，則拒絕「
顯然，如果r判定halttm，則s判定atm，因為atm是不可判定的，故halttm也必定是不可判定的
定理 etm是不可判定的(圖靈機不接受任何串l(m)=ф)
證明 m1=」再輸入x上：
1）如果x不等於w，則拒絕2）如果x=w則在x上執行m，當m接受時，就接受」
這個機器以w作為他的描述的一部分，檢查x=w是否成立的方法很顯然，即掃瞄輸入並且乙個字元乙個字元第將他與w進行比較，就可確定他們是否相同，在假設tm r判定etm，如下構造判定atm的tm s：
s=「再輸入上，此處 是tm m的和串w的編碼：
1） 用m和w的描述來構造上述tm m12）再輸入上執行r3）如果r接受，則拒絕；如果r拒絕，則接受「如果r是etm的判定其，則s就是atm的判定其，而後者是不存在的，故我們知道etm必定是不可判定的
定理 regulartm是不可判定的（測定乙個給定的圖靈機是否有乙個與之等價的有窮自動機問題）
證明設r是判定regulartm的乙個tm ,下面構造判定atm的tm s，s的執行方式如下：
s=「對於輸入其中m是tm，w是串：
1） 構造下述tm m2：m2=」再輸入x上：a）如果x具有形式0n1n，則接受b）如果x不具有此形式，則在輸入w上執行m，如果m接受w，則接受」2）再輸入上執行r3）如果r接受，則接受；如果r拒絕，則拒絕」
定理 eqtm是不可判定的
證明設tm r判定eqtm，如下構造判定etm 的tm s：
s=「對於輸入,其中m是tm：1）在輸入上執行r，其中m1是拒絕所有輸入的圖靈機2）如果r接受；則接受；如果r拒絕，則拒絕」
如果r判定eqtm，則s判定etm，但etm是不可判定的，故eqtm也必定是不可判定的
定理如果a《mb且b是可判定的，則a也是可判定的
證明設m是b的判定其，f是a都b的歸約，a的判定器n的描述如下：n=「對於輸入w：1）計算f（w）2）在f（w）上執行m，輸出m的輸出」顯然，如果w屬於a則f（w）屬於b，因為f是從a到b的歸約，因此，只要w屬於a，則m接受f(w)，故n的執行正如所求
遞迴定理設t是計算函式t：∑**∑*→∑*的乙個圖靈機，則存在計算函式r：∑*→∑*的乙個圖靈機r，是的對每乙個w，有r(w)=t(,w)
定理乙個語言在np中，當且僅當它能被某個非確定型多項式時間圖靈機判定
證明對於該定理從左向右的方向，設a屬於np，要證a被多項式時間ntm n判定，由np的定義，存在a的多項式時間驗證機v，假設v是乙個在時間nk內執行的tm，構造n如下：n=「對長為n的輸入w： 1）非確定地選擇最長為nk的字串c2）再輸入上執行v3）若v接受，則接受,否則拒絕」為了證明該定理的另乙個方向，假設a唄多項式時間ntm n判定，構造多想時間驗證機v如下：
v=「對輸入,這裡w，c是字串:1)在輸入w上模擬n，把c的每乙個符號看做是對每一步所做的非確定性選擇的描述2）若n的計算分支接受，則接受；否則，拒絕」
定理 clique屬於np
證明下面是clique的驗證機v v=「對輸入<,c>: 1）檢查c是否是g中k個結點的集合2）檢查g是否包含連線c終結點的所有邊3）若兩項檢查都通過，則接受；否則，拒絕」
定義如果語言b滿足下面兩個條件，就稱為np完全的：1）b屬於np並且2）np中的每個a都多項式時間可歸約到b
定理若上述的b是np完全的，且b屬於p，則p=np
定理若上述的b是np完全的，且b《=pc，c屬於np，則c是np完全的
薩維奇定理對於任何函式f：n→r+,其中f(n)>=n,nspace(f(n))包含於space(f2(n))
牛頓定理經典例題
第二單元 牛頓定律 內容和方法 本單元內容包括力的概念及其計算方法，重力 彈力 摩擦力的概念及其計算，牛頓運動定律，物體的平衡，失重和超重等概念和規律。其中重點內容重力 彈力和摩擦力在牛頓第二定律中的應用，這其中要求學生要能夠建立起正確的 運動和力的關係 因此，深刻理解牛頓第一定律，則是本單元中運用...
動能定理經典例題
1 質量為500t的機車以恆定的功率由靜止出發，經5min行駛2.25km，速度達到最大值54km h，設阻力恆定且取g 10m s2 求 1 機車的功率p 2 機車的速度為36km h時機車的加速度a 2 如圖4所示，ab為1 4圓弧軌道，半徑為r 0.8m，bc是水平軌道，長s 3m，bc處的摩...
命題 定理 證明
一 教法建議 拋磚引玉 本單元的主要內容是命題，定理和證明。在教學時，通過學生學習的一些命題和證明的定理，向學生介紹一些簡單的邏輯知識，邏輯的概念和術語，但不要在這些概念和術語上下功夫，能初步掌握就可以了，結合學生學過的圖形的性質和判定，用具體的例子說明什麼是命題，命題的組成和命題的真假，要講清楚這...