Докажите что составное высказывание является тавтологией

04. Тавтология и противоречие

Определение. Тавтологией Называется составное высказывание, истинное при Всех Наборах истинностных значений составляющих его простых высказываний.

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

Пример. Доказать, что высказывание является тавтологией, а высказывание – противоречием.

Решение. Для доказательства составим общую таблицу истинности для этих формул.

При всех истинностных значениях высказывания А высказывание принимает истинное значение, значит, является тавтологией. При всех истинностных значениях высказывания А высказывание принимает ложное значение, значит, является противоречием. □

Теорема 1.3. Отрицанием тавтологии является противоречие, отрицанием противоречия является тавтология.

Доказательство. 1) Рассмотрим формулу, являющуюся тавтологией. По определению, при всех наборах истинностных значений составляющих её простых высказываний она принимает значение «истина». Тогда, по определению, отрицание данной формулы при всех наборах истинностных значений составляющих её простых высказываний принимает значение «ложь». Значит, отрицание тавтологии является противоречием.

2) Рассмотрим формулу, являющуюся противоречием. По определению, при всех наборах истинностных значений составляющих её простых высказываний она принимает значение «ложь». Тогда, по определению, отрицание данной формулы при всех наборах истинностных значений составляющих её простых высказываний принимает значение «истина». Значит, отрицание противоречия является тавтологией. ■

Задачи и упражнения

1.14. Докажите, что следующие составные высказывания являются тавтологиями:

1) ;

2) ;

3) ;

4) ;

5) .

1.15. Докажите, что следующие составные высказывания являются противоречиями:

1) ; 2) ; 3) .

Источник

Логика высказываний: теория и применение. Примеры решений задач

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

Логика высказываний: определение и применение

Высказываниями принято считать такие предложения (написанные на «словесном» либо математическом языке), о которых можно сказать одно из двух: либо они являются истинными, либо ложными.

С математическими высказываний проще всего: они всегда имеют либо значение «истина», либо значение «ложь». Для высказываний, сделанных на «словесном» языке, понятия «истинности» и «ложности» несколько более расплывчаты. Однако, например, такие словесные формы, как «Иди домой» и «Идёт ли дождь?», не являются высказываниями. Поэтому понятно, что высказываниями являются такие словесные формы, в которых что-либо утверждается. Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования. Их невозможно оценить значениями «истина» и «ложь».

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

Логические операции над высказываниями

Итак, высказывания можно рассмотривать как величину, которая может принимать два значения: «истина» и «ложь».

Таблица истинности для конъюнкции:

Таблица истинности для дизъюнкции:

Таблица истинности для следования (импликации):

4. Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается

A (можно встретить также употребление не символа

, а символа ¬, а также верхнего надчёркивания над A).

A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности для отрицания:

Таблица истинности для эквивалентности:

В большинстве языков программирования есть специальные символы для обозначения логических значений высказываний, записываются они почти во всех языках как true (истина) и false (ложь).

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

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

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

Пример 1. Вычислите логические значения следующих высказываний:

3) («Сосна» = «Дуб») ИЛИ («Вишня» = «Клён») ;

6) («Глаза даны, чтобы видеть») И («Под третьим этажом находится второй этаж») ;

Пример 2. Запишите с помощью логических операций следующие сложные высказывания:

1) «Пользователь не зарегистрирован»;

2) «Сегодня воскресенье и некоторые сотрудники находятся на работе»;

3) «Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными».

Решить примеры на логику высказываний самостоятельно, а затем посмотреть решения

Пример 3. Вычислите логические значения следующих высказываний:

1) («В минуте 70 секунд») ИЛИ («Работающие часы показывают время») ;

2) (28 > 7) И (300/5 = 60) ;

4) Не((300 > 100) ИЛИ («Жажду можно утолить водой»)) ;

Пример 4. Запишите с помощью логических операций следующие сложные высказывания и вычислите их логические значения:

1) «Если часы неправильно показывают время, то можно невовремя прийти на занятия»;

Пример 5. Определите логическое значение выражения

Формулы логики высказываний

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

В примерах 1 и 2 мы учились записывать с помощью логических операций сложные высказывания. Вообще-то они называются формулами логики высказываний.

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

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

Для построения формул логики высказываний кроме указанных выше букв используются знаки логических операций

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

1) элементарные формулы (атомы) являются формулами логики высказываний;

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

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

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

1) «нет действительных чисел, которые являются рациональными»;

2) «если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными»;

5) «все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными»;

6) «не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными».

p	q	r					f
И	И	И	И	И	И	И	И
И	И	Л	И	И	И	Л	И
И	Л	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	Л	И	И
Л	И	И	Л	И	Л	И	И
Л	И	Л	Л	И	Л	И	Л
Л	Л	И	И	И	И	И	И
Л	Л	Л	И	И	И	Л	И

Заметим, что никакой атом не имеет вида

Число скобок в формулах логики высказываний можно уменьшить, если принять, что

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций «по старшинству»:

В этом списке знак ↔ имеет самую большую область действия, а знак

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

(при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.

Пример 8. Восстановите скобки в формуле логики высказываний B ↔

Решение. Скобки восстанавливаются пошагово следующим образом:

Не всякая формула логики высказываний может быть записана без скобок. Например, в формулах А → (B → C) и

(A → B) дальнейшее исключение скобок невозможно.

Тавтологии и противоречия

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

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

Противоположный смысл имеет логическое противоречие. Если все значения высказываний равны 0, то выражение есть логическое противоречие.

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

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

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

Решение. Составляем таблицу истинности:

И	И	И	И	И
И	Л	Л	Л	И
Л	И	Л	И	И
Л	Л	Л	Л	И

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

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

Решение. Составляем таблицу истинности:

И	И	И	И	И	И
И	И	Л	И	Л	Л
И	Л	И	Л	И	И
И	Л	Л	Л	Л	И
Л	И	И	Л	И	И
Л	И	Л	Л	Л	И
Л	Л	И	Л	И	И
Л	Л	Л	Л	Л	И

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

И	И	И
И	Л	Л
Л	И	И
Л	Л	И

Пример 11. Перепишите формулу логики высказываний без использования импликации и эквиваленции, пользуясь тождеством и законами де Моргана:

;

.

Заменяем импликацию между двумя парами скобок, отрицая самый левый знак отрицания:

.

Убираем эквиваленцию между p и q и между q и не r :

.

Используя закон де Моргана, немного упрощаем и окончательно получаем:

.

Посылки и выводы. Валидный и не валидный аргумент

Пример валидного аргумента:

То есть, из посылок логически следует вывод.

Пример не валидного аргумента:

То есть, из посылок логически не следует вывод.

Пример 12. Проверьте валидность аргумента, если

Решение. Составляем таблицу истинности:

И	И	Л	И	И	И
И	Л	Л	Л	Л	И
Л	И	И	И	И	Л
Л	Л	И	И	И	И

Применение логики высказываний в информатике и программировании

Так, может быть объявлена логическая переменная с именем «ПользовательЗарегистрирован» (или его англоязычный аналог), имеющая форму высказывания, которой может быть присвоено логическое значение «истина» при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения переменных могут меняться в зависимости от того, какое логическое значение («истина» или «ложь») имеет переменная «ПользовательЗарегистрирован». В других случах переменной, например, с именем «ДоДняХОсталосьБолееТрёхДней», может быть присвоено значение «Истина» до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на «ложь» и от значения этой переменной зависит ход дальнейшего исполнения программы.

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

Источник