Глава 01. Логические исчисления. Логические связки

Высказывания

Элементами логических рассуждений являются утверждения, которые либо ис­тинны, либо ложны, но не то и другое вместе. Такие утверждения называются (простыми) высказываниями. Простые высказывания обозначаются Пропозицио­нальными переменными, Принимающими Истинностные значения «И» (или 1) и Ложные значения «Л» (или 0). Из простых высказываний с помощью Логических связок Могут быть построены со­ставные высказывания. Обычно рассматривают следующие логические связки:

Название	Прочтение	Обозначение
Отрицание Конъюнкция Дизъюнкция Импликация Эквивалентность	Не И Или Если... то Равносильно	Ø, &, Ù , × Ú ®, Þ «, Û, ~, =, º

Формулы

Правильно построенные составные высказывания называются (Пропозициональ­ными) формулами. Формулы имеют следующий синтаксис:

(формула) :: = И | Л |

<пропозициональная переменная> |

(Ø <формула>) |

(<формула> & <формула>) |

(<формула> <формула>) |

(<формула> ® <формула>)|

(<формула> « <формула>)

Для упрощения записи вводится старшинство связок (Ø, &, , ®, «) и лишние скобки опускаются.

Истинностное значение формулы определяется через истинностные значения ее составляющих в соответствии со следующей таблицей:

A	B	Ø A	А&В	AB	AB	A «B
Л	Л	И	Л	Л	И	И
Л	И	И	Л	И	И	Л
И	Л	Л	Л	И	Л	Л
И	И	Л	И	И	И	И

Интерпретация

Пусть A(X1,..., Xn) — пропозициональная формула, где Х1,.… хN — входящие в нее пропозициональные переменные. Конкретный набор истинностных значе­ний, приписанных переменным X1,...,Xn, называется интерпретацией форму­лы А. Формула может быть истинной (иметь значение И) при одной интер­претации и ложной (иметь значение Л) при другой интерпретации. Значение формулы А в интерпретации I Будем обозначать I(А). Формула, истинная при некоторой интерпретации, называется выполнимой. Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией). Фор­мула, ложная при всех возможных интерпретациях, называется невыполнимой (или противоречием).

Пример

А Ø A — тавтология, А & ØА — противоречие, AØА - выполнимая формула, она истинна при I(А) = Л.

ТЕОРЕМА Пусть А — некоторая формула. Тогда:

1. если А — тавтология, то ØA — противоречие, и наоборот;

2. если А — противоречие, то А — тавтология, и наоборот;

3. если А — тавтология, то неверно, что А — противоречие, но не наоборот;

4. если А — противоречие, то неверно, что А — тавтология, но не наоборот.

Логическое следование и логическая эквивалентность

Говорят, что формула В логически следует из формулы А (обозначается АВ), если формула В имеет значение И при всех интерпретациях, при которых фор­мула А имеет значение И.

Говорят, что формулы A и В логически эквивалентны (обозначается А В или просто А = В), если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения при любой интерпретации.

ТЕОРЕМА (РQ) = (ØPQ).

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

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

Р	Q	PQ	ØР	ØPQ
И	И	И	Л	И
Л	И	И	И	И
И	Л	Л	Л	Л
Л	Л	И	И	И

ТЕОРЕМА Если А, В, С — любые формулы, то имеют место следующие логиче­ские эквивалентности:

1.

2.

3.

4.

5.

6. Л=A, Л=Л;

7. И=И, И=A;

8.

9.

10. И, Л.

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

Непосредственно проверяется построением таблиц истинности.

Следующая >