Основные логические операции.

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

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

Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”.

Введем множество

Над высказываниями можно выполнять следующие операции:

1. ^┐ (не) – одноместная операция отрицания;

2. (или) – двуместная операция дизъюнкция;

3. (и) – двуместная операция конъюнкция;

4. (если, то) – двуместная операция импликация;

Каждая операция характеризуется своей таблицей истинности:

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

1) Отрицание. Отрицанием (логическим “ не ”) высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.

Обозначается Р или .

Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид:

 

P	Р
И	Л
Л	И

 

2) Конъюнкция. Конъюнкцией (логическим “ и ”) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.

Обозначается P&Q или Р Q.

P	Q	P Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

 

3) Дизъюнкция. Дизъюнкцией (логическим “ или ”) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.

Обозначается P Q.

Р	Q	P Q
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

 

4) Импликация. Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно.

Обозначается PÉQ (или Р Q). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.

P	Q	P Q
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

 

5) Эквиваленция. Эквиваленцией (логической равносильностью) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.

Обозначается Р~Q или РÛQ.

 

P	Q	P~Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

 

С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.

Построим истинностную таблицу сложного высказывания:

S=(A→B)∧( ^┐C)∨(A↔C)

Очевидно, истинностная таблица будет содержать 2³ = 8 строк.

Скобки применяются, если нарушаются естественный порядок операций: отрицание, конъюнкция, дизъюнкция, импликация, двойная импликация. Скобки (А→В) указывают на то, что сначала нужно выполнить

импликацию, затем найти (А→В)∧С. Скобки в выражении (A↔C) можно опустить. Заключительной операцией в построении истинностной таблицы для S будет дизъюнкция двух высказываний: (А→В)∧С и (A↔C).

Таблица

А	В	С	А→В	(А→В)∧С	┐С	A↔C	C (A↔C)

Итак, формула S задает высказывание, которое истинно на следующих наборах значений элементарных высказываний:

А=1 В=1 С=1 (все три элементарных высказывания истинны)

А=1 В=0 С=1 (А, С - истинны, В - ложно)

А=0 В=1 С=1 (А - ложно, В и С - истинны)

А=0 В=1 С=0 (В - истинно, А и С - ложны)

А=0 В=0 С=1 (С - истинно, А и В - ложно)

А=0 В=0 С=0 (все три высказывания ложны).

Высказывательной формой называется: 1) любая переменная (она в свою очередь называется элементарной (атомарной) высказывательной формой); 2) если и высказывательные формы, то и их отрицания, , , , , также являются высказывательными формами.

Формулы логики

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

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

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

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

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

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

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

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

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

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

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

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

· Отрицание

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

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

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

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

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

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

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

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

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

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