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

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

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

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

· Множество элементов основного множества Е, не принадлежащих множеству А, называется дополнением множества А до множества Е или просто дополнением.

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

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

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

· Отрицанием высказывания Р называется высказывание, истинное тогда и только тогда, когда высказывание Р ложно.

· Конъюнкцией двух высказывания П и К называется высказывание, истинное тогда и только тогда, когда истины оба высказывания.

· Дизъюнкцией двух высказываний П и К называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.

· Строгая дизъюнкция – высказывание П и К – «либо-либо», которое истинно тогда и только тогда, когда лишь одно из выражений истинно.

· Импликацией двух высказываний П и К является высказывание, ложное тогда и только тогда, когда П истинно, а К ложно.

· Эквиваленцией двух высказываний П и К называется высказывание, истинное тогда и только тогда, когда истистинностные значения П и К совпадают.

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

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

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

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

· Выполнимая формула это функция, которая на некоторых оценках списка переменных она принимает значение истины.

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

· Опровержимая формула – это функция, которая на некоторой оценке списка переменных принимает значение ложь.

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

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

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

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

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

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

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

· Логический закон: Закон тождества в правильном рассуждении = каждое высказывание тождественно самому себе.

· Противоречие: 2 высказывания, которые отрицают, друг друга не могут быть вместе истинными.

· Исключение третьего: 2 высказывания, которые отрицают, друг друга не могут быть вместе ложными, одно из них обязательно истинно, третье же исключено.

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

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

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