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

Для начала определим основные термины математической логики, которые необходимы для работы над данной темой.

Алгебра высказываний

Высказыванием будем называть предложение, представляющее собой утверждение, о котором можно сказать истинно оно или ложно. Высказывания обозначаются заглавными латинскими буквами: A, B, C .

Примеры:

1. Высказывание = «г. Москва – столица России».

2. Высказывание = «У кошки 4 ноги».

3. Высказывание = «7<6».

4. Высказывание = «12 делится на 7».

На совокупности всех высказываний определим функцию .

Функция λ называется функцией истинности, а значение λ(P) называется логическим значением или значением истинности высказываний P.

1. λ ( )=1

2. λ ( )=1

3. λ ( )=0

4. λ ( )=0

Основные операции над высказываниями:

1. Отрицание. Отрицанием высказывания P называется высказывание « не P», которое истинно, если высказывание P ложно, и ложно, если высказывание P истинно.

Таблица истинности

0	1
1	0

2.Конъюнкция. Конъюнкцией 2-х высказываний P и Q, которое истинно лишь в том случае, когда истинны оба высказывания P и Q, и ложны во всех остальных случаях.

Обозначаем: P۸Q.

Таблица истинности

0	0	0
0	1	0
1	0	0
1	1	1

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

Обозначаем: P۷Q

Таблица истинности

0	0	0
0	1	1
1	0	1
1	1	1

4.Импликация. Импликацией двух высказываний P и Q называется «Если P, то Q», из P следует Q, P достаточно для Q необходимо для P, которое ложно в единственном случае, когда высказывание P истинно, а высказывание Q ложно.

Обозначаем:

Таблица истинности

0	0	1
0	1	1
1	0	0
1	1	1

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

Обозначаем:

Таблица истинности

0	0	1
0	1	0
1	0	0
1	1	1