Проверьте любым способ является ли данные логические формулы тавтологией

Третий способ – сокращенный.

Практическое занятие № 4 «Логические рассуждения»

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

Для логического следования используется запись: ├─ . Рассуждение будем записывать в виде схемы рассуждения:

Три способа проверки правильности логического рассуждения:

I. Применить определение:

а) записать все посылки и заключения в виде формул логики высказываний;

б) составить конъюнкцию формализованных посылок ;

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

II. Использовать Признак логического следования:

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

III. Применить сокращенный способ проверки правильности логического рассуждения.

Рассуждение строится «методом от противного»:

Рассуждение является неправильным, если найдется набор значений переменных такой, что посылка ( ) =1, а заключение ( ) =0.

Сокращенный метод заключается в следующем.

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

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

Если в параллелограмме диагонали взаимно перпендикулярны (А), то параллелограмм – ромб (B). В данном параллелограмме диагонали не взаимно перпендикулярны (отрицание А), следовательно, он не является ромбом (отрицание B)».

Составим схему логического рассуждения:

Первый способ проверки – по определению.Составляем конъюнкцию формализованных посылок: .

Проверим по таблице истинности:

Так как на наборе (A=0, B=1) конъюнкция посылок истинна, а заключение ложно, то рассуждение не является логически правильным.

Второй способ, основанный на признаке логического следования.

Построим формулу и проверим, является ли она тавтологией.

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

Формула не является тавтологией, следовательно, данное логическое рассуждение не является логически правильным.

Третий способ – сокращенный.

Проверим сокращенным способом правильность логического рассуждения ├─ .

Пусть существует набор при котором посылки истинны, а заключение ложно. Оформим это предположение в виде таблицы

№	Истина	Ложь

Из строк 2,3 следует: , . Подставляем полученные значения в первую строку: . Таким образом, противоречий нет, следовательно, рассуждение ├─ не является логически правильным.

Если число представлено в виде несократимой дроби (A), то оно рациональное (B). Если число целое (C), то оно не является рациональным(отриц. В). Следовательно, если число целое(С), то оно не представлено в виде несократимой дроби(отриц. А)».

Решение: Составим схему логического рассуждения:

Первый способ проверки – по определению.Составляем конъюнкцию формализованных посылок: .

Проверим по таблице истинности:

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

Второй способ, основанный на признаке логического следования.

Построим формулу и проверим, является ли она тавтологией.

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

Формула является тавтологией, следовательно, данное логическое рассуждение является правильным.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также: Boku это способ оплаты

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

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

, .

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

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

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

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

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

, .

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

, , , .

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

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

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

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

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

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

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

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

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

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

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

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

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

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