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

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

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

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

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

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

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

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

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

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

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

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

1) ;

2) ;

3) ;

4) ;

5) .

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

1) ; 2) ; 3) .

Источник

Доказательство тавтологий

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

Пример: . Упорядочим переменные в набор: .

_______________________________________________________________________________

_________________________________________________________________________

___________________________________________________________________

___________________________________________________________________

_________________________________________________________________________

___________________________________________________________________

___________________________________________________________________

_______________________________________________________________________________

_________________________________________________________________________

___________________________________________________________________

___________________________________________________________________

_________________________________________________________________________

___________________________________________________________________

___________________________________________________________________

Метод обратных рассуждений

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

Пример: .

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

Пример: .

Доказательство тавтологий можно проводить с помощью правил вывода:

1. правило подстановки:_______________________________________________________________

2. правило заключения:_______________________________________________________________

Выводимая формула – __________________________________________________________

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

Предложено много различных систем аксиом логики высказываний. Рассмотрим одну из них:

А1. ╞

А2. ╞

А3. ╞

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

Рассмотрим еще одну систему аксиом:

А1. ╞

А2. ╞

А3. ╞

А4. ╞

А5. ╞

А6. ╞

А7. ╞

А8. ╞

А9. ╞

А10.╞

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

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

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

Правило сложного заключения.

Если формулы — тавтологии и — тавтология, то и формула — тавтология.

Если и – тавтологии, то формула – тавтология.

Если , то доказуема формула – тавтология.

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

Если и – тавтологии, то формула – тавтология.

Правило перестановки посылок.

Если , то формула – тавтология.

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

Теорема. Пусть Г: – некоторый набор формул. Тогда, если формула логически следует из набора Г, дополненного формулой А, то формула логически следует из набора Г.

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

Случай 1. _______________________________________________________________________

Случай 2. _______________________________________________________________________

Случай 3. _______________________________________________________________________

Случай 4. _______________________________________________________________________

Пример. Докажем, что в системе аксиом А1-А10.

Источник

Логические законы (тавтологии).

Минимальная дизъюнктивная нормальная форма. Если задача такова, что мы должны оперировать с полным набором двоичных переменных (или с фиксированным числом двоичных разрядов), то мы должны пользоваться СДНФ. Если же нам хочется использовать минимум двоичных переменных и основных операций (например, наиболее просто запрограммировать какое-то сложное логическое условие), лучше воспользоваться самым коротким представлением этой функции в дизъюнктивной или конъюнктивной нормальной форме. Такое представление называют, соответственно, минимальной дизъюнктивной нормальной формой (МДНФ)илиминимальной конъюнктивной нормальной формой (МКНФ).

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

1. Закон отрицания отрицания: .

2. Закон идемпотентности: .

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

4. Ассоциативность: .

5. Дистрибутивность: .

6. Закон нуля и единицы: .

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

8. Законы поглощения: .

9. Законы склеивания: .

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

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

Штрих Шеффера и стрелка Пирса представляются через МДНФ согласно принципу двойственности (закон де Моргана): = , = .

Импликация принимает значение 0 только на наборе (1,0). СДНФ для нее тогда будет такая: . Попробуем получить более короткое представление. Самый короткий способ – воспользоваться СДНФ для ее антиоперации – разности. Она имеет очень простой вид: Значит, импликацию можно записать так: . Воспользовавшись законом де Моргана, получаем: .

Пример. Докажем следующую тавтологию:

В соответствии с порядком выполнения логических операций последней будет выполняться импликация между скобками. Обозначим левую часть импликации буквой A, правую – буквой B и перейдем к ее дизъюнктивной нормальной форме: Такой прием позволит нам избавиться от антидизъюнкции:

Подставив ДНФ для операции эквивалентности в этом выражении, перейдем к следующему:

Используем для преобразования конъюнкции двух отрицаний закон де Моргана и далее применим дистрибутивный закон и закон нуля и единицы:

Теперь займемся преобразованием правой части исходной импликации:

В соответствии с законом поглощения (bÚc)×b=b; отсюда получаем:

Подставим результаты преобразований A и B в исходное выражение и продолжим преобразования, выполняя перегруппировку и используя закон нуля и единицы:

4.Множества и подмножества.Универсально множество.Основные определения и свойства.Мощность множества,степень множества.

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

Предикатный способ: A=<a|P(a)>, где P(a) – условие (предикат), которому удовлетворяет а. Пример: множество положительных действительных чисел – A=0>.

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

Количество элементов, из которых состоит множество A, называется мощностью множества и обозначается M(A)=|A|.

Объект a является элементом множества A, обозначают так: aÎA. Если объект не является элементом A, пишут aÏA. aÎA – это элементарное высказывание, которое может быть либо истинным, либо ложным, но не то и другое вместе. Это высказывание часто называют предикатом принадлежности.

В теории множеств совокупность объектов, из которой формируются множества конкретной модели, называют универсальным множествомилиуниверсумом. Универсум принято обозначать буквой U. Множество состоит из отдельных элементов, значит, оно делимо и можно ввести еще одно понятие – подмножество множества А. Будем обозначать его Q(A) и писать, что Q(A)ÌA. Если Q(A) может совпадать с A, пишут Q(A)ÍA. Множество множеств иногда называют классом или семейством.

Сколько же подмножеств мы можем сформировать из нашего конкретного множества А? Давайте заведем коробку, куда будем складывать элементы a_i, назовем ее Q(A) и займемся комбинаторикой.

Любому подмножеству конечного множества мощности n можно сопоставить элементарную конъюнкцию из n переменных, где каждой переменной x_i соответствует высказывание «a_iÎA».

Сколько существует подмножеств заданной мощности N n =A´…´A – всего n раз

Источник