1. Докажите, что формула является тавтологией (тождественно истинной). Математическая логика.

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

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

Пусть дана формула логики высказываний, например содержащая переменные $A, B, C$. Формула называется тавтологией, если для всех возможных наборов значений этих переменных она равна $1$, то есть истинна.

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

1. Доказательство с помощью таблицы истинности

Нужно выписать все возможные значения переменных и вычислить значение всей формулы.

Например, докажем, что формула

является тавтологией.

Составим таблицу истинности:

В последнем столбце везде стоит $1$. Значит, формула $A \vee \neg A$ истинна при любом значении $A$. Следовательно, она является тавтологией.

Рассмотрим более сложный пример:

Это закон контрапозиции. Проверим его таблицей истинности.

Импликация $A \to B$ ложна только тогда, когда $A = 1$, а $B = 0$. Во всех остальных случаях она истинна.

Последний столбец содержит только единицы. Значит,

является тавтологией.

2. Доказательство с помощью равносильных преобразований

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

Например, докажем, что формула

является тавтологией.

Используем равносильность импликации:

Тогда:

А формула

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

является тавтологией.

Ещё пример:

Преобразуем импликацию:

По закону де Моргана:

Тогда:

Перегруппируем:

Так как

получаем:

Значит,

тождественно истинна, то есть является тавтологией.

Итак, чтобы доказать, что формула является тавтологией, нужно показать, что при любых значениях переменных она принимает значение $1$. Это можно сделать либо таблицей истинности, либо равносильными преобразованиями, приводя формулу к константе $1$.