Доказать что формула является тавтологией
Перейти к содержимому

Доказать что формула является тавтологией

  • автор:

1. Высказывания, формулы, тавтологии

Определение. Высказыванием называется утверждение, которое является истинным или ложным (но не одновременно).

То есть, чтобы выяснить, является ли некоторое предложение высказыванием, нужно сначала убедиться, что это утверждение, а затем установить, истинно оно или ложно.

Пример. “Москва – столица России” – истинное высказывание.

“5 –четное число” – ложное высказывание.

” – не высказывание (неизвестно, какие значения принимает ).

“Студент второго курса” не высказывание (не является утверждением).

Высказывания бывают элементарные и составные.

Элементарные высказывания не могут быть выражены через другие высказывания. Составные высказывания можно выразить с помощью элементарных высказываний.

Пример. “Число 22 четное” – элементарное высказывание.

“Число 22 четное и делится на 11” – составное высказывание.

Высказывания обозначают заглавными буквами латинского алфавита: , , ,… Эти буквы называют логическими Атомами.

При фиксированном множестве букв Интерпретацией называется функция , которая отображает множество во множество истинностных (логических) значений , то есть .

Истинностные значения истина и ложь сокращенно обозначаются и, л или T, F, или 1,0. Мы будем использовать обозначения 1 и 0. В определенной интерпретации буквы принимают значения 1 или 0.

К высказываниям и буквам можно применять известные из курса дискретной математики логические связки или логические операции. При этом получаются Формулы (формы). Формулы становятся высказываниями при подстановке всех значений букв.

Таблицы истинности основных логических операций.

Более строго формула определяется так.

Определение. 1) Всякая буква есть формула.

2) Если , — формулы, то формулами являются также , , , , .

3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

В классической логике формулы принято заключать в круглые скобки, но в мы этого делать не будем. Для всякой формулы можно построить таблицу истинности.

Значение формулы в заданной интерпретации обозначают (или , или ).

Часть формулы, которая сама является формулой, называется Подформулой данной формулы.

Определение. Формула называется Тавтологией, если она принимает только истинные значения при любых значениях букв.

Другими словами, тавтология – это тождественно истинная формула.

Установить, является ли формула тавтологией, можно:

– по таблице истинности,

– используя свойства логических операций.

Из курса дискретной математики известны основные логические эквивалентности (свойства логических операций), которые являются примерами тавтологий.

1. Коммутативность: , .

, .

, .

4. Идемпотентность: , .

5. Закон двойного отрицания: .

6. Закон исключения третьего: .

7. Закон противоречия: .

8. Законы де Моргана:

, .

9. Свойства операций с логическими константами:

, , , .

Здесь , и – любые буквы.

Примеры. 1. Доказать, что формула является тавтологией.

Доказательство. Допустим, что при некоторых значениях букв (то есть в некоторой интерпретации)

Приходим к противоречию, которое доказывает, что исходная формула – тавтология.

2. Доказать, что формула является тавтологией.

Доказательство. Эквиваленция истинна, если левая и правая части принимают одинаковые значения на некотором наборе значений букв.

Допустим, что при некоторых значениях букв

Следовательно, исходная формула – тавтология.

3. Доказать, что формула является тавтологией.

Доказательство. Допустим, что при некоторых значениях букв

Следовательно, исходная формула – тавтология.

Таким образом, тождественную истинность импликации удобно доказывать от противного, а тождественную истинность эквиваленции установлением равенства значений левой и правой части.

Теорема. Пусть формулы и – тавтологии. Тогда формула – тавтология.

Доказательство. Пусть , , …, – буквы в формулах и . В теории булевых функций было доказано, что все булевы функции, а, следовательно, и формулы, можно считать зависящими от одного и того же количества букв. Рассмотрим некоторый набор значений , , …, , где , . Подставим данный набор значений в формулы и вместо соответствующих букв. Формулы являются тавтологиями по условию теоремы, следовательно, и . По таблице истинности импликации получаем, что . Поскольку набор значений , , …, был произволен, формула – тавтология, что и требовалось доказать.

Теорема. Пусть формула – тавтология, , , …, – буквы в формуле , , , …, – любые формулы. Тогда новая формула – тавтология.

Доказательство аналогично доказательству предыдущей теоремы.

  • Главная
  • Заказать работу
  • Стоимость решения
  • Варианты оплаты
  • Ответы на вопросы (FAQ)
  • Отзывы о нас
  • Примеры решения задач
  • Методички по математике
  • Помощь по всем предметам
  • Заработок для студентов

Определить, является ли формула тавтологией

Author24 — интернет-сервис помощи студентам

Является ли формула тавтологией
Помогите решить еще одну задачу: Является ли формула тавтологией (a->b)->c<=>(a^неb)vc .

Является ли тавтологией формула
Является ли данная формула тавтологией? ((P ⊃Q) & (R ⊃Q) & (T ⊃ (P ∨ R)) & ¬T) ⊃ Q?

Является ли формула тавтологией?
Является ли формула ((p ⊃ q) & (q ⊃ p) & (p ∨ r) & ¬r) ⊃p тавтологией?

Эксперт по математике/физике

4891 / 3515 / 1137
Регистрация: 01.09.2014
Сообщений: 9,577
А вы знаете, что такое тавтология?
Регистрация: 25.10.2017
Сообщений: 155
Да, если исходная формула принимает значение 1.

Эксперт по математике/физике

4891 / 3515 / 1137
Регистрация: 01.09.2014
Сообщений: 9,577

Правильно. Но если в случае функции из натуральных чисел или действительных чисел не так-то просто проверить, всегда ли она равна 1, так как область определения функции бесконечна, то в случае булевой функции это можно проверить непосредственно, поскольку она принимает лишь конечное число аргументов. Это называется построение таблицы истинности.

