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

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. Доказать, что формула является тавтологией.

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

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

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

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

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

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

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

Источник

Операции над высказываниями и предикатами. Таблицы истинности

п.1. Отрицание

Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».

п.2. Конъюнкция

Обозначение конъюнкции A ∧ B, читается «А и В». Таблица истинности:

С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.

п.3. Дизъюнкция

Обозначение дизъюнкции A ∨ B, читается «А или В». Таблица истинности:

С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).

п.4. Импликация

Обозначение импликации A → B, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:

п.5. Эквиваленция

Обозначение эквиваленции A ↔ B, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:

п.6. Законы де Моргана

Докажем эквивалентность с помощью таблиц истинности:

Мы видим, что итоговые столбцы слева и справа полностью совпадают.
Значит, высказывания эквивалентны.

Докажем эквивалентность с помощью таблиц истинности:

Высказывания слева и справа эквивалентны.

Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A

B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».

п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности

Например:
Докажем следующее свойство:

Источник

Тавтология. доказательство при помощи таблицы истинности.

Понятие множества. Диаграммы Эйлера-Венна. Дополнение.

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

Диаграммы Эйлера-Венна используются для наглядного представления соотношения между несколькими подмножествами какого-либо универсума. (См. в тетради).

Высказывание. Элементарное высказывание. Основные операции (отрицание, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация, эквиваленция).

Высказывание – некоторое утверждение относительно, которого можно сказать истинно оно или нет.

Элементарное высказывание – одно утверждение.

p>+ смотри в тетради.

Правильные рассуждения. Тавтология. Выполнимая формула. Тождественно ложная формула. Опровержимая формула.

Рассуждения являются правильными, если из конъюнкции начальных следует заключение, т.е посылка истинны заключаются истинно(р1, р2)-посылки. Д-заключение.

Совершенная дизъюнктивная нормальная форма.

В наборе элементов, где Булевы функции = истина. Если значение переменной = ложь, то эта переменная берётся с отрицанием. Если значение переменной = истина, то эта переменная берётся без отрицания. Соединив все переменные, соответствующие этому набору через знак конъюнкции, мы получим элементарную конъюнкцию. Тогда дизъюнкция всех элементарных конъюнкций, соответствующих набору значений переменных, где функция принимает значение истина и восстанавливает исходную функцию – это СДНФ нашей функции.

Совершенная конъюнктивная нормальная форма.

Обращаем внимание на набор переменных, при которых функция принимает значение ложь. Если в этот набор переменных входит с истистинностным значением ложь, то её берём без знака (чёрточка над буквой). Если она входит в истину, то её берём с этим знаком. Переменные внутри одного набора (+) и получают элементарную дизъюнкцию. Конъюнкция элементарных дизъюнкций и образует СКНФ.

Тавтология. Доказательство при помощи таблицы истинности.

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

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

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

С увеличением числа переменных табличный метод – неудобный, потому что число строк в таблице истинности резко увеличивается.

Статьи к прочтению:

Братство Языка — Тавтология

Похожие статьи:

Таблицы сложения и умножения в восьмеричной системе 4 страница

6. Информатика. Базовый курс. / Под ред.Симоновича. – СПб., 2001. 7. Косарев В.П., Еремин Л.В. Компьютерные системы и сети. – М., 1999. 8. Дорот В.,…

Введение В предыдущей части статьи об управлении планировщиком заданий средствами командной строки вы узнали о фундаментальных отличиях планировщика…

Источник

Составив соответствующие таблицы истинности, докажи¬те, что все следующие формулы являются тавтологиями :

Как составить истинные высказывания?

Как составить истинные высказывания.

Срочно?

Какие из следующей таблицы перечислены (х, у) пары являются решениями уравнения?

Дана таблица истиности функции F?

Дана таблица истиности функции F.

ABF 000 010 101 110 Какое выражение соответствует F?

Помогите кто чем может?

Помогите кто чем может.

Докажите, что следующее высказывание истинно при любых предположениях об истинности А, В.

Составьте таблицу истинности (А или В)илиВ?

Составьте таблицу истинности (А или В)илиВ.

Состав те таблицу истинности (АvB)B?

Состав те таблицу истинности (АvB)B.

Не пользуясь таблицей простых чисел, докажите, что число : а) 29 ; б) 41 ; в) 53 ; г) 59 является простым?

Не пользуясь таблицей простых чисел, докажите, что число : а) 29 ; б) 41 ; в) 53 ; г) 59 является простым.

Таблица истинности (A ^ B)vA?

Таблица истинности (A ^ B)vA.

Источник

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

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

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

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

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

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

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

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

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

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

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

1) ;

2) ;

3) ;

4) ;

5) .

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

1) ; 2) ; 3) .

Источник