Математическая логика и теория алгоритмов

Ìàòåìàòè÷åñêàÿ ëîãèêà è òåîðèÿ àëãîðèòìîâ. Ëåêöèÿ 2 2020 ÌËÒÀ. Ëåêöèÿ 2 2020 1 / 32 Îïåðàòîð ìèíèìèçàöèè Îïðåäåëåíèå n  ìåñòíûì ïðåäèêàòîì Pˆx1 , . . . , xn , çàäàííûì íà ìíîæåñòâàõ M1 , . . . , Mn , íàçûâàåòñÿ âñÿêîå ïðåäëîæåíèå, ñîäåðæàùåå n ïðåäìåòíûõ ïåðåìåííûõ x1 , . . . , xn , êîòîðîå ïðè çàìåíå êàæäîãî xi ýëåìåíòîì ai > Mi ˆi 1, . . . , n ïðåâðàùàåòñÿ â èñòèííîå èëè ëîæíîå âûñêàçûâàíèå. Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ïðåäèêàòà: χP ˆx1 , . . . , xn  œ 1, SPˆx1 , . . . , xn S 0, SPˆx1 , . . . , xn S 1 ˆPˆx1 , . . . , xn  èñòèíà 0 ˆPˆx1 , . . . , xn  ëîæü Ïðåäèêàò íàçûâàåòñÿ ïðèìèòèâíî-ðåêóðñèâíûì, åñëè åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ïðèìèòèâíî-ðåêóðñèâíàÿ. ÌËÒÀ. Ëåêöèÿ 2 2020 2 / 32 Îïåðàòîð ìèíèìèçàöèè Îïðåäåëåíèå Ôóíêöèÿ f ˆx1 , . . . , xn  ïîëó÷àåòñÿ îïåðàòîðîì ìèíèìèçàöèè èç ïðåäèêàòà Pˆx1 , . . . , xn , z, åñëè â ëþáîé òî÷êå ˆx1 , . . . , xn  çíà÷åíèåì ôóíêöèè f ˆx1 , . . . , xn  ÿâëÿåòñÿ ìèíèìàëüíîå çíà÷åíèå z, îáðàùàþùåå ïðåäèêàò Pˆx1 , . . . , xn , z â èñòèíó. Îáîçíà÷åíèå: f ˆx 1 , . . . , x n  µz ˆPˆx1 , . . . , xn , z. ÌËÒÀ. Ëåêöèÿ 2 2020 3 / 32 Îïåðàòîð ìèíèìèçàöèè Çàìå÷àíèå Äëÿ òîãî, ÷òîáû äëÿ ëþáîãî ïðåäèêàòà Pˆx1 , . . . , xn , z íàéòè ìèíèìàëüíîå çíà÷åíèå z, îáðàùàþùåå Pˆx1 , . . . , xn , z â èñòèíó, íóæíî ïîñëåäîâàòåëüíî ïåðåáèðàòü çíà÷åíèÿ z 0, 1, 2, . . . . int f(int x1,..., int xn) ˜ int z=0; while (P(x1,...,xn,z)==0) z++; return z;  ÌËÒÀ. Ëåêöèÿ 2 2020 4 / 32 Îïåðàòîð ìèíèìèçàöèè Ïðèìåð Ðàññìîòðèì f ˆx µy ˆ2 y x  4. Âû÷èñëèì çíà÷åíèå f ˆ0: y 0, 2 0 x 0  4, SPˆ0, 0S 0, y 1, 2 1 x 0  4, SPˆ0, 1S 0, y 2, 2 2 0  4, SPˆ0, 2S 1, çíà÷èò, f ˆ0 2. Âû÷èñëèì çíà÷åíèå f ˆ1: y 0, 2 0 x 1  4, SPˆ0, 0S 0, y 1, 2 1 x 1  4, SPˆ0, 1S 0,. . . y n, 2 n x 1  4, SPˆ0, nS 0 äëÿ ëþáîãî çíà÷åíèÿ n > N, çíà÷èò, ôóíêöèÿ f ˆx íå îïðåäåëåíà â òî÷êå x 1. ÌËÒÀ. Ëåêöèÿ 2 2020 5 / 32 Îïåðàòîð ìèíèìèçàöèè Çàìå÷àíèå Ñ ïîìîùüþ îïåðàòîðà ìèíèìèçàöèè èç ïðèìèòèâíî-ðåêóðñèâíûõ ôóíêöèé ìîæíî ïîëó÷èòü íå âñþäó îïðåäåëåííûå ôóíêöèè, ïîýòîìó îïåðàòîð ìèíèìèçàöèè âûâîäèò èç êëàññà ïðèìèòèâíî-ðåêóðñèâíûõ ôóíêöèé. ÌËÒÀ. Ëåêöèÿ 2 2020 6 / 32 Îãðàíè÷åííûé îïåðàòîð ìèíèìèçàöèè Îïðåäåëåíèå Ôóíêöèÿ f ˆx1 , . . . , xn  ïîëó÷àåòñÿ îãðàíè÷åííûì îïåðàòîðîì ìèíèìèçàöèè èç ïðåäèêàòà Pˆx1 , . . . , xn , z è ãðàíè÷íîé ôóíêöèè U ˆx1 , . . . , xn , åñëè â ëþáîé òî÷êå çíà÷åíèå ýòîé ôóíêöèè îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: 1) ñóùåñòâóåò z @ U ˆx1 , . . . , xn  òàêîå, ÷òî SPˆx1 , . . . , xn , zS 1, òîãäà f ˆx 1 , . . . , x n  µz ˆPˆx1 , . . . , xn , z; 2) íå ñóùåñòâóåò z @ U ˆx1 , . . . , xn  òàêîå, ÷òî SPˆx1 , . . . , xn , zS 1, òîãäà â êà÷åñòâå çíà÷åíèÿ ôóíêöèè ïðèíèìàåòñÿ çíà÷åíèå ãðàíè÷íîé ôóíêöèè f ˆx1 , . . . , xn  U ˆx1 , . . . , xn . Îáîçíà÷åíèå: f ˆx1 , . . . , xn  µz@U ˆx1 ,...,xn  ˆPˆx1 , . . . , xn , z. ÌËÒÀ. Ëåêöèÿ 2 2020 7 / 32 Îãðàíè÷åííûé îïåðàòîð ìèíèìèçàöèè Çàìå÷àíèå Åñëè â îïðåäåëåíèè îãðàíè÷åííîãî îïåðàòîðà ìèíèìèçàöèè îòíîøåíèå z @ U ˆx1 , . . . , xn  çàìåíèòü íà z B U ˆx1 , . . . , xn , çíà÷åíèå ôóíêöèè f ˆx1 , . . . , xn  íå èçìåíèòñÿ. int f(int x1, ... ,int xn) ˜ int z=0; while (!P(x1,...,xn,z) && (z