Доказать что формула является тавтологией

Рассмотрим следующую логическую формулу А Ù ( А ® В ) ® В . Построим ее таблицу истинности.

А Ù (А ® В )

А Ù (А ® В ) ® В

Оказывается, при любых значениях входящих в эту формулу логических переменных она принимает значение «истина», т.е. 1. Такие логические формулы и соответствующие им высказывания называются тождественно истинными или тавтологиями.

Сложное высказывание, истинное при любых значениях входящих в него простых, называется тождественно истинным или тавтологией.

Факт, что высказывание А является тавтологией, обозначается так ½ = А.

Сложное высказывание называется тождественно ложным, если оно принимает значение «ложь» при любых значениях входящих в него простых высказываний. Очевидно, что отрицание тождественно истинного высказывания будет тождественно ложным. То есть, если ½ = А, то — тождественно ложно.

Тождественно истинные формулы имеют большое значение в математической логике, поэтому их также называют законами логики. Существует бесконечно много тождественно истинных формул. Рассмотрим наиболее важные из них, наиболее часто использующиеся в математических доказательствах.

1. Закон силлогизма

Закон силлогизма можно «прочесть» так . Если из высказывания А следует В, а из высказывания В следует С, то можно заключить, что из А следует С. Этот закон позволяет при доказательствах некоторого утверждения пользоваться цепочками заключений.

«Если будет хорошая погода, мы пойдем на пляж. Если мы пойдем на пляж, то обязательно искупаемся.» Следовательно, согласно закону силлогизма можно сделать вывод: «Если будет хорошая погода, мы искупаемся».

2. Modus ponens ( лат .)

Если А – истинно и из А следует В, то В также будет истинно.

Этот закон очень часто применяется при математических доказательствах. Например, треугольники АВС и А1В1С1 равны. Если треугольники равны, то соответствующие их стороны равны друг другу. Значит, согласно modus ponens , стороны АВ и А1В1, ВС и В1С1, АС и А1С1 равны.

3. Закон контрапозиции

Следование из высказывания А высказывания В равносильно тому, что из не В следует не А.

Так, высказывание «Если погода будет хорошей, мы пойдем на пляж» равносильно (эквивалентно) высказыванию «Из того, что мы не ходили на пляж, следует, что погода была плохой». (Такое соответствие закону контрапозиции не совсем строгое, так как мы изменили времена глаголов во втором высказывании).

4. Закон исключения третьего

Для любого высказывания А или само высказывание А истинно, или истинно его отрицание (не А). В терминах самого высказывания этот закон можно сформулировать еще и таким образом: любое высказывание либо истинно, либо ложно.

5. Закон противоречия

Закон противоречия отражает следующее утверждение: « Для любого высказывания А неверно, что одновременно истинны и само высказывание А, и его отрицание (не А)».

Очевидно, что если , то высказывание, стоящее под общим отрицанием, будет всегда ложно . То есть, не могут быть одновременно истинны и высказывание А, и его отрицание (не А).

6. Закон двойного отрицания

Отрицание от отрицания любого высказывания эквивалентно (равносильно) самому высказыванию.

Здесь мы привели лишь некоторые, наиболее часто используемые законы логики. Доказать любой закон достаточно просто. Для этого необходимо построить таблицу истинности приведенного высказывания и убедиться, что при любых исходных данных оно истинно. Так, таблица истинности высказывания закон силлогизма будет такова:

Как доказывать, что данная формула является тавтологией. Два способа.

Пусть дана некоторая формула F логики высказываний и надо выяснить, является ли формула F тавтологией. Простой метод доказательства – использовать таблицу истинности. Хорошо, если эта таблица небольшая, но когда высказывательных переменных много, то такой подход трудоемок. В случае, когда F имеет вид F1⊃F2, желательно использовать метод доказательства от противного. Вы предполагаете, что формула F ложна и, делая отсюда выводы, приходите к противоречию или определяете значения переменных, при которых формула ложна. Для формул указанного вида ложность F1⊃F2 однозначно определяет: F1 – истинна, а F2 – ложна. Пример. Является ли формула ((PQ)& P) ⊃ (Q ⊃ ¬P) тавтологией? Решение. Предположим, что формула ((PQ) & P) ⊃ (Q ⊃ ¬P) ложна при некоторых значениях высказывательных переменных P и Q. Получили значения переменных (Q = И и P = И), при которых формула ((PQ)& P) ⊃ (Q ⊃ ¬P) = Л, следовательно, эта формула не является тавтологией.

    Равносильные формулы. Примеры равносильностей. Способы доказательств равносильностей.

    16.03.2016 1.58 Mб 43 otchet_po_GPO.docx

    16.03.2016 1.58 Mб 25 otchet_po_GPO.docx

    11.05.2015 1.46 Mб 138 Otchet_po_praktike_Pasha.docx

    18.09.2019 816.13 Кб 5 OTVET.doc

    11.05.2015 107.7 Кб 39 Otvety.docx

    11.05.2015 507.98 Кб 148 otvety2014_1.docx

    10.09.2019 175.62 Кб 5 otvety_izl_2011.doc

    10.09.2019 522.24 Кб 9 otvety_kovtun.doc

    11.05.2015 355.48 Кб 97 Otvety_k_kontrolnym_voprosam.docx

    04.08.2019 48.95 Кб 9 Otvety_minkov.docx

    10.05.2015 578.05 Кб 35 otvety_na_voprosy_dlya_ekzamena_GMF.doc

    Ограничение

    Для продолжения скачивания необходимо пройти капчу:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *