Логические связки

Введение

Дискретная математика – это цикл математических наук, изучающих свойства конечных множеств.

В настоящее время эти науки бурно развиваются, что определяется тремя очень важными факторами:

1) развитием компьютерной техники и компьютерных наук, которые базируются, а по существу являются продолжением дискретной математики;

2) запросами различных прикладных наук – теории управления, экономики, оптимизации и многих, многих других;

3) логикой внутреннего развития этих наук: появлением новых разделов, глубоких интересных проблем, развитием мощных методов их решения.

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

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

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

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

Формулы

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

Р	Q	P Q	Ø Р	Ø p q
И	И	И	Л	И
Л	И	И	И	И
И	Л	Л	Л	Л
Л	Л	И	И	И

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

1.

2.

3.

4.

5.

6. Л= A, Л=Л;

7. И=И, И=A;

8.

9.

10. И, Л.

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

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

Дата добавления: 2014-12-27