- •1. Всякое предложение, о к-ом можно определенно сказать истинно оно или ложно наз-ся высказыванием.
- •5. Формула наз-ся логическим следствием формулы , если для любых конкретных выск-ий из истинности следует истинность .
- •6. Правила вывода
- •7. Булевой ф-ией от одного аргумента наз-ся ф-ия , заданная на множестве из двух элементов и принимающая значения в том же двухэлементном мн-ве. : .
- •10. Т.(о дедукции).Если ├f, то т-ма ├ в частности, если ├f, то├ д-во: Предположим,что посл-сть формул (1)
- •11. Получаемые вторичные
- •12.Т.(о полноте формализованного исчисления
- •Определение формулы логики предикатов.
- •19. Теорема. Всякая формула, получающаяся из тавтологии
- •20. Т.1 Всякая формула, получающаяся из тавтологии
- •29.Теории первого порядка
5. Формула наз-ся логическим следствием формулы , если для любых конкретных выск-ий из истинности следует истинность .
Если формула явл-ся логическим следствием формулы , то записывается так: ╞ .
Т.1. (признак логического следствия). Формула будет логическим следствием ф-лы F тогда и только тогда, когда формула F → Н явл-ся тавтологией: ╞ ╞ → .
Д-во.Необх-сть. Дано: ╞ , т.е. если для набора выск-ий имеет место , то . Тогда для любого набора выск-ий имеет место равенство , поскольку равенство нулю возможно лишь в том случае, когда , а , но такая ситуация исключена условием. Сл-но, для любых выск-ий . Это означает, что ф-ла → — тавтология,т.е.╞ → .
Дост-сть. Дано:╞ → . Тогда: для любых выск-ий , откуда . Предположим теперь, что . Тогда:1→ , откуда, на основании опр-ия импликации, , ибо в противном случае 1→ 0 = 1 — противоречие. Но это значит, по опр-ию логического следствия, что ╞ .
Т.2. Для любых формул ( ) следующие утверждения равносильны:
а) ╞ , б) ╞ , в)╞ ( )→ .
Т.3. Отн-ие логического следования между формулами алгебры выск-ий обладает следующими свойствами:
а) ╞ для ;
б)если ╞ для и ╞ , то ╞ .
Т.3. Две ф-лы алгебры выск-ий равносильны тогда и только тогда, когда каждая из них явл-ся логическим следствием другой: ╞ и ╞ .
Замечание. Если некоторая ф-ла явл-ся тавтологией, то и всякое ее логическое следствие также явл-ся тавтологией. Символически: если ╞ и ╞ , то ╞ .
6. Правила вывода
Если в процессе дедуктивного рассуждения некоторое утверждение G выводится из утверждений , то говорят, что справедливо правило вывода:
Основные правила вывода:
Правило modus ponens: .
Это правило означает: от утверждения об истинности посылкой с помощью другой посылки переходят к утверждению об истинности следствия G.
Правило modus tollens: . От отрицания истинности посылки G с помощью посылки переходят к отрицанию истинности F.
Правило введения конъюнкции: .
Правила удаления конъюнкции: и .
Правила введения дизъюнкции: и
Правило контрапозиции: .
Правило силлогизма (цепного заключения): .
Правило перестановки посылок: .
Правила объед-ия и разъединения посылок: и
Приложение алгебры выск-ий к логико-матем-ой практике. Прямая и обратная теоремы. Многие математические теоремы имеют структуру, выражаемую ф-лой . Утверждение X наз-ся условием теоремы, а утверждение Y — ее заключением.
Если некоторая матем-ая теорема имеет структуру, выражаемую ф-лой X→Y, то высказывание Y наз-ся необходимым условием для выск-ия X, а выск-ие X наз-ся достаточным условием для выск-ия Y.
Обратная теорема — такая, в к-ой условие и заключение прямой теоремы поменялись местами.Если некоторая теорема имеет форму X→Y, то утверждение Y→Х наз-ся обратным для данной теоремы. Это утверждение может быть справедливым, и тогда оно наз-ся теоремой обратной для теоремы X→Y, к-ая, в свою очередь, наз-ся прямой теоремой.
Обратная теорема — такая, в к-ой условие и заключение прямой теоремы поменялись местами.
Противоположная и обратная противоположной теоремы. Закон контрапозиции. Для теоремы, сформулированной в виде импликации X→Y, кроме обратного утверждения Y→Х можно сформулировать противоположное утверждение. Им наз-ся утверждение вида . Утверждение, противоположное данной теореме, может быть также теоремой, то есть быть истинным выск-ием, но может таковым и не быть. Это следует из того, что формулы X→Y и не равносильны.
Теорема, обратная противоположной: . Мы не случайно назвали теоремой утверждение, обратное противоположному.
Оно действительно будет истинным тогда и только тогда, когда истинно исходное утверждение, что вытекает из равносильности X→У , называемой законом контрапозиции. Т.о. на основании закона контрапозиции предложение, обратно противоположное какой-либо теореме, само явл-ся теоремой, и вместо док-ва данной теоремы можно доказывать обратно противоположную ей теорему.
Методы матем-ских док-ств. На основании закона контрапозиции можно вместо теоремы X→У доказывать обратно противоположную ей теорему: . Этот метод док-ва теорем, называемый док-вом от противного, часто используется в математике.
Т.1. (об обратимости системы импликаций, или принцип полной дизъюнкции). Пусть справедливы все следующие прямые теоремы ( ):
, , …, — причем из посылок по меньшей мере одна выполняется (истинна), а следствия попарно исключают друг друга Тогда справедливы и все обратные импликации: , , …, .
Умозаключение есть логическая (мыслительная) операция (процедура), состоящая в получении нового суждения из одного или нескольких ранее известных суждений. Ранее известные суждения, входящие в состав умозаключения, наз-ся его посылками, а новое суждение наз-ся его следствием (или заключением). Рассуждение есть последовательность умозаключений, причем посылками последующих умозаключений служат следствия предыдущих умозаключений данной последовательности.