Математическая логика
жүктеу/скачать 0.93 Mb.
|
| Ud = U U = (U1 ( )) (U2 ( ))
(U1 ( ) U2 ( )) = U( ). В случае в) выкладки аналогичны. Теорема доказана. Следствие. Если U – ТИ-формула, то Ud – ТЛ-формула. Теорема 2.6. Если U V, то Ud Vd. Доказательство. Если U V, то (U) (V). Значит, в силу теоремы 2.5, Ud(Х1, …, Хn) = U( ) и Vd(Х1, …, Хn) = V( ). Отсюда: Ud = (U( )) (V( )) = Vd. В силу транзитивности эквиваленции, получим Ud Vd , что и требовалось доказать. 3. Использование законов логики в доказательстве теорем и построении схем Эквиваленции и импликации играют важную роль в математике при построении логического вывода, в частности, при доказательстве различных высказываний (теорем). Рассмотрим, например, следующую теорему: асимметричное бинарное отношение антирефлексивно. С точки зрения алгебры высказываний теорема имеет структуру следования А В, где А = “отношение R асимметрично”, В = “отношение R антирефлексивно”. Следующая теорема – для связности графа необходимо и достаточно, чтобы в нем какая-нибудь фиксированная вершина v была достижима из всех вершин, имеет вид двойного следования А В (А В, В А), где А = “граф G – связный”, В = “вершина v достижима из всех вершин”. Согласно теоремам 3.1 и 3.2, следование А В имеет место тогда и только тогда, когда импликация А В является ТИ-формулой, а двойное следование А В выполняется, когда ТИ-формулой является эквиваленция А В. Таким образом, для доказательства какой-либо теоремы надо доказать ТИ соответствующей импликации или эквиваленции. Рассмотрим основные приемы таких доказательств, использующие законы математической логики. жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
|