Тема 2.2 Формулы логики.

Алфавитом называется любой непустой набор символов. Элементы этого набора называются символами алфавита.

Словом в алфавите называется произвольная конечная (возможно пустая) последовательность символов из . Фиксируем некоторый конечный или счетный алфавит переменных

Формула алгебры логики определяется следующим образом (индуктивное определение):

• Любая логическая переменная есть формула.

• Если - формула, то - формула (допустимы технические символы)

• Если и – формулы, то – тоже формулы (допустимы все логические связки).

• Других формул нет.

Подформулой формулы называется любое подслово слова , которое само является формулой.

Для сокращения записи формул обычно принимаются следующие соглашения:

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

• если над частью формулы стоит знак отрицания, то он заменяет собой скобки, в которые заключена эта часть формулы.

Принят следующий порядок выполнения операций:

• Отрицание

• конъюнкция,

• дизъюнкция,

• импликация и эквивалентность в порядке их записи,

Формула называется тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0.

Являются ли формулы тождественно истинными:

Формулы логики, принимающие всегда ложное значение, называются тождественно ложными (или противоречиями).

Например, формула - противоречие.

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

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

Формулы Р и Q называются равносильными, если их истинностные значения совпадают при любом выборе истинностных значений атомов, входящих в эти формулы.

Запись Р Q означает, что формулы Р и Q равносильны

Самостоятельная работа №2.

Тема 2.3 Дизъюнктивная нормальная форма.

Отрицание относящиеся к переменной называется тесным (простым). Отрицание, не являющееся тесным, называется сложным.

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

Теорема: Для любой высказывательной формы существуют равносильные приведенные формы.

Доказательство:

1. Пусть высказывательная форма Ы – есть переменная (тривиально);

2. Пусть Ы - = ^┐L и для L теорема 1 выполняется, т.е. существует L*, которое является приведенной формой: L* L, тогда рассмотрим ^┐ L* применяя нужное число раз законы Моргана, получим, что внешнее отрицание перенесется внутрь либо на отрицание переменной, либо на отрицание отрицания переменной, таким образом ^┐L – является приведенной высказывательной формой.

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

4. Пусть , аналогично п.3

5. Пусть , для теорема 1 выполняется, применяем закон импликации:

Символическая степень высказывания – это , причем может быть истиной, либо ложной, причем:

Свойства символической степени высказывания:

1. 

2. 

Высказывательная форма, состоящая из переменных или отрицания переменных применением только одной операции дизъюнкции, называется элементарной дизъюнкцией.

Высказывательная форма, состоящая из элементарных конъюнкций, применением только одной операции дизъюнкции называется дизъюнктивной нормальной формой (ДНФ).

Совершенной дизъюнктивной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: