PageSourceSearch

https://lektsia.com/1x538.html

html lektsia.com collected 2026-10-02 16:46:34 UTC 49,993 bytes, 430 lines download raw bytes

1
2
3<!DOCTYPE html>
4<html>
5<head>
6<meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
7    <meta name="viewport" content="width=device-width, initial-scale=1">
8<meta name="description" content="6. Полученная схема называется решеткой с р входами и q выходами элементов &, которая определяется матрицей соединений (cih)"><title>Программируемые логические матрицы</title>
9<link rel="icon" href="/img/icon.ico" type="image/x-icon">
10<link rel="shortcut icon" href="/img/icon.ico" type="image/x-icon">
11
12
13
14
15
16<style>
17
18img {
19    max-width: 100%;
20    height: auto;      
21}
22
23body {
24 font-family:Verdana, Arial; background: #FFF; color:#424242; font-size:14px;
25}
26p {font-family:Verdana, Arial, sans-serif; font-size:16px;color:#424242; margin:15px;}
27h1{color:#0404B4; margin-left: 30px; font-size:22px;}
28h2{color:#2E64FE; margin: 20px; font-size:18px; border-bottom:solid 1px #B99400; }
29h3,h4,h5,h6{color:#2E64FE; margin: 20px; font-size:18px; border-bottom:solid 1px #B99400;}
30
31
32
33a:link { cursor: pointer; color: #0000FF; text-decoration: underline; }
34ul {list-style: square;}
35
36.divhead{ background: #FFF; }
37.divcenter{ background: #F0F0F0; }
38a.nd{ 
39	font-size:13px;
40	color: #0000FF;
41    text-decoration: underline;
42	padding: 1px 3px 1px 10px;
43}
44a.nd:hover {
45	color: #FF0000;
46}
47.nizpravo{ font-size:12px; color: #555; }
48pre{overflow:auto;}
49.anizpravo{ color: #0000FF; font-size:12px;}
50
51.littletext{ color:#666; font-size:10px;}
52a.littletext{  color:#666; font-size:10px;}
53
54
55
56 .link1{
57border: 1px solid #7188FF;
58 background: #fefcea; /
59    background: linear-gradient(to top, #FFF, #BFD4FF);
60width:90%;
61color: #900000; 
62font-size:11pt; 
63}
64
65.link2{border: 1px solid #7188FF; width: 90%; text-align:left;}
66.link2 p{margin-left:10px;}
67.link2 a {
68    color: #0a49be;;
69    font-size:10pt;
70    font-weight:bold;
71	margin:20px;
72   }
73
74.link2 a:hover { text-decoration: none; color: #000060;  }
75
76
77.pagelink {  margin-left: 20px; font-size:11.5pt; }
78        
79.pagelink a {
80    text-decoration: none;
81	background:#fff;
82	border: solid 1px #AAE;
83	color: #15B;
84	text-align:center;
85}
86
87.pagelink a, .pagelink span {
88    display: block;
89    float: left;
90    padding: 0.3em 0.5em;
91    margin-right: 5px;
92	margin-bottom: 5px;
93	min-width:1em;
94	text-align:center;
95}
96
97.pagelink .current {
98    color: #AAA;
99	font-weight:bold;
100}
101.pagelink .back_link {display: inline-block; border: 1px solid; padding: 3px; margin-top: 0px; text-decoration: none; left: 250px;}
102
103.pagelink a:hover {color:#000; border: solid 1px #FE9A2E; 
104text-shadow: 1px 1px 5px #FE9A2E, 0 0 0.1em #FE9A2E; /* Параметры тени */
105}
106.pagelink .next_link {display: inline-block; border: 1px solid; padding: 3px; margin-top: 0px; text-decoration: none; right: 100px;}
107
108
109.pagelink a:hover {color:#000; border: solid 1px #FE9A2E; 
110text-shadow: 1px 1px 5px #FE9A2E, 0 0 0.1em #FE9A2E; /* Параметры тени */
111}
112.pagelink .next_linkmob {display: inline-block; border: 1px solid; padding: 3px; margin-top: 0px; text-decoration: none; right: 10px;}
113.pagelink .back_linkmob {display: inline-block; border: 1px solid; padding: 3px; margin-top: 0px; text-decoration: none; left: 10px;}
114
115
116
117 </style>
118
119<!-- Yandex.RTB -->
120<script>window.yaContextCb=window.yaContextCb||[]</script>
120
121
122</head>
123
124<body id="top" style="font-size: 100%;">
125
126
127<!-- Yandex.RTB R-A-2158804-26 -->
128<script>
129window.yaContextCb.push(()=>{
130	Ya.Context.AdvManager.render({
131		"blockId": "R-A-2158804-26",
132		"type": "fullscreen",
133		"platform": "desktop"
134	})
135})
136</script>
136
137
138
139            
139<script src="https://partner-widget.vse-sdal.com/assets/builds/js/partner_widget/chat.min.js"></script>
139
140            <iframe 
141                id="vsesdal-chat"
142                src="https://partner-widget.vse-sdal.com/chat?ref=1666204"
143                style="border: none; max-width: 100%; margin: auto; display: none; position: fixed; right: 0; bottom: 0;" width="354" height="430">
144            </iframe>
145
146
147<div class="divhead">
148<table width="950" border="0" cellpadding="0" cellspacing="0" align="center" bgcolor="#FFF" >
149<tr>
150    <td width="220" valign="top" class="leftblock">
151	<a href="/"><img src="/img/lektsia.jpg" align="top"></a>
152</td>
153    <td valign="top">
154	<a href='/4/' class='nd'>Архитектура</a> <a href='/6/' class='nd'>Аудит</a> <a href='/11/' class='nd'>Военная наука</a> <a href='/20/' class='nd'>Иностранные языки</a> <a href='/38/' class='nd'>Медицина</a> <a href='/40/' class='nd'>Металлургия</a> <a href='/41/' class='nd'>Метрология</a> <br><a href='/45/' class='nd'>Образование</a> <a href='/49/' class='nd'>Политология</a> <a href='/54/' class='nd'>Производство</a> <a href='/56/' class='nd'>Психология</a> <a href='/63/' class='nd'>Стандартизация</a> <a href='/67/' class='nd'>Технологии</a>	
155
156 </td>
157</tr>
158</table>
159	</div>
160	<br>
161
162<div class="divcenter">
163<br>
164<table width="950" border="0" cellpadding="0" cellspacing="0" align="center" bgcolor="#FFF" >
165 <tr>
166    <td valign="top">
167	<div class="divobvodka">
168 <h1>Программируемые логические матрицы</h1>
169
170<div class="pagelink" ><a href="/1x537.html" class="back_linkmob">&lArr; Предыдущая</a><span class="currentmob">Стр 16 из 27</span><a href="/1x539.html" class="next_linkmob">Следующая &rArr;</a></div><br><br><table width="450" border="0" align="left" cellpadding="5" cellspacing="5"><tr><td>
171</td><td valign = "top">
172<center>
173
174<!-- Yandex.RTB R-A-2158804-10 -->
175<div id="yandex_rtb_R-A-2158804-10"></div>
176<script>window.yaContextCb.push(()=>{
177  Ya.Context.AdvManager.render({
178    renderTo: 'yandex_rtb_R-A-2158804-10',
179    blockId: 'R-A-2158804-10'
180  })
181})</script>
181
182
183</center>
184
185</td></tr></table><p>Рассмотрим схему, состоящую из <i>р</i> входов <i>z </i>1, ..., <i>zp</i>и <i>q </i>выходов <i>g </i>1, …, <i>g q</i> (рис. 6.28), в которой значения выходов определяются <i>матрицей соединений</i> (<i>cih</i>), 1 &#8804; <i>i </i>&#8804; <i>p </i>, 1 &#8804; <i>y </i>&#8804; <i>q </i>, <i>cih</i>&#8712; {0, 1} по следующим правилам <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image669.gif" /> Таким образом, <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image671.gif" /> где <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image673.gif" />, а остальные <i>cih</i>= 0. Полученная схема называется <i>решеткой с р входами и q выходами элементов </i>&amp;, которая определяется матрицей соединений (<i>cih</i>).</p>
186 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image675.gif" /></p>
187 <p><strong> Рис. 6.28</i> </strong> </p>
188 <p><i>Программируемой логической матрицей </i>(ПЛМ) называется изображенная на рис. 6.29 схема, получающаяся соединением решетки <i>А </i>с 2<i>n </i>входами и <i>k </i>выходами, определяемой матрицей соединений (<i>aih</i>), и решетки <i>В</i> с <i>k </i>входами и <i>т </i>выходами, определяемой матрицей соединений (<i>bhj</i>).</p>
189 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image677.jpg" /></p>
190 <p><strong> Рис. 6.29</i> </strong> </p>
191 <p>Опишем преобразования, которые происходят при прохождении через ПЛМ значений переменных <i>x </i>1, <i>x </i>2, …, <i>xn</i>. Поскольку к каждому входу <i>xi</i>присоединен инвертор <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image585.gif" />, на 2<i>n </i>входов решетки <i>А </i>подаются значения переменных <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image679.gif" /></p>
192 <p>После прохождения решетки <i>A h </i>-й выход принимает значение функции <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image681.gif" />, а последующей операции инвертирования соответствует функция</p>
193 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image683.jpg" /></p>
194 <p>Полученные <i>k </i>значений (1 &#8804; <i>h </i>&#8804; <i>k </i>) подаются на входы решетки <i>B </i>, после прохождения которой на выходе <i>j </i>образуется значение функции</p>
195 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image685.jpg" /></p>
196 <p>В заключение после инвертирования по законам де Моргана на выходе <i>j </i>получаем значение функции <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image687.gif" /> <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image688.gif" />, <i>j </i>= 1, …, <i>m </i>. Функции <i>fi</i>соответствует дизъюнкция конъюнктов (определяемых формулами <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image689.gif" /> ) таких, что <i>bhj</i>= 1.</p>
197 <p>Таким образом, при соответствующем выборе матриц (<i>aih</i>) и (<i>bhj</i>) можно одновременно реализовать <i>m </i>произвольных ДНФ, содержащих не более <i>k </i>различных конъюнктов переменных от <i>x </i>1, <i>x </i>2, …, <i>xn</i>.</p>	<center>
198<!-- Yandex.RTB R-A-2158804-6 -->
199<div id="yandex_rtb_R-A-2158804-6"></div>
200<script>window.yaContextCb.push(()=>{
201  Ya.Context.AdvManager.render({
202    renderTo: 'yandex_rtb_R-A-2158804-6',
203    blockId: 'R-A-2158804-6'
204  })
205})</script>
205
206</center>
207 <p><i>Цит. по: Элементы дискретной математики: учебник / <br> С.В. Судоплатов, Е.В. Овчинникова. — М.: ИНФРА-М; <br> Новосибирск: НГТУ, 2003. — С. 172–210. — (Серия «Высшее образование»). </i></p>
208						<p><strong> Тема 2. Логика предикатов </strong> </p>
209						
210						<p><strong> Предикаты. Кванторы </strong> </p>
211						<p>В текстах естественного языка часто встречаются повествовательные предложения, не являющиеся высказываниями, например эти предложения могут иметь неопределенные параметры. Например, такие предложения, как «У девочки красивая коса», «Число <i>х</i> — простое», «<i>х + у</i> = <i>z </i>».</p>
212 <p>Если в такие предложения вместо параметров (переменных) поставить конкретную девочку и конкретные числа <i>х</i>, <i>у</i>, <i>z </i>, то получим высказывания, которые станут истинными или ложными, например «У Веры красивая коса», «Число 17 простое» или «7 + 8 = 9» и т. п.</p>
213 <p>Повествовательные предложения с параметрами называются предикатами.</p>
214 <p><strong> Определение 9.1 </strong> (<i>предиката</i> ). Функция <i>Р</i> (<i>х</i> 1, ..., <i>хп</i>), определенная на некотором множестве <i>М</i> и принимающая одно из двух значений: И (истина) или Л (ложь): </p>
215 <p><i>P </i>: <i>M </i>&#8594; {И, Л}, </p>
216 <p>называется <i>п-местным предикатом</i>.</p>
217 <p>Множество <i>М</i> часто задано по умолчанию обычным математическим контекстом.</p>
218 <p>Предикаты обозначаются прописными буквами латинского алфавита с перечислением всех переменных. Иногда бывает удобно указывать число независимых переменных предиката верхним индексом</p>
219 <p>Рассмотренные высказывания — нуль-местные предикаты. Поэтому логика предикатов, как частный случай, включает в себя логику высказываний.</p>
220 <p>Над предикатами можно производить обычные логические операции. В результате будут получаться новые предикаты. Тем самым логика предикатов является алгеброй предикатов.</p><center>
221<!-- Yandex.RTB R-A-2158804-7 -->
222<div id="yandex_rtb_R-A-2158804-7"></div>
223<script>window.yaContextCb.push(()=>{
224  Ya.Context.AdvManager.render({
225    renderTo: 'yandex_rtb_R-A-2158804-7',
226    blockId: 'R-A-2158804-7'
227  })
228})</script>
228
229</center>
230 <p><strong> Пример 9</i></strong>.<strong> <i>1</i></strong>. Пусть <i>Р</i> (1)(<i>х</i> ) — предикат «<i>х</i> делится на два»; <i>Q </i>(1)( <i>x </i>) — предикат «<i>х</i> делится на три».</p>
231 <p>Тогда выражение</p>
232 <p><i>Р </i>(1)(<i>х</i> ) &amp; <i>Q </i>(1)( <i>x </i>)</p>
233 <p>означает: «<i>х</i> делится на два и <i>х</i> делится на три», т. е, это выражение определяет предикат «<i>х</i> делится на шесть».</p>
234 <p>Аналогичным образом можно использовать все логические связки логики высказываний: </p>
235 <p>&amp;, &#8744; , &#8969; , &#8658; , ~.</p>
236 <p>Кроме операций алгебры высказываний в алгебре предикатов имеются еще две дополнительные — операции связывания переменных кванторами. О кванторах уже говорили и использовали их для краткости записи и удобства в определениях и формулировках теорем. Теперь введем эти понятия как унарные операции алгебры предикатов.</p>
237 <p><strong> Определение 9.2 </strong> (<i>квантора общности</i> ). Пусть <i>Р</i> (<i>х</i> ) — некоторый предикат, принимающий значения И или Л для каждого <i>х</i> множества <i>М</i>. Под выражением ( &#8704; <i>x </i>) <i>P </i>( <i>x </i>) будем подразумевать высказывание истинное, когда <i>Р</i> (<i>х</i> ) истинно для каждого элемента <i>х</i> из множества <i>М</i>, и ложное — в противном случае. Читается оно: «для всех <i>х Р</i> (<i>х</i> )». Этот новый предикат уже не зависит от <i>х</i>, т. е. является высказыванием. Символ &#8704; называется<strong> <i>квантором общности</i></strong>, а переменная <i>х</i> называется<strong> <i>связанной</i> </strong> (квантором). Несвязанные квантором переменные обычно называются<strong> <i>свободными</i></strong>. </p>
238 <p><strong> Определение 9.3 </strong> (<i>квантора существования</i> ). Пусть <i>Р</i> (<i>х</i> ) — некоторый предикат. Под выражением ( &#8707; <i>х </i>)<i>Р</i> (<i>х</i> ) будем понимать высказывание истинное, когда существует элемент множества <i>М</i>, для которого <i>Р</i> (<i>х</i> ) истинно, и ложное — в противном случае. Читается это выражение так: «существует <i>х</i> такое, что <i>Р</i> (<i>х</i> )», или «существует <i>х</i>, для которого <i>Р</i> (<i>х</i> )». Полученный новый предикат тоже не зависит от <i>х</i> и является высказыванием. Символ &#8707; называется<strong> <i>квантором существования</i></strong>, а переменная <i>х</i> — <i>связанной</i> (квантором). Несвязанные квантором переменные обычно называют<strong> <i>свободными</i></strong>. </p><center>
239<!-- Yandex.RTB R-A-2158804-8 -->
240<div id="yandex_rtb_R-A-2158804-8"></div>
241<script>window.yaContextCb.push(()=>{
242  Ya.Context.AdvManager.render({
243    renderTo: 'yandex_rtb_R-A-2158804-8',
244    blockId: 'R-A-2158804-8'
245  })
246})</script>
246
247</center>
248 <p><strong> Пример 9</i></strong>.<strong> <i>2</i></strong>. Вернемся к примеру 9.1 о делимости на 3 и на 2. Тогда на множестве натуральных чисел предикат</p>
249 <p>(&#8707; <i>х </i>) <i>Р</i> (1)(<i>х</i> ) &amp; <i>Q </i>(1)( <i>x </i>)) —</p>
250 <p>истинное высказывание, а предикат</p>
251 <p>(&#8704; <i>х </i>) <i>Р</i> (1)(<i>х</i> ) &amp; <i>Q </i>(1)( <i>x </i>)) —</p>
252 <p>ложное высказывание.</p>
253 <p><strong> Замечание 9.1. </strong> Операцию связывания кванторами можно применять и к предикатам от большего числа переменных. При этом те переменные в предикате, на которые действует какой-либо квантор, будут связанными, а все остальные — свободными.</p>
254						<p><strong> Формулы логики предикатов </strong> </p>
255						<p>Теперь определим понятие формулы логики предикатов.</p>
256 <p><strong> Определение 9.4. <i>Алфавит логики предикатов</i> </strong> содержит следующие символы.</p>
257 <p>1. <i>Символы предметных переменных: </i></p>
258 <p><i>x </i>1, <i>x </i>2, …</p>
259 <p>2. <i>Символы предикатов: </i></p>
260 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image691.gif" /></p>
261 <p>где <i>t </i>= 0, 1, …</p>
262 <p>3. <i>Логические символы: </i></p>
263 <p>&#8969;, &amp;, &#8744; , &#8658; , ~.</p>
264 <p>4. <i>Символы кванторов: </i></p>
265 <p>&#8707; , &#8704; .</p>
266 <p>5. <i>Скобка и запятая: </i></p>
267 <p>), (.</p>
268 <p>Отличие алфавита логики высказываний от алфавита логики предикатов в наличии п. 1 и 4; кроме того, п. 2 здесь шире (в алфавите логики высказываний <i>t </i>= 0); в п. 5 появилась «запятая».</p><center>
269<!-- Yandex.RTB R-A-2158804-9 -->
270<div id="yandex_rtb_R-A-2158804-9"></div>
271<script>window.yaContextCb.push(()=>{
272  Ya.Context.AdvManager.render({
273    renderTo: 'yandex_rtb_R-A-2158804-9',
274    blockId: 'R-A-2158804-9'
275  })
276})</script>
276
277</center>
278 <p>Чтобы избежать нагромождения индексов, часто символы переменных будем обозначать через <i>x </i>, <i>y</i>, <i>z</i>, а символы предикатов через <i>Р</i>, <i>Q </i>, <i>R </i>, <i>S </i>и т. д.</p>
279 <p><strong> Определение 9.5. </strong> Слово в алфавите логики предикатов называется<strong> <i>формулой</i> </strong> или правильно построенным словом, если оно удовлетворяет следующему рекурсивному определению.</p>
280 <p>1. Если <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image693.gif" /> — символ предиката; <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image695.gif" /> — символы предметных переменных, необязательно различные, то <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image697.gif" /> — формула. Такая формула называется<strong> <i>атомарной</i></strong>. Все предметные переменные атомарных формул свободные, связанных переменных нет.</p>
281 <p>2. Пусть <i>а</i> — формула. Тогда &#8969; <i>а </i>— тоже формула. Свободные и связанные переменные формулы &#8969; <i>а </i>— соответственно свободные и связанные переменные формулы <i>а</i>.</p>
282 <p>3. Пусть <i>а </i>и <i>b </i>— формулы, причем нет таких переменных, которые были бы связанными в одной формуле и свободными в другой. Тогда</p>
283 <p>(<i>а</i> &#8744; <i>b </i>), ( <i>a </i>&amp; <i>b </i>), (<i>а</i> &#8658; <i>b </i>), (<i>а</i> ~ <i>b </i>)</p>
284 <p>есть формулы, в которых свободные переменные формул <i>а</i> и <i>b </i>остаются свободными, связанные остаются связанными.</p>
285 <p>4. Пусть <i>а</i> — формула, содержащая свободную переменную <i>х</i>. Тогда ( &#8704; <i>x </i>)<i>а</i>, ( &#8707; <i>х </i>)<i>а</i> — тоже формулы. Переменная <i>x </i>в них — связанная. Остальные переменные, которые в формуле <i>а</i> свободны, остаются свободными и в этих формулах.</p>
286 <p>Переменные, которые в формуле <i>а</i> связаны, остаются связанными.</p>
287 <p>В формуле ( &#8704; <i>x </i>)<i>а</i> формула <i>а</i> называется<strong> <i>областью действия</i> </strong> квантора &#8704; , а в формуле ( &#8707; <i>х </i>)<i>а</i> — областью действия квантора &#8707; .</p>
288 <p>5. Других правил нет.</p>
289 <p><strong> Замечание 9.2. </strong> По определению формулы никакая переменная не может быть одновременно свободной и связанной. Для оценки формулы на истинность и ложность требуется зафиксировать значения всех свободных предметных переменных, взяв их значения из множества допустимых значений.</p>
290 <p><strong> Пример 9</i></strong>.<strong> <i>3</i>. </strong> Рассмотрим предикат «Каждый водитель должен соблюдать правила».</p>
291 <p>Назовем параметры: «водитель», «правила». Первый параметр — связанная переменная, второй — свободная.</p>
292 <p>Зафиксируем вторую переменную: «правила дорожного движения». Если такой закон в РФ есть, то получаем «И», если нет, то «Л».</p>
293 <p>То, что сейчас проделано, называется заданием, или рассмотрением некоторой интерпретации предиката.</p>
294 <p><strong> Определение 9.6. <i>Интерпретацией</i> </strong>
294 называется пара <i>I </i>= &aacute; <i>М </i>, Ф &ntilde; , состоящая из непустого множества <i>М</i> и соответствия Ф. При этом множество <i>М</i> задает область значений предметных переменных, а соответствие Ф сопоставляет каждой атомарной формуле <i>Aj</i>( <i>x </i>1, ..., <i>xt</i>) конкретный <i>t </i>-местный предикат, заданный на <i>М</i>.</p>
295 <p>При заданной интерпретации считают, что предметные переменные пробегают множество М, а символы &#8969;, &amp;, &#8744; , &#8658; , ~.и символы кванторов имеют обычный смысл.</p>
296 <p>Для данной интерпретации каждая формула без свободных переменных представляет собой высказывание, которое истинно или ложно. Всякая формула со свободными переменными выражает некоторый предикат на множестве <i>М</i>, который истинен при одних значениях переменных из этого множества и ложен при других.</p>
297 <p><strong> Пример 9. 4. </i> </strong> Пусть <i>f </i>( <i>x </i>) — произвольная фиксированная функция, заданная на отрезке [<i>а</i>, <i>b </i>].</p>
298 <p>1. Рассмотрим интерпретацию <i>I </i>= &aacute; <i>М </i>, Ф1&ntilde; , где <i>М</i> — множество действительных чисел; Ф1— соответствие, сопоставляющее формулам <i>Р</i> (<i>х</i>, &#948; ), <i>Q </i>( <i>x </i>, &#949; ), <i>R </i>(&#949; ) их конкретные предикаты (характеристические функции): </p>
299 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image699.gif" /></p>
300 <p>Здесь <i>х</i> 0— фиксированный элемент отрезка [<i>а</i>, <i>b </i>]; <i>с</i> — некоторое фиксированное действительное число. Тогда определение того, что <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image701.gif" /> записывается формулой</p>
301 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image703.gif" /></p>
302 <p>2. Рассмотрим интерпретацию <i>I </i>= &aacute; <i>М </i>, Ф2&ntilde; , где <i>М</i> — множество действительных чисел; Ф2— соответствие, сопоставляющее формулам <i>Р</i> (<i>х</i>, &#948; ), <i>S </i>( <i>x </i>, &#949; ), <i>R </i>(&#949; ) предикаты: </p>
303 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image705.gif" /></p>
304 <p>Здесь <i>х</i> 0— произвольный фиксированный элемент отрезка [<i>а</i>, <i>b </i>]. Тогда определение о том, что функция <i>f </i>( <i>x </i>) непрерывна в точке <i>х</i> 0, записывается формулой</p>
305 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image707.gif" /></p>
306 <p>Здесь рассмотрен простой вариант определения формул логики предикатов. Для описания более серьезных языковых конструкций требуется расширение понятия формулы и использование еще понятия <i>терма</i>. Мир термов описывает предметную область интерпретации средствами классической математики. Для определения термов требуется расширить алфавит формальной теории. Кроме символов предметных переменных <i>xi</i>требуется ввести еще символы констант <i>aj</i>и функциональные символы <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image709.gif" /> алгебраических операций над предметными переменными и Ð
306½Ð°Ð´ константами. Здесь число <i>m </i>= 0, 1, 2, ... называется арностью или числом мест операции. Терм определяется рекурсивно.</p>
307 <p><strong> Определение 9.7. </strong> Всякая предметная переменная, или константа, является <i>термом</i>.</p>
308 <p><strong> Правила преобразования формул логики предикатов </strong> </p>
309 <p>Пусть формулы <i>f </i>и <i>g </i>имеют одно и то же множество свободных переменных (в частности, пустое).</p>
310 <p><strong> Определение 9.8. </strong> Формулы <i>f </i>и <i>g<strong> равносильны в </strong> </i><strong> <i>данной интерпретации</i> </strong> <i>I </i>= &aacute; <i>М </i>, Ф &ntilde; , если на любом наборе значений свободных переменных они принимают одинаковые значения, т. е. если формулы выражают в данной интерпретации один и тот же предикат.</p>
311 <p>Формулы <i>f </i>и <i>g<strong> равносильны на </strong> </i><strong> <i>множестве</i> </strong> <i>М</i>, если они равносильны во всех интерпретация
311х, заданных на множестве <i>М</i>. Формулы <i>f </i>и <i>g равносильны </i>в алгебре (логике) предикатов, если они равносильны во всех интерпретациях. Тогда будем писать: <i>f </i>&#8801; <i>g </i>.</p>
312 <p><strong> Пример 9</i></strong>.<strong> <i>6</i></strong>. Рассмотрим формулы: </p>
313 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image711.gif" /></p>
314 <p>Эти формулы равносильны на одноэлементном множестве. В самом деле, если область интерпретации — одноэлементное множество, то какой бы предикат ни взяли в качестве интерпретации <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image713.gif" /> на этом множестве, он принимает только значения И или Л.</p>
315 <p>В первом случае обе формулы принимают значение И, во втором — Л, и, следовательно, они равносильны на этом множестве.</p>
316 <p>С другой стороны, на двухэлементном множестве {<i>а</i>, <i>b </i>} эти формулы не равносильны.</p>
317 <p>Теперь рассмотрим правила перехода от одних формул к другим, им равносильным во всех интерпретация
317х.</p>
318 <p><strong> Теорема 9.1 </strong> (<i>правила булевой алгебры</i> ). Для формул алгебры предикатов сохраняются все равносильности и правила равносильных преобразований алгебры высказываний.</p>
319 <p><i>Доказательство </i>. Проведем показательное рассуждение для одной равносильности.</p>
320 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image715.gif" /></p>
321 <p>Здесь формулы <i>а</i>, <i>b </i>, <i>с</i> являются предикатами. Рассмотрим произвольную интерпретацию <i>I </i>= &aacute; <i>М </i>, Ф &ntilde; и зададим свободные переменные в формулах <i>а</i>, <i>b </i>, <i>с</i> конкретными значениями. Тогда эти формулы станут высказываниями со своими истинностными значениями, для которых закон дистрибутивности выполняется. Следовательно, в силу произвольности интерпретации, дистрибутивность будет выполняться в логике предикатов. Аналогично доказываются все равносильности из логики высказываний, </p>
322 <p><strong> Теорема 9.2 </strong> (<i>правило переноса квантора через отрицание</i> ). Пусть <i>а</i> — формула, содержащая свободную переменную <i>х</i>. Тогда: </p>
323 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image717.gif" /></p>
324 <p><strong> Теорема 9.3 </strong> (<i>правило выноса квантора за скобки</i> ). Пусть <i>а</i> (<i>х</i> ) содержит свободную переменную <i>х</i>, формула <i>b </i>не содержит переменной <i>х</i> и обе они удовлетворяют п. 3 определения 9.5, т.е. нет таких переменных, которые были бы связаны в одной формуле и свободны в другой. Тогда: </p>
325 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image719.gif" /></p>
326 <p>Если в предыдущих правилах допустить, чтобы формула <i>b </i>содержала переменную <i>х</i>, то будут выполняться только две равносильности: </p>
327 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image721.gif" /></p>
328 <p><strong> Теорема 9.4 </strong> (<i>правило перестановки одноименных кванторов</i> ).</p>
329 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image723.gif" /></p>
330 <p><strong> Теорема 9.5 </strong> (<i>правило переименования связанных переменных</i> ). Заменяя связанную квантором переменную формулы <i>а</i> всюду в области действия квантора другой переменной, не входящей в эту формулу, получаем формулу, равносильную а.</p>
331 <p><strong> Определение 9.9. <i>Длиной формулы</i> </strong> называется общее число входящих в нее символов предикатов (атомарных формул), логических символов и символов кванторов.</p>
332 <p><strong> Пример 9</i></strong>.<strong> <i>7</i></strong>. Рассмотрим формулу</p>
333 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image725.gif" /></p>
334 <p>Эта формула имеет длину 5. Длину здесь составляют символы: </p>
335 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image727.gif" /></p>
336 <p><strong> Определение 9.10. </strong> Формулы, в которых из логических символов имеются только символы &amp;, &#8744; , &#8969; (стандартный базис), причем символ &#8969; встречается только перед атомарными подформулами (тесное отрицание), называются<strong> <i>приведенными</i></strong>. </p>
337 <p><strong> Пример 9</i></strong>.<strong> <i>8</i></strong>. Рассмотрим формулы: </p>
338 <p><img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image729.gif" /></p>
339 <p>Первая является приведенной, вторая — нет. (Почему? ) В заключение укажем, до какой степени формулы можно упростить с помощью равносильностей.</p>
340 <p><strong> Определение 9.11. </strong> Приведенная формула называется <i>нормальной</i>, если она содержит все символы кванторов впереди или кванторов вовсе нет.</p>
341 <p><strong> Пример 9</i></strong>.<strong> <i>9</i></strong>. Формула <img src="https://konspekta.net/lektsiacom/baza1/466818609835.files/image731.gif" /> является нормальной.</p>
342 <p>Относительно нормальных формул справедлива следующая теорема, которую приведем без докаÐ
342·Ð°Ñ‚ельства.</p>
343 <p><strong> Теорема 9.6. </strong> Для любой формулы существует равносильная ей приведенная формула, для которой, в свою очередь, существует равносильная ей нормальная формула.</p>
344 <p><strong> Пример 9</i></strong>.<strong> <i>10</i></strong>. Рассмотрим некоторую теорему из математического анализа.</p>
345 <p><strong> Теорема Лагранжа о конечном приращении. </strong> Если функция <i>f </i>( <i>x </i>) непрерывна на отрезке [<i>а</i>, <i>b </i>] и дифференцируема в интервале (<i>а</i>, <i>b </i>), то существует точка <i>с</i>, <i>с</i> &#8712; (<i>а</i>, <i>b </i>), такая, что выполняется равенство <i>f </i>( <i>b </i>) – <i>f </i>( <i>a </i>) = <i>f </i> '( <i>c </i>)( <i>b </i>– <i>а</i> ).</p>
346 <p>Обратим внимание на то, что <i>классическая математическая</i> символика используется в основном для <i>термов</i> (предметов), а все свойства термов и утверждения о них написаны на <i>естественном языке</i> (см. формулировку теоремы). Математическая логика позволяет формализовать весь текст теоремы и записать ее в виде <i>формулы</i>. Вот почему математическую логику часто называют <i>метаматематикой</i>. Мир формул логики предикатов относят к <i>неклассической математике</i>.</p>
347 <p>Перейдем к формализации теоремы Лагранжа в рамках логики предикатов.</p>
348 <p><i>Шаг 1</i>. Перечислим все предметы, о которых идет речь в теореме, и обозначим их <i>предметными переменными</i>. Всего в теореме четыре предмета — три числа <i>а</i>, <i>b </i>, <i>с</i> и одна функция <i>f </i>, или в стандартном обозначении <i>f </i>( <i>x </i>).</p>
349 <p><i>Шаг 2</i>. Выделим в теореме простейшие части текста (смыслы) о предметах и формализуем их в виде <i>атомарных формул</i>. Получим: </p>
350 <p><i>P </i>( <i>a </i>, <i>b </i>, <i>f </i>( <i>x </i>)) = «функция <i>f </i>( <i>x </i>) непрерывная на отрезке [<i>а</i>, <i>b </i>]»; </p>
351 <p><i>Q </i>( <i>a </i>, <i>b </i>, <i>f </i>( <i>x </i>)) = «функция <i>f </i>( <i>x </i>) дифференцируемая в интервале (<i>а</i>, <i>b </i>)»; </p>
352 <p><i>R </i>(<i>a</i>, <i>b</i>, <i>с </i>) = « <i>с </i>&#8712; ( <i>а </i>, <i>b</i> )»; </p>
353 <p><i>S </i>(<i>a</i>, <i>b</i>, <i>с </i>, <i>f</i> (<i>x</i> )) = «<i>f</i> (<i>b</i> ) – <i>f</i> (<i>a</i> )) = <i>f</i> '(<i>c</i> ) (<i>b</i> – <i>а </i>)».</p>
354 <p><i>Шаг 3. </i>Соединим атомарные формулы в одну <i>сложную формулу</i> при помощи логических связок, следуя тексту теоремы. Получим следующую формулу рассматриваемой теоремы.</p><!-- Yandex.RTB R-A-2158804-2 -->
355<div id="yandex_rtb_R-A-2158804-2"></div>
356<script>window.yaContextCb.push(()=>{
357  Ya.Context.AdvManager.render({
358    renderTo: 'yandex_rtb_R-A-2158804-2',
359    blockId: 'R-A-2158804-2'
360  })
361})</script>
361<br><table width="100%" border="0" cellspacing="0" cellpadding="0"><tbody><tr><td width="75%" ><div class="pagelink" ><a href="/1x537.html" class="back_link">&lArr; Предыдущая</a><a href="/1x533.html">11</a><a href="/1x534.html">12</a><a href="/1x535.html">13</a><a href="/1x536.html">14</a><a href="/1x537.html">15</a><span class="current">16</span><a href="/1x539.html">17</a><a href="/1x53a.html">18</a><a href="/1x53b.html">19</a><a href="/1x53c.html">20</a><a href="/1x539.html" class="next_link">Следующая &rArr;</a></div>		</td><td width="25%"><center><font color="red">Поделиться:</font></center>
362<center>
362<script src="https://yastatic.net/share2/share.js"></script>
362
363<div class="ya-share2" data-curtain data-services="messenger,vkontakte,odnoklassniki,telegram,twitter,moimir,lj"></div>
364</center></td></tr></tbody></table>
365<br>
366
367	<br><br>
368
369
370<!-- Yandex Native Ads C-A-2158804-11 -->
371<div id="yandex_rtb_C-A-2158804-11"></div>
372<script>window.yaContextCb.push(()=>{
373  Ya.Context.AdvManager.renderWidget({
374    renderTo: 'yandex_rtb_C-A-2158804-11',
375    blockId: 'C-A-2158804-11'
376  })
377})</script>
377
378<center><div class='link1'>Популярное:</div><div class='link2'><p><ol><li><a href="/1x5f0f.html">II.2. Локальные геосистемы – морфологические единицы ландшафта</a></li><li><a href="/1x5f11.html">III.1. Методологические основы классификации ландшафтов</a></li><li><a href="/1x85f8.html">III.2. Психобиологические предпосылки асоциального поведения несовершеннолетних и их учет в воспитательно-профилактической работе.</a></li><li><a href="/1x73bb.html">PR-менеджмент: технологические основы</a></li><li><a href="/1x5c91.html">V. Кибернетические (или постбиологические) методы достижения бессмертия (искусственная жизнь “в силиконе”)</a></li><li><a href="/1x6509.html">Активные морфонологические процессы в структуре русского производного слова.</a></li><li><a href="/1x120.html">Анатомо-физиологические особенности вегетативной нервной системы.</a></li><li><a href="/1x5669.html">Бесконтактные логические элементы</a></li><li><a href="/1x3b0f.html">Биологические и хозяйственные особенности свиней.</a></li><li><a href="/1x3b0a.html">Биологические особенности лошадей.</a></li><li><a href="/1x3b10.html">Биологические особенности птицы и ее продуктивность.</a></li><li><a href="/1x267e.html">Биологические особенности свиней.</a></li></ol></p></div></div><center><br><div class="ya-site-form ya-site-form_inited_no" onclick="return {'action':'https://lektsia.com/search.php','arrow':false,'bg':'transparent','fontsize':12,'fg':'#000000','language':'ru','logo':'rb','publicname':'Yandex Site Search #2310067','suggest':true,'target':'_self','tld':'ru','type':2,'usebigdictionary':true,'searchid':2310067,'input_fg':'#000000','input_bg':'#ffffff','input_fontStyle':'normal','input_fontWeight':'normal','input_placeholder':null,'input_placeholderColor':'#000000','input_borderColor':'#7f9db9'}"><form action="https://yandex.ru/search/site/" method="get" target="_self" accept-charset="utf-8"><input type="hidden" name="searchid" value="2310067"/><input type="hidden" name="l10n" value="ru"/><input type="hidden" name="reqenc" value=""/><input type="search" name="text" value=""/><input type="submit" value="Найти"/></form></div><style type="text/css">.ya-page_js_yes .ya-site-form_inited_no { display: none; }</style>
378<script type="text/javascript">(function(w,d,c){var s=d.createElement('script'),h=d.getElementsByTagName('script')[0],e=d.documentElement;if((' '+e.className+' ').indexOf(' ya-page_js_yes ')===-1){e.className+=' ya-page_js_yes';}s.type='text/javascript';s.async=true;s.charset='utf-8';s.src=(d.location.protocol==='https:'?'https:':'http:')+'//site.yandex.net/v2.0/js/all.js';h.parentNode.insertBefore(s,h);(w[c]||(w[c]=[])).push(function(){Ya.Site.Form.init()})})(window,document,'yandex_site_callbacks');</script>
378
379
380
381<!-- Yandex.RTB R-A-2158804-3 -->
382<div id="yandex_rtb_R-A-2158804-3"></div>
383<script>window.yaContextCb.push(()=>{
384  Ya.Context.AdvManager.render({
385    renderTo: 'yandex_rtb_R-A-2158804-3',
386    blockId: 'R-A-2158804-3'
387  })
388})</script>
388
389</div>
390
391</td>
392  </tr>
393</table>
394
395<center><p class="littletext">Последнее изменение этой страницы: 2016-03-16; Просмотров: 24861; <a href='/call.php' class='littletext'>Нарушение авторского права страницы</a></p></center><br></div>
396
397<center><span class="nizpravo">lektsia.com 2007 - 2026 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.068 с.)
398	<br><a href="/" class="anizpravo">Главная</a> | <a href="/random.php" class="anizpravo">Случайная страница</a> | <a href="/call.php" class="anizpravo">Обратная связь</a> </span> </center>
399<br><br><br><br><br>
400<!--LiveInternet counter-->
400<script type="text/javascript"><!--
401new Image().src = "//counter.yadro.ru/hit?r"+
402escape(document.referrer)+((typeof(screen)=="undefined")?"":
403";s"+screen.width+"*"+screen.height+"*"+(screen.colorDepth?
404screen.colorDepth:screen.pixelDepth))+";u"+escape(document.URL)+
405";"+Math.random();//--></script>
405<!--/LiveInternet-->
406
407<!-- Yandex.Metrika counter -->
408<script type="text/javascript" >
vendor: 406 bytes, lines 408-415
408
409   (function(m,e,t,r,i,k,a){m[i]=m[i]||function(){(m[i].a=m[i].a||[]).push(arguments)};
410   m[i].l=1*new Date();
411   for (var j = 0; j < document.scripts.length; j++) {if (document.scripts[j].src === r) { return; }}
412   k=e.createElement(t),a=e.getElementsByTagName(t)[0],k.async=1,k.src=r,a.parentNode.insertBefore(k,a)})
413   (window, document, "script", "https://mc.yandex.ru/metrika/tag.js", "ym");
414
415   ym(
41590961445
vendor: 100 bytes, lines 415-419
415, "init", {
416        clickmap:true,
417        trackLinks:true,
418        accurateTrackBounce:true
419   });
420</script>
420
421<noscript><div><img src="https://mc.yandex.ru/watch/90961445" style="position:absolute; left:-9999px;" alt="" /></div></noscript>
422<!-- /Yandex.Metrika counter -->
423		
424<script src="https://yandex.ru/ads/system/context.js" async></script>
424
425
426<script defer src="https://eduforms.org/partnersforms/widget/?component=copyPaste&subComponent=2&ref=96efe5b94400ecf1"></script>
426
427
428<script type="module" src="https://static.cloudflareinsights.com/beacon.min.js/v31edd6df95cf4e85bb4c19e7a9bdbcba1788362987495" integrity="sha512-iIg7k2xntmwu6/uSb5tpc/hySgZc4eoL31yB29W6tJFo2akwjPWcEqnCEdJvGexCL0KEQwVYv5BlowfhVz26hg==" data-cf-beacon='{"version":"2024.11.0","token":"9c86201abac04cca9e48e96b45c92f71","r":1,"spa":2}' crossorigin="anonymous"></script>
428
429</body>
430</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.