λ演算与函数式设计语言 有以下函数： Y = λg.((λf.g(f f)) (λf .g(f f)))

Presentation on theme: "λ演算与函数式设计语言 有以下函数： Y = λg.((λf.g(f f)) (λf .g(f f)))"— Presentation transcript:

1 λ演算与函数式设计语言 有以下函数： Y = λg.((λf.g(f f)) (λf .g(f f)))
试证 YF = F (YF)[F是任意函数] 证明： Y F = λg.((λf.g(f f)) (λf .g(f f))) F = (λf.F(f f)) (λf .F(f f)) = F((λf .F(f f))(λf .F(f f))) = F(Y F)

2 2. 利用λ规约法则将下式化到最简 (λp.λq.λr.p q r)(λp.λq.p q r). =(λp.λq.λr.p q r)(λq.r q)[beta] =(λp.λq.λw.p q r) r[yita,alpha] =λq.λw.r q r[beta] =λw.r r[beta] =r

3 逻辑式设计语言 设谓词good(X)表示X是好整数,谓词pow2(Y, Z)表示2的Y次方为Z.根据以下公理证明1020是个好整数.
f1 good(0) f2 pow2(0, 1) r3 good(A-2)←good(A) r4 good(A+2)←good(A) r5 good(A*2)←good(A) r6 good(A)←pow2(P,A), good(P) r7 pow2(P+1, A*2)←pow2(P,A)

4 s1 good(2) f1和r4 s2 good(4) s1和r5 s3 good(8) f2和r5 s4 good(16) s3和r5 s5 good(32) s4和r5 s6 good(64) s5和r5 s7 good(128) s6和r5 s8 good(256) s7和r5 s9 good(512) s8和r5 s10 good(1024) s9和r5 s11 good(1022) s10和r3 s12 good(1020) s11和r3

5 2.用prolog写出完整的矩阵相乘程序. 方法一: %第二个矩阵转置 matrix_mul(X,Y,Z)：-trans(Y,Y1),mmultiply(X,Y1,Z). %将矩阵分解成向量的list和向量，调用multiply做list与向量乘 mmultiply([],_,[]). mmultiply([V0|Rest],V1,[Result|Others]):-mmultiply(Rest,V1,Others), multiply(V1,V0,Result). multiply([],_,[]). multiply([V0|Rest],V1,[Result|Others]):-multiply(Rest,V1,Others), vmul(V1,V0,Result). %向量乘 vmul([],[],0). vmul([H1|T1],[H2|T2],Result):-vmul(T1,T2,Newresult), Result is H1*H2+Newresult.

6 firstCol([[H|T\|Tail],[H|Col],[T|Rows]):- firstCol(Tail,Col,Rows).
%矩阵转置 trans([],[]). trans([[H|T]|Tail],[[H|NT]|NTail]):-firstCol(Tail,NT,Rest), trans(Rest,NRest), firstCol(NTail,T,NRest). firstCol([],[],[]). firstCol([[H|T\|Tail],[H|Col],[T|Rows]):- firstCol(Tail,Col,Rows).

7 方法二 domains Vt=integer * Vm_Multi(L1,[H2|T2],[H3|T3]) :- Ut=integer *
predicate form_Vector(Vt,integer) form_Matrix(Ut,integer,integer) Matrinx_Multi(Ut,Ut,Ut) Vm_Multi((Vt,Ut,Ut) Vector_Multi((Vt,Vt,integer) Main_fun(Ut) Clavses form_Vector([H|T],X):-0 readist(H), form_Vector(T,X-1), form_Vector([],0). Matrix_Multi([H|T],L2,[H3|T3]):- Vm_Multi(H1,L2,H3). Matrix_Multi(T1,L2,T3). Matrix_Multi([],_,[]). Matrix_Multi(_,[],[]). Vm_Multi(L1,[H2|T2],[H3|T3]) :- Vector_Multi(L1,H2, H3). Vm_Multi(L1,T2, T3) . Vm_Multi([],_, []). Vm_Multi(_,[], []). Vector_Multi([H1|T1,[H2|T2],[H3|T3]) :- S1=H1*H2, Vector_Multi(T1, T2,S2) :- S=S1+S2. Vector_Multi([],_,0). Mach_fun(l):- Readint(X,) Readint(Y), X>0,Y>0, form_Matrix(L1,X,Y), form_Matrix(L2,X,Y), Matrix_Multi(L1,L2,L).

8 总结prolog中的cut用法，怎样是安全的，怎样是不安全的？
用法： 当获得正确解，停止求解防止回溯； 一个子句匹配后不再试图匹配其他子句，提高效率； 与预定义谓词fail结合，对一个目标求解立即失败，放弃对其他子句的选择。 安全：仅仅用于提高效率的cut操作,不会去掉所有解，破坏证明完整性； 不安全：用于表达选择和循环等控制逻辑的cut操作，cut掉仅有的解，破坏证明的完整性